基于廣義等差數(shù)列的大圍長(zhǎng)QC-LDPC碼構(gòu)造

趙 輝，余孟潔，安 靜，鄺凱達(dá)，呂典楷

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2.重慶郵電大學(xué) 信號(hào)與信息處理重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

0 引 言

準(zhǔn)循環(huán)低密度奇偶校驗(yàn)(quasi-cyclic low-density parity-check，QC-LDPC)碼由于具有接近香農(nóng)極限、易于實(shí)現(xiàn)等優(yōu)異性能，逐漸發(fā)展為當(dāng)前編碼領(lǐng)域的研究熱點(diǎn)之一[1]。因?yàn)轭?lèi)似于置信傳播(belief propagation，BP)[2]的QC-LDPC碼譯碼算法是基于Tanner圖中變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)間的符號(hào)可靠性信息迭代更新的決策過(guò)程[3]，短環(huán)的存在會(huì)嚴(yán)重影響譯碼性能。因此，構(gòu)造大圍長(zhǎng)QC-LDPC碼對(duì)于提高碼字的編譯碼性能具有重要意義。

目前，QC-LDPC碼的構(gòu)造方法大致分為隨機(jī)構(gòu)造和結(jié)構(gòu)化構(gòu)造兩類(lèi)[4]。由于當(dāng)碼長(zhǎng)較短時(shí)基于隨機(jī)方法構(gòu)造的QC-LDPC碼容易出現(xiàn)較高的錯(cuò)誤平層且復(fù)雜度較高，考慮到工程實(shí)現(xiàn)的可能性，人們對(duì)結(jié)構(gòu)化構(gòu)造方法進(jìn)行了大量的研究。彭海英等在文獻(xiàn)[5]中提出了一種基于中國(guó)剩余定理(Chinese remainder theorem，CRT)的QC-LDPC碼組合設(shè)計(jì)方法，設(shè)計(jì)出的碼字中不存在6環(huán)，但該方法在擴(kuò)展因子的取值上存在一定局限性，且只能用于構(gòu)造列重為3的QC-LDPC碼。袁建國(guó)等提出了一種基于斐波那契-盧卡斯序列的Type-II QC-LDPC碼構(gòu)造方法，該方法雖然避免了4環(huán)的存在，但需要額外的打孔技術(shù)來(lái)減少6環(huán)的數(shù)量。文獻(xiàn)[7]中張軼等提出了一種利用等差數(shù)列構(gòu)造圍長(zhǎng)為8的QC-LDPC碼的方法，但該方法只能用于構(gòu)造列權(quán)重為3的QC-LDPC碼，在靈活性上具有一定的局限性。

針對(duì)上述分析，本文提出一種基于廣義等差數(shù)列(generalized arithmetic sequence，GAS)的QC-LDPC碼構(gòu)造方法。利用GAS中元素的差值不等性構(gòu)造QC-LDPC碼的循環(huán)移位系數(shù)矩陣(cyclic shift coefficient matrix，CSCM)，并給出移位系數(shù)值(shift coefficient value，SCV)的解析表達(dá)式。然后提出一種局部?jī)?yōu)化算法對(duì)存在第二類(lèi)6環(huán)結(jié)構(gòu)的碼字進(jìn)行圍長(zhǎng)優(yōu)化，構(gòu)造的QC-LDPC碼圍長(zhǎng)至少為8。

1 QC-LDPC碼理論基礎(chǔ)

QC-LDPC碼是由CSCM和擴(kuò)展因子P確定的一種高度結(jié)構(gòu)化的LDPC碼?？紤]一個(gè) (n,k) QC-LDPC碼，碼字的CSCM為[8]

(1)

式中：每一個(gè)pj,l(1≤j≤J， 1≤l≤L) 都是一個(gè)SCV,取值范圍為 {-1,0,1,2,…,P-1},J=(n-k)/P，L=n/P分別為CSCM的行數(shù)和列數(shù)。將式(1)中J×L個(gè)SCV用與其相對(duì)應(yīng)的J×L個(gè)大小為P×P的循環(huán)置換矩陣(cyclic permutation matrix，CPM)代替，可得QC-LDPC碼的奇偶校驗(yàn)矩陣H[9]

(2)

