一種改進的時不變LDPC卷積碼構造方法*

穆麗偉，劉星成

(1. 華南師范大學物理與電信工程學院∥廣東省量子調控工程與材料重點實驗室，廣東 廣州510006;2. 中山大學信息科學與技術學院，廣東 廣州510006)

一種改進的時不變LDPC卷積碼構造方法*

穆麗偉1，劉星成2

(1. 華南師范大學物理與電信工程學院∥廣東省量子調控工程與材料重點實驗室，廣東 廣州510006;2. 中山大學信息科學與技術學院，廣東 廣州510006)

提出一種新的時不變LDPC卷積碼構造算法。對Tanner等的構造方案進行改進，產生了給定碼率下的LDPC卷積碼多項式矩陣；根據卷積碼特性，對該多項式矩陣進行修正，獲得具有最大給定編碼記憶和快速編碼特性的改進的時不變LDPC卷積碼。該算法具有的快速編碼特性可以降低硬件實現時的編碼復雜度。該算法獲得的在給定碼率下具有最大給定編碼記憶的特性可提高譯碼性能。對碼的特性參數和仿真結果的分析表明，文中構造的時不變LDPC卷積碼是優異的。

低密度奇偶校驗(LDPC)卷積碼；時不變；給定碼率；給定編碼記憶；快速編碼

隨著Shannon[1]開創性論文的發表以及Hamming[2]碼和Golay[3]碼的出現，致力于低復雜度、低延遲以及接近容量的編碼理論研究開始蓬勃發展起來。過去20年，主要集中在以圖論為基礎的編碼理論研究上，尤其是turbo碼和低密度奇偶校驗(LDPC，Low-Density Parity-Check)分組碼。用具有低運算復雜度的置信傳播算法進行譯碼，LDPC分組碼展現了優異的譯碼性能。然而，用LDPC分組碼進行編碼，需要把數據流分成幀進行傳遞，不適于某些應用[4]。

與分組碼不同，卷積碼適于基于數據流傳輸的通信系統。自1999年LDPC卷積碼的構造譯碼算法提出以來[5]，具有隨機和結構化特性的LDPC卷積碼的構造方法已經成為很多學者關注的研究方向。常利用LDPC分組碼獲得LDPC卷積碼,對LDPC分組碼進行拆分重組可獲得隨機化特性的時變LDPC卷積碼[6-9]。根據環同構，可直接用準循環(QC，Quasi-Cyclic) LDPC分組碼獲得具有結構化特性的時不變LDPC卷積碼[10-13]。Tanner等[13]提出了經典的構造時不變LDPC卷積碼的算法。他們首先給出一種QC-LDPC碼構造算法，然后根據環同構關系，獲得了LDPC卷積碼的多項式奇偶校驗矩陣。與QC-LDPC分組碼類似，時不變LDPC卷積碼具有占用存儲空間小、易于實現的特性。但是Tanner等[13]的構造算法還存在如下不足之處：① LDPC卷積碼的編碼碼率只能根據給定構造參數獲得，不能預先給定；② 最大編碼記憶只有在獲得生成矩陣后才可獲知；③ 不具有LDPC卷積碼本身固有的優勢：快速編碼特性[1]。

根據以上分析，本文首先介紹了Tanner等[13]提出的時不變LDPC卷積碼構造算法，由該算法的具體構造參數進一步指出其不足之處。然后對該算法進行改進，構造了在給定碼率和給定最大編碼記憶下，具有快速編碼特性的結構化LDPC卷積碼的多項式形式奇偶校驗矩陣。最后，對所構造的碼給出仿真結果并進行性能分析。

1 時不變LDPC卷積碼的構造算法

介紹Tanner等[13]提出的LDPC卷積碼構造算法，分析其不足之處。

先介紹其構造算法。首先，根據給定的構造參數：非負整數m以及兩個參數a、b， 由乘階O(a)=K，O(b)=J，獲得(J,K)多項式矩陣

(1)

其中，J×K矩陣P的第(s,t)個元素Ps,t=atbs(0≤s≤J-1,0≤t≤K-1)。

