黃 勝，龐曉磊，賈雪婷，袁建國

?

基于盧卡斯數(shù)列的大圍長QC-LDPC碼構(gòu)造方法

黃 勝，龐曉磊，賈雪婷，袁建國

(重慶郵電大學(xué)光通信與網(wǎng)絡(luò)重點實驗室 重慶 南岸區(qū) 400065)

提出一種基于盧卡斯數(shù)列構(gòu)造圍長至少為8的規(guī)則(,) 盧卡斯QC-LDPC(L-QC-LDPC)碼的方法。該方法構(gòu)造的碼字圍長較大，能夠有效地消除短環(huán)。循環(huán)置換子矩陣維數(shù)值的下界允許連續(xù)取值，且在硬件實現(xiàn)方面可節(jié)省存儲空間，進而降低硬件實現(xiàn)成本以及復(fù)雜度。仿真結(jié)果表明，在碼率為1/2、碼長為1 302和誤碼率為10-6時，L-QC-LDPC碼與OCS-LDPC碼相比，凈編碼增益(NCG)提高了約2 dB，比確定性碼的NCG提高了約0.8 dB；與二次函數(shù)相比，性能略優(yōu)于二次函數(shù)LDPC(QF-LDPC)碼，有約0.1 dB NCG的改善。同時，在相同碼率、相近碼長和誤碼率為10-6時，L-QC-LDPC碼與基于有限域的循環(huán)子集構(gòu)造的QC-LDPC碼相比，提高了約0.5 dB的凈編碼增益。

大圍長; 盧卡斯數(shù)列; 凈編碼增益; 準循環(huán)低密度奇偶校驗碼

人們對通信系統(tǒng)的要求是永無止境的，例如希望通信系統(tǒng)更廉價、更快速、更可靠、不但需要傳輸話音，還需要傳輸數(shù)據(jù)圖像等，這些迫使許多研究者尋找取得接近或最終達到香農(nóng)限的可靠通信的方式。文獻[1]提出低密度奇偶校驗(low density parity check, LDPC)碼，近十幾年來，它在糾錯編碼領(lǐng)域得到了極大的發(fā)展，已經(jīng)成為了Turbo碼的有力競爭者。LDPC碼是最有希望在廣泛的信道范圍下接近香農(nóng)極限的誤差糾正技術(shù)[2]。

根據(jù)LDPC碼校驗矩陣的構(gòu)造方式的不同，編碼的構(gòu)造方法主要分為隨機構(gòu)造和結(jié)構(gòu)化構(gòu)造兩類。隨機構(gòu)造的方法雖然糾錯性能優(yōu)秀，但是由于校驗矩陣的隨機性無法實現(xiàn)簡單編碼，編碼復(fù)雜度高、硬件成本昂貴且不易于實現(xiàn)[3-4]。結(jié)構(gòu)型碼由于其校驗矩陣的準循環(huán)特性使其備受青睞，具有代表性的結(jié)構(gòu)型碼主要是文獻[5-6]提出的一系列基于有限幾何和基于有限域的LDPC碼的構(gòu)造方法。由于LDPC碼不允許存在短環(huán)，否則將使得譯碼器不能快速收斂甚至不能收斂，因此構(gòu)造大圍長的LDPC碼成為編碼學(xué)的研究熱點[7]。文獻[8]提出了一類QC-LDPC碼存在2環(huán)的充要條件，碼字性能非常優(yōu)秀，但缺點是循環(huán)置換矩陣的維數(shù)值下界不能簡單連續(xù)取值。文獻[9]提出當列重為5、6及不小于7的3種情況時，依次利用完全確定的方式構(gòu)造圍長為8的QC-LDPC碼。文獻[10]基于環(huán)約束方程并利用貪婪算法獲得大圍長的OCS-LDPC碼，需要通過計算機搜索獲得。文獻[11]的確定碼和文獻[12]的QF-LDPC碼都是定式構(gòu)造圍長為8的碼字，但是由于列重為3的單一選擇以及碼率受限，導(dǎo)致實際應(yīng)用有很大的局限性。

本文利用盧卡斯數(shù)列(Lucas sequence)的性質(zhì)提出了一種行重為，列重為(≥3)的規(guī)則的盧卡斯QC-LDPC(L-QC-LDPC)碼構(gòu)造方法。這種方法構(gòu)造出來的QC-LDPC碼可以有效地避免短環(huán)，且L-QC-LDPC的圍長至少為8；特別地，該方法構(gòu)造碼的碼型都具有一定的結(jié)構(gòu)特征、計算復(fù)雜度低、易于硬件實現(xiàn)且值的下界允許連續(xù)取值。