式中：I(pj,l) 是將大小為P×P的單位矩陣IP×P向左循環(huán)移位pj,l個(gè)單位得到的CPM。當(dāng)pj,l=0時(shí)，I(pj,l) 代表P×P單位矩陣；當(dāng)pj,l=-1時(shí)，I(pj,l) 代表P×P零矩陣[10]。若式(1)中所有的pj,l均不等于-1，則由E確定的QC-LDPC碼為規(guī)則LDPC碼，否則為不規(guī)則LDPC碼[11]。

當(dāng)用Tanner圖對(duì)QC-LDPC碼進(jìn)行表示時(shí)，Tanner圖中的變量節(jié)點(diǎn)和校驗(yàn)節(jié)點(diǎn)依次交替連接的邊所形成的閉合路徑稱為QC-LDPC碼的環(huán)。環(huán)所包含的邊的數(shù)目稱為環(huán)的長(zhǎng)度，長(zhǎng)度為4和6的環(huán)被稱為短環(huán)。假設(shè)QC-LDPC碼的CSCM中有k個(gè)SCV{p1,p2,…,pk}， 其中k為大于2的整偶數(shù)。若 {p1,p2,…,pk} 滿足pi和pi+1在同一列或同一行，pi和pi+2不在同一列和同一行，則 {p1,p2,…,pk} 形成長(zhǎng)度為k的環(huán)的充要條件為[12]

(3)

若一個(gè)QC-LDPC碼的CSCM中有S個(gè)長(zhǎng)度為k的環(huán)，那么當(dāng)CSCM根據(jù)擴(kuò)展因子P的大小擴(kuò)展為QC-LDPC碼時(shí)，校驗(yàn)矩陣H中將會(huì)出現(xiàn)至多S×P個(gè)長(zhǎng)度相同的環(huán)[13]。由此可以看出，若能保證CSCM中不存在短環(huán)結(jié)構(gòu)，則對(duì)應(yīng)的校驗(yàn)矩陣H也不會(huì)受到相應(yīng)短環(huán)結(jié)構(gòu)對(duì)碼字譯碼性能的影響。因此，本文將CSCM作為構(gòu)造大圍長(zhǎng)QC-LDPC碼的目標(biāo)矩陣，先構(gòu)造不存在短環(huán)結(jié)構(gòu)的CSCM，再根據(jù)擴(kuò)展因子對(duì)CSCM進(jìn)行擴(kuò)展得到無(wú)短環(huán)結(jié)構(gòu)的QC-LDPC碼。

2 基于GAS的QC-LDPC碼構(gòu)造

廣義等差數(shù)列是由等差數(shù)列衍生而來(lái)的一種常見(jiàn)的整數(shù)數(shù)列，其定義為：對(duì)于一組整數(shù)數(shù)列，若數(shù)列中所有偶數(shù)位上的值與其前一位奇數(shù)位上的值之差滿足等差數(shù)列的定義，則稱其為廣義等差數(shù)列。廣義等差數(shù)列中奇偶位上的差值滿足的等差數(shù)列的公差稱為廣義等差數(shù)列的廣義差值，記為dj。由于廣義等差數(shù)列中所有元素之間的差值滿足等差數(shù)列的定義，因此廣義等差數(shù)列中的元素具有差值不等的性質(zhì)。例如數(shù)列 {1,2,4,7,11} 和數(shù)列 {0,4,12,24,40} 都是廣義等差數(shù)列，數(shù)列中各元素的差值分別為 {1,2,3,4} 和 {4,8,12,16}， 廣義差值分別為dj=1和dj=4。 由于本文將CSCM作為構(gòu)造大圍長(zhǎng)QC-LDPC碼的目標(biāo)矩陣，因此基于GAS的QC-LDPC碼構(gòu)造實(shí)質(zhì)上是基于GAS構(gòu)造QC-LDPC碼的CSCM。為了保證所構(gòu)造的CSCM中不存在短環(huán)結(jié)構(gòu)，下面分別對(duì)CSCM中不存在環(huán)長(zhǎng)為4和環(huán)長(zhǎng)6的短環(huán)結(jié)構(gòu)的條件進(jìn)行分析。

圖1 4環(huán)結(jié)構(gòu)分布

