基于盧卡斯數列的大圍長QC-LDPC碼構造方法

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

?

基于盧卡斯數列的大圍長QC-LDPC碼構造方法

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

(重慶郵電大學光通信與網絡重點實驗室 重慶 南岸區 400065)

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

大圍長; 盧卡斯數列; 凈編碼增益; 準循環低密度奇偶校驗碼

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

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

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

1 QC-LDPC碼的通用構造方法

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

對應的指數矩陣為：

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

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

2 基于盧卡斯數列的QC-LDPC碼的構造方法

2.1 盧卡斯數列的定義

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

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

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

本文基于盧卡斯數列中元素的性質特征構造出一個列重和行重分別為和、圍長至少為8的規則QC-LDPC碼。

2.2 基于盧卡斯數列的QC-LDPC碼的構造方法

首先構造一個指數矩陣為：

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

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

證明：為了證明對應的Tanner圖中的環長為8，要依次證明Tanner圖中沒有四環和六環。

對于四環，由式(3)可知要避免四環即(0,0)-(1,0)+(1,1)-(0,1) ≠0 mod。為了不失去一般性，假設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)<

因此所構造的校驗矩陣已經有效地避免了四環的存在。

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

1) 第一大類

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

① 當六環的所在位置的第一行就是校驗矩陣的第一行，即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的六環不存在性證明也分為兩種情況。

① 六環的所在位置的第一行就是校驗矩陣的第一行，即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種六環形式是不存在的。因此當>((-2)(+1)+-1)時，構造的L-QC-LDPC碼的校驗矩陣對應的Tanner圖中沒有四六環，定理2得證。

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

3 性能分析

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

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

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

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

4 結 束 語

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

[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)-規則 QC-LDPC 碼的一種確定性構造方法[J]. 電子與信息學報, 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

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

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