低存儲可線性編碼的QC-LDPC碼設(shè)計

孔令軍 姜 明 趙春明

(1東南大學(xué)移動通信國家重點實驗室, 南京 210096)(2南京郵電大學(xué)通信與信息工程學(xué)院, 南京 210003)

低存儲可線性編碼的QC-LDPC碼設(shè)計

孔令軍1,2姜 明1趙春明1

(1東南大學(xué)移動通信國家重點實驗室, 南京 210096)(2南京郵電大學(xué)通信與信息工程學(xué)院, 南京 210003)

為了解決構(gòu)造任意長度、無小停止集且無短環(huán)QC-LDPC碼的設(shè)計問題,研究了基于Tanner圖的停止集、圍長和最小碼重三者之間的關(guān)系,提出了QC-LDPC碼無短停止距離且無短環(huán)的充要條件.在此基礎(chǔ)上,為了進(jìn)一步降低編碼復(fù)雜度并保留結(jié)構(gòu)化特性,提出了一種具有線性編碼復(fù)雜度的基于后向迭代的QC-LDPC碼.仿真結(jié)果表明:所構(gòu)造的QC-LDPC碼的糾錯性能與IEEE 802.11n中QC-LDPC碼相近,與IEEE 802.16e中QC-LDPC碼相比,在誤碼率為10-6時,可獲得0.15 dB的性能增益;此外,該碼字只需存儲移位因子和單位子矩陣的階數(shù),所占硬件存儲空間明顯小于另外2種QC-LDPC碼.

QC-LDPC碼;準(zhǔn)循環(huán)碼;停止集;停止距離;圍長

近年來,LDPC碼[1-2]憑借其在AWGN等信道中具有接近香農(nóng)限的糾錯性能且可實現(xiàn)的譯碼復(fù)雜度,成為當(dāng)今信道編碼領(lǐng)域的研究熱點之一[3-5].QC-LDPC碼是借用數(shù)學(xué)分析法(如幾何代數(shù)方法)來構(gòu)造的一類非常重要的LDPC碼,其校驗矩陣具有類循環(huán)特性,實現(xiàn)復(fù)雜度低,可以采用簡單的移位寄存器硬件來實現(xiàn)編碼器,易于硬件實現(xiàn)[6-7].

LDPC碼的校驗矩陣主要基于停止集和圍長來進(jìn)行構(gòu)造.停止集及其停止距離制約著迭代譯碼收斂速率;當(dāng)圍長趨于無窮時,和積譯碼算法近似為最優(yōu)譯碼算法.文獻(xiàn)[8]指出,經(jīng)過二進(jìn)制刪除信道或AWGN信道傳輸, 采用迭代譯碼算法時停止集具有重要的作用.文獻(xiàn)[9-10]指出,采用迭代譯碼算法時譯碼性能差的主要原因是LDPC碼對應(yīng)的Tanner圖中含有小的停止集.編碼復(fù)雜度是影響LDPC碼應(yīng)用的一個主要問題.通常采用生成矩陣的方法進(jìn)行編碼,編碼運算復(fù)雜度為碼長的平方.LDPC碼的碼長往往多達(dá)數(shù)千比特,會影響編碼器的實現(xiàn).為此,需要回避生成矩陣,直接通過校驗矩陣進(jìn)行編碼.在碼字性能允許的范圍內(nèi),校驗矩陣結(jié)構(gòu)化能最大限度地降低編碼復(fù)雜度.IEEE 802.16e和IEEE 802.11n標(biāo)準(zhǔn)中均采用了可近似線性編碼的LDPC碼方案,雖然降低了編碼的復(fù)雜度,但破壞了LDPC碼校驗矩陣的結(jié)構(gòu)特性,增加了編解碼器所占的硬件存儲資源.

為了在降低編碼復(fù)雜度的同時保留結(jié)構(gòu)化特性,本文提出了一種基于后向迭代的可線性編碼的QC-LDPC碼,綜合考慮了停止集、圍長、最小碼重三者之間的關(guān)系,在增加圍長和停止距離的同時盡可能提高最小碼重.仿真結(jié)果表明,所設(shè)計的碼字具有良好的誤碼率性能,更適于實際應(yīng)用.

1 QC-LDPC碼的停止集與圍長