圖2 QC-LDPC碼中6種可能的6環(huán)結(jié)構(gòu)

圖3 6環(huán)結(jié)構(gòu)分布

根據(jù)上述分析構(gòu)造CSCM，使其每一行的元素均構(gòu)成一個(gè)GAS，且廣義公差滿足dj+1>dj， 則CSCM滿足無(wú)4環(huán)和第一類(lèi)6環(huán)結(jié)構(gòu)的條件，即f2-f1?f3-f4，f1-f2+f3-f4+f5-f6?0。 例如，考慮一個(gè)大小為3×6的CSCM

(4)

可見(jiàn)，E0的每一行都是一個(gè)GAS，廣義公差分別為1,3和5。由于E0滿足無(wú)4環(huán)和第一類(lèi)6環(huán)結(jié)構(gòu)的條件f2-f1?f3-f4和f1-f2+f3-f4+f5-f6?0， 則由E0擴(kuò)展得到的QC-LDPC碼中不存在4環(huán)和第一類(lèi)6環(huán)結(jié)構(gòu)。

為使全文敘述更加清晰，對(duì)相關(guān)的參數(shù)作如下規(guī)定：在基于GAS構(gòu)造的CSCM中，第j行中每前后兩個(gè)數(shù)的差值組成的等差數(shù)列記為uj，uj的公差即為廣義差值dj； 第j行的第一個(gè)值記為初值aj； 第j行與第一行的初值之差記為梯度值bj。 表1給出了式(4)所示矩陣E0中上述參數(shù)的取值情況。

表1 矩陣E0的相關(guān)參數(shù)取值

可見(jiàn)，基于GAS構(gòu)造的CSCM中梯度值bj和廣義差值dj滿足關(guān)系

(5)

則CSCM中的元素滿足

(6)

由式(6)可知

(7)

將式(5)代入式(7)，則得SCV的解析表達(dá)式

(8)

該方法可以通過(guò)改變CSCM的行數(shù)J、列數(shù)L，初始值a1和初始坐標(biāo) (j,l) 來(lái)實(shí)現(xiàn)碼率和碼長(zhǎng)的靈活性選擇。例如，令J=3,L=6,a1=3， (j,l)=(2,2)， 將j={1,2,3}，l={1,2,…,5,6} 代入式(8)，可得碼率約為0.5的QC-LDPC碼的CSCM

(9)

同理，令J=3,L=10,a1=2， (j,l)=(1,2)， 將j={1,2,3}，l={1,2,…,9,10} 代入式(8)，可得碼率約為0.7的QC-LDPC碼的CSCM

(10)

3 圍長(zhǎng)分析

3.1 4環(huán)分析

由式(3)可知，當(dāng)移位系數(shù)值pj0,l0，pj0,l1，pj1,l1，pj1,l0滿足

pj0,l0-pj0,l1+pj1,l1-pj1,l0≡0(modP)

(11)

時(shí)，4環(huán)存在。令pj0,l0-pj0,l1+pj1,l1-pj1,l0=Qfour， 1≤j0≤j1≤J， 1≤l0≤l1≤L， 將式(8)代入Qfour有

(12)

Qfour=pj0,l0-pj0,l1+pj1,l1-pj1,l0>0

(13)

另一方面，用pj1,l0替換pj0,l0， 有

Qfour=pj0,l0-pj0,l1+pj1,l1-pj1,l0

(14)

根據(jù)式(13)，式(14)和夾逼定理可得

0

(15)

由此可知，本文構(gòu)造的QC-LDPC碼不滿足式(12)，即基于GAS構(gòu)造的QC-LDPC碼中不存在4環(huán)結(jié)構(gòu)。

3.2 6環(huán)分析

對(duì)于第一類(lèi)6環(huán)結(jié)構(gòu)，以圖2中的結(jié)構(gòu)(a)為例，當(dāng)且僅當(dāng)移位系數(shù)值pj0,l0，pj0,l1，pj1,l1，pj1,l2，pj2,l2，pj2,l0滿足

pj0,l0-pj0,l1+pj1,l1-pj1,l2+pj2,l2-pj2,l0≡0(modP)

(16)

