范文同，馬林華，林志國，鄒浩彥，田 雨

(1.空軍工程大學(xué) a.航空航天工程學(xué)院； b.裝備管理與安全工程學(xué)院, 陜西 西安 710051;

一類環(huán)長(zhǎng)至少為10的準(zhǔn)循環(huán)LDPC碼

范文同1a，馬林華1a，林志國1b，鄒浩彥2，田 雨3

(1.空軍工程大學(xué) a.航空航天工程學(xué)院； b.裝備管理與安全工程學(xué)院, 陜西 西安 710051;

2.中國人民解放軍駐西安飛機(jī)工業(yè)公司軍事代表室,陜西 西安710089; 3.中國人民解放軍95876 部隊(duì), 甘肅 張掖 734100)

為擴(kuò)展性能優(yōu)良、易于工程實(shí)現(xiàn)的LDPC碼的構(gòu)造方法，提出了一類環(huán)長(zhǎng)至少為10的準(zhǔn)循環(huán)低密度奇偶校驗(yàn)碼的構(gòu)造方法。該方法首先基于基矩陣和2m準(zhǔn)則構(gòu)造出環(huán)長(zhǎng)至少為10的校驗(yàn)矩陣；然后，利用掩蔽矩陣對(duì)得到的校驗(yàn)矩陣進(jìn)行變換；最終，構(gòu)造出滿秩的準(zhǔn)循環(huán)LDPC碼。理論分析和仿真結(jié)果表明，該類QC-LDPC碼字構(gòu)造靈活，在AWGN信道下具有優(yōu)異的性能。

通信；環(huán)長(zhǎng)；滿秩；準(zhǔn)循環(huán)低密度奇偶校驗(yàn)碼

1 準(zhǔn)循環(huán)LDPC碼

低密度奇偶校驗(yàn)碼[1](LDPC)是Gallager于1962年提出的一種線性糾錯(cuò)編碼方案，因其具有接近香農(nóng)限的優(yōu)異性能，現(xiàn)已被諸多通信標(biāo)準(zhǔn)所采納并應(yīng)用[2-4]。LDPC碼構(gòu)造是其應(yīng)用的基礎(chǔ)。隨機(jī)構(gòu)造的碼字性能優(yōu)異，但往往編解碼復(fù)雜，難以在實(shí)際工程中應(yīng)用。構(gòu)造易于工程實(shí)現(xiàn)且性能優(yōu)異的LDPC碼成為研究的重點(diǎn)方向。

準(zhǔn)循環(huán)LDPC碼具有結(jié)構(gòu)化的特點(diǎn)，相較于隨機(jī)構(gòu)造的LDPC碼，其校驗(yàn)矩陣構(gòu)造簡(jiǎn)單，易于存儲(chǔ)，編解碼算法復(fù)雜度低，工程上易于實(shí)現(xiàn)，且通過設(shè)計(jì)可以構(gòu)造出性能優(yōu)異的碼字，因而得到了廣泛的研究[5-14]。通過循環(huán)置換矩陣構(gòu)造準(zhǔn)循環(huán)LDPC碼是一種常用的構(gòu)造方法。文獻(xiàn)[11]給出了此方法構(gòu)造碼字的一類框架，分析了構(gòu)造原理，但此方法構(gòu)造出的校驗(yàn)矩陣不滿秩；文獻(xiàn)[12]提出了一類基矩陣，基于最大公約數(shù)思想構(gòu)造環(huán)長(zhǎng)至少為8的準(zhǔn)循環(huán)LDPC碼，并給出了具體的掩蔽矩陣使校驗(yàn)矩陣滿秩，但未給出掩蔽矩陣的構(gòu)造原理；文獻(xiàn)[13]研究了構(gòu)造列重較大的環(huán)長(zhǎng)至少為8的準(zhǔn)循環(huán)LDPC碼的方法，也未說明如何構(gòu)造使校驗(yàn)矩陣滿秩的掩蔽矩陣；文獻(xiàn)[14]提出了兩種構(gòu)造環(huán)長(zhǎng)至少為10的LDPC碼的方法，但僅限于列重為3的情況，且構(gòu)造出的碼字不具有嚴(yán)格的準(zhǔn)循環(huán)特性。

2 環(huán)及環(huán)長(zhǎng)

(N,K)LDPC碼可以由校驗(yàn)矩陣H表示，N表示碼字長(zhǎng)度，K表示信息位長(zhǎng)度。校驗(yàn)矩陣中含有不同長(zhǎng)度的環(huán)[1]，任一 LDPC 碼的校驗(yàn)矩陣所含環(huán)的環(huán)長(zhǎng)至少為4，且均為偶數(shù)。短環(huán)的存在會(huì)加速錯(cuò)誤信息的傳播，導(dǎo)致譯碼發(fā)散和錯(cuò)誤，構(gòu)造大環(huán)長(zhǎng)的LDPC碼通常能夠獲得比用同等構(gòu)造方法構(gòu)造的短環(huán)LDPC碼更高的信噪比增益。

結(jié)合本文構(gòu)造方法需要，以下列出了校驗(yàn)矩陣中不同環(huán)長(zhǎng)對(duì)應(yīng)的停止集。校驗(yàn)矩陣中長(zhǎng)度為4的環(huán)表現(xiàn)形式如圖1所示，則圍長(zhǎng)至少為6的LDPC碼的校驗(yàn)矩陣中不含圖1所示的環(huán)。

圖1 環(huán)長(zhǎng)為4的停止集

校驗(yàn)矩陣中長(zhǎng)度為6的環(huán)表現(xiàn)形式如圖2所示，則圍長(zhǎng)至少為8的LDPC碼的校驗(yàn)矩陣中不含圖1和圖2所示的環(huán)。

圖2 環(huán)長(zhǎng)為6的停止集

校驗(yàn)矩陣中長(zhǎng)度為8的環(huán)表現(xiàn)形式較多，本文只列出其中一部分，如圖3所示。在構(gòu)造圍長(zhǎng)至少為10的LDPC碼時(shí)，應(yīng)避免其校驗(yàn)矩陣中含圖1、圖2或圖3所示的環(huán)。

圖3 環(huán)長(zhǎng)為8的部分停止集

3 本文構(gòu)造方法

定義矩陣

(1)

式中：J，L均為正整數(shù)，且J≥3，L≥3；a0,a1,…,aL-1為滿足 0≤a0

將矩陣中ai·j(i=0,…,L-1;j=0,…,J-1)轉(zhuǎn)換為大小為P×P的循環(huán)置換矩陣I(ai·j)，ai·j(modP)為單位陣I循環(huán)右移的位置。轉(zhuǎn)換后得到的新矩陣表示為

(2)

式中：pj,i=ai·j(0≤j≤J-1,0≤i≤L-1)。

維數(shù)為J×L的矩陣H即為本文設(shè)計(jì)的校驗(yàn)矩陣，矩陣E稱為校驗(yàn)矩陣H的基矩陣。

文獻(xiàn)[11]中給出了LDPC碼校驗(yàn)矩陣中含有環(huán)長(zhǎng)為2m(m>1)的環(huán)的條件，由此可得定理1。

定理1：準(zhǔn)循環(huán)LDPC碼的校驗(yàn)矩陣H包含環(huán)長(zhǎng)為2m的環(huán)的充分必要條件是

(3)

式中:0≤jk≤J-1，jk≠jk+1，jm=j0，0≤ik≤L-1。

依據(jù)此定理，式(2)所示的準(zhǔn)循環(huán)LDPC碼的校驗(yàn)矩陣的環(huán)長(zhǎng)至少為10的充分必要條件是

ai0j0-ai0j1+ai1j1-ai1j0≠0(modP)

(4)

ai0j0-ai0j1+ai1j1-ai1j2+ai2j2-ai2j0≠0(modP)

(5)

ai0j0-ai0j1+ai1j1-ai1j2+ai2j2-ai2j3+

ai3j3-ai3j0≠0(modP)

(6)

式中:0≤j0,j1,j2,j3≤J-1,0≤i0,i1,i2,i3≤L-1。

式(4)保證了校驗(yàn)矩陣中無環(huán)長(zhǎng)為4的環(huán)，式(5)保證了無環(huán)長(zhǎng)為6的環(huán)，式(6)保證了無環(huán)長(zhǎng)為8的環(huán)。因此，通過式(4)～式(6)構(gòu)造的準(zhǔn)循環(huán)LDPC碼的校驗(yàn)矩陣的環(huán)長(zhǎng)至少為10。

綜上所述，本文給出搜索S={a0,a1,…,aL-1}的具體步驟如下：

步驟1),初始化S={a0}，a0為非負(fù)整數(shù)，i=0。

