張 軼,達(dá)新宇,蘇一棟

(空軍工程大學(xué)信息與導(dǎo)航學(xué)院,陜西西安 710077)

?

任意列重大圍長QC-LDPC碼的確定性構(gòu)造

張 軼,達(dá)新宇,蘇一棟

(空軍工程大學(xué)信息與導(dǎo)航學(xué)院,陜西西安 710077)

針對準(zhǔn)循環(huán)低密度奇偶校驗(Quasi-Cyclic Low-Density Parity-Check,QC-LDPC)碼中準(zhǔn)循環(huán)基矩陣的移位系數(shù)確定問題，提出基于等差數(shù)列的確定方法.該方法構(gòu)造的校驗矩陣圍長為8，列重可任意選取，移位系數(shù)由簡單的數(shù)學(xué)表達(dá)式確定，編碼復(fù)雜度與碼長呈線性關(guān)系，節(jié)省了編解碼存儲空間.研究結(jié)果表明，列重和圍長是影響碼字性能的重要因素.在加性高斯白噪聲(Additive White Gauss Noise,AWGN)信道和置信傳播(Belief Propagation,BP)譯碼算法下，該方法構(gòu)造的碼字在短碼時可以獲得與IEEE 802.11n、802.16e碼相一致的性能，在長碼時誤比特率性能接近DVB-S2碼.同時表明該方法對碼長和碼率參數(shù)的設(shè)計具有較好的靈活性.

準(zhǔn)循環(huán)低密度奇偶校驗碼;列重;圍長;準(zhǔn)循環(huán)基矩陣;高效編碼

電子學(xué)報URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.006

1 引言

碼的結(jié)構(gòu)決定了低密度奇偶校驗(Low-Density Parity-Check,LDPC)碼的性能.基于循環(huán)移位矩陣構(gòu)造的QC-LDPC碼，其校驗矩陣的準(zhǔn)循環(huán)特性使其易于高效編解碼，碼的代數(shù)結(jié)構(gòu)為超大規(guī)模集成電路的實現(xiàn)提供了可能，因此受到廣泛關(guān)注和研究.圍長是碼中最小的環(huán)長度，增大圍長可以提高碼字的性能.借助于計算機搜索，人們已經(jīng)提出了一些圍長大于6的QC-LDPC碼構(gòu)造方法[1～6]，但為了滿足各種約束條件，這些準(zhǔn)隨機方法通?；ㄙM時間長、存在失敗可能，且對編解碼存儲空間提出了更高要求.

針對上述問題，國內(nèi)外學(xué)者對確定性構(gòu)造方法的研究屢有成果涌現(xiàn).Tanner[7]和Zhang Fan[8]分別采用群結(jié)構(gòu)法、3維循環(huán)網(wǎng)絡(luò)法構(gòu)造出了圍長在10以上的QC-LDPC碼，但是校驗矩陣的行重只局限于特定范圍內(nèi)；Zhang Guo-hua[9]提出了基于二次函數(shù)的確定性方法，但方程系數(shù)與行重有關(guān)，任意行重只能構(gòu)造兩種校驗矩陣；張國華[10～12]基于貪婪算法構(gòu)造了圍長為8的QC-LDPC碼，其循環(huán)移位矩陣尺寸具有連續(xù)變化的優(yōu)點，但該方法要求準(zhǔn)循環(huán)基矩陣首行首列元素必須為0；Zhang Jian-hua[13]首次提出任意列重的構(gòu)造方法，然而固定碼參數(shù)下的校驗矩陣形式是唯一的.此外，以上方法均未考慮由校驗矩陣直接編碼的方案，這在一定程度上限制了它們的實際應(yīng)用.

在此基礎(chǔ)上，本文提出一種構(gòu)造任意列重、圍長為8的QC-LDPC碼確定性方法.首先構(gòu)造了列重為4的基矩陣，分析了其圍長特性；通過總結(jié)推導(dǎo)將特殊情形推廣，進(jìn)而提出任意列重的確定性構(gòu)造方法，并證明了該碼的圍長至少為8；然后利用特殊的子矩陣結(jié)構(gòu)實現(xiàn)了由校驗矩陣進(jìn)行迭代編碼，降低了編碼復(fù)雜度；最后通過軟件仿真，驗證了該方法構(gòu)造的QC-LDPC碼參數(shù)設(shè)置靈活、性能優(yōu)良.