對于每個變量節(jié)點v∈V和校驗節(jié)點c∈C,dv和dc分別表示v和c的度,dV(c)表示連接c到變量節(jié)點集合V的邊的數(shù)量.集合S為LDPC碼對應(yīng)的Tanner圖的變量節(jié)點集合V的子集.如果集合S的所有鄰節(jié)點(與Tanner圖中集合S的變量節(jié)點相連的校驗節(jié)點)與S相連的次數(shù)不少于2,則稱S為停止集.停止集一般由多個環(huán)構(gòu)成.構(gòu)成停止集的變量節(jié)點分為2種:① 變量節(jié)點與其他變量節(jié)點構(gòu)成環(huán);② 變量節(jié)點連接不同的環(huán).

QC-LDPC碼的校驗矩陣由單位陣的循環(huán)移位組合而成,其移位數(shù)由索引矩陣確定[6].索引矩陣P可表示為

(1)

式中,索引矩陣元素Px,y=aybx,其中0≤x≤j-1,0≤y≤k-1,j和k分別為矩陣的行數(shù)和列數(shù),a和b為移位因子.

QC-LDPC碼的校驗矩陣H可由P得到,其元素IPx,y由m階單位陣I循環(huán)移位Px,y(modm)位構(gòu)成.

定理1 QC-LDPC碼的校驗矩陣H含有停止距離為3的停止集的充要條件為：至少存在一組數(shù)(x,x′,x″,y,y′,y″)使得方程組

(2)

中至少一個方程成立,同時滿足

H(i,y)+H(i,y′)+H(i,y″)≠1

(3)

式中,0≤x≤j-3;1≤x′≤j-2;2≤x″≤j-1;x≠x′≠x″;0≤y≤k-3; 1≤y′≤k-2;2≤y″≤k-1;y≠y′≠y″;0≤i≤j-1;i≠x≠x′≠x″.

證明 至少存在一組數(shù)(x,x′,x″,y,y′,y″)使得方程組(2)中任意一方程成立時,QC-LDPC碼的校驗矩陣H含有6環(huán).定理1的證明等價于若校驗矩陣H含有6環(huán),其6環(huán)所含有的3個變量節(jié)點構(gòu)成停止距離為3的停止集.由停止集定義可知,其鄰節(jié)點與本身連接邊的數(shù)目不少于2.構(gòu)成6環(huán)的3個鄰節(jié)點滿足定義,只要確保其他鄰節(jié)點也滿足定義即可.式(3)確保了其他校驗節(jié)點與構(gòu)成6環(huán)的變量集合S連接次數(shù)不等于1.此時,變量集合S構(gòu)成停止距離為3的停止集.

推論1 QC-LDPC碼校驗矩陣H中無停止距離為3的停止集的必要條件為

(4)

式中, 1≤s≤k-2;2≤s′≤k-1;s

根據(jù)推論1,本文提出停止距離為3的停止集檢測方程組為

(5)

式中,1≤s≤k-2;2≤s′≤k-1;s

以列重為3、行重為6的(3,6)QC-LDPC碼為例,根據(jù)式(5)得出停止距離為3的停止集檢測矩陣F為

F=F1&F2&F3&F4&F5&F6

(6)

式中

(7)

式中,1≤v≤6.

設(shè)定移位因子a,b及最小單位子矩陣的階次m后,檢測矩陣F中非下三角矩陣的值是否無零元素,即可確定QC-LDPC碼是否含有停止距離為3的停止集. 根據(jù)式(5),可得出任意QC-LDPC碼的檢測矩陣,從而構(gòu)造出任意行重和列重的無停止距離為3的QC-LDPC碼,進(jìn)一步構(gòu)造出無停止距離為2的QC-LDPC碼.低碼重碼的存在使譯碼器糾錯能力低下,不能糾正多個比特的錯誤.根據(jù)最小碼重定義可知,生成矩陣行向量的最小碼重小于該碼字的最小碼重,可作為最小碼重的一個上界,從而為構(gòu)造無低碼重的LDPC碼提供依據(jù).

2 低存儲可線性編碼的QC-LDPC碼構(gòu)造算法

根據(jù)定理1及推論1,給定移位因子,計算其對應(yīng)的QC-LDPC碼停止集檢測矩陣,篩選出使碼字無停止距離為2和3的移位因子.為進(jìn)一步降低編碼復(fù)雜度,令所構(gòu)造LDPC碼的校驗矩陣Hd為

Hd=[HtHbs]

(8)

式中,Ht和Hbs分別表示具有準(zhǔn)循環(huán)結(jié)構(gòu)的子矩陣和后向迭代的雙對角矩陣,且Ht的索引矩陣滿足式(1).由式(1)可知,只需確定移位因子a和b、單位子矩陣階數(shù)p以及列重cw,即可得出校驗矩陣Ht.