時(shí)，6環(huán)存在。令pj0,l0-pj0,l1+pj1,l1-pj1,l2+pj2,l2-pj2,l0=Qsix， 其中1≤j0≤j1≤j2≤J， 1≤l0≤l1≤l2≤L。 將式(8)代入Qsix可得

(17)

用j1代替j2代入式(17)可得

(18)

同理，用pj2,l0替換pj0,l0代入式(17)可得

Qsix=pj2,l0-pj0,l1+pj1,l1-pj1,l2+pj2,l2-pj2,l0=-pj0,l1+pj1,l1-pj1,l2+pj2,l2

(19)

因?yàn)閜j1,l1-pj0,l1

Qsix

(20)

同理，根據(jù)式(18)、式(20)和夾逼定理可知

0

(21)

因此，式(16)不成立，即構(gòu)造的QC-LDPC碼中不存在第一類(lèi)6環(huán)結(jié)構(gòu)(a)(圖2)。同理可以證明第一類(lèi)6環(huán)結(jié)構(gòu)中的其余3種結(jié)構(gòu)也不存在，即基于GAS構(gòu)造的QC-LDPC碼中不存在第一類(lèi)6環(huán)結(jié)構(gòu)。

下面分析第二類(lèi)6環(huán)結(jié)構(gòu)。以第二類(lèi)6環(huán)結(jié)構(gòu)中的結(jié)構(gòu)(e)(圖2)為例，將第二類(lèi)6環(huán)結(jié)構(gòu)(e)(圖2)與第一類(lèi)6環(huán)結(jié)構(gòu)中的結(jié)構(gòu)(a)(圖2)進(jìn)行比較，比較分析結(jié)果如圖4所示。

圖4 第二類(lèi)6環(huán)和第一類(lèi)6環(huán)的結(jié)構(gòu)比較分析

由圖4中的子圖(b)和式(3)可知，6環(huán)結(jié)構(gòu)(e)(圖2)不存在的充要條件是

pj2,l2-pj2,l3+pj4,l3-pj4,l4+pj3,l4-pj3,l2?0(modP)

(22)

令pj2,l2-pj2,l3+pj4,l3-pj4,l4+pj3,l4-pj3,l2=Qleft， 引入pj3,l3對(duì)Qleft進(jìn)行變換可得

Qleft=-(pj2,l3-pj2,l2)-(pj4,l4-pj4,l3)+(pj3,l4-pj3,l3)+(pj3,l3-pj3,l2)

(23)

將上式中4組SCV用對(duì)應(yīng)的差值d1，d2，d3，d4表示可得

Qleft=-d1-d4+d3+d2

(24)

因?yàn)閐2-d1>0，d3-d4<0， 所以當(dāng)d2-d1=d3-d4時(shí)，有

Qleft=(d2-d1)+(d3-d4)=0

(25)

即式(22)不能被保證，第二類(lèi)6環(huán)結(jié)構(gòu)(e)(圖2)在d2-d1=d3-d4時(shí)存在，同理對(duì)于圖2中第二類(lèi)6環(huán)結(jié)構(gòu)(f)(圖2)也存在同樣的問(wèn)題。然而，對(duì)于第一類(lèi)6環(huán)結(jié)構(gòu)(a)(圖2)，由于d3-d1>0，d4-d2>0， 因此式(22)總是成立的，即第一類(lèi)6環(huán)結(jié)構(gòu)總是不存在的，這與第一類(lèi)6環(huán)結(jié)構(gòu)部分的證明結(jié)果是一致的。

3.3 局部?jī)?yōu)化算法

為消除基于GAS構(gòu)造的CSCM在滿足d2-d1=d3-d4時(shí)存在的第二類(lèi)6環(huán)結(jié)構(gòu)，這里提出一種局部?jī)?yōu)化算法對(duì)CSCM的圍長(zhǎng)進(jìn)行優(yōu)化，該算法的流程如下。

步驟1 獲取輸入矩陣E0， 設(shè)置控制因子σ=1， 初始化權(quán)值矩陣B為與E0大小相同的零矩陣。

步驟2 判斷矩陣E0中是否存在三列值可以組成新的矩陣M， 若存在，執(zhí)行步驟3；若不存在，即所有可能的組合已經(jīng)全部搜索完畢，執(zhí)行步驟4。