2 QC-LDPC碼

QC-LDPC碼的校驗矩陣以單位陣的循環(huán)移位陣和零方陣為子陣，可表示為

(1)

其中：I(pij)表示一個p×p的循環(huán)移位矩陣.把循環(huán)右移系數(shù)pij寫成一個矩陣P，稱為準(zhǔn)循環(huán)基矩陣，如式(2)所示[14]：

(2)

在基矩陣P中，若干個點(元素)p1,p2,…,p2k構(gòu)成一個環(huán)，則對應(yīng)的H矩陣也存在與之對應(yīng)的p個同樣大小的環(huán).顯然，環(huán)的長度只能是大于或等于4的偶數(shù).表示H中長為2k環(huán)的序列(p1,p2,…,p2k)滿足如下定理：

定理1[15]對于基矩陣P中的序列(p1,p2,…,p2k)，其中pi和pi+1在同一行或同一列，pi和pi+2在不同行且不同列，則(p1,p2,…,p2k)構(gòu)成長為2k環(huán)的充要條件是

(3)

短環(huán)的存在使LDPC碼在譯碼時不能快速收斂，造成誤比特率(Bit Error Rate,BER)性能變差.因此，為了使校驗矩陣不含長為2k的環(huán)，就必須通過某種設(shè)計，使得式(3)不成立.圖1給出了6環(huán)存在的六種形狀.

3 構(gòu)造方法

將校驗矩陣H分為校驗部分Ha和信息部分Hb，如式(4)所示：

H=

(4)

其中，Ha為下三角結(jié)構(gòu)，大小為mp×mp，主對角線由單位陣構(gòu)成，0表示零矩陣；Hb大小為mp×kp(k=n-m).

首先考慮一種(4,n)基矩陣P的配置方式：

p1,j+1-p1,j=d1>0,1≤j

(5)

p2,j+1-p2,j=d2>d1,2≤j

(6)

p3,j+1-p3,j= max[(n-j)·(d2-d1)+d1+1,(j-1)

·(d2-d1)+d1+1], 3≤j

(7)

p4,j+1-p4,j=p3,j+1-p3,j+1, 4≤j

(8)

顯然P中第1、2行元素分別構(gòu)成單增等差數(shù)列.首先證明一些引理.

引理1 P中無4環(huán).

證明 由式(5)～式(8)，對任意4≤i

p4,j-p4,i>p3,j-p3,i>p2,j-p2,i>p1,j-p1,i>0

(9)

同理對任意2≤i

引理2 P中無圖1(a)～(d)所示6環(huán).

證明 根據(jù)引理1的證明過程，引理2顯然成立.

引理3 P中無圖1(e)～(f)所示6環(huán).

證明 令P中第x,y,z行(1≤x,y,z≤4)構(gòu)成的矩陣為P(x,y,z).考慮P(1,2,3)和圖1(e)的情形，不失一般性，令2≤i

由式(7)可得p3,j-p3,l≥(d2-d1)·l+d1+1，故

(p3,j-p3,l)+(p1,l-p1,i)+(p2,i-p2,j)

≥(d2-d1)·l+d1+1+(l-i)·d1+(i-j)·d2

=(d2-d1)·(i-1)+1>0

(10)

因此P(1,2,3)中無圖1(e)所示6環(huán)，同理也不存在圖1(f)所示6環(huán).采用相同的分析方法易知P(1,2,4)、P(1,3,4)和P(2,3,4)的中均無6環(huán).

將其推廣至任意列重的基矩陣，令di,j=pi,j+1-pi,j，1≤i≤m，i≤j

(1)當(dāng)m≤4時，按照式(5)～式(8)配置P.