低存儲可線性編碼的QC-LDPC碼構(gòu)造算法步驟如下:

①κ=1,根據(jù)Tκ=(aκ,bκ)可得移位因子aκ和bκ,令a=aκ,b=bκ,根據(jù)式(1)可得到Htκ.

② 后向雙對角矩陣Hbsκ矩陣為

(9)

式中,I0表示無移位的單位矩陣.

④ 根據(jù)Tκ中的移位因子，構(gòu)造出無短環(huán)和無小停止集、具有線性編碼復(fù)雜度的QC-LDPC碼.

⑦ 得到最終所構(gòu)造碼字的最小漢明距離dmin≈wmin.

綜合考慮環(huán)、停止集以及最小碼重對LDPC碼性能的影響,進(jìn)行低存儲、可線性編碼的QC-LDPC碼設(shè)計.此外,采用本文方法還可估算QC-LDPC碼的最小漢明距離.

3 性能分析與仿真比較

所構(gòu)造的QC-LDPC碼校驗矩陣Hd為

(10)

式中,單位陣I的下標(biāo)根據(jù)式(1)確定.

表1 LDPC碼的參數(shù)

與IEEE 802.11n和IEEE 802.16e中QC-LDPC碼的校驗矩陣相比,所提出的基于后向迭代的子矩陣結(jié)構(gòu)最為簡單,IEEE 802.11n和IEEE 802.16e中碼字的校驗矩陣只是具有近似的雙對角結(jié)構(gòu).此外,IEEE 802.11n和IEEE 802.16e中QC-LDPC碼的校驗矩陣左邊子矩陣不具備準(zhǔn)循環(huán)特性,因此需要大量的硬件存儲資源存儲校驗矩陣,而所構(gòu)造的校驗矩陣只需存儲移位因子a和b.

圖1為本文構(gòu)造的QC-LDPC碼與其他LDPC碼的BER曲線比較.由構(gòu)造方法可知,所設(shè)計的碼字既不含停止距離為2和3的停止集,又有效避免了4環(huán)和6環(huán);同時,所提方案確保碼字的最小碼重盡可能最大化.仿真結(jié)果證明,與等長的隨機LDPC碼相比,基于后向迭代的不規(guī)則QC-LDPC碼具有較好的BER性能,在SNR<2 dB時能迅速收斂.本文構(gòu)造的QC-LDPC碼具有優(yōu)于IEEE 802.16e 中標(biāo)準(zhǔn)中等長QC-LDPC碼的BER性能,當(dāng)BER=10-6時,具有大約0.15 dB的增益;而與IEEE 802.11n中的QC-LDPC碼相比,兩者具有相近的糾錯性能.此外,所構(gòu)造的QC-LDPC碼具有線性編碼復(fù)雜度,且在碼率和碼長已知時,只需存儲移位因子和單位子矩陣的階數(shù),因而存儲校驗矩陣所占硬件存儲空間較小,而另外2種QC-LDPC碼為近似線性編碼,需要較大的存儲空間.

圖1 LDPC碼仿真誤碼率比較

4 結(jié)論

1)為了在降低編碼復(fù)雜度的同時保留結(jié)構(gòu)化特征,本文提出了一種基于后向迭代的可線性編碼的不規(guī)則QC-LDPC碼.該碼字具有良好的BER性能,既不含停止距離為2和3的停止集,又有效避免了4環(huán)和6環(huán);所提方案確保碼字的最小碼重盡可能最大化.

2)仿真結(jié)果表明,該碼字具有優(yōu)于IEEE 802.16e標(biāo)準(zhǔn)中等長碼的BER性能,以及和IEEE 802.11n中碼字相近的誤碼率性能；所構(gòu)造的QC-LDPC碼具有線性編碼復(fù)雜度,且存儲校驗矩陣所占的硬件存儲空間較小,因而實際應(yīng)用更加可行.

References)

[1]Gallager R. Low-density parity-check codes[J].IEEETransactionsonInformationTheory, 1962, 8(1): 21-28. DOI:10.1109/tit.1962.1057683.

[2]Richardson T J. LDPC design for high parallelism, low error floor, and simple encoding:US, US9306601[P]. 2016-04-05.

[3]Ganesan K, Grover P, Rabaey J, et al. On the total power capacity of regular-LDPC codes with iterative message-passing decoders[J].IEEEJournalonSelectedAreasinCommunications, 2016, 34(2): 375-396. DOI:10.1109/jsac.2015.2504276.

