黃 勝,龐曉磊,賈雪婷,袁建國(guó)
?
基于盧卡斯數(shù)列的大圍長(zhǎng)QC-LDPC碼構(gòu)造方法
黃 勝,龐曉磊,賈雪婷,袁建國(guó)
(重慶郵電大學(xué)光通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室 重慶 南岸區(qū) 400065)
提出一種基于盧卡斯數(shù)列構(gòu)造圍長(zhǎng)至少為8的規(guī)則(,) 盧卡斯QC-LDPC(L-QC-LDPC)碼的方法。該方法構(gòu)造的碼字圍長(zhǎng)較大,能夠有效地消除短環(huán)。循環(huán)置換子矩陣維數(shù)值的下界允許連續(xù)取值,且在硬件實(shí)現(xiàn)方面可節(jié)省存儲(chǔ)空間,進(jìn)而降低硬件實(shí)現(xiàn)成本以及復(fù)雜度。仿真結(jié)果表明,在碼率為1/2、碼長(zhǎng)為1 302和誤碼率為10-6時(shí),L-QC-LDPC碼與OCS-LDPC碼相比,凈編碼增益(NCG)提高了約2 dB,比確定性碼的NCG提高了約0.8 dB;與二次函數(shù)相比,性能略優(yōu)于二次函數(shù)LDPC(QF-LDPC)碼,有約0.1 dB NCG的改善。同時(shí),在相同碼率、相近碼長(zhǎng)和誤碼率為10-6時(shí),L-QC-LDPC碼與基于有限域的循環(huán)子集構(gòu)造的QC-LDPC碼相比,提高了約0.5 dB的凈編碼增益。
大圍長(zhǎng); 盧卡斯數(shù)列; 凈編碼增益; 準(zhǔn)循環(huán)低密度奇偶校驗(yàn)碼
人們對(duì)通信系統(tǒng)的要求是永無(wú)止境的,例如希望通信系統(tǒng)更廉價(jià)、更快速、更可靠、不但需要傳輸話音,還需要傳輸數(shù)據(jù)圖像等,這些迫使許多研究者尋找取得接近或最終達(dá)到香農(nóng)限的可靠通信的方式。文獻(xiàn)[1]提出低密度奇偶校驗(yàn)(low density parity check, LDPC)碼,近十幾年來(lái),它在糾錯(cuò)編碼領(lǐng)域得到了極大的發(fā)展,已經(jīng)成為了Turbo碼的有力競(jìng)爭(zhēng)者。LDPC碼是最有希望在廣泛的信道范圍下接近香農(nóng)極限的誤差糾正技術(shù)[2]。
根據(jù)LDPC碼校驗(yàn)矩陣的構(gòu)造方式的不同,編碼的構(gòu)造方法主要分為隨機(jī)構(gòu)造和結(jié)構(gòu)化構(gòu)造兩類。隨機(jī)構(gòu)造的方法雖然糾錯(cuò)性能優(yōu)秀,但是由于校驗(yàn)矩陣的隨機(jī)性無(wú)法實(shí)現(xiàn)簡(jiǎn)單編碼,編碼復(fù)雜度高、硬件成本昂貴且不易于實(shí)現(xiàn)[3-4]。結(jié)構(gòu)型碼由于其校驗(yàn)矩陣的準(zhǔn)循環(huán)特性使其備受青睞,具有代表性的結(jié)構(gòu)型碼主要是文獻(xiàn)[5-6]提出的一系列基于有限幾何和基于有限域的LDPC碼的構(gòu)造方法。由于LDPC碼不允許存在短環(huán),否則將使得譯碼器不能快速收斂甚至不能收斂,因此構(gòu)造大圍長(zhǎng)的LDPC碼成為編碼學(xué)的研究熱點(diǎn)[7]。文獻(xiàn)[8]提出了一類QC-LDPC碼存在2環(huán)的充要條件,碼字性能非常優(yōu)秀,但缺點(diǎn)是循環(huán)置換矩陣的維數(shù)值下界不能簡(jiǎn)單連續(xù)取值。文獻(xiàn)[9]提出當(dāng)列重為5、6及不小于7的3種情況時(shí),依次利用完全確定的方式構(gòu)造圍長(zhǎng)為8的QC-LDPC碼。文獻(xiàn)[10]基于環(huán)約束方程并利用貪婪算法獲得大圍長(zhǎng)的OCS-LDPC碼,需要通過(guò)計(jì)算機(jī)搜索獲得。文獻(xiàn)[11]的確定碼和文獻(xiàn)[12]的QF-LDPC碼都是定式構(gòu)造圍長(zhǎng)為8的碼字,但是由于列重為3的單一選擇以及碼率受限,導(dǎo)致實(shí)際應(yīng)用有很大的局限性。
本文利用盧卡斯數(shù)列(Lucas sequence)的性質(zhì)提出了一種行重為,列重為(≥3)的規(guī)則的盧卡斯QC-LDPC(L-QC-LDPC)碼構(gòu)造方法。這種方法構(gòu)造出來(lái)的QC-LDPC碼可以有效地避免短環(huán),且L-QC-LDPC的圍長(zhǎng)至少為8;特別地,該方法構(gòu)造碼的碼型都具有一定的結(jié)構(gòu)特征、計(jì)算復(fù)雜度低、易于硬件實(shí)現(xiàn)且值的下界允許連續(xù)取值。
QC-LDPC碼的校驗(yàn)矩陣是由分組矩陣構(gòu)成的,而每個(gè)分組的矩陣又是由滿秩的循環(huán)置換矩陣和全0的方陣組合而成。校驗(yàn)矩陣的列重和行重分別用和表示, QC-LDPC碼的校驗(yàn)矩陣為:
對(duì)應(yīng)的指數(shù)矩陣為:
式中,2≤≤≤;0是′維的單位矩陣;是置換矩陣,通過(guò)0右移位得到;指數(shù)矩陣中的(,)(0≤<,0≤<)表示該循環(huán)置換矩陣的移位值。
校驗(yàn)矩陣含有的環(huán)可以用對(duì)應(yīng)的指數(shù)矩陣中的元素表示,QC-LDPC碼中長(zhǎng)度為2的環(huán)可以表示為(0,0),(0,1),(1,1), …,(s-1,i-1),(s-1,0),(0,0)。文獻(xiàn)[8]給出了校驗(yàn)矩陣中存在長(zhǎng)度為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è)計(jì)的QC-LDPC碼避免存在長(zhǎng)度為2的環(huán),就必須通過(guò)一定規(guī)則的設(shè)計(jì)使得下式不成立:
定義 1 對(duì)于一個(gè)整數(shù)數(shù)列(),為正整數(shù)。如果()=(-1)+(-2),≥3且(1)=2,(2)=1,滿足以上初始條件和遞推關(guān)系的數(shù)列稱為盧卡斯數(shù)列,它的每一項(xiàng)稱為盧卡斯數(shù)。
典型盧卡斯數(shù)列表示如下:2, 1, 3, 4, 7, 11, 18, 39, 57, 96,…。
定理 1 對(duì)于一個(gè)盧卡斯數(shù)列,若>且,,∈Z+,則有(+)-()>(+)-()[13]。
本文基于盧卡斯數(shù)列中元素的性質(zhì)特征構(gòu)造出一個(gè)列重和行重分別為和、圍長(zhǎng)至少為8的規(guī)則QC-LDPC碼。
首先構(gòu)造一個(gè)指數(shù)矩陣為:
式中,的維數(shù)為′,≥3,>。指數(shù)矩陣的第一行為全0,第二行為集合{()}中的前個(gè)元素:(0),(1),…,(-1);從集合{()}中的第+1個(gè)元素開(kāi)始到第+個(gè)元素作為指數(shù)矩陣的第三行:(+1),(+2),…,(+);…;最后一行的元素為:((-2)(+1)),((-2)(+1)+1),…,((-2)(+1)+-1),即指數(shù)矩陣中任意元素(,)( 0≤<, 0≤<),當(dāng)=0時(shí),(,)=0;當(dāng)≠0時(shí),(,)=((-1)(+1)+)。然后對(duì)指數(shù)矩陣進(jìn)行填充,中對(duì)應(yīng)的元素用′的單位矩陣及其相應(yīng)的循環(huán)移位矩陣替換,其中>((-2)(+1)+-1);0元素用′的單位矩陣0替換,(s, i)用相應(yīng)的單位矩陣右循環(huán)移位(,)位得到的矩陣(((-1)(+1)+))進(jìn)行替換,最終構(gòu)成校驗(yàn)矩陣。
定理 2 只要滿足>((-2)(+1)+-1),基于盧卡斯數(shù)列構(gòu)造的QC-LDPC碼的校驗(yàn)矩陣對(duì)應(yīng)的Tanner圖的圍長(zhǎng)至少為8。
證明:為了證明對(duì)應(yīng)的Tanner圖中的環(huán)長(zhǎng)為8,要依次證明Tanner圖中沒(méi)有四環(huán)和六環(huán)。
對(duì)于四環(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)造的校驗(yàn)矩陣已經(jīng)有效地避免了四環(huán)的存在。
對(duì)于六環(huán),Tanner圖中存在六環(huán)的可能性有6種形式,如圖1所示。
1) 第一大類
圖1中的形式1的六環(huán)不存在性證明分為兩種情況。
① 當(dāng)六環(huán)的所在位置的第一行就是校驗(yà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-且>,原式可以簡(jiǎn)化為:
(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。
② 當(dāng)0≠0時(shí),有:
(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)<
所以利用夾逼準(zhǔn)則可知,原式≠0 mod。
2) 第二大類
圖1中的形式5的六環(huán)不存在性證明也分為兩種情況。
① 六環(huán)的所在位置的第一行就是校驗(yà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-且>,原式可以簡(jiǎn)化為:
(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。
② 當(dāng)0≠0時(shí),有:
(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)>-
所以,利用夾逼準(zhǔn)則可知,原式≠0 mod。
綜上所述,圖1中的6種六環(huán)形式是不存在的。因此當(dāng)>((-2)(+1)+-1)時(shí),構(gòu)造的L-QC-LDPC碼的校驗(yàn)矩陣對(duì)應(yīng)的Tanner圖中沒(méi)有四六環(huán),定理2得證。
通常情況下,QC-LDPC碼為了存儲(chǔ)其校驗(yàn)矩陣,需要存儲(chǔ)指數(shù)矩陣中的每一個(gè)元素值,即使是僅僅存儲(chǔ)每一個(gè)元素值,也需要一定的存儲(chǔ)空間,對(duì)于編碼器來(lái)說(shuō),節(jié)省存儲(chǔ)空間就是降低實(shí)際應(yīng)用中的成本。而對(duì)于盧卡斯數(shù)列,僅需存儲(chǔ)0、(1)和(2)的3個(gè)元素,其他元素的值可由簡(jiǎn)單的加法和乘法運(yùn)算得到,這樣很大程度上節(jié)省了系統(tǒng)所需要的存儲(chǔ)空間。
本文在仿真中采用BPSK調(diào)制,傳輸信道選用AWGN信道,采用BP譯碼算法。首先基于盧卡斯數(shù)列所構(gòu)造的L-QC-LDPC碼指數(shù)矩陣如式(4)所示;然后確定所構(gòu)造的LDPC碼的列重和行重的參數(shù)和,構(gòu)造一個(gè)′的指數(shù)矩陣;例如=3,=6,對(duì)應(yīng)的指數(shù)矩陣可以表示為(3,6)。將維的全0向量作為指數(shù)矩陣的第一行,前個(gè)盧卡斯數(shù)作為指數(shù)矩陣的第二行,第四個(gè)到第+3個(gè)數(shù)作為指數(shù)矩陣的第三行,即得到指數(shù)矩陣:
通過(guò)指數(shù)矩陣確定參數(shù),上述指數(shù)矩陣的取值范圍為>47,為構(gòu)造碼長(zhǎng)1 302的QC-LDPC碼,令=217,指數(shù)矩陣中的0元素?cái)U(kuò)展為217′217的單位矩陣0,其他元素?cái)U(kuò)展為相應(yīng)的單位矩陣的右循環(huán)移位。圖2給出了所構(gòu)造的碼字在BP譯碼中不同迭代次數(shù)下的誤碼性能,由圖2可見(jiàn),在BER為10-5時(shí),迭代次數(shù)為10、20、30、40和50時(shí)所需的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的情況下,所對(duì)應(yīng)的BER分別約為:3.277′10-6、7.424′10-7、3.84′10-7、3.064′10-7和2.569′10-7。通過(guò)以上分析可以得出,隨著迭代次數(shù)的增加,糾錯(cuò)性能越來(lái)越好,但NCG提高幅度卻越來(lái)越小。迭代過(guò)程其實(shí)是節(jié)點(diǎn)信息更新的一個(gè)過(guò)程,變量節(jié)點(diǎn)譯碼器將附加的信息傳送給校驗(yàn)節(jié)點(diǎn)譯碼器,然后校驗(yàn)節(jié)點(diǎn)譯碼器將更新的信息傳送給變量節(jié)點(diǎn)譯碼器,如此迭代,最終完成整個(gè)譯碼過(guò)程。但是當(dāng)每個(gè)譯碼器信息更新到一定量后,每次迭代后再轉(zhuǎn)化的信息很少,對(duì)結(jié)果影響不大,甚至有可能沒(méi)有需要再轉(zhuǎn)化的信息。通過(guò)仿真分析可以看出,譯碼迭代30次與50次時(shí)與香農(nóng)限僅僅相差0.05 dB左右,非常接近,而譯碼迭代50次時(shí)時(shí)間復(fù)雜度和運(yùn)算量都較高。因此,需要在復(fù)雜度和糾錯(cuò)性能之間找到一個(gè)折衷點(diǎn),所以選擇迭代30次。
為充分說(shuō)明(1 302,651)L-QC-LDPC碼的糾錯(cuò)性能,在相同條件下不同碼字仿真結(jié)果如圖3所示。由圖3可知,在誤碼率為10-6時(shí),在相同的碼長(zhǎng)、1/2碼率的條件下,所構(gòu)造的L-QC-LDPC碼與其他算法構(gòu)造的碼相比,均有不同程度的性能提升,如表1所示。從表中可以看出,L-QC-LDPC碼與文獻(xiàn)[10]的OCS-LDPC碼相比,可獲得約2 dB的凈編碼增益,與文獻(xiàn)[11]的確定性碼及文獻(xiàn)[12]的QF-LDPC碼相比,分別有約0.8 dB和0.1 dB凈編碼增益的改善。在相近碼長(zhǎng)、相同行列重和碼率的情況下,所提出的碼字與文獻(xiàn)[7]中基于有限域的循環(huán)子集的QC- LDPC碼相比,提高了約0.5 dB的凈編碼增益的改善。同時(shí)可以從表中看出,本文提出的碼最接近香農(nóng)限。
表1 不同對(duì)比算法所構(gòu)造的碼與香農(nóng)限的距離及 和L-QC-LDPC碼相比獲得的凈編碼增益
4 結(jié) 束 語(yǔ)
本文提出一種基于盧卡斯數(shù)列構(gòu)造圍長(zhǎng)至少為8的規(guī)則L-QC-LDPC碼的確定性方法。當(dāng)>((-2)(+1)+-1)時(shí),這類碼字可以有效地避免四六環(huán)。仿真結(jié)果表明,在同等條件下,L-QC-LDPC碼的性能明顯優(yōu)于OCS-LDPC碼和確定性碼,略優(yōu)于QF-LDPC碼。與OCS-LDPC碼相比,其構(gòu)造簡(jiǎn)單,不需要借助計(jì)算機(jī)搜索或者計(jì)算,雖然確定性碼和QF-LDPC碼都是定式構(gòu)造—給定校驗(yàn)矩陣的顯式表達(dá)式,但是它們的列重受限。除此之外,對(duì)于編碼器而言,基于盧卡斯數(shù)列的碼字只需要存儲(chǔ)3個(gè)元素:0、(1)和(2),其他元素的值可以通過(guò)簡(jiǎn)單的加法和乘法運(yùn)算得到,可以有效地節(jié)約系統(tǒng)所需要的存儲(chǔ)空間,進(jìn)而降低硬件實(shí)現(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] 張國(guó)華, 陳超, 楊洋, 等. Girth-8 (3,L)-規(guī)則 QC-LDPC 碼的一種確定性構(gòu)造方法[J]. 電子與信息學(xué)報(bào), 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
國(guó)家自然科學(xué)基金(61371096, 61171158,61275077);重慶市自然科學(xué)基金(cstc2013jcyjA40052,cstc2012jjA40060);重慶市教委科學(xué)技術(shù)研究項(xiàng)目(KJ130515)
黃勝(1974 -),男,博士,教授,主要從事光纖通信系統(tǒng)、信道編碼和未來(lái)網(wǎng)絡(luò)等方面的研究.