其次獲得矩陣P對應的QC-LDPC分組碼矩陣

(2)

其中，Ix是一個行循環左移x位的m×m單位陣。

最后，根據環同構，獲得LDPC卷積碼多項式矩陣

(3)

其中，D是延時算子，D的冪x即單位陣循環左移的位數x，該LDPC卷積碼的碼率是(1-J/K)。H(D)稱為LDPC卷積碼的多項式奇偶校驗矩陣[13]。

由構造過程可知，該算法的不足之處在于：① 給定構造參數m和a、b后，才可獲知LDPC卷積碼的碼率(1-J/K)；② 構造前，編碼記憶不詳(只有得到H(D)對應的生成矩陣G(D)后，才可獲悉最大編碼記憶[13])；③ 該算法要用高斯消去法從H(D)獲得生成矩陣G(D)后，才可對輸入信息進行編碼獲得LDPC卷積碼[13]，因此并不具有卷積碼特有優勢之一：快速編碼特性，即不具有由H(D)直接進行編碼的特性。

2 時不變LDPC卷積碼構造算法的改進

本部分對前述算法進行改進，構造在給定碼率和給定最大編碼記憶下具有快速編碼特性的LDPC卷積碼。

首先，獲得在給定最大編碼記憶和給定碼率下的矩陣H(D)。給定最大編碼記憶m，可獲得參數(J,K)及碼率R=(1-J/K)，其中， (J,K)是φ(m)的因子[13]；

根據文獻[13]，兩個待求的非零整數a、b滿足乘階O(a)=K,O(b)=J，且

(4)

(5)

對碼長為K的LDPC卷積碼直接進行編碼獲得J個校驗位。其它(K-J)位是輸入的信息位，可直接輸出[1]。這種可由H(D)直接編碼的特殊矩陣形式，稱為快速編碼特性，是LDPC卷積碼的特有優勢，可減小編碼復雜度。

本文直接把矩陣H(D)最后J列對角線上元素置換為D0，即可獲得具有快速編碼特性的矩陣結構。根據在相同譯碼算法下，卷積碼譯碼性能與記憶長度成正比這一特性，直接把H(D)前J列對角線上元素置換為Dm，即可獲得每個時刻上的最大編碼記憶ms=m，本文里m為給定參數。至此，本文構造了在給定碼率(1-J/K)以及給定最大編碼記憶m下，具有快速編碼特性的LDPC卷積碼多項式矩陣，其結構如下

(6)

由(6)式可推知，僅具有快速編碼特性的矩陣可表示為

(7)

本文用(m，J，K)表示一個碼率為(1-J/K)的LDPC卷積碼，其中m為最大編碼記憶，J為多項式矩陣HFm(D)的行數，K為列數。本文所有的仿真都是在加性白色高斯噪聲(AWGN)信道下，在接收端使用BP(Belief Propagation,置信傳播)譯碼算法，迭代次數為50的編譯環境下獲得的性能結果。圖1給出了(31，3，5)LDPC卷積碼在奇偶校驗矩陣H(D)、HF(D)以及HFm(D)下的仿真結果。本文中所有圖的縱坐標用BER(biterrorrate，誤比特率)表示。橫坐標用Eb/N0表示，其中Eb是傳輸每比特(bit)信息所消耗的平均能量，N0/2是AWGN信道上的平均功率譜密度。仿真結果表明，在BER為4×10-7左右，由HFm(D)所獲得的LDPC卷積碼比由H(D)所獲得的碼要好1.8dB左右，比HF(D)所獲得的碼要好1dB左右。其中最主要的原因是經變換后，LDPC卷積碼的多項式矩陣結構發生了變化，尤其是環和記憶長度。表1給出了相同構造參數的LDPC卷積碼在不同多項式矩陣下的環和記憶長度。表1的特性參數表明，圖1中所有 (31,3,5)LDPC卷積碼具有相同的girth(最小環長)，但由HFm(D)所獲得的碼具有最大編碼記憶m=31。圖2(a)表明，與(122,3,5)LDPC卷積碼相比， (26,3,4)LDPC卷積碼具有更大的性能增益。表1顯示，所有(26,3,4)LDPC卷積碼中，由HFm(D)所獲得的碼具有最大的girth(girth=10)和最大的編碼記憶(m=26)。所有(122,3,5)LDPC卷積碼的girth相同，但由HFm(D)所獲得的碼具有最大的編碼記憶(m=26)。圖2(b)表明，在低信噪比區，推薦的(211,3,5)碼具有更好的性能，而在高信噪比區，推薦的碼與原碼性能幾乎相同，由表1可看出，所有(211,3,5)LDPC卷積碼中，盡管由HFm(D)所獲得的碼其記憶長度比原碼大，但girth卻比原碼小。由此可看出，具有相同構造參數的所有LDPC卷積碼，在girth(memory)相同的情況下，memory(girth)越大，LDPC卷積碼的性能越好；但girth(memory)較小，memory(girth)較大時，在高信噪比區，LDPC卷積碼具有相似的性能。經過對大量仿真結果的分析，本文所構造的LDPC卷積碼的性能比原碼更好或幾乎相同，而本文提出的碼具有快速編碼特性，可大大減小編碼復雜度。所以本文構造的碼具有優異的特性。

