利用等差數列構造大圍長準循環低密度奇偶校驗碼

張 軼 達新宇 蘇一棟

1 引言

碼的結構決定了低密度奇偶校驗(Low-Density Parity-Check, LDPC)碼的性能。基于循環移位矩陣構造的準循環低密度奇偶檢驗(Quasi-Cyclic Low-Density Parity-Check, QC-LDPC)碼，其校驗矩陣的準循環特性使其易于高效編解碼，碼的代數結構為超大規模集成電路的實現提供了可能，因此受到廣泛關注和研究。圍長是碼中最小的環長度，增大圍長可以提高碼字的性能。借助于計算機搜索，人們已經提出了一些圍長大于6的QC-LDPC碼構造方法[17]-，但為了滿足各種約束條件，這些準隨機方法通常花費時間長，存在失敗可能，且對編解碼存儲空間提出了更高要求。

針對上述問題，國內外學者對確定性構造方法的研究屢有成果涌現。文獻[8]和文獻[9]分別采用群結構法、3維循環網絡法構造出了圍長在10以上的QC-LDPC碼，但是校驗矩陣的行重只局限于特定范圍內；文獻[10-12]基于貪婪算法構造了圍長為 8的QC-LDPC碼，其循環移位矩陣尺寸具有連續變化的優點，但該方法要求準循環基矩陣首行首列元素必須為0；文獻[13]提出了基于二次函數的確定性方法，但方程系數與行重有關，任意行重只能構造兩種校驗矩陣。這在一定程度上限制了它們的實際應用。

在此基礎上，本文利用等差數列提出一種列重為3、圍長至少為8的 QC-LDPC碼構造方法。首先通過舉例歸納得到約束條件，總結出推導思路和方法；然后將特殊情形推廣，進而提出基于一般等差數列的確定性構造方法，并證明了其圍長特性；最后通過軟件仿真，驗證了該方法構造的 QC-LDPC碼參數設置靈活、性能優良。

2 QC-LDPC碼

QC-LDPC碼是一類非常特殊的高度結構化的LDPC碼，它的校驗矩陣以單位陣的循環移位陣和零方陣為子陣，可表示為

其中： I (pij)表示一個p×p的循環移位矩陣，pij∈{0,1,2,… ,p -1,∞ }。易知I(0)就是單位陣Ip×p，零方陣用I(∞)表示。把循環右移系數pij寫成一個矩陣P，稱為準循環基矩陣，如式(2)所示[14]。當P確定后，校驗矩陣H也隨之確定。

在基矩陣P中，若干個點(元素)p1,p2,… , p2k構成一個環，則對應的H矩陣也存在與之對應的p個同樣大小的環。顯然，環的長度只能是大于或等于4的偶數。表示H中長為2k環的序列(p1, p2,…,p2k)滿足定理1。

定理 1[15]對于基矩陣 P中的序列(p1, p2,… ,p2k)，其中 pi和 pi+1在同一行或同一列，pi和 pi+2在不同行且不同列，則(p1, p2,… , p2k)構成長為2k環的充分必要條件是

短環的存在使 LDPC碼在譯碼時不能快速收斂，甚至不能收斂，造成誤比特率(Bit Error Rate,BER)性能變差。因此，為了使校驗矩陣不含長為2k的環，就必須通過某種設計，使得式(3)不成立。圖1給出了6環存在的6種形狀。

圖1 6種形狀的6環

3 基于等差數列的確定性構造

3.1 歸納推導

對列重為3的校驗矩陣的基矩陣采取的配置方式為

其中n為基矩陣的列數。顯然，此時 { p1,j}為正整數列， { p2,j}為正偶數列。對 p3,2進行賦值時，為避免出現短環，則Δ1應滿足：

依此類推，可以得到滿足圍長至少為8的{Δj} 的取值下界，如表1所示。

表1 n69=～時j{}Δ的取值下界

3.2 構造方法

上節的結論是基于一種特例推導給出的。若采取相同的分析方法，將式(4)推廣至一般等差數列，則得到一種(3,)n基矩陣的構造方法為

其中1d,2d分別為兩個等差數列的公差。

4 圍長至少為8的性質證明

定理2 對于任意 n ≥ 3 ，滿足式(9)~式(12)定義的基矩陣P的圍長至少為8。