1 QC-LDPC碼的通用構(gòu)造方法

QC-LDPC碼的校驗矩陣是由分組矩陣構(gòu)成的，而每個分組的矩陣又是由滿秩的循環(huán)置換矩陣和全0的方陣組合而成。校驗矩陣的列重和行重分別用和表示， QC-LDPC碼的校驗矩陣為：

對應(yīng)的指數(shù)矩陣為：

式中，2≤≤≤；0是′維的單位矩陣；是置換矩陣，通過0右移位得到；指數(shù)矩陣中的(,)(0≤<，0≤<)表示該循環(huán)置換矩陣的移位值。

校驗矩陣含有的環(huán)可以用對應(yīng)的指數(shù)矩陣中的元素表示，QC-LDPC碼中長度為2的環(huán)可以表示為(0,0),(0,1),(1,1), …,(s-1,i-1),(s-1,0),(0,0)。文獻[8]給出了校驗矩陣中存在長度為2的環(huán)的充要條件滿足式(3)，其中，i≠i+1, s≠s+1。構(gòu)造LDPC碼的首要條件就是避免四環(huán)，即(0,0)-(1,0)+(1,1)-(0,1)≠0 mod。因此若要使得設(shè)計的QC-LDPC碼避免存在長度為2的環(huán)，就必須通過一定規(guī)則的設(shè)計使得下式不成立：

2 基于盧卡斯數(shù)列的QC-LDPC碼的構(gòu)造方法

2.1 盧卡斯數(shù)列的定義

定義 1 對于一個整數(shù)數(shù)列()，為正整數(shù)。如果()=(-1)+(-2)，≥3且(1)=2，(2)=1，滿足以上初始條件和遞推關(guān)系的數(shù)列稱為盧卡斯數(shù)列，它的每一項稱為盧卡斯數(shù)。

典型盧卡斯數(shù)列表示如下：2, 1, 3, 4, 7, 11, 18, 39, 57, 96，…。

定理 1 對于一個盧卡斯數(shù)列，若>且，，∈Z+，則有(+)-()>(+)-()[13]。

本文基于盧卡斯數(shù)列中元素的性質(zhì)特征構(gòu)造出一個列重和行重分別為和、圍長至少為8的規(guī)則QC-LDPC碼。

2.2 基于盧卡斯數(shù)列的QC-LDPC碼的構(gòu)造方法

首先構(gòu)造一個指數(shù)矩陣為：

式中，的維數(shù)為′，≥3，>。指數(shù)矩陣的第一行為全0，第二行為集合{()}中的前個元素：(0),(1),…,(-1)；從集合{()}中的第+1個元素開始到第+個元素作為指數(shù)矩陣的第三行：(+1),(+2),…,(+)；…；最后一行的元素為：((-2)(+1)),((-2)(+1)+1),…,((-2)(+1)+-1)，即指數(shù)矩陣中任意元素(,)( 0≤<, 0≤<)，當=0時，(,)=0；當≠0時，(,)=((-1)(+1)+)。然后對指數(shù)矩陣進行填充，中對應(yīng)的元素用′的單位矩陣及其相應(yīng)的循環(huán)移位矩陣替換，其中>((-2)(+1)+-1)；0元素用′的單位矩陣0替換，(s, i)用相應(yīng)的單位矩陣右循環(huán)移位(,)位得到的矩陣(((-1)(+1)+))進行替換，最終構(gòu)成校驗矩陣。

定理 2 只要滿足>((-2)(+1)+-1)，基于盧卡斯數(shù)列構(gòu)造的QC-LDPC碼的校驗矩陣對應(yīng)的Tanner圖的圍長至少為8。

證明：為了證明對應(yīng)的Tanner圖中的環(huán)長為8，要依次證明Tanner圖中沒有四環(huán)和六環(huán)。

對于四環(huán)，由式(3)可知要避免四環(huán)即(0,0)-(1,0)+(1,1)-(0,1) ≠0 mod。為了不失去一般性，假設(shè)0<1,0<1，則有：

(0,1)-(0,0)=((0-1)(+1)+1)-

((0-1)(j+1)+0)

(1,1)-(1,0)=((1-1)(+1)+1)-

((1-1)(+1)+0)

由定理1可得：

(1,1)-(1,0)>(0,1)-(0,0),

0(1,1)-(1,0)+(0,0)-(0,1)<

因此所構(gòu)造的校驗矩陣已經(jīng)有效地避免了四環(huán)的存在。