步驟2),令Y=ai。

步驟3),令Y=Y+1，k=0,…,i，ai+1=Y，代入式(1)，計(jì)算E(a0,…,ai,ai+1)是否滿足式(4)，若滿足，則表明其中不含4環(huán)，執(zhí)行下一步驟；若不滿足，則表明其中含4環(huán)，重復(fù)步驟3)。

步驟4),計(jì)算E(a0,…,ai,ai+1)是否滿足式(5)，若滿足，則表明其中不含6環(huán)，執(zhí)行下一步驟；若不滿足，則表明其中含6環(huán)，跳轉(zhuǎn)至步驟3)。

步驟5),計(jì)算E(a0,…,ai,ai+1)是否滿足式(6)，若滿足，則表明其中不含8環(huán)，執(zhí)行下一步驟；若不滿足，則表明其中含8環(huán)，跳轉(zhuǎn)至步驟3)。

步驟6),S=S∪Y，i=i+1。若i

給定參數(shù)J,L,a0，通過上述搜索算法可以得到本文的基矩陣參數(shù)a0,a1,…,aL-1，進(jìn)而由式(2)構(gòu)造出環(huán)長(zhǎng)至少為10的準(zhǔn)循環(huán)LDPC碼。由搜索過程可知，矩陣參數(shù)a0,a1,…,aL-1不是唯一的，也說明構(gòu)造方法是靈活的。

