圍長為8的QC-LDPC碼的顯式構(gòu)造及其在CRT方法中的應(yīng)用

張國華，孫蓉，王新梅

（西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室，陜西 西安 710071）

1 引言

具有較大圍長的準(zhǔn)循環(huán)低密度奇偶校驗(QC-LDPC)碼，由于具有線性時間可編碼、需要的存儲空間較小、譯碼性能優(yōu)良等優(yōu)點，目前得到人們越來越多的研究。借助于計算機(jī)搜索，人們提出了一些構(gòu)造圍長大于6的QC-LDPC碼的準(zhǔn)隨機(jī)方法[1,2]。這些基于搜索的方法雖然比較靈活,但是由于沒有解決碼的存在性問題，因此不可避免地存在構(gòu)造失敗的可能性。相比而言，確定性方法可以直接給出校驗矩陣的顯式表達(dá)式，不存在構(gòu)造失敗的可能性，但是確定性方法的設(shè)計具有很大的挑戰(zhàn)性，所以研究成果比較罕見。

(J,L) QC-LDPC碼的校驗矩陣是一個JL×的陣列，陣列中的每個元素都是一個PP×的循環(huán)置換矩陣（CPM）。到目前為止，構(gòu)造圍長大于6的QC-LDPC碼的確定性方法只有幾種。對于列重 J為 3的情形，Tanner[3]基于群結(jié)構(gòu)提出了一類圍長幾乎全部達(dá)到最大值12的(3,5)QC-LDPC碼（碼長為5P,P為素數(shù)且P-1可被15整除）；B.Vasic[4]基于最早序列提出了一類girth-8 (3,L)QC-LDPC碼;K.K.Liu[5]提出了一類girth-8 (3,L) QC-LDPC碼；張國華[6]受貪婪搜索啟發(fā)提出了一類girth-8 (3,L)QC-LDPC碼。對于列重為4的情形，目前已知的確定性構(gòu)造方法只有一種，即K.K.Liu提出的一類girth-8 (4,L) QC-LDPC碼[7]。

本文提出了一種構(gòu)造girth-8(4,L)QC-LDPC碼的新的確定性方法。這種方法構(gòu)造出的碼允許碼長在某個門限之上以L為步進(jìn)連續(xù)取值；更引人注目的是，這種碼的連續(xù)碼長最小值不僅比文獻(xiàn)[7]中碼的連續(xù)碼長最小值要小得多（僅為其3/4左右），而且?guī)缀蹩梢赃_(dá)到目前利用計算機(jī)大規(guī)模搜索得出的碼長最小值。

本文組織如下：第2節(jié)描述了這種新碼的構(gòu)造方法，并證明了其圍長特性；第3節(jié)比較了新構(gòu)造方法和一些著名的搜索方法得到的碼長最小值；第4節(jié)提出了這種新碼的一種具體應(yīng)用，即結(jié)合中國剩余定理(CRT)構(gòu)造出一類圍長至少為8并且碼長非常靈活的合成QC-LDPC碼；第5節(jié)是結(jié)束語。

2 構(gòu)造方法

(4,L) QC-LDPC碼的校驗矩陣可以表示為

其中，I(x)表示一個受控于x的循環(huán)置換矩陣，具體定義與文獻(xiàn)[1]完全相同；為了便于論述和證明，下文使用m表示x的第一個索引標(biāo)記，使用i, j, k表示x的第二個索引標(biāo)記。本文按照如下方式配置pm,j(0≤m≤3,0≤j≤L-1)：

令上述配置下得到的矩陣用HD表示。定義HD中第r, s, t行(0≤r, s, t≤3)循環(huán)置換矩陣所構(gòu)成的矩陣為HD(r, s, t)。首先證明一些性質(zhì)和引理。

性質(zhì)1 p2,L-1＜3L2/4。

性質(zhì)2 若j＞i,則p2,j＞p2,i+p1,j。

證明 對j采用數(shù)學(xué)歸納法。首先考察j=i+1的情形。根據(jù)式(2)和式(3)，p2,i+1＞p2,i+(i +1)=p2,i+p1,i+1?，F(xiàn)在假設(shè)p2,j-1＞p2,i+p1,j-1,則根據(jù)式(2)和式(3)有p2,j＞p2,j-1+1＞p2,i+p1,j。

