利用等差数列构造大围长准循环低密度奇偶校验码

张 轶 达新宇 苏一栋

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.