一種改進(jìn)的時(shí)不變LDPC卷積碼構(gòu)造方法*

穆麗偉，劉星成

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

一種改進(jìn)的時(shí)不變LDPC卷積碼構(gòu)造方法*

穆麗偉1，劉星成2

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

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

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

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

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

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

1 時(shí)不變LDPC卷積碼的構(gòu)造算法

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

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

(1)

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

其次獲得矩陣P對(duì)應(yīng)的QC-LDPC分組碼矩陣

(2)

其中，Ix是一個(gè)行循環(huán)左移x位的m×m單位陣。

最后，根據(jù)環(huán)同構(gòu)，獲得LDPC卷積碼多項(xiàng)式矩陣

(3)

其中，D是延時(shí)算子，D的冪x即單位陣循環(huán)左移的位數(shù)x，該LDPC卷積碼的碼率是(1-J/K)。H(D)稱為L(zhǎng)DPC卷積碼的多項(xiàng)式奇偶校驗(yàn)矩陣[13]。

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

2 時(shí)不變LDPC卷積碼構(gòu)造算法的改進(jìn)

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

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

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

(4)

(5)

對(duì)碼長(zhǎng)為K的LDPC卷積碼直接進(jìn)行編碼獲得J個(gè)校驗(yàn)位。其它(K-J)位是輸入的信息位，可直接輸出[1]。這種可由H(D)直接編碼的特殊矩陣形式，稱為快速編碼特性，是LDPC卷積碼的特有優(yōu)勢(shì)，可減小編碼復(fù)雜度。

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

(6)

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

(7)

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

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

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

表1LDPC卷積碼在不同校驗(yàn)矩陣下的特性

Table1ThecharacteristicsofLDPCconvolutionalcodeswithdifferentcheckmatrices

LDPC卷積碼H(D)girth/girth數(shù)memoryHF(D)girth/girth數(shù)memoryHFm(D)girth/girth數(shù)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 仿真結(jié)果

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

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

4 結(jié) 語(yǔ)

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

[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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61401164，61173018)；廣東省自然科學(xué)基金資助項(xiàng)目(2014A030310308)

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

TN

A

0529-6579(2016)01-0063-05