引理1 對于任意整數(shù)P≥3L2/4,HD(0,1,2)中無4-環(huán)；對于任意整數(shù)P≥3L2/4+L-1,HD中無4-環(huán)。

證明 根據(jù)式(2)～式(4)和性質(zhì)2，引理1很顯然成立。

引理2 對于任意整數(shù)P≥3L2/4，HD(0,1,2)的圍長為8。

證明 根據(jù)引理1，只需證明不存在6-環(huán)和證明存在8-環(huán)。假設(shè)HD(0,1,2)中存在6-環(huán)。則該環(huán)可用式(5)描述，其中，0≤i, j, k＜L互異。

情形1)j＞k, k≠0：式(5)變成p2,j=p2,k-p1,i+p1,jmod P，這是不可能的，因為根據(jù)性質(zhì)2，式(6)成立。

情形2)j＞k, k=0：式(5)變成p2,j+p1,i-p1,j=0mod P，這是不可能的，因為根據(jù)性質(zhì)2，式(7)成立。

情形3)j＜k：式(5)變成p2,k=p2,j+p1,i-p1,jmod P，這是不可能的，因為根據(jù)式(3)，式(8)成立。

現(xiàn)在考慮8-環(huán)。根據(jù)式(2)，HD(0,1,2)中總是存在一個由式(9)描述的不依賴于P的8-環(huán)：

引理3 對于任意整數(shù)P≥3L2/4,HD(1,2,3)中無6-環(huán)。

證明 假設(shè)HD(1,2,3)中存在6-環(huán)。則該環(huán)可用式(10)描述，其中，0≤i, j, k＜L互異。

根據(jù)式(4)，式(10)變成(0-p1,i)+(p1,j-p2,j)+(p2,k-0)=0modP ，這意味著HD(0,1,2)中存在6-環(huán)。與引理1矛盾。

引理4 對于任意整數(shù)P≥3L2/4+L-1，HD(0,1,3)中無6-環(huán)。

證明 假設(shè)HD(0,1,3)中存在6-環(huán)。則該環(huán)可用等式(11)描述，其中，0≤i, j, k＜L互異。

根據(jù)式(4)，式(11)變成：

情形1)i＞k, k≠0：式(12)是不可能的，因為式(13)導(dǎo)致式(14)成立。

情形2)i＞k, k=0：式(12)變成p2,i+p1,i=p1,jmodP ，這是不可能的，因為根據(jù)性質(zhì)1，式(15)成立。

情形3)i＜k, i≠0：式(12)變成p2,k=p2,i+p1,i-p1,jmod P，這是不可能的，因為根據(jù)式(3)，式(16)成立。

情形4)i＜k, i=0：等式(12)變成p2,k+p1,j=0modP，這是不可能的，因為式(17)成立。

引理5 對于任意整數(shù)P≥3L2/4+L-1,HD(0,2,3)中無6-環(huán)。

證明 假設(shè)HD(0,2,3)中存在6-環(huán)。則該環(huán)可用式(18)描述，其中，0≤i, j, k＜L互異。

根據(jù)式(4)，式(18)變成：

情形1)i＞j,j≠0：式(19)變成p2,i=p2,j-，p1,i+p1,kmod P，這是不可能的，因為根據(jù)式(3)，式(20)成立。

情形2)i＞j,j=0：式(19)變成p2,i+p1,i=p1,kmod P，這是不可能的，因為根據(jù)性質(zhì)1，式(21)成立。

情形3)i＜j,i≠0：式(19)變成p2,j=p2,i+p1,i-p1,kmod P，這是不可能的，因為根據(jù)式(3)，式(22)成立。

情形(4)i＜j,i=0：式(19)變成0=p2,j+p1,kmod P，這是不可能的，因為根據(jù)性質(zhì)1，式(23)成立。

根據(jù)引理1～引理5可以得到定理1。

定理1 對于任意整數(shù)P≥3L2/4+L-1,HD的圍長均為8。

3 最小P值的比較

K.K.Liu最近提出了(4, L) QC-LDPC碼的一種確定性構(gòu)造方法，對于任意2PL≥，該方法構(gòu)造出的LDPC碼的圍長均為8。根據(jù)定理1，構(gòu)造的girth-8(4,L) QC-LDPC碼的最小P值僅大約為K.K.Liu (4,L)QC-LDPC碼的最小P值的3/4。這說明，構(gòu)造的girth-8 (4,L) QC-LDPC碼的碼長具有更加廣泛的取值范圍。

