基于圍長約束與EMD的低錯誤平層LDPC碼構(gòu)造方法

袁建國，王宏森，張希瑞，范福卓，袁 夢

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

0 引 言

隨著通信技術(shù)的日益發(fā)展，人們對通信可靠性的要求越來越高，而在實際的通信系統(tǒng)中，一定會存在干擾，所以需要使用信道編碼技術(shù)提升通信系統(tǒng)的可靠性。1962年，Gallager發(fā)現(xiàn)了低密度奇偶校驗(low-density parity-check, LDPC)碼。LDPC碼是一種能發(fā)現(xiàn)并糾正誤碼的信道編碼技術(shù)，并且其糾錯性能接近香農(nóng)限[1-3]，因而受到廣大研究者的關(guān)注，并且應(yīng)用于無線通信，深空通信，數(shù)字水印技術(shù)，快速數(shù)據(jù)存儲系統(tǒng)，超高速光纖傳輸?shù)确矫鎇4]，其實際意義和經(jīng)濟(jì)價值很大。目前，LDPC碼也已經(jīng)成為了5G編碼方案的標(biāo)準(zhǔn)碼之一。

LDPC碼的錯誤平層問題是指在一定的高信噪比區(qū)域，誤碼率性能曲線的斜率突然減小甚至接近于0的現(xiàn)象。近年來，為了使LDPC碼具有更好的糾錯性能，許多研究者提出了一系列降低錯誤平層的方法。文獻(xiàn)[5]提出了一種采用算術(shù)約束和小陷阱集約束的斜率序列來構(gòu)造(3,k)LDPC碼的方法，該方法構(gòu)造出的LDPC碼中不存在(5,3)，(7,3)，(6,2)和(8,2)陷阱集，降低了錯誤平層。文獻(xiàn)[6]提出了在Tanner圖中利用圖覆蓋消除校驗矩陣中的陷阱集的方法。文獻(xiàn)[7]提出了一種利用數(shù)列分割移位的方法來減少Tanner圖中陷阱集的個數(shù)，從而達(dá)到降低錯誤平層的效果。文獻(xiàn)[8]提出以平均圍長為約束條件，逐列構(gòu)造校驗矩陣，以局部優(yōu)化平均圍長為目的構(gòu)造LDPC碼，使得LDPC碼具有更低的錯誤平層，但是這種方法構(gòu)造出的LDPC碼中會存在一些連通性差的環(huán)，這同樣也會影響碼字的糾錯性能。

針對LDPC碼中的錯誤平層問題，本文將圍長約束與額外信息度(extrinsic message degree, EMD)算法結(jié)合起來，提出了一種基于圍長約束和EMD的低錯誤平層LDPC碼構(gòu)造方法。在該方法中，首先將圍長約束與漸進(jìn)邊增長(progressive edge growth, PEG)算法進(jìn)行結(jié)合，然后提升構(gòu)成環(huán)的變量節(jié)點的EMD值，最后通過添加一個校驗節(jié)點對校驗矩陣中的環(huán)的連通性進(jìn)一步提升，得到最終的校驗矩陣H。仿真結(jié)果表明，利用本文提出的方法構(gòu)造的LDPC碼型，有效改善了在高信噪比區(qū)域的錯誤平層現(xiàn)象。

1 PEG算法簡介

PEG算法是一種經(jīng)典的隨機構(gòu)造方法[9]。該算法是在滿足所需度分布的情況下，通過逐個添加校驗矩陣中變量節(jié)點和校驗節(jié)點之間的邊，使得變量節(jié)點的局部圍長最大，由此來構(gòu)造出奇偶校驗矩陣對應(yīng)的Tanner圖。在構(gòu)造校驗矩陣的過程中，設(shè)置合適的校驗矩陣大小，以便靈活調(diào)整LDPC碼的碼長碼率，再根據(jù)密度進(jìn)化算法來選取合適的度分布，從而使構(gòu)造出的LDPC碼具有良好的糾錯性能。其中，校驗矩陣中各個節(jié)點的度分布定義為

(1)

(1)式中:dv表示所有校驗節(jié)點與某一變量節(jié)點連接邊數(shù)的最大值，即最大列重；dc表示所有變量節(jié)點與某一校驗節(jié)點連接邊數(shù)的最大值，即最大行重；λi表示校驗節(jié)點與所有度為i的變量節(jié)點之間連接邊數(shù)占Tanner圖中總邊數(shù)的百分比；ρi表示變量節(jié)點與所有度為i的校驗節(jié)點之間連接邊數(shù)占總邊數(shù)的百分比。雖然PEG構(gòu)造在添加新的邊時能夠保證當(dāng)前邊所在環(huán)的環(huán)長盡可能大，但是這僅僅是從局部進(jìn)行考慮的，并不能從全局角度去優(yōu)化校驗矩陣中存在的環(huán)，這會導(dǎo)致校驗矩陣中環(huán)結(jié)構(gòu)比較復(fù)雜，特別是在碼長較長情況下，各個環(huán)之間會存在大量的公共節(jié)點[10]，又因為環(huán)是在譯碼過程中重要的信息傳遞路徑，所以會在一定程度上降低迭代譯碼的性能。