[4]Song L, Huang Q, Wang Z, et al. Two enhanced reliability-based decoding algorithms for nonbinary LDPC codes[J].IEEETransactionsonCommunications, 2016, 64(2): 479-489. DOI:10.1109/tcomm.2015.2512582.

[5]Tasdighi A, Banihashemi A H, Sadeghi M R. Efficient search of girth-optimal QC-LDPC codes[J].IEEETransactionsonInformationTheory, 2016, 62(4): 1552-1564. DOI:10.1109/tit.2016.2523979.

[6]Tanner R M, Sridhara D, Sridharan A, et al. LDPC block and convolutional codes based on circulant matrices[J].IEEETransactionsonInformationTheory, 2004, 50(12): 2966-2984. DOI:10.1109/tit.2004.838370.

[7]林炳, 姜明, 趙春明. 基于二維優(yōu)化的QC-LDPC碼構(gòu)造方法[J]. 東南大學(xué)學(xué)報(自然科學(xué)版), 2010, 40(1): 6-10. DOI:10.3969/j.issn.1001-0505.2010.01.002. Lin Bing, Jiang Ming, Zhao Chunming. Construction of QC-LDPC codes based on two-dimentional optimization[J].JournalofSoutheastUniversity(NaturalScienceEdition), 2010, 40(1): 6-10. DOI:10.3969/j.issn.1001-0505.2010.01.002.(in Chinese)

[8]Di C A, Proietti D, Telatar I E, et al. Finite-length analysis of low-density parity-check codes on the binary erasure channel[J].IEEETransactionsonInformationTheory, 2002(6): 1570-1579. DOI:10.1109/tit.2002.1003839.

[9]Tian T, Jones C, Villasenor J D, et al. Construction of irregular LDPC codes with low error floors[C]//Proceedingsof2003IEEEInternationalConferenceonCommunications. Anchorage, Alaska, USA, 2003: 3125-3129.

[10]馬克祥. LDPC碼快速及低錯誤平層譯碼算法研究[D]. 西安: 西安電子科技大學(xué)通信工程學(xué)院, 2014.

QC-LDPC code design with low hardware storage and linear encoding

Kong Lingjun1, 2Jiang Ming1Zhao Chunming1

(1National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China)(2College of Telecommunications and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China)

To solve the design problem of constructing quasi-cyclic low-density parity-check (QC-LDPC) codes of any length without small stopping sets or small girth, the relationship among the stopping set, the girth and the minimum weight based on the Tanner graph is investigated. The necessary and sufficient conditions of the QC-LDPC codes without small stopping sets or small girth are proposed. To further reduce the encoding complexity and maintain the structural characteristics, the backward iteration based QC-LDPC code with linear encoding complexity is proposed. The simulation results show that the error correction performance of the constructed QC-LDPC code is similar to that of the QC-LDPC code in IEEE 802.11n. And the designed code achieves a performance gain of 0.15 dB at the bit error rate of 10-6compared with the QC-LDPC code in IEEE 802.16e. Meanwhile, the proposed code only needs to store the shift factor and the order of the unit sub-matrix, inducing that the hardware storage resource is obviously smaller than those of the other two QC-LDPC codes.

low-density parity-check (QC-LDPC) code; quasi-cyclic (QC) code; stopping set; stopping distance; girth

10.3969/j.issn.1001-0505.2017.03.001

2016-11-10. 作者簡介: 孔令軍(1982—),男,博士,副教授,ljkong@njupt.edu.cn.

中國博士后科學(xué)基金資助項目(2015M581698)、國家自然科學(xué)基金青年基金資助項目(61501250)、教育部留學(xué)回國人員科研啟動基金資助項目(BJ215002)、江蘇省博士后科研資助計劃資助項目(1501037B)、江蘇省自然科學(xué)基金青年基金資助項目(SJ214029)、江蘇省高校自然科學(xué)研究面上項目資助項目(14KJB510021)、南京郵電大學(xué)引進(jìn)人才科研啟動基金資助項目(NY214015).

孔令軍，姜明，趙春明.低存儲可線性編碼的QC-LDPC碼設(shè)計[J].東南大學(xué)學(xué)報(自然科學(xué)版),2017,47(3):421-425.

10.3969/j.issn.1001-0505.2017.03.001.

TN911.22

A

1001-0505(2017)03-0421-05