構(gòu)造的girth-8 (4,L)QC-LDPC碼的最小P值甚至可以非常逼近基于計算機(jī)搜索的準(zhǔn)隨機(jī)方法所得到的最小P值。Fossorier[1]和Sullivan[2]采用基于計算機(jī)搜索的準(zhǔn)隨機(jī)方法，構(gòu)造出了P值非常小的girth-8 (4,L) QC-LDPC碼。對于L=4～13,Fossorier 給出了使得girth-8 (4,L) QC-LDPC碼存在的最小P值。對于L=5～12,Sullivan給出了對應(yīng)的搜索結(jié)果。圖1表明，對于L=5～13本文新方法給出的最小P值與上述2種準(zhǔn)隨機(jī)方法給出的最小P值非常接近。

需要指出的是，雖然圖1中的3種方法得到的最小P值非常接近，但是本文的方法是確定性的，不需要借助于任何計算機(jī)搜索過程。此外，該方法所對應(yīng)的最小P值是P允許連續(xù)取值的最小值：只要P不小于該最小值，相應(yīng)LDPC碼的圍長就為8。對于Fossorier和Sullivan方法得到的最小P值而言，當(dāng)P大于該最小值時LDPC碼的圍長不能保證必然為8，除非利用他們的搜索算法再次搜索出滿足girth-8條件的校驗矩陣。

圖1 3種方法得到的最小P值的比較

將HD的零空間對應(yīng)的二元碼記為D-QCLDPC碼。下面首先分析D-QC-LDPC碼的理論價值。文獻(xiàn)[1]在III-B節(jié)中提出了一個相當(dāng)難的問題（問題1）：如何給出使(J,L) QC-LDPC碼圍長至少為g的最小P值的解析結(jié)果？由定理1可知，只要P≥3L2/4+L-1就存在圍長至少為8的(4, L)QC-LDPC碼。顯然，該結(jié)論對于條件g=8，J=4下問題1的解決具有重要的理論參考價值。

另一方面，通過仿真發(fā)現(xiàn)，與文獻(xiàn)[1]搜索出的girth-8準(zhǔn)隨機(jī)QC-LDPC碼相比，D-QC-LDPC碼在譯碼性能上沒有明顯優(yōu)勢。但是，這并不說明D-QC-LDPC碼就沒有應(yīng)用價值。相反，D-QC-LDPC碼作為一個基本模塊可以在其他的LDPC碼構(gòu)造方法（例如CRT構(gòu)造法）中發(fā)揮至關(guān)重要的作用。

4 基于CRT構(gòu)造圍長至少為8的QC-LDPC碼

最近，中國剩余定理（CRT, Chinese remainder theorem）被應(yīng)用到QC-LDPC碼的構(gòu)造中[8,9]。利用CRT構(gòu)造LDPC碼的優(yōu)勢是，用若干個QC-LDPC短碼作為分量碼可以構(gòu)造出QC-LDPC長碼，并且QC-LDPC長碼的圍長不小于所有分量碼的最大圍長。將array碼作為分量碼，文獻(xiàn)[8]利用CRT構(gòu)造出了不含4環(huán)的QC-LDPC碼，文獻(xiàn)[9]利用CRT方法構(gòu)造出了一類不含4環(huán)并且6環(huán)數(shù)量大大減少（但不能完全消除）的QC-LDPC碼。由于array碼的CPM尺寸為素數(shù)，因此這2種方法得到的QC-LDPC碼的碼長取值非常受限。本節(jié)將D-QC-LDPC碼作為分量碼，利用其CPM尺寸可以任意取值的優(yōu)勢，基于CRT方法構(gòu)造出一類不僅完全消除4環(huán)和6環(huán)，而且碼長非常靈活的QC-LDPC碼。

4.1 構(gòu)造方法

根據(jù)CRT原理，利用一個不含6環(huán)的QC-LDPC短碼作為分量碼，可以構(gòu)造出一系列不含6環(huán)的QC-LDPC長碼。D-QC-LDPC碼的圍長為8且CPM尺寸可以任意取值，因而非常合適作為CRT方法中的這種分量碼。