步驟3 若M中存在一組SCV滿足式(3)，則在權(quán)值矩陣B中記錄成環(huán)路徑，即令矩陣B中對(duì)應(yīng)位置上的值+1，然后執(zhí)行步驟2；若不存在一組SCV滿足式(3)，則直接執(zhí)行步驟2。

步驟4 若矩陣B為非零矩陣，選取矩陣B中元素值最大的坐標(biāo) (j,l) 作為需要被更新的坐標(biāo)，執(zhí)行步驟5；若矩陣B為零矩陣，算法結(jié)束，輸出矩陣E=E0。

步驟5 根據(jù)步驟4中得到的坐標(biāo) (j,l) 更新矩陣E0對(duì)應(yīng)坐標(biāo)上的SCV，E0j,l=pj,l+σ。

步驟6 判斷新的E0中是否存在第二類(lèi)6環(huán)結(jié)構(gòu)，若不存在，算法結(jié)束，輸出矩陣E=E0； 否則執(zhí)行步驟2。

以式(4)所示的E0為例，將E0代入上述提出的局部?jī)?yōu)化算法，得到矩陣B中元素值最大的坐標(biāo)為 (j,l)=(3,3)， 因此E03,3=p3，3+σ， 通過(guò)上述局部?jī)?yōu)化算法處理以后得到矩陣

(26)

且由E構(gòu)造的QC-LDCP碼中不存在6環(huán)結(jié)構(gòu)，圍長(zhǎng)為8?？梢?jiàn)，當(dāng)d2-d1=d3-d4時(shí)，在基于GAS構(gòu)造的QC-LDPC碼不存在4環(huán)結(jié)構(gòu)和第一類(lèi)6環(huán)結(jié)構(gòu)的基礎(chǔ)上，該局部?jī)?yōu)化算法可以保證構(gòu)造的QC-LDPC碼中不存在第二類(lèi)6環(huán)結(jié)構(gòu)，即構(gòu)造的QC-LDPC碼的圍長(zhǎng)至少為8。

4 仿真與性能分析

為了驗(yàn)證本文所提構(gòu)造方法的性能，本節(jié)對(duì)提出的基于GAS構(gòu)造的QC-LDPC碼與文獻(xiàn)[4]、文獻(xiàn)[7]和文獻(xiàn)[12]中提出的QC-LDPC碼進(jìn)行Monte Carlo仿真比較。基于MATLAB的仿真環(huán)境設(shè)置如下：信道為加性高斯白噪聲(additive white Gaussian noise，AWGN)信道，調(diào)制方式為二進(jìn)制相移鍵控(binary phase shift keying，BPSK)調(diào)制，譯碼算法為L(zhǎng)og-似然比(LLR)-BP譯碼算法，每個(gè)信噪比下的錯(cuò)誤碼組數(shù)不小于100組，設(shè)置最大迭代次數(shù)為50。

將參數(shù)J=3，L=6，a1=1， (j,l)=(1,3) 代入式(8)所示的SCV解析表達(dá)式，得到基于GAS構(gòu)造的大小為3×6的QC-LDPC碼的CSCM為

(27)

取擴(kuò)展因子P=256對(duì)式(27)所示的CSCM進(jìn)行擴(kuò)展，得到碼率R約為0.5，碼長(zhǎng)為1536的QC-LDPC碼。為了保證比較的有效性，根據(jù)文獻(xiàn)[4]、文獻(xiàn)[7]和文獻(xiàn)[12]中提出的方法構(gòu)造碼長(zhǎng)相同的QC-LDPC碼與本文提出的基于GAS構(gòu)造的QC-LDPC碼進(jìn)行比較，仿真結(jié)果如圖5所示。從圖5可以看出，與文獻(xiàn)[12]和文獻(xiàn)[7]中提出的QC-LDPC碼相比，本文基于GAS方法構(gòu)造的QC-LDPC碼在誤碼率(bit error rate，BER)為10-5時(shí)分別實(shí)現(xiàn)了大約0.1 dB和0.2 dB的信噪比增益。同時(shí)可以看出，與文獻(xiàn)[4]中提出的碼字相比，本文構(gòu)造的QC-LDPC碼在BER=10-4時(shí)實(shí)現(xiàn)大約0.5 dB的信噪比增益。