(2)當(dāng)m>4時，設(shè)

d4k+1,j=p4k-1,n-(n-4k)·d1+1,k≥1

(11)

d2k+2,j=d2k+1,j+1,k≥2

(12)

d4k+3,j=max(d4k+1,j+n-j

+1,d4k+1,j+j-4k),k≥1

(13)

引理4 (m,n)基矩陣P中無6環(huán).

證明 不失一般性，令1≤r

考慮關(guān)系①和圖1(e)的情形，注意到此時4k+1≤i≤4k+4，得到：

(14)

因此有

(pt,j-pt,l)+(pr,l-pr,i)+(ps,i-ps,j)

≥p4k+3,n-(n-4k-4)·d1+1+(n-4k-5)

·d1-p4k+4,n

=p4k+3,n-p4k+4,n-d1+1

(15)

由式(12)易知

p4k+4,n=p4k+3,n-p4k+3,4k+4+(n-4k-4)

(16)

再由式(13)可得：

p4k+3,4k+4=d4k+3,4k+3

=d4k+1,4k+3+n-4k-2

(17)

將式(16)、式(17)代入式(15)可知其結(jié)果大于0.同理可得，當(dāng)行指數(shù)滿足關(guān)系②、③、④，以及m為任意值時引理4成立.證畢.

根據(jù)引理1～4可得到定理2.

定理2 對于任意列重m、任意行重n，由式(4)～式(8)、式(11)～式(13)定義的基矩陣P的圍長至少為8.

可以發(fā)現(xiàn)，基矩陣P的第4k+1、4k+2(k≥0)行元素均構(gòu)成單增等差數(shù)列；當(dāng)初始值m、n、d1、d2確定后，移位系數(shù)可由數(shù)學(xué)公式計算得到；本文方法參數(shù)設(shè)置靈活，而移位矩陣的維數(shù)p大于移位系數(shù)，故p的取值下界為

infp=max(pi,n)+1,1≤i≤m

(18)

例1 利用本文方法設(shè)計的一種(6,8)基矩陣如式(19)所示：

(19)

4 編碼復(fù)雜度分析

由式(4)易知Ha滿秩，因此H是非奇異的，即可回避生成矩陣G而直接由校驗矩陣進(jìn)行編碼.

采用LU分解法，令信息比特向量為s=[s1s2…sk]，校驗比特向量為p=[p1p2…pm]，編碼器輸出行向量為c，它的長度N=np=(m+k)p，則有

(20)

根據(jù)校驗等式H·cT=0可得：

Ha·pT+Hb·sT=0

(21)

由于運算在GF(2)中進(jìn)行，所以有

(22)

將式(22)展開由第m式可得：

(23)

將式(23)回代到方程組式(22)的第m-1式可得：

(24)

依次類推可得到各個pi，代入到式(20)，編碼完畢.

編碼復(fù)雜度主要關(guān)注編碼過程的運算量、運算復(fù)雜度和編碼所需存儲的參數(shù).運算量即乘法和加法次數(shù)，運算復(fù)雜度即運算量與碼長的變化關(guān)系.QC-LDPC碼的各個子矩陣都是稀疏矩陣，因此按照稀疏矩陣的運算方式可大大減小運算量.現(xiàn)計算pi的運算量如表1所示.

表1 編碼算法的運算量

從表1可明顯地看到，計算各個校驗分向量pi的運算復(fù)雜度為O(N)，即運算復(fù)雜度與碼長呈線性關(guān)系.同時由于該碼采用代數(shù)構(gòu)造法，校驗矩陣中的元素由簡單的數(shù)學(xué)運算得到，只需要存儲一組初始參數(shù)和幾個數(shù)學(xué)表達(dá)式即可，編碼器的實際存儲量需求非常小.

5 仿真與實驗

5.1 最小碼重、碼距分析

