基于廣義等差數列的大圍長QC-LDPC碼構造

趙 輝，余孟潔，安 靜，鄺凱達，呂典楷

(1.重慶郵電大學 通信與信息工程學院，重慶 400065；2.重慶郵電大學 信號與信息處理重慶市重點實驗室，重慶 400065)

0 引 言

準循環低密度奇偶校驗(quasi-cyclic low-density parity-check，QC-LDPC)碼由于具有接近香農極限、易于實現等優異性能，逐漸發展為當前編碼領域的研究熱點之一[1]。因為類似于置信傳播(belief propagation，BP)[2]的QC-LDPC碼譯碼算法是基于Tanner圖中變量節點和校驗節點間的符號可靠性信息迭代更新的決策過程[3]，短環的存在會嚴重影響譯碼性能。因此，構造大圍長QC-LDPC碼對于提高碼字的編譯碼性能具有重要意義。

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

針對上述分析，本文提出一種基于廣義等差數列(generalized arithmetic sequence，GAS)的QC-LDPC碼構造方法。利用GAS中元素的差值不等性構造QC-LDPC碼的循環移位系數矩陣(cyclic shift coefficient matrix，CSCM)，并給出移位系數值(shift coefficient value，SCV)的解析表達式。然后提出一種局部優化算法對存在第二類6環結構的碼字進行圍長優化，構造的QC-LDPC碼圍長至少為8。

1 QC-LDPC碼理論基礎

QC-LDPC碼是由CSCM和擴展因子P確定的一種高度結構化的LDPC碼。考慮一個 (n,k) QC-LDPC碼，碼字的CSCM為[8]

(1)

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

(2)

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

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

(3)

若一個QC-LDPC碼的CSCM中有S個長度為k的環，那么當CSCM根據擴展因子P的大小擴展為QC-LDPC碼時，校驗矩陣H中將會出現至多S×P個長度相同的環[13]。由此可以看出，若能保證CSCM中不存在短環結構，則對應的校驗矩陣H也不會受到相應短環結構對碼字譯碼性能的影響。因此，本文將CSCM作為構造大圍長QC-LDPC碼的目標矩陣，先構造不存在短環結構的CSCM，再根據擴展因子對CSCM進行擴展得到無短環結構的QC-LDPC碼。

2 基于GAS的QC-LDPC碼構造

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

圖1 4環結構分布

圖2 QC-LDPC碼中6種可能的6環結構

圖3 6環結構分布

根據上述分析構造CSCM，使其每一行的元素均構成一個GAS，且廣義公差滿足dj+1>dj， 則CSCM滿足無4環和第一類6環結構的條件，即f2-f1?f3-f4，f1-f2+f3-f4+f5-f6?0。 例如，考慮一個大小為3×6的CSCM

(4)

可見，E0的每一行都是一個GAS，廣義公差分別為1,3和5。由于E0滿足無4環和第一類6環結構的條件f2-f1?f3-f4和f1-f2+f3-f4+f5-f6?0， 則由E0擴展得到的QC-LDPC碼中不存在4環和第一類6環結構。

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

表1 矩陣E0的相關參數取值

可見，基于GAS構造的CSCM中梯度值bj和廣義差值dj滿足關系

(5)

則CSCM中的元素滿足

(6)

由式(6)可知

(7)

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

(8)

該方法可以通過改變CSCM的行數J、列數L，初始值a1和初始坐標 (j,l) 來實現碼率和碼長的靈活性選擇。例如，令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 圍長分析

3.1 4環分析

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

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

(11)

時，4環存在。令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)

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

0

(15)

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

3.2 6環分析

對于第一類6環結構，以圖2中的結構(a)為例，當且僅當移位系數值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)

時，6環存在。令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)

因為pj1,l1-pj0,l1

Qsix

(20)

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

0

(21)

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

下面分析第二類6環結構。以第二類6環結構中的結構(e)(圖2)為例，將第二類6環結構(e)(圖2)與第一類6環結構中的結構(a)(圖2)進行比較，比較分析結果如圖4所示。

圖4 第二類6環和第一類6環的結構比較分析