通過上述方法構(gòu)造的準(zhǔn)循環(huán)LDPC碼不是滿秩的，實(shí)際上，通過循環(huán)置換矩陣構(gòu)造的碼字都存在這樣的問題[11-13]。為使H滿秩，常用的方法是設(shè)計(jì)掩蔽矩陣M，M和E(a0,…,aL-1)具有相同的維數(shù)，M中的0元素對(duì)應(yīng)的H中相應(yīng)位置用P×P的全0陣替代，其余不變。經(jīng)此變換后得到的校驗(yàn)矩陣H′滿秩，且滿足環(huán)長(zhǎng)至少為10。

定理2：掩蔽矩陣M滿秩是H′滿秩的必要條件。

證明：假設(shè)M為非滿秩矩陣，不失一般性，令M中第i行和第j行之和等于第k行。由M和H′的對(duì)應(yīng)關(guān)系可知H′中第(i-1)P+1行至第iP行，第(j-1)P+1至jP行之和，等于(k-1)P+1行至第kP行之和，H′不滿秩。因此，M滿秩是H′滿秩的必要條件。得證。

由此，在構(gòu)造LDPC碼時(shí)，首先根據(jù)本文前述方法構(gòu)造出如式(2)所示的校驗(yàn)矩陣；然后，構(gòu)造滿秩矩陣M，M的維數(shù)通常較小，易于構(gòu)造；最后，用M對(duì)校驗(yàn)矩陣進(jìn)行掩蔽，并檢測(cè)新矩陣是否滿秩，若不滿秩則重新構(gòu)造滿秩矩陣M。

4 仿真結(jié)果與分析

例1：取J=4,L=5,P=300，掩蔽矩陣M如式(7)，構(gòu)造出N=1 500,K=300的環(huán)長(zhǎng)至少為10的滿秩準(zhǔn)循環(huán)LDPC碼。與文獻(xiàn)[12]構(gòu)造的J=4,L=5,P=300，即同等碼長(zhǎng)、碼率的環(huán)長(zhǎng)至少為8的滿秩準(zhǔn)循環(huán)LDPC碼字的性能比較如圖4所示。仿真中均采用BP譯碼算法[15]，最大迭代次數(shù)均設(shè)置為100次。