設(shè)J∈{3,4}，L是滿足L＞J的任意整數(shù)。令Pth(3,L)=3L2/4，Pth(4,L)=3L2/4+L-1。設(shè)P1≥Pth(J, L)。D-QC-LDPC碼的校驗矩陣H1是由P1×P1的CPM所組成的一個J×L陣列，其指數(shù)矩陣為。設(shè)P2是滿足gcd(P1, P2)=1的整數(shù)（gcd表示最大公約數(shù)），H2是由P2×P2的CPM所組成的一個J×L陣列，其指數(shù)矩陣為E(H2)=()。令P=P1P2，定義指數(shù)矩陣E(H)=(pm,j)，其中，，A1和A2是滿足gcd(A1, P1)=1、gcd(A2, P2)=1的2個任意正整數(shù)。根據(jù)CRT原理[9]，校驗矩陣H是由P×P的CPM所組成的一個J×L陣列矩陣，其圍長可以確保至少為8。

2方式下校驗矩陣H的圍長可能不同；即使圍長相同，長度等于圍長的短環(huán)數(shù)量也可能差別很大。下面提出一種選擇指數(shù)矩陣E(H2)的啟發(fā)式策略，以使校驗矩陣H的圍長盡可能大，并且短環(huán)數(shù)量盡可能小。

1)指數(shù)矩陣E(H)的首行首列元素初始化為0，即p0,j=0(0≤j≤L -1),pm,0=0(0≤m≤J -1)，其余元素初始化為∞。

2)按 照p1,1,…,pJ-1,1,p1,2,…,pJ-1,2,…,p1,L-1,…,pJ-1,L-1的順序，依次確定。確定的策略是在0至P2-1中選擇使當(dāng)前H圍長最大的元素。如果有多個元素同時滿足該條件，可以隨機(jī)或按照固定方式選擇其中一個。這里采用固定方式，即選擇最小元素。

4.2 例子與仿真

相對于高碼率的LDPC碼而言，構(gòu)造性能優(yōu)良的中低碼率LDPC碼通常會更困難。例如，W E.Ryan和S.Lin在系統(tǒng)總結(jié)目前LDPC碼構(gòu)造進(jìn)展的最新專著《Channel Codes: Classical and Modern》[10]中所給出的絕大多數(shù)LDPC碼舉例均對應(yīng)于高碼率(大于0.75)，只有很少的幾個例子對應(yīng)于中低碼率(0.5及其以下)。下面利用4.1節(jié)所述方法構(gòu)造了2個設(shè)計碼率為0.5的合成QC-LDPC碼。為了對新合成碼的性能作出客觀評價，選擇2種比較基準(zhǔn)。第一種比較基準(zhǔn)是1/2碼率條件下的Shannon限(0.188dB)。第二種比較基準(zhǔn)是文獻(xiàn)[10]中設(shè)計碼率為0.5且碼長與新合成碼最為接近的LDPC碼。

例1 選擇P1=29,P2=7,A1=19,A2=2。根據(jù)4.1節(jié)構(gòu)造方法，得到了校驗矩陣H的指數(shù)矩陣E(H)：

經(jīng)驗證，校驗矩陣H的圍長為10。校驗矩陣H的CPM維數(shù)為(29×7)×(29×7)=203×203。對應(yīng)的合成碼碼長為203×6=1218、碼率為0.5016。在進(jìn)行譯碼仿真時，和積譯碼算法的最大迭代次數(shù)設(shè)定為80。在BER=10-6時，譯碼性能距離Shannon限僅2.43dB(如圖2所示)。文獻(xiàn)[10]中Example 11.8利用基于RS碼特殊子集的方法構(gòu)造了一個碼長為1488、碼率為0.502的QC-LDPC碼，在BER=10-6時該碼的譯碼性能距離Shannon限為3.5dB。新合成碼比Example 11.8碼的性能改善了約1.07dB。

例2 選擇P1=64,P2=7,A1=21,A2=2。根據(jù)4.1節(jié)所述構(gòu)造方法，得到了校驗矩陣H的指數(shù)矩陣E(H)：

經(jīng)驗證，校驗矩陣H的圍長為8。校驗矩陣H的CPM維數(shù)為(64×7)×(64×7)=448×448。對應(yīng)的合成碼碼長為448×8=3 584、設(shè)計碼率為0.501 1。在進(jìn)行譯碼仿真時，和積譯碼算法的最大迭代次數(shù)設(shè)定為80。在BER=10-6時，譯碼性能距離Shannon限僅2.15dB(如圖2所示)。文獻(xiàn)[10]中Example 11.12.基于素域中的加法群方法構(gòu)造了一個碼長為4 672、碼率為0.501的(4,8)QC-LDPC碼，在BER=10-6時該碼的譯碼性能距離Shannon限為2.05dB。雖然新合成碼比Example 11.12碼的性能略差一些，但是前者碼長要比后者碼長短1 088bit。這說明新合成碼的性能是非常優(yōu)異的。