對于六環(huán)，Tanner圖中存在六環(huán)的可能性有6種形式，如圖1所示。

1) 第一大類

圖1中的形式1的六環(huán)不存在性證明分為兩種情況。

① 當六環(huán)的所在位置的第一行就是校驗矩陣的第一行，即0=0，令t=s-1,1≤<，由式(3)和式(4)可得：

(0,0)-(0,1)+(1,1)-

(1,2)+(2,2)-(2,0)=

0-0+(1(+1)+1)-(1(+1)+2)+

(2(+1)+2)-(2(+1)+0)=

(1(+1)+1)-(1(+1)+2)+

(2(+1)+2)-(2(+1)+0)

由圖1中的第一種形式令0=2-,1=2-且>，原式可以簡化為：

(1(+1)+2-)-(1(+1)+2)+

(2(+1)+2)-(2(+1)+2-)=

{(2(+1)+2)-(2(+1)+2-)}-

{(1(+1)+2)-(1(+1)+2-)} (5)

由定理1可得：(2(+1)+2)-(2(+1)+2-)>(1′(+1)+2)-(1(+1)+2-)。

所以，0<(5)<(2(+1)+2)<即原式≠0 mod。

② 當0≠0時，有：

(0,0)-(0,1)+(1,1)-

(1,2)+(2,2)-(2,0) >

(0,0)-(0,1)+(1,1)-

(1,2)+(1,2)-(1,0) =

(0,0)-(0,1)+(1,1)-

(1,0)>0

(0,0)-(0,1)+(1,1)-

(1,2)+(2,2)-(2,0) <

(2,0)-(0,1)+(1,1)-

(1,2)+(2,2)-(2,0) =

(1,1)-(0,1)+(2,2)-

(1,2)<(1,2)+(2,2)-

(1,2)=(2,2)<

所以利用夾逼準則可知，原式≠0 mod。

2) 第二大類

圖1中的形式5的六環(huán)不存在性證明也分為兩種情況。

① 六環(huán)的所在位置的第一行就是校驗矩陣的第一行，即0=0，令t=s-1,1≤<，由式(3)和式(4)可得：

(0,0)-(0,1)+(2,1)-

(2,2)+(1,2)-(1,0)=

0-0+(2(+1)+1)-(2(+1)+2)+

(1(+1)+2)-(1(+1)+0)=

(2(+1)+1)-(2(+1)+2)+

(1(+1)+2)-(1(+1)+0)

由圖中的第五種形式令0=2-，1=2-且>，原式可以簡化為：

(2(+1)+2-)-(2(+1)+2)+

(1(+1)+2)-(1(+1)+2-)=

{(1(+1)+2)-(1(+1)+2-)}-

{(2(+1)+2)-(2(+1)+2-)} (6)

由定理1可得：

(1(+1)+2)-(1(+1)+2-)<

(2(+1)+2)-(2(+1)+2-)

所以，0>(6)>-(2(+1)+2)，即原式≠0 mod。

② 當0≠0時，有：

(0,0)-(0,1)+(2,1)-

(2,2)+(1,2)-(1,0)<

(1,0)-(1,1)+(2,1)-

(2,2)+(1,2)-(1,0)=

(1,2)-(1,1)+(2,1)-(2,2)<0

(0,0)-(0,1)+(2,1)-

(2,2)+(1,2)-(1,0)>

(0,0)-(0,1)+(2,1)-

(2,2)+(0,2)-(0,0)=

(0,2)-(0,1)+(2,1)-

(2,2)>(2,1)-(2,2)>

-(2,2)>-

所以，利用夾逼準則可知，原式≠0 mod。

綜上所述，圖1中的6種六環(huán)形式是不存在的。因此當>((-2)(+1)+-1)時，構(gòu)造的L-QC-LDPC碼的校驗矩陣對應(yīng)的Tanner圖中沒有四六環(huán)，定理2得證。

通常情況下，QC-LDPC碼為了存儲其校驗矩陣，需要存儲指數(shù)矩陣中的每一個元素值，即使是僅僅存儲每一個元素值，也需要一定的存儲空間，對于編碼器來說，節(jié)省存儲空間就是降低實際應(yīng)用中的成本。而對于盧卡斯數(shù)列，僅需存儲0、(1)和(2)的3個元素，其他元素的值可由簡單的加法和乘法運算得到，這樣很大程度上節(jié)省了系統(tǒng)所需要的存儲空間。

3 性能分析