證明 圍長至少為8即不存在4環和6環。

(1)4環檢驗 不失一般性，令1 ≤ s ＜t ≤ n 。若P中存在4環，則滿足式(13)中的至少一項

這是不可能的，因為當n為奇數時，

當n為偶數時，同理可得

因此有

注意到 0 ＜ p3,s- p3,t＜p 和 0 ＜ p2,s- p2,t＜ p ，故式(13)不成立。因此，P中不存在4環。

(2)6環檢驗 不失一般性，令1 ≤ i ＜ k ＜j ≤ n。若P中存在圖1(a)所示6環，則

這是不可能的，因為由4環檢驗的結論，有

故式(17)不成立，同理可證P中也不存在圖1(b)~圖1(d)所示6環。

下面考慮圖1(e)的情形：

若 j - k = 1 ，由式(12)可得 p3,j-p3,k≥(d2-d1)?k+d1+1，故

若 j - k ≥ 2 ，以 n為奇數為例(偶數時同理)，由 { p3,j}為單增數列可得

因此P中不存在圖1(e)所示6環，同理也不存在圖1(f)所示6環。

綜上，基矩陣P的圍長至少為8。 證畢

利用等差數列求和公式可求出3,np 的通項表達式。

當n為奇數時，

當n為偶數時，

可以發現，當3,1p ,1d,2d確定后，3,np 是關于n的二次函數。由于本文方法中參數設置的靈活性，而移位矩陣的維數p大于移位系數，故p的取值下界為

特別地，當 p1,1= p2,1= p3,1= d1= 0 , d2= 1 時，式(21)的計算結果為 3 (n2- 1 )/4，式(22)為 3 n2/4 - 1，此時p的下界為 3 n2/4，與文獻[10]給出的研究結果相一致，說明該基矩陣是本文方法的一種特例。

5 仿真與分析

5.1 p值下界分析

構造3種準循環基矩陣，設 di= i , i ∈ { 1,2}，其它參數如表2所示。圖2描繪了這3種碼字p的取值下界隨n的變化曲線。

表2 d i = i , i ∈ { 1,2}時的參數配置

從圖2中可以看到，p的取值下界隨n的增大而增大。當3≤n＜8時，碼1、碼2的p值下界與n呈線性關系，當 n ≥ 8 時，3條曲線重合，此時p的取值僅與 p3,n有關。這是因為3種基矩陣的 { p3,j}完全一致，且由式(16)可知， { p3,j}中元素的增幅顯然大于 { p1,j}和{p2,j}，隨著n的增大，無論初始參數如何設置， in f p = p3,n+ 1都是必然結果。同時表明，利用本文方法構造的任意參數的準循環基矩陣，都可使p值獲得連續取值的下界。

5.2 圍長分析

構造3種準循環基矩陣，設 n = 6 ，其它參數如表3所示。圖3描繪了這3種碼字的8環數目隨p值的變化曲線，圖4為碼長一定(N = n ? p= 9 60)條件下，碼3的8環數目隨n的變化曲線。可以看到，基矩陣一定時8環數隨p值增大而增多；而當碼長一定時，p值越小則行重越大，意味著形成短環的概率越大，造成環數增多。因此在構造基矩陣時，針對不同的編碼參數需求，本文方法提供了一種簡單、靈活的設計思路。

表3 n 6= 時的參數配置

5.3 性能分析

構造兩種準循環基矩陣，設碼率 1/2R= ，其它參數如表 4所示。在加性高斯白噪聲(Additive White Gauss Noise, AWGN)信道下進行仿真，譯碼采用置信傳播(Belief Propagation, BP)算法，最大迭代次數為30，調制方式為BPSK，選取同碼長碼率的漸進邊增長(Progressive Edge-Growth,PEG)[16]碼進行性能比較。仿真結果如圖5所示。

表4 R 1/2= 時的參數配置

圖2 p的取值下界隨n的變化曲線

圖3 8環數目隨p值的變化曲線

圖4 碼長一定時8環數目隨n的變化曲線

圖5 本文構造碼字與PEG碼的性能比較

仿真結果表明，碼長為504時二者的譯碼性能差異不大；當碼長為1008, BER為10-5時，與PEG碼相比本文構造碼字信噪比增益約為0.3 dB。此外，PEG方法需要對度數的分布進行優化處理，其算法復雜度也高于本文方法。