2 基于圍長約束與EMD的低錯誤平層LDPC碼構(gòu)造

2.1 LDPC碼中圍長的約束

本文將Tanner圖中變量節(jié)點記為VN，校驗節(jié)點記為CN。從任意VN出發(fā)，依次經(jīng)過CN和VN，最后回到出發(fā)節(jié)點的路徑稱為環(huán)。記經(jīng)過不同變量節(jié)點數(shù)量為d，則環(huán)長為l=2d。Tanner圖中最短的環(huán)長叫作圍長。通過一個變量節(jié)點的最短環(huán)長度稱為變量節(jié)點的局部圍長，校驗矩陣的平均圍長(girth average, GA)定義為[11]

(2)

(2)式中：k為第i個變量節(jié)點的局部圍長的一半；lmax為所有變量節(jié)點的最大圍長；gi(l)為局部圍長為l的變量節(jié)點占總變量節(jié)點的百分比。

以PEG算法為框架，逐列進(jìn)行校驗矩陣的構(gòu)造：首先，根據(jù)密度進(jìn)化理論選取合適的變量節(jié)點度分布；然后，計算出各個度對應(yīng)的變量節(jié)點個數(shù)，并根據(jù)各變量節(jié)點的度大小依次排列；最后，在構(gòu)造各列矢量時，按照各個約束條件進(jìn)行構(gòu)造。在文獻(xiàn)[8]中，其構(gòu)造規(guī)則歸納如下。

步驟1設(shè)置校驗矩陣的大小為(m,n)，變量節(jié)點序號為i，且i=1,2,…,n，初始化i=n。

步驟2記循環(huán)生成第i個變量節(jié)點的次數(shù)為N，初始化N=0。

步驟3在符合設(shè)定度分布的條件下，隨機生成第i個變量節(jié)點對應(yīng)的列向量。

步驟4若i-n+1≤m，判斷新生成的列向量是否與之前生成的列向量線性無關(guān)，若線性無關(guān)，執(zhí)行步驟5，否則執(zhí)行步驟3。

步驟5令N=N+1，利用(2)式計算當(dāng)前節(jié)點的平均圍長，并與之前記錄的最大平均圍長進(jìn)行比較，并記錄下較大值。

步驟6若N=C，令i=i-1，執(zhí)行步驟7，否則執(zhí)行步驟3。

步驟7若i=0，算法結(jié)束，否則執(zhí)行步驟2。

該算法對于每個變量節(jié)點都構(gòu)造了C個列矢量，對C的選取是一個比較困難的問題，若C過大，則算法復(fù)雜度會較高；若C過小，則構(gòu)造出的LDPC碼的局部圍長也會較小。并且以這種方法構(gòu)造出的LDPC碼會存在環(huán)的連通性較差的情況。因而本文將對此算法予以改進(jìn)。

2.2 提升校驗矩陣中環(huán)的連通性

在LDPC碼的迭代譯碼過程中，環(huán)作為消息傳遞的路徑，對碼字的糾錯性能起著至關(guān)重要的作用。連通性差的環(huán)對LDPC碼的迭代譯碼性能影響非常大，因而本文從增大環(huán)的連通性角度，提出一種降低LDPC碼錯誤平層的改進(jìn)構(gòu)造方法。

環(huán)的連通性通?？捎肊MD或者近似環(huán)額外信息度(approximate extrinsic message degree, ACE)[12]來表示。對于額外信息度，有如下定理。

定理1對于變量節(jié)點集合L，如果存在僅與集合L只連接一次的校驗節(jié)點，那么該校驗節(jié)點稱為集合L的外節(jié)點。集合L的外節(jié)點個數(shù)稱為變量節(jié)點集合L的EMD值[13]。

ACE值是針對構(gòu)成環(huán)的變量節(jié)點集合EMD值的近似計算，且ACE值是EMD值的上限值。所以用ACE值對環(huán)的連通性度量并不如使用EMD值更加精確，雖然EMD值計算會比ACE值計算復(fù)雜，但是在本方法中，僅需計算構(gòu)成環(huán)的變量節(jié)點EMD值，并且可利用基于樹圖的環(huán)統(tǒng)計方法進(jìn)行環(huán)統(tǒng)計，因此，二者的運算復(fù)雜度比較接近。對此采用EMD值來度量環(huán)的連通性。