(7)

圖4 本文構(gòu)造方法與文獻(xiàn)[12]構(gòu)造方法性能比較

例2：取J=3,L=5,P=155，掩蔽矩陣M如式(8)，構(gòu)造出N=775,K=465的環(huán)長(zhǎng)至少為10的滿秩準(zhǔn)循環(huán)LDPC碼。與文獻(xiàn)[14]構(gòu)造的J=3,L=5，N=775,K=459，環(huán)長(zhǎng)至少為10的LDPC碼字的性能比較如圖5所示。仿真條件同上。

(8)

圖5 本文構(gòu)造方法與文獻(xiàn)[14]構(gòu)造方法性能比較

圖4顯示本文構(gòu)造的碼字性能明顯優(yōu)于文獻(xiàn)[12]構(gòu)造的碼字性能，主要是本文構(gòu)造的碼字環(huán)長(zhǎng)至少為10，而后者最小環(huán)長(zhǎng)為8。由此也可以看出環(huán)長(zhǎng)對(duì)碼字的性能有影響。圖5顯示本文構(gòu)造的碼字與文獻(xiàn)[14]構(gòu)造的碼字性能相當(dāng)，兩者均是環(huán)長(zhǎng)至少為10的LDPC碼，然而文獻(xiàn)[14]構(gòu)造出的碼字并不是嚴(yán)格準(zhǔn)循環(huán)的，這在實(shí)際應(yīng)用中會(huì)增加譯碼復(fù)雜度。

為進(jìn)一步對(duì)比本文構(gòu)造的準(zhǔn)循環(huán)碼字與非嚴(yán)格準(zhǔn)循環(huán)碼字的譯碼復(fù)雜度，基于例2中本文和文獻(xiàn)[14]構(gòu)造的2種碼字，在Altera Stratix II EP2S60F1020I4芯片上，通過Verilog編程、ModelSim仿真，實(shí)現(xiàn)譯碼器的硬件仿真，譯碼器資源消耗及處理時(shí)延如表1所示。

表1 兩種方法構(gòu)造的碼字的譯碼復(fù)雜度對(duì)比

方法ALUT/個(gè)內(nèi)存/bit迭代一次所需時(shí)鐘周期文獻(xiàn)[14]862457367136本文算法658340269112

從表中可以看出，本文方法構(gòu)造的準(zhǔn)循環(huán)碼字無論在資源消耗還是處理時(shí)延上均優(yōu)于文獻(xiàn)[14]中構(gòu)造的非嚴(yán)格準(zhǔn)循環(huán)碼字，即本文方法構(gòu)造的碼字更易于工程實(shí)現(xiàn)。

5 小結(jié)

本文在前人研究的基礎(chǔ)上，提出了一類環(huán)長(zhǎng)至少為10的滿秩準(zhǔn)循環(huán)LDPC碼構(gòu)造方法，仿真表明該類碼字性能優(yōu)異。本文的構(gòu)造方法進(jìn)一步擴(kuò)展了LDPC優(yōu)良碼字的可選擇性，具有一定的工程應(yīng)用價(jià)值。

[1] GALLAGER R G. Low-density parity-check codes[J]. IRE Trans. Information Theory，1962，8(1)：21-28.

[2] ANDREWS K S, DOLINAR S, JONES R.The development of turbo and LDPC codes for deep-space applications[C]// Proc. the IEEE Conference.[S.l.]：IEEE Press，2007， 95(11)：2142-2156.

[3] Draft ETSI EN 302 307 V1.1.1， European standard (telecommunication series) Digital Video Broadcasting (DVB)[S].1997.

[4] CCSDS 131.0-P-1.1， Consultative Committee for Space Data Systems(CCSDS)，tm synchronization and channel coding， draft recommendation for space data system standard[S].2012.