一般認(rèn)為碼重小于10的碼為低碼重碼[16]，這類碼的存在使LDPC譯碼器糾錯能力低下.目前尚沒有辦法準(zhǔn)確求出碼字的最小碼重，本文采用文獻(xiàn)[16]給出的搜索算法，即通過生成矩陣的行向量估計LDPC碼的最小碼重和最小碼距的上界.仿真選取4種碼字，基矩陣尺寸分別為(4,8)，(4,12)，(5,10)，(6,12)，初始參數(shù)均為d1=1，d2=2.各碼字碼長及碼重分布情況如圖2所示，計算機搜索得到的最小碼重、最小碼距的上界如表2所示.

表2 最小碼重、最小碼距搜索結(jié)果

仿真結(jié)果表明，(4,8)和(4,12)兩種基矩陣下其最小碼重的上界均為14，這是因為兩種校驗矩陣的列重結(jié)構(gòu)是一樣的，都包含4種列重，而(4,12)中小列重的比例更小，因此碼重為16的行向量所占比重較大；隨著列重的增大，LDPC碼的最小碼重和碼距也增大，因此校驗矩陣使用大的列重可減小產(chǎn)生低碼重碼的可能性.

5.2 性能分析

IEEE 802.11n、802.16e以及DVB-S2標(biāo)準(zhǔn)中均采用準(zhǔn)雙對角線子矩陣實現(xiàn)迭代編碼，與本文設(shè)計的方法類似，故與這3種碼字進(jìn)行性能比較.仿真環(huán)境為加性高斯白噪聲(AWGN)信道，譯碼采用置信傳播(BP)算法，最大迭代次數(shù)為30，調(diào)制方式為BPSK.

實驗1 與IEEE 802.11n、802.16e標(biāo)準(zhǔn)LDPC碼的比較

根據(jù)IEEE 802.11n標(biāo)準(zhǔn)選擇2種參數(shù)的基矩陣：維數(shù)p=27，碼長N=648，碼率R=1/2；維數(shù)p=54，碼長N=1296，碼率R=2/3.利用本文方法構(gòu)造同碼長碼率的2種基矩陣分別為：維數(shù)p=81，d1=5，d2=7；維數(shù)p=108，d1=3，d2=4.仿真結(jié)果如圖3所示.

根據(jù)IEEE 802.16e標(biāo)準(zhǔn)選擇2種參數(shù)的基矩陣：維數(shù)p=24，碼長N=576，碼率R=1/2；維數(shù)p=48，碼長N=1152，碼率R=2/3B類.利用本文方法構(gòu)造同碼長碼率的2種基矩陣分別為：維數(shù)p=72，d1=3，d2=5；維數(shù)p=96，d1=1，d2=2.仿真結(jié)果如圖4所示.

仿真結(jié)果表明，在中短碼條件下，本文構(gòu)造的碼字與IEEE 802.11n、802.16e標(biāo)準(zhǔn)的LDPC碼相比BER性能相一致.從仿真參數(shù)可以看到，本文給出的校驗矩陣的列重顯然比上述兩類標(biāo)準(zhǔn)的要小，即最小碼重更小，然而BER性能卻并未由此下降，說明大圍長特性促進(jìn)了該部分的性能增益，驗證了理論推導(dǎo)的正確性.此外，IEEE 802.11n、802.16e標(biāo)準(zhǔn)的LDPC碼分別只提供了4種和6種基矩陣形式，不同碼率下需要存儲不同的移位系數(shù)，隨著通信技術(shù)的不斷發(fā)展在實際應(yīng)用中難免受到約束.而本文方法可根據(jù)需求靈活地設(shè)置初始參數(shù)，校驗矩陣由數(shù)學(xué)公式自動計算得到，大大節(jié)省了編解碼存儲空間，校驗矩陣形式也更多樣化.

實驗2 與DVB-S2標(biāo)準(zhǔn)LDPC碼的比較

DVB-S2標(biāo)準(zhǔn)中的LDPC碼只有兩種碼長，即使短碼也長達(dá)16200 bit，這對于編解碼器的實現(xiàn)具有較大的難度，故采用文獻(xiàn)[17]中的縮短碼設(shè)計，選擇2種碼率R=1/2的基矩陣，碼長分別為5400和8100.利用本文方法構(gòu)造同碼長碼率的2種基矩陣分別為：維數(shù)p=540，d1=11，d2=13；維數(shù)p=675，d1=16，d2=17；仿真結(jié)果如圖5所示.