本文在仿真中采用BPSK調(diào)制，傳輸信道選用AWGN信道，采用BP譯碼算法。首先基于盧卡斯數(shù)列所構(gòu)造的L-QC-LDPC碼指數(shù)矩陣如式(4)所示；然后確定所構(gòu)造的LDPC碼的列重和行重的參數(shù)和，構(gòu)造一個′的指數(shù)矩陣；例如=3，=6，對應(yīng)的指數(shù)矩陣可以表示為(3,6)。將維的全0向量作為指數(shù)矩陣的第一行，前個盧卡斯數(shù)作為指數(shù)矩陣的第二行，第四個到第+3個數(shù)作為指數(shù)矩陣的第三行，即得到指數(shù)矩陣：

通過指數(shù)矩陣確定參數(shù)，上述指數(shù)矩陣的取值范圍為>47，為構(gòu)造碼長1 302的QC-LDPC碼，令=217，指數(shù)矩陣中的0元素擴展為217′217的單位矩陣0，其他元素擴展為相應(yīng)的單位矩陣的右循環(huán)移位。圖2給出了所構(gòu)造的碼字在BP譯碼中不同迭代次數(shù)下的誤碼性能，由圖2可見，在BER為10-5時，迭代次數(shù)為10、20、30、40和50時所需的SNR分別為：3.81、3.60、3.48、3.45和3.43 dB，距香農(nóng)限分別為：3.623、3.413、3.293、3.263和3.243 dB。在SNR=4.0 dB的情況下，所對應(yīng)的BER分別約為：3.277′10-6、7.424′10-7、3.84′10-7、3.064′10-7和2.569′10-7。通過以上分析可以得出，隨著迭代次數(shù)的增加，糾錯性能越來越好，但NCG提高幅度卻越來越小。迭代過程其實是節(jié)點信息更新的一個過程，變量節(jié)點譯碼器將附加的信息傳送給校驗節(jié)點譯碼器，然后校驗節(jié)點譯碼器將更新的信息傳送給變量節(jié)點譯碼器，如此迭代，最終完成整個譯碼過程。但是當每個譯碼器信息更新到一定量后，每次迭代后再轉(zhuǎn)化的信息很少，對結(jié)果影響不大，甚至有可能沒有需要再轉(zhuǎn)化的信息。通過仿真分析可以看出，譯碼迭代30次與50次時與香農(nóng)限僅僅相差0.05 dB左右，非常接近，而譯碼迭代50次時時間復(fù)雜度和運算量都較高。因此，需要在復(fù)雜度和糾錯性能之間找到一個折衷點，所以選擇迭代30次。

為充分說明(1 302，651)L-QC-LDPC碼的糾錯性能，在相同條件下不同碼字仿真結(jié)果如圖3所示。由圖3可知，在誤碼率為10-6時，在相同的碼長、1/2碼率的條件下，所構(gòu)造的L-QC-LDPC碼與其他算法構(gòu)造的碼相比，均有不同程度的性能提升，如表1所示。從表中可以看出，L-QC-LDPC碼與文獻[10]的OCS-LDPC碼相比，可獲得約2 dB的凈編碼增益，與文獻[11]的確定性碼及文獻[12]的QF-LDPC碼相比，分別有約0.8 dB和0.1 dB凈編碼增益的改善。在相近碼長、相同行列重和碼率的情況下，所提出的碼字與文獻[7]中基于有限域的循環(huán)子集的QC- LDPC碼相比，提高了約0.5 dB的凈編碼增益的改善。同時可以從表中看出，本文提出的碼最接近香農(nóng)限。

表1 不同對比算法所構(gòu)造的碼與香農(nóng)限的距離及 和L-QC-LDPC碼相比獲得的凈編碼增益

4 結(jié) 束 語

本文提出一種基于盧卡斯數(shù)列構(gòu)造圍長至少為8的規(guī)則L-QC-LDPC碼的確定性方法。當>((-2)(+1)+-1)時，這類碼字可以有效地避免四六環(huán)。仿真結(jié)果表明，在同等條件下，L-QC-LDPC碼的性能明顯優(yōu)于OCS-LDPC碼和確定性碼，略優(yōu)于QF-LDPC碼。與OCS-LDPC碼相比，其構(gòu)造簡單，不需要借助計算機搜索或者計算，雖然確定性碼和QF-LDPC碼都是定式構(gòu)造—給定校驗矩陣的顯式表達式，但是它們的列重受限。除此之外，對于編碼器而言，基于盧卡斯數(shù)列的碼字只需要存儲3個元素：0、(1)和(2)，其他元素的值可以通過簡單的加法和乘法運算得到，可以有效地節(jié)約系統(tǒng)所需要的存儲空間，進而降低硬件實現(xiàn)成本和復(fù)雜度。