圖1 (31，3，5)LDPC卷積碼在不同校驗矩陣下的仿真結果Fig.1 Simulation results of (31,3,5) LDPC convolutional codes associated with different check matrices

圖2 不同構造參數下LDPC卷積碼的BER性能Fig.2 The BER performance of LDPC convolutional codes under different construction parameters

表1LDPC卷積碼在不同校驗矩陣下的特性

Table1ThecharacteristicsofLDPCconvolutionalcodeswithdifferentcheckmatrices

LDPC卷積碼H(D)girth/girth數memoryHF(D)girth/girth數memoryHFm(D)girth/girth數memory(26，3，4)8/94258/132510/1226(31，3，5)8/190288/85258/4931(122，3，5)10/26811910/6711910/138122(151，3，5)10/741188/11188/71151(211，3，5)12/88020110/9620110/49211

3 仿真結果

本部分構造本文提出的 (151,3,5)LDPC卷積碼并對其進行仿真，仿真結果見圖3。由圖3可知，在BER為4×10-6左右，具有矩陣HFm(D)的(151,3,5)LDPC卷積碼比文 [6] 中所構造的(209,3,5)FE-I型(見文[6]Fig.1的FE-ICC曲線)LDPC卷積碼好0.1dB左右，比Tanner等[13]所構造的 (187,3,5)(見文[12]Fig. 12的R=2/5convcode,ms=187曲線)的LDPC卷積碼好0.2dB左右，與文獻[14]中的(204,3,5)碼(見文[14]Fig.9的m=204,ms=204曲線)性能幾乎相同(圖3中所有用于比較的碼性能均復制于對應的文獻中)。該仿真結果表明，與其他構造算法相比，在相同碼率R下，要獲得同樣的BER，該改進構造算法需要更小的記憶。值得注意的是該改進的構造還具有快速編碼特性，可減小編碼復雜度。

圖3 幾種LDPC卷積碼的仿真結果Fig.3 Several simulation results of LDPC convolutional codes

4 結 語

本文提出了一種新的LDPC卷積碼的構造算法。新的算法首先獲得在給定碼率下的結構化LDPC卷積碼。然后根據快速編碼特性可以簡化編碼復雜度；在同樣的譯碼算法下，記憶越大性能越好這兩個卷積碼特有的屬性，本文進一步構造了具有快速編碼特性和最大給定編碼記憶的LDPC卷積碼多項式矩陣。對碼進行的特性分析和給出的仿真結果表明，該算法是優異的。

[1]SHANNONCE.Amathematicaltheoryofcommunication[J].BellSystemTechnicalJournal, 1948, 27: 379-423, 623-656.

[2]HAMMINGRW.Errordetectinganderrorcorrectingcodes[J].BellSystemTechnicalJournal, 1950, 26(2): 147-160.