6 結束語

本文提出了一種構造圍長至少為 8的(3,)nQC-LDPC碼的確定性方法。該碼的準循環基矩陣由等差數列生成的數學表達式確定，構造方法簡單，節省了編解碼存儲空間。研究結果表明，這類碼只需少量的初始值控制就可設計任意參數的基矩陣，同時在AWGN信道中能夠獲得較好的糾錯能力，因此對信道編碼理論的研究和應用具有一定的參考價值。在此方法基礎上，如何消除8環，從而構造圍長為10的QC-LDPC碼是今后深入研究的內容之一。

[1] O’Sullivan M E. Algebraic construction of sparse matrices with large girth[J]. IEEE Transactions on Information Theory, 2006, 52(2): 718-727.

[2] Milenkovic O, Kashyap N, and Leyba D. Shortened array codes of large girth[J]. IEEE Transactions on Information Theory, 2006, 52(8): 3707-3722.

[3] Jiang X and Lee M H. Large girth non-binary LDPC codes based on finite fields and Euclidean geometries[J]. IEEE Signal Processing Letters, 2009, 16(6): 521-524.

[4] Huang Jen-fa, Huang Chun-ming, and Yang Chao-chin.Construction of one-coincidence sequence quasi-cyclic LDPC codes of large girth[J]. IEEE Transactions on Information Theory, 2012, 58(3): 1825-1836.

[5] Zhang Guo-hua, Sun Rong, and Wang Xin-mei. Construction of girth-eight QC-LDPC codes from greatest common divisor[J]. IEEE Communications Letters, 2013, 17(2):369-372.

[6] Park H, Hong S, NO J S, et al.. Design of multiple-edge protographs for QC LDPC codes avoiding short inevitable cycles[J]. IEEE Transactions on Information Theory, 2013,59(7): 4598-4614.

[7] Mohammad G and Ghaffar R. Column weight two and three LDPC codes with high rates and large girths[OL].http://arxiv.org/abs/1403.6090, 2014.4.

[8] Kim S, NO J S, Chung H, et al.. On the girth of tanner (3, 5)quasi-cyclic LDPC codes[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1739-1744.

[9] Zhang Fan, Mao Xue-hong, Zhou Wu-yang, et al.. Girth- 10 LDPC codes based on 3-D cyclic lattices[J]. IEEE Transactions on Vehicular Technology, 2008, 57(2):1049-1060.

[10] 張國華, 陳超, 楊洋, 等. 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.

[11] Zhang Guo-hua, Sun Rong, and Wang Xin-mei. Several explicit constructions for (3, L) QC-LDPC codes with girth at least eight[J]. IEEE Communications Letters, 2013, 17(9):1822-1825.

[12] 張國華, 孫蓉, 王新梅. 圍長為8的QC-LDPC碼的顯示構造及其在 CRT方法中的應用[J]. 通信學報, 2012, 33(3):171-176.Zhang Guo-hua, Sun Rong, and Wang Xin-mei. Explicit construction of girth-eight QC-LDPC codes and its application in CRT method[J]. Journal of Communications,2012, 33(3): 171-176.

[13] Zhang Guo-hua, Sun Rong, and Wang Xin-mei. Deterministic construction of girth-eight (3, L) QC-LDPC codes from quadratic function[J]. Electronics Letters, 2013, 49(9):600-602.

[14] 楊民, 張文彥, 鐘杰, 等. 準循環多進制 LDPC碼構造[J]. 電子與信息學報, 2013, 35(2): 297-302.Yang Min, Zhang Wen-yan, Zhong Jie, et al.. Construction of non-binary QC-LDPC codes[J]. Journal of Electronics &Information Technology, 2013, 35(2): 297-302.

[15] Fossorier M P C. Quasi-cyclic low-density parity-check codes from circulant permutation matrices[J]. IEEE Transactions on Information Theory, 2004, 50(8): 1788-1793.

[16] Hu Xiao-yu, Eleftheriou E, and Amold D M. Progressive edge-growth tanner graphs[C]. Proceedings of the IEEE Global Telecommunications Conference, San Antonio, USA,2001: 995-1001.