[1] GALLAGER R. Low-density parity-check codes[J]. IRE Transactions on Information Theory, 1962, 8(1): 21-28.

[2] MACKAY D J C, NEAL R M. Near Shannon limit performance of low density parity check codes[J]. Electronics letters, 1996, 32(18): 1645.

[3] MACKAY D J C. Good error-correcting codes based on very sparse matrices[J]. IEEE Transactions on Information Theory, 1999, 45(2): 399-431.

[4] ASVADI R, BANIHASHEMI A H. A rate-compatible puncturing scheme for finite-length LDPC codes[J]. IEEE Communications Letters, 2013, 17(1): 147-150.

[5] TANG H, XU J, LIN S, et al. Codes on finite geometries[J]. IEEE Transactions on Information Theory, 2005, 51(2): 572-596.

[6] HAN G, GUAN Y, KONG L. Construction of irregular QC-LDPC codes via masking with ACE optimization[J]. IEEE Communications Letters, 2014, 18(2): 348-351.

[7] ZHANG L, LIN S, ABDEL-GHAFFAR K, et al. Quasi-cyclic LDPC codes on cyclic subgroups of finite fields[J]. IEEE Transactions on Communications, 2011, 59(9): 2330-2336.

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

[9] ZHANG J, ZHANG G. Deterministic girth-eight QC-LDPC codes with large column weight[J]. IEEE Communications Letters, 2014,18(4): 656-659.

[10] HUANG J F, HUANG C M, YANG C C. Construction of one-coincidence sequence quasi-cyclic LDPC codes of large girth[J]. IEEE Transactions on Information Theory, 2012, 58(3): 1825-1836.

[11] 張國華, 陳超, 楊洋, 等. 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.

[12] ZHANG G, SUN R, WANG X. Deterministic construction of girth-eight (3,L) QC-LDPC codes from quadratic function[J]. Electronics Letters, 2013, 49(9): 600-602.

[13] FU Cheng-hua, LI Xiu-li. Construction of QC-LDPC codes on combinatorial sequences[C]//2013 Fifth International Conference on Intelligent Human-Machine Systems and Cybernetics. [S.l.]: IEEE, 2013(2): 74-78.

編 輯 黃 莘

Construction Method of Large Girth QC-LDPC Codes Based on Lucas Sequences

HUANG Sheng, PANG Xiao-lei, JIA Xue-ting, and YUAN Jian-guo

(Key Labaratory of Optical Communication and Network, Chongqing University of Posts and Telecommunications Nan’an Chongqing 400065)

This paper proposes a construction method of regular (,) Lucas quasi-cyclic low-density parity-check (L-QC-LDPC) codes with girth at least eight based on the Lucas sequence. By this method, the girth of L-QC-LDPC codes is large, which can effectively eliminate short cycles. Besides, lower bound of circulant permutation submatrix dimensionis allowed continuous values. In addition, it can save the storage space in terms of hardware implementation which reduces the cost and complexity of hardware realization correspondingly. Simulation results show that the L-QC-LDPC codes have net coding gain (NCG) of about 2dB and 0.8dB compared with one-coincidence sequence quasi-cyclic LDPC (OCS-LDPC) codes and deterministic codes, respectively, at code rate of 1/2, code length of 1302 and bit error rate (BER) of 10-6. At the same condition, the performance of L-QC-LDPC codes is slightly better than that of the quadratic function LDPC (QF-LDPC) codes, which has an NCG improvement of around 0.1dB. Meanwhile, at code rate of 1/2, similar code length and BER of 10-6, the NCG of L-QC-LDPC codes outweigh about 0.5dB compared with that of QC-LDPC codes based on cyclic subgroups of finite fields.

large girth; Lucas sequence; net code gain(NCG); quasi-cyclic low-density parity-check code

TN911.22

A

10.3969/j.issn.1001-0548.2016.03.003

2014 - 11 - 28；

2015 - 10 - 16

國家自然科學(xué)基金(61371096, 61171158，61275077)；重慶市自然科學(xué)基金(cstc2013jcyjA40052，cstc2012jjA40060)；重慶市教委科學(xué)技術(shù)研究項目(KJ130515)

黃勝(1974 -)，男，博士，教授，主要從事光纖通信系統(tǒng)、信道編碼和未來網(wǎng)絡(luò)等方面的研究.