圖5 本文構(gòu)造的(1536,765)QC-LDPC碼與對(duì)比文獻(xiàn)的碼字BER性能對(duì)比

同理，將參數(shù)J=3，L=10，a1=0， (j,l)=(1,1) 代入式(8)所示的SCV解析表達(dá)式，得到基于GAS構(gòu)造的大小為3×10的QC-LDPC碼的CSCM為

(28)

設(shè)置擴(kuò)展因子P=256對(duì)式(28)中的CSCME2進(jìn)行擴(kuò)展，得到的QC-LDPC碼碼長(zhǎng)為2560，碼率約為0.7。同理，為了保證比較的有效性，根據(jù)文獻(xiàn)[4]、文獻(xiàn)[7]和文獻(xiàn)[12]中提出的方法構(gòu)造碼長(zhǎng)同為2560的QC-LDPC碼進(jìn)行仿真比較，仿真比較結(jié)果如圖6所示。由仿真結(jié)果可知，與文獻(xiàn)[4]、文獻(xiàn)[7]和文獻(xiàn)[12]中提出的碼字相比，本文構(gòu)造的碼字在BER為10-5時(shí)分別實(shí)現(xiàn)了約0.1 dB、0.2 dB和0.4 dB的BER性能提升。此外，從圖中可以看出，本文提出的QC-LDPC碼在BER接近10-7的時(shí)候，“瀑布區(qū)”仍然具有很大的斜率，且沒(méi)有出現(xiàn)錯(cuò)誤平層。

圖6 本文構(gòu)造的(2560,765)QC-LDPC碼與對(duì)比文獻(xiàn)的碼字BER性能對(duì)比

為了進(jìn)一步說(shuō)明上述進(jìn)行仿真的4種QC-LDPC碼之間誤碼率性能差異的原因，本文利用環(huán)搜索算法分別對(duì)上述4種碼字的短環(huán)數(shù)量進(jìn)行了仿真比較，分別給出了各碼字在擴(kuò)展因子P=256時(shí)的短環(huán)數(shù)和8環(huán)數(shù)，如表2所示。從表中可以看出，在相同的碼長(zhǎng)和碼率下，本文提出的基于GAS構(gòu)造的QC-LDPC碼具有更大的圍長(zhǎng)，或者在具有相同圍長(zhǎng)的情況下?lián)碛懈俚亩汰h(huán)數(shù)。由于QC-LDPC碼的圍長(zhǎng)越大，短環(huán)數(shù)越少，碼字的最小漢明距離(MHD)下界就越大，BP類(lèi)迭代譯碼算法的性能下降就越少，因此本文提出的基于GAS構(gòu)造的QC-LDPC碼具有更佳的BER性能。

表2 本文提出的QC-LDPC碼和參考碼字的環(huán)數(shù)比較

5 結(jié)束語(yǔ)

本文提出了一種基于GAS和局部?jī)?yōu)化算法的大圍長(zhǎng)QC-LDPC碼構(gòu)造方法。首先，利用GAS中各元素之間的差值不等性構(gòu)造QC-LDPC碼的CSCM，根據(jù)擴(kuò)展因子對(duì)構(gòu)造的CSCM進(jìn)行擴(kuò)展，得到的QC-LDPC碼中一定不存在4環(huán)和第一類(lèi)6環(huán)結(jié)構(gòu)，且當(dāng)CSCM中的元素不滿足d2-d1=d3-d4時(shí)第二類(lèi)6環(huán)結(jié)構(gòu)也不存在。然后提出一種局部?jī)?yōu)化算法對(duì)存在第二類(lèi)6環(huán)結(jié)構(gòu)的CSCM進(jìn)行圍長(zhǎng)優(yōu)化，消除CSCM的第二類(lèi)6環(huán)結(jié)構(gòu)，確?；贑SCM擴(kuò)展得到的QC-LDPC碼中不存在短環(huán)結(jié)構(gòu)影響碼字的譯碼性能，圍長(zhǎng)至少為8。仿真結(jié)果表明，與現(xiàn)有的一些構(gòu)造方法相比，根據(jù)本文提出的基于GAS構(gòu)造方法構(gòu)造的QC-LDPC碼在AWGN信道上表現(xiàn)出更好的誤碼率性能。