除了具有優(yōu)異的譯碼性能，新合成碼的一個突出優(yōu)勢在于碼長取值的靈活性。對于例1和例2所述的基于RS碼特殊子集的方法和基于素域中加法群的方法，其CPM尺寸與有限域的階數(shù)(為素數(shù)或素數(shù)的冪)存在密切關(guān)聯(lián)，因而CPM尺寸的選取不夠靈活。而4.1節(jié)提出的新方法CPM尺寸為P=P1P2，其中P1為滿足P1≥Pth(J, L)的任意整數(shù)，P2只要滿足gcd(P1, P2)=1即可，所以CPM尺寸的取值非常靈活。此外，新合成碼構(gòu)造時不需要有限域知識背景，因此對于實際工程應(yīng)用而言具有較大競爭力。

圖2 D-QC-LDPC碼作為分量碼利用CRT得到的合成QC-LDPC碼的性能曲線

5 結(jié)束語

本文提出了一種構(gòu)造圍長為8的(4,L)QCLDPC碼的確定性方法。這類新碼的最小P值與Fossorier和Sullivan利用準(zhǔn)隨機(jī)方法通過計算機(jī)大量搜索得到的最小P值非常接近。將新QC-LDPC碼作為分量碼，基于中國剩余定理構(gòu)造出一類圍長至少為8且碼長取值非常靈活的合成QC-LDPC碼。在1/2設(shè)計碼率和中等碼長條件下的仿真結(jié)果表明，這類新的合成QC-LDPC碼在AWGN信道下具有優(yōu)異的譯碼性能。顯然，本文設(shè)計的矩陣DH也可以用來構(gòu)造圍長至少為8的多元QC-LDPC碼，具體構(gòu)造細(xì)節(jié)和譯碼性能仿真將是近期的研究內(nèi)容之一。

[1] FOSSORIER M P C. Quasi-cyclic low-density parity-check codes from circulant permutation matrices[J]. IEEE Trans on Information Theory, 2004, 50(8):1788-1793.

[2] O’SULLIVAN M E. Algebraic construction of sparse matrices with large girth[J]. IEEE Trans on Information Theory, 2006, 52(2):718-727.

[3] KIM S, NO J S,CHUNG H, et al. On the girth of tanner (3,5)quasi-cyclic LDPC codes[J]. IEEE Trans on Information Theory, 2006,52(4):1739–1744.

[4] VASIC B, PEDAGANI K, IVKOVIC M. High-rate girth-eight low-density parity-check codes on rectangular integer lattices[J].IEEE Trans on Communications, 2004, 52(8):1248-1252.

[5] LIU K K, FEI Z S, KUANG J M. Novel algebraic constructions of nonbinary structured LDPC codes over finite fields[A]. Proc 68th IEEE VTC Fall[C]. Calgary, Alberta, Canada, 2008. 1-5.

[6] 張國華, 陳超, 楊洋等. Girth-8 (3,L)-規(guī)則QC-LDPC碼的一種確定性構(gòu)造方法[J]. 電子與信息學(xué)報, 2010,32(5): 1152-1156.ZHANG G H, CHEN C, YANG Y, et al. Girth-8 (3, L)-regular QC-LDPC codes based on novel deterministic design technique[J].Journal of Electronics & Information Technology, 2010, 32(5):1152-1156.

[7] LIU K K, FEI Z S, KUANG J M. Three algebraic methods for constructing nonbinary LDPC codes based on finite fields[A]. Proc 19th IEEE PIMRC[C]. Cannes, French Riviera, France, 2008.1-5.

[8] MYUNG S, YANG K. A combining method of quasi-cyclic LDPC codes by the Chinese remainder theorem[J]. IEEE Communication Letters, 2005, 9(9):823-825.

[9] LIU Y H, WANG X M, CHEN R W, et al. Generalized combining method for design of quasi-cyclic LDPC codes[J]. IEEE Communication Letters, 2008, 12(5):392-394.

[10] RYAN W E, LIN S. Channel Codes: Classical and Modern[M]. Cambridge University Press, 2009.