由圖4中的子圖(b)和式(3)可知，6環結構(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對Qleft進行變換可得

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

(23)

將上式中4組SCV用對應的差值d1，d2，d3，d4表示可得

Qleft=-d1-d4+d3+d2

(24)

因為d2-d1>0，d3-d4<0， 所以當d2-d1=d3-d4時，有

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

(25)

即式(22)不能被保證，第二類6環結構(e)(圖2)在d2-d1=d3-d4時存在，同理對于圖2中第二類6環結構(f)(圖2)也存在同樣的問題。然而，對于第一類6環結構(a)(圖2)，由于d3-d1>0，d4-d2>0， 因此式(22)總是成立的，即第一類6環結構總是不存在的，這與第一類6環結構部分的證明結果是一致的。

3.3 局部優化算法

為消除基于GAS構造的CSCM在滿足d2-d1=d3-d4時存在的第二類6環結構，這里提出一種局部優化算法對CSCM的圍長進行優化，該算法的流程如下。

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

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

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

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

步驟5 根據步驟4中得到的坐標 (j,l) 更新矩陣E0對應坐標上的SCV，E0j,l=pj,l+σ。

步驟6 判斷新的E0中是否存在第二類6環結構，若不存在，算法結束，輸出矩陣E=E0； 否則執行步驟2。

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

(26)

且由E構造的QC-LDCP碼中不存在6環結構，圍長為8。可見，當d2-d1=d3-d4時，在基于GAS構造的QC-LDPC碼不存在4環結構和第一類6環結構的基礎上，該局部優化算法可以保證構造的QC-LDPC碼中不存在第二類6環結構，即構造的QC-LDPC碼的圍長至少為8。

4 仿真與性能分析

為了驗證本文所提構造方法的性能，本節對提出的基于GAS構造的QC-LDPC碼與文獻[4]、文獻[7]和文獻[12]中提出的QC-LDPC碼進行Monte Carlo仿真比較。基于MATLAB的仿真環境設置如下：信道為加性高斯白噪聲(additive white Gaussian noise，AWGN)信道，調制方式為二進制相移鍵控(binary phase shift keying，BPSK)調制，譯碼算法為Log-似然比(LLR)-BP譯碼算法，每個信噪比下的錯誤碼組數不小于100組，設置最大迭代次數為50。

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

(27)

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

圖5 本文構造的(1536,765)QC-LDPC碼與對比文獻的碼字BER性能對比

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

(28)

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

圖6 本文構造的(2560,765)QC-LDPC碼與對比文獻的碼字BER性能對比

為了進一步說明上述進行仿真的4種QC-LDPC碼之間誤碼率性能差異的原因，本文利用環搜索算法分別對上述4種碼字的短環數量進行了仿真比較，分別給出了各碼字在擴展因子P=256時的短環數和8環數，如表2所示。從表中可以看出，在相同的碼長和碼率下，本文提出的基于GAS構造的QC-LDPC碼具有更大的圍長，或者在具有相同圍長的情況下擁有更少的短環數。由于QC-LDPC碼的圍長越大，短環數越少，碼字的最小漢明距離(MHD)下界就越大，BP類迭代譯碼算法的性能下降就越少，因此本文提出的基于GAS構造的QC-LDPC碼具有更佳的BER性能。

表2 本文提出的QC-LDPC碼和參考碼字的環數比較

5 結束語

本文提出了一種基于GAS和局部優化算法的大圍長QC-LDPC碼構造方法。首先，利用GAS中各元素之間的差值不等性構造QC-LDPC碼的CSCM，根據擴展因子對構造的CSCM進行擴展，得到的QC-LDPC碼中一定不存在4環和第一類6環結構，且當CSCM中的元素不滿足d2-d1=d3-d4時第二類6環結構也不存在。然后提出一種局部優化算法對存在第二類6環結構的CSCM進行圍長優化，消除CSCM的第二類6環結構，確保基于CSCM擴展得到的QC-LDPC碼中不存在短環結構影響碼字的譯碼性能，圍長至少為8。仿真結果表明，與現有的一些構造方法相比，根據本文提出的基于GAS構造方法構造的QC-LDPC碼在AWGN信道上表現出更好的誤碼率性能。