構(gòu)造(m,n)校驗矩陣的算法流程圖如圖1。

圖1 校驗矩陣構(gòu)造流程圖Fig.1 Check matrix construction flow chart

首先，使用改進(jìn)的算法構(gòu)造(m-1,n)的矩陣H1，對H1中環(huán)的連通性進(jìn)行局部優(yōu)化。改進(jìn)算法流程歸納如下。

步驟1設(shè)置矩陣大小為(m-1,n)，設(shè)置平均圍長閾值γav，EMD閾值η，變量節(jié)點序號為i，且i=1,2,…,n，初始化i=n。

步驟2在符合設(shè)定度分布的條件下，隨機生成第i個變量節(jié)點對應(yīng)的列向量。

步驟3若i-n+1≤m，判斷新生成的列向量是否與之前生成的列向量線性無關(guān)，若線性無關(guān)，執(zhí)行步驟4，否則執(zhí)行步驟2。

步驟4利用(2)式計算當(dāng)前節(jié)點的平均圍長gav，并計算構(gòu)成最小環(huán)的變量節(jié)點EMD之和，記錄其和的值為ηi。

步驟5若gav≥γav且ηi≥η，令i=i-1，執(zhí)行步驟6，否則執(zhí)行步驟2。

步驟6若i=0，算法結(jié)束，否則執(zhí)行步驟2。

此時，完成了對校驗矩陣的圍長約束和環(huán)的連通性初步優(yōu)化。

然后，利用基于樹圖的環(huán)搜索方法遍歷搜索H1中的所有不大于lth的環(huán)，并計算其中包含的變量節(jié)點EMD值和對應(yīng)變量節(jié)點序號，并記錄到列表φ中，再篩選出φ中的最小EMD值，并按照出現(xiàn)次數(shù)從多到少對變量節(jié)點進(jìn)行排序，分別記為vmi,i=1,2,…。通過添加一個校驗節(jié)點cm，將cm與vmi相連，判斷是否存在長度小于γav的環(huán)，若存在，則刪去連接的邊，選擇下一個變量節(jié)點相連，直到cm的度接近校驗節(jié)點的平均度分布，得到一個n維行向量hm，此時進(jìn)一步提升了構(gòu)成環(huán)的數(shù)量較多的變量節(jié)點連通性。

(3)

最后，將H1和hm如(3)式所示進(jìn)行合并，得到最終的校驗矩陣H。

由于本文所構(gòu)造的LDPC碼碼率為k=1-n/m，所以只要選取合適的碼長n和校驗節(jié)點數(shù)目m，就可靈活調(diào)整碼長碼率，得到能適用于不同系統(tǒng)且滿足需要的LDPC碼。

3 性能分析

3.1 仿真分析

根據(jù)本文所提出的一種基于圍長約束和EMD的低錯誤平層LDPC碼構(gòu)造方法，分別構(gòu)造了碼長為3 024，碼率為0.5和碼長為1 200，碼率為0.67的LDPC碼，并進(jìn)行了Matlab仿真分析，以此驗證本文構(gòu)造方法的性能。本文仿真條件：二進(jìn)制相移鍵控(binary phase shift keying，BPSK)調(diào)制，加性高斯白噪聲(additive white gaussian noise，AWGN)信道，置信傳播(belief propagation，BP)譯碼，綜合折中考慮糾錯性能與譯碼復(fù)雜度，譯碼迭代次數(shù)選擇50次。

圖2 PGAE-LDPC(3 024,1 512)碼與其他碼的糾錯性能仿真圖Fig.2 Simulation diagram of the error-correctionperformance among the PGAE-LDPC(3 024,1 512) code and other codes

圖3 PGAE-LDPC(1 200,800)碼與其他碼的糾錯性能仿真圖Fig.3 Simulation diagram of the error-correctionperformance among the PGAE-LDPC(1 200,800) code and other codes

本文根據(jù)密度進(jìn)化算法，設(shè)定校驗矩陣的度分布為λ(x)=0.383 54x+0.042 37x2+0.574 09x3，校驗矩陣大小分別為m=1 512，n=3 024和m=400，n=1 024構(gòu)造得到的PEG-GA-EMD(PGAE)-LDPC(3 024,1 512)碼型和PGAE-LDPC(1 200,800)碼型，與利用PEG算法得到的PEG-LDPC碼型、利用PEG算法和圍長約束得到的PEG-GA-LDPC碼型以及利用PEG算法和ACE算法[14]得到的PEG-ACE-LDPC碼型進(jìn)行仿真對比分析。其誤碼率性能仿真對比圖分別如圖2和圖3。