[3]GOLAYMJE.Notesondigitalcoding[J].ProceedingsofIRE, 1949, 37: 657.

[4]COSTELLODJJr,PUSANEAE,BATESS,etal.AcomparisonbetweenLDPCblockandconvolutionalcodes[C]∥ProceedingsofInformationTheoryandApplicationsWorkshop,SanDiego,CA,USA, 2006.

[5]JIMENEZFA,ZIGANGIROVKS.Time-varyingperiodicconvolutionalcodeswithlow-densityparity-checkmatrix[J].IEEETransactionsonInformationTheory, 1999, 45(6): 2181-2191.

[6]BOCHAROVAIE,KUDRYASHOVBD,JOHANNESSONR.SearchingforbinaryandnonbinaryblockandconvolutionalLDPCcodes[J].IEEETransactionsonInformationTheory, 2015,1-1:99.

[7]MULW,LIUXC,LIANGCL.ImprovedconstructionofLDPCconvolutionalcodeswithsemi-randomparity-checkmatrices[J].ScienceChinaInformationScience, 2014, 57(2): 022304:1-022304:10.

[8]GROSJEANL,RASMUSSENLK,THOBABENR,etal.SystematicLDPCconvolutionalcodes:asymptoticandfinite-lengthanytimeproperties[J].IEEETransactionsonCommunications, 2014, 62(12): 4165-4183.

[9]ZHOUHua,GOERTZN.RecoverabilityofvariablenodesinperiodicallypuncturedLDPCconvolutionalcode[J].IEEECommunicationsLetters, 2015, 19(4): 521-524.

[10]KUDEKARS,RICHARDSONT,URBANKERL.Spatiallycoupledensemblesuniversallyachievecapacityunderbeliefpropagation[J].IEEETransactionsonInformationTheory, 2013, 59(12): 7761-7813.

[11]MULW,LIUXC,LIANGCL.ConstructionofLDPCconvolutionalcodesoverfinitefields[J].IEEECommunicationsLetters, 2013, 16(6): 897-900.

[12]BALDIM,CANCELLIERIG,CHIARALUCEF.Arrayconvolutionallowdensityparity-checkcodes[J].IEEECommunicationsLetters, 2014, 18(2): 336-339.

[13]TANNERRM,SRIDHARAD,SRIDHARANA,etal.LDPCblockandconvolutionalcodesbasedoncirculantmatrices[J].IEEETransactionsonInformationTheory, 2004,IT-50(12): 2966-2984.

[14]ZHOUH,GOERTZN.Girthanalysisofpolynomial-basedtime-invariantLDPCconvolutionalcodes[C]∥InternationalConferenceonSystems,SignalsandImageProcessing,Vienna,Austria, 2012: 104-108.

Construction of time-invariant LDPC convolutional codes with modified method

MULiwei1,LIUXingcheng2

(1. Guangdong Provincial Key Laboratory of Quantum Engineering and Quantum Materials∥ School of Physics and Telecommunication Engineering, South China Normal University, Guangzhou 510006, China；2. Department of Electronic and Communications Engineering, Sun Yat-sen University,Guangzhou 510006, China)

A novel approach of constructing time-invariant LDPC convolutional codes is proposed. The matrix of an LDPC (Low-Density Parity-Check) convolutional code with a given rate is generated according to the original matrix generated by Tanner etc. Then, the matrix with maximum given encoding memory and fast encoding property is obtained by modifying the above-mentioned matrix. The fast encoding property of the proposed matrix can reduce the encoding complexity. And the maximum given encoding memory of the proposed LDPC convolutional code can improve the decoding performance. The characteristic parameters and simulation results show that the proposed LDPC convolutional codes are excellent .

LDPC convolutional codes; time-invariant; given rate; given memory; fast encoding

10.13471/j.cnki.acta.snus.2016.01.011

2015-03-28

國家自然科學基金資助項目(61401164，61173018)；廣東省自然科學基金資助項目(2014A030310308)

穆麗偉(1980年生)，女；研究方向：信道編碼與無線通信；E-mail:liweimuscnu@163.com

TN

A

0529-6579(2016)01-0063-05