仿真結(jié)果表明，DVB-S2標(biāo)準(zhǔn)的LDPC碼比本文構(gòu)造的碼字性能略優(yōu).這是因為該標(biāo)準(zhǔn)下校驗矩陣的最大列重為8，在長碼條件下的性能增益會更凸顯，而本文設(shè)計的碼字在無列重優(yōu)勢的情況下，BER性能已經(jīng)可以與之接近.另外，與IEEE 802.11n、802.16e標(biāo)準(zhǔn)類似，DVB-S2標(biāo)準(zhǔn)針對不同碼率規(guī)定了不同的編碼信息表，同樣可能存在編碼器存儲與應(yīng)用范圍受限等問題.綜上所述，本文構(gòu)造碼字不失為一種好碼.

6 結(jié)論

本文提出了一種構(gòu)造圍長至少為8的(m,n)QC-LDPC碼的確定性方法.該碼的準(zhǔn)循環(huán)基矩陣由數(shù)學(xué)表達(dá)式確定，構(gòu)造方法簡單，節(jié)省了編解碼存儲空間，校驗矩陣可直接進(jìn)行迭代編碼，降低了編碼復(fù)雜度.研究結(jié)果表明，這類碼只需少量的初始值控制就可設(shè)計任意參數(shù)的基矩陣，同時在AWGN信道中能夠獲得較好的糾錯能力，因此對信道編碼理論的研究和應(yīng)用具有一定的參考價值.在此方法基礎(chǔ)上，如何構(gòu)造圍長大于8的QC-LDPC碼是今后深入研究的內(nèi)容之一.

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

[2]Jiang X,Lee M H.Large girth non-binary LDPC codes based on finite fields and Euclidean geometries[J].IEEE Signal Processing Letters,2009,16(6):521-524.

[3]Huang Jen-Fa,Huang Chun-Ming,Yang Chao-Chin.Construction of one-coincidence sequence quasi-cyclic LDPC codes of large girth[J].IEEE Transactions on Information Theory,2012,58(3):1825-1836.

[4]Zhang Guo-hua,Sun Rong,Wang Xin-mei.Construction of girth-eight QC-LDPC codes from greatest common divisor[J].IEEE Communications Letters,2013,17(2):369-372.

[5]Park H,Hong S,NO J S,et al.Design of multiple-edge protographs for QC LDPC codes avoiding short inevitable cycles[J].IEEE Transactions on Information Theory,2013,59(7):4598-4614.

[6]Wang Ju-hua,Zhang Guo-hua,Zhou Quan.Coset-based QC-LDPC codes without small cycles[J].Electronics Letters,2014,50(22):1597-1598.

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

[8]Zhang Fan,Mao Xue-hong,Zhou Wu-yang,et al.Girth-10 LDPC codes based on 3-D cyclic lattices[J].IEEE Transactions on Vehicular Technology,2008,57(2):1049-1060.

[9]Zhang Guo-hua,Sun Rong,Wang Xin-mei.Deterministic construction of girth-eight (3,L) QC-LDPC codes from quadratic function[J].Electronics Letters,2013,49(9):600-602.

[10]張國華,陳超,楊洋，等.Girth-8 (3,L)-規(guī)則QC-LDPC碼的一種確定性構(gòu)造方法[J].電子與信息學(xué)報,2010,32(5):1152-1156.

Zhang Guo-hua,Chen Chao,Yang Yang,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.(in Chinese)

[11]Zhang Guo-hua,Sun Rong,Wang Xin-mei.Several explicit constructions for (3,L) QC-LDPC codes with girth at least eight[J].IEEE Communications Letters,2013,17(9):1822-1825.

[12]張國華,孫蓉,王新梅.圍長至少為8的QC-LDPC碼的新構(gòu)造:一種顯示框架[J].電子學(xué)報,2012,40(2):331-337.