本文構(gòu)造的碼率為0.5的PGAE-LDPC(3 024,1 512)碼和碼率為0.67的PGAE-LDPC(1 200,800)碼的圍長均為8，由圖2和圖3分析可知，PGAE-LDPC(3 024,1 512)碼在誤碼率為10-6時，相較于PEG-ACE-LDPC(3 024,1 512)碼，凈編碼增益提升了大約0.04 dB，相較于PEG-LDPC(3 024,1 512)碼，凈編碼增益提升了大約0.22 dB，相較于PEG-GA-LDPC(3 024,1 512)碼，凈編碼增益提升了大約0.20 dB，在誤碼率為10-7時，本文構(gòu)造的碼率為0.5的PGAE-LDPC(3 024,1 512)碼，相較于PEG-ACE-LDPC(3 024,1 512)碼，凈編碼增益提升了大約0.25 dB；且在信噪比為2.2 dB時，PGAE-LDPC(3 024,1 512)碼的誤碼率為4.64×10-8，PEG-ACE-LDPC(3 024,1 512)碼的誤碼率為3.31×10-7，PEG-GA-LDPC(3 024,1 512)碼的誤碼率為5.47×10-7，PEG-LDPC(3 024,1 512)碼的誤碼率為7.30×10-7。本文構(gòu)造的碼率為0.67的PGAE-LDPC(1 200,800)碼在誤碼率為10-6時，相較于PEG-ACE-LDPC(1 200，800)碼，凈編碼增益提升了大約0.09 dB，相較于PEG-LDPC(1 200,800)碼，凈編碼增益提升了大約0.77 dB。尤其是基于本文方法所構(gòu)造的PGAE-LDPC(3 024,1 512)碼和PGAE-LDPC(1 200,800)碼不存在明顯的錯誤平層現(xiàn)象，而其他幾種LDPC碼型存在明顯的錯誤平層現(xiàn)象。

3.2 復(fù)雜度分析

從編碼復(fù)雜度的角度來看，基于本文構(gòu)造方法所構(gòu)造的LDPC碼相較于文獻(xiàn)[8]基于圍長約束構(gòu)造的PEG-GA-LDPC碼、文獻(xiàn)[14]利用經(jīng)典PEG方法構(gòu)造的PEG-LDPC碼和基于PEG與ACE構(gòu)造的PEG-ACE碼，具有相同的碼長碼率，且都是通過生成矩陣進(jìn)行編碼，四者的編碼運算復(fù)雜度均是O(n2)。唯一不同的是，本文在構(gòu)造校驗矩陣的過程中，有一個額外的遍歷搜索矩陣中連通性較差的變量節(jié)點的過程，這個過程在構(gòu)造LDPC碼的過程中只存在一次。在本文構(gòu)造的碼長為3 024的PGAE-LDPC(3 024,1 512)碼和碼長為1 200的PGAE-LDPC(1 200,800)碼時，此過程的耗時分別僅為63.47 s和54.18 s，運算復(fù)雜度會有略微增加。綜上分析可知，本文提出的構(gòu)造方法與文獻(xiàn)[8]和文獻(xiàn)[14]相比，在僅增加可接受的運算復(fù)雜度情況下，糾錯性能得到明顯改善的同時，也進(jìn)一步降低了其錯誤平層。

4 結(jié) 論

為了消除或降低高信噪比區(qū)域LDPC碼存在的錯誤平層現(xiàn)象，本文提出了一種基于圍長約束和EMD的低錯誤平層LDPC碼構(gòu)造方法，首先約束校驗矩陣的圍長，并初步提升構(gòu)成環(huán)的變量節(jié)點EMD值，然后通過添加一個校驗節(jié)點，再次提升構(gòu)成環(huán)數(shù)量較多的變量節(jié)點的連通性，從而得到最終的校驗矩陣。仿真結(jié)果表明，利用本文提出的構(gòu)造方法所構(gòu)造出的LDPC碼型中不存在四環(huán)和六環(huán)，碼字的糾錯性能優(yōu)于基于PEG算法與ACE相結(jié)合構(gòu)造的同碼長碼率的碼型，同樣也優(yōu)于PEG算法結(jié)合圍長約束構(gòu)造的同碼長碼率的碼型。本文提出的方法，一方面保證了LDPC碼圍長足夠大，另一方面提升了環(huán)的連通性，從而減小了小陷阱集出現(xiàn)的概率，特別是在高信噪比區(qū)域，有效地改善了LDPC碼的糾錯性能，并且具有較低的錯誤平層。