[5] LI Lixin， ZHU Meng， YANG Fan. Performance analysis of QC-LDPC construction based on distance graph[C]//Proc. 2013 IEEE 8th Conference on Industrial Electronics and Applications (ICIEA). [S.l.]：IEEE Press，2013：1162-1166.

[6] ZHANG Jianjun，DONG Mingke，JIN Ye. A QC-LDPC construction algorithm for increasing the throughput of layered decoders[C]//Proc. 2013 15th IEEE International Conference on Communication Technology. [S.l.]：IEEE Press，2013：604-608.

[7] HAN Guojun，GUAN Yongliang，KONG Lingjun. Construction of irregular QC-LDPC codes via masking with ACE optimization[J]. IEEE Commun. Letters，2014，18(2)：348-351.

[8] CHEN Zhixiong，YUAN Jinsha. Construction of structure LDPC codes with full rank based on multi-permutation matrix[J]. ACTA Electronica Sinica，2012，40 (2)：313-318.

[9] ALEXANDER G， MICHAEL H. Low-density parity-check codes from transversal designs with improved stopping set distributions[J]. IEEE Trans. Commun.，2013，61(6)：2190-2200.

[10] DAVID G M M，ROXANA S， DANIEL J C. Quasi-cyclic LDPC codes based on pre-lifted protographs[J]. IEEE Trans. Inf. Theory，2014，60(10)：5856-5874.

[11] FOSSORIER M P C. Quasi-cyclic low-density parity-check codes from circulant permuation maries[J]. IEEE Trans. Inf. Theory，2004，50(8)：1788-1793.

[12] ZHANG Guohua，SUN Rong，WANG Xinmei. Construction of girth-eight QC-LDPC codes from greatest common divisor[J]. IEEE Commun. Letters，2013，17(2)：369-372.

[13] ZHANG Jianhua，ZHANG Guohua. Deterministic girth-eight QC-LDPC codes with large column weight[J]. IEEE Commun. Letters，2014，18(4)：656-659.

[14] WANG Juhua，ZHANG Guohua，ZHOU Quan， et al. Explicit constructions for type-1 QC-LDPC codes with girth at least ten[J]. IEEE Information Theory Workshop， 2014(6)：436-440.

[15] RICHARDSON T J， URBANKE R. The capacity of low-density parity check codes under message passing decoding[J]. IEEE Trans. Inf. Theory， 2001，47(1)：599-618.

范文同(1983— )， 博士生，主研協(xié)同通信；

馬林華(1963— )， 教授，主要研究方向?yàn)闊o線通信技術(shù)；

林志國(1986— )， 博士生，主研信道編解碼、調(diào)制解調(diào)技術(shù)研究。

責(zé)任編輯：閆雯雯

A Class of QC-LDPC Codes With Girth at Least 10

FAN Wentong1a, MA Linhua1a, LIN Zhiguo1b, ZOU Haoyan2, TIAN Yu3

(1a.AeronauticsandAstronauticsEngineeringCollege;1b.EquipmentManagementandSafetyEngineeringCollege,AFEU,Xi’an710051,China;2.PLAMilitaryRepresentativeOfficeinXi’anAircraftIndustryCorporation,Xi’an710089,China;3.Unit95876ofthePeople’sLiberationArmy,GansuZhangye734100,China)

Aiming at extending the construction methods of quasi-cyclic low-density parity-check (QC-LDPC) codes with good performance and easy applications, a scheme for constructing a class of QC-LDPC codes with girth at least 10 is proposed. First, based on a basis matrix and the 2mcriterion, parity-check matrices with girth at least 10 are constructed. Then, these matrices are transformed with masking matrices. Finally, full rank QC-LDPC codes are obtained. Theory analysis and simulation results show that the construction of these QC-LDPC codes are flexible and they perform very well over the additive white Gaussian noise (AWGN) channel.

communication; girth; full rank; QC-LDPC codes

TN911.22

A

10.16280/j.videoe.2015.19.015

2015-05-24

【本文獻(xiàn)信息】范文同，馬林華，林志國，等.一類環(huán)長(zhǎng)至少為10的準(zhǔn)循環(huán)LDPC碼[J].電視技術(shù),2015，39(19).