Zhang Guo-hua,Sun Rong,Wang Xin-mei.Novel constructions of QC-LDPC codes with girth at least eight:an explicit framework[J].Acta Electronica Sinica,2012,40(2):331-337.(in Chinese)

[13]Zhang Jian-hua and Zhang Guo-hua.Deterministic girth-eight QC-LDPC codes with large column weight[J].IEEE Communications Letters,2014,18(4):656-659.

[14]鄭健,別紅霞,類春陽,等.優(yōu)化循環(huán)轉(zhuǎn)移矩陣偏移量的QC-LDPC碼構(gòu)造[J].北京郵電大學(xué)學(xué)報,2014,37(1):16-19.

Zheng Jian,Bie Hong-xia,Lei Chun-yang,et al.A construction algorithm with optimized shift value of circulant permutation matrix for QC-LDPC codes[J].Journal of Beijing University of Posts and Telecommunications,2014,37(1):16-19.(in Chinese)

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

[16]肖揚.Turbo與LDPC編解碼及其應(yīng)用[M].北京:人民郵電出版社,2010.

Xiao Yang.Turbo and LDPC Codes and Their Applications[M].Posts & Telecom Press,Beijing,2010.(in Chinese)

[17]肖揚,范俊,黃希.DVB-S2標(biāo)準(zhǔn)的LDPC碼改進(jìn)[J].鐵道學(xué)報,2011,33(2):52-59.

Xiao Yang,FAN Jun,HUANG Xi.Improvement in LDPC codes in DVB-S2 standard[J].Journal of The China Railway Society,2011,33(2):52-59.(in Chinese)

張 軼 男,1986年10月出生，山西太原人.空軍工程大學(xué)信息與導(dǎo)航學(xué)院博士研究生，從事信道編碼理論方面的有關(guān)研究.

E-mail:zhangyi1290@163.com

達(dá)新宇 男,1961年4月出生，陜西眉縣人.教授、博士生導(dǎo)師、國家精品課程《通信原理》負(fù)責(zé)人.1983年、1988年和2007年分別在西安電子科技大學(xué)、空軍地空導(dǎo)彈學(xué)院和西北工業(yè)大學(xué)獲工學(xué)學(xué)士、工學(xué)碩士和工學(xué)博士學(xué)位.現(xiàn)為空軍工程大學(xué)信息與導(dǎo)航學(xué)院教授，主要從事衛(wèi)星通信、信道編碼、認(rèn)知無線電等方面的研究工作.

Deterministic Construction of QC-LDPC Codes for Any Column Weight with a Large Girth

ZHANG Yi,DA Xin-yu,SU Yi-dong

(InformationandNavigationCollege,AirForceEngineeringUniversity,Xi’an,Shaanxi710077,China)

To cope with the issue of determining cyclic shift coefficients of the quasi-cyclic sub-matrix in the Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes,a method was presented based on the arithmetic progression to compute the cyclic shift coefficients.By this method,a class of girth eight QC-LDPC codes for any column weight is obtained,and the cyclic shift coefficients can be expressed in simple analytic expressions to reduce required memory usage.Meanwhile,the encoding complexity is linearly proportional to code length due to the lower triangular parity matrix.The simulation result shows that column weight and girth have important influences on code performance.Furthermore,over an Additive White Gauss Noise (AWGN) channel and under the Belief Propagation (BP) decoding algorithm,the simulation results represent that bit error rate of the proposed QC-LDPC codes is no less than the LDPC codes in IEEE 802.11n and 802.16e with short code length,and is close to the LDPC codes in DVB-S2 with long code length.Moreover,the study result also confirms that the proposed algorithm has high flexibility with respect to the design of code length and rate.

quasi-cyclic low-density parity-check (QC-LDPC) codes;column weight;girth;quasi-cyclic sub-matrix;efficient encoding

2014-12-17;

2015-04-10；責(zé)任編輯：馬蘭英

國家自然科學(xué)基金(No.61271250)

TN911.22

A

0372-2112 (2016)08-1814-06