基于杨辉三角结构的QC-LDPC码构造

张轶¹，达新宇¹，褚振勇²

(1. 空军工程大学 信息与导航学院，陕西 西安，710077；

2. 空军工程大学 科研部，陕西 西安，710051)

摘要：针对准循环低密度奇偶校验(QC-LDPC)码中准循环基矩阵的移位系数确定问题，提出基于杨辉三角结构的确定方法。该方法构造的校验矩阵不含四环，移位系数由简单的数学表达式确定，编码复杂度与码长呈线性关系，节省存储空间，对码长和码率参数的设计具有较好的灵活性。仿真结果表明：在加性高斯白噪声信道和BP译码算法下，该方法构造的码字在误比特率为10^-4时，信噪比优于随机LDPC码接近0.3 dB，在误比特率为10^-6时优于DVB-S2标准的LDPC码0.2 dB，并可以获得与IEEE 802.16e码相一致的性能。同时表明合理的选择循环移位矩阵的尺寸，可以改善码字的误比特率性能。

关键词：准循环低密度奇偶校验码；杨辉三角；循环移位系数；高效编码

中图分类号：TN911.2            文献标志码：A         文章编号：1672-7207(2014)03-0755-07

Construction of QC-LDPC codes based on Yang Hui triangle

ZHANG Yi¹, DA Xinyu¹, CHU Zhenyong²

(1. School of Information and Navigation, Air Force Engineering University, Xi’an 710077, China;

2. Department of Scientific Research, Air Force Engineering University, Xi’an 710051, China)

Abstract: For the issue of determining cyclic shift coefficients of the quasi-cyclic sub-matrix in the quasi-cyclic low-density parity-check, a method was presented based on Yang Hui triangle to compute the cyclic shift coefficients. By this method, cyclic shift coefficients could be expressed in simple analytic expressions, and cycles of length four in parity matrix were eliminated. The parity matrix is quasi-cyclic to save required memory and is prone to coding and decoding, and has high flexibility with respect to the design of code length and rate. Over an additive white Gauss noise channel and under the BP decoding algorithm, simulations show that the SNR of the QC-LDPC codes with the proposed algorithm is better than random codes close to 0.3 dB at the BER performance of 10^-4 and better than the LDPC codes in DVB-S2 0.2 dB at the BER performance of 10^-6. Moreover, the BER performance of the new codes is no less than the LDPC codes in IEEE 802.16e under the same conditions. Furthermore, the simulation result also indicates that by making a reasonable choice of the size of the cyclic shift matrix, the BER performance of the codeword can be improved.

Key words: quasi-cyclic low-density parity-check (QC-LDPC) codes; Yang Hui triangle; cyclic shift coefficients; efficient encoding

低密度奇偶校验(LDPC)码^[1]最初由Gallager提出，是一种基于稀疏校验矩阵的线性分组码。正是其校验矩阵的稀疏性，保证了译码复杂度只随码长呈线性增加，是一种性能逼近Shannon限的好码，因此近年来一直是纠错编码领域的热点。目前国际上对LDPC码的研究已取得重要进展，基于LDPC码的编码方案也被诸多标准所采纳^[2-5]。码的结构决定了LDPC码的性能。随机构造的LDPC码虽然纠错性能好，但其校验矩阵中1的分布没有规律，其码树上的校验节点和信息节点的连接没有规律^[6]，需要存储生成矩阵和校验矩阵的所有行向量，造成编码复杂，因此在其编解码的超大规模集成电路(VLSI)上实现较为困难。基于循环移位矩阵构造的QC-LDPC码，其校验矩阵的准循环特性使其易于高效编解码，码的代数结构给VLSI的实现提供了可能，因此对QC-LDPC码构造的研究具有实际意义。针对上述问题，国内外学者屡有成果涌现。张丽丽等^[7]、詹伟等^[8]、朱磊基等^[9]分别利用Z形及等差数列、斐波那契数列、大衍数列构造了QC-LDPC码，但都没有从量化角度描述编码优势；张国华等^[10]构造出一种围长至少为8的QC-LDPC 码的显式框架，构造的循环移位矩阵尺寸具有连续变化的优点，但该方法侧重于理论分析，缺乏仿真支撑；Huang等^[11]提出了单重合序列QC-LDPC码的构造方法，讨论了围长对编码性能的影响，然而对循环移位矩阵尺寸如何选取并没有给出具体分析。在此基础上，本文作者提出利用杨辉三角构造QC-LDPC码的方法。首先提出具体的构造方案，通过理论推导证明了该码无四环，并简要分析了六环分布情况；进一步详细计算了编码复杂度，定量的给出了编码算法的运算量；最后通过软件仿真，验证了杨辉型QC-LDPC码具备优异的性能。

1  QC-LDPC码

QC-LDPC码是一类非常特殊的高度结构化的LDPC码，它的校验矩阵以单位阵的循环移位阵和零方阵为子阵。下式给出的是一个4×4的循环移位阵：

               (1)

该矩阵由单位阵每行向右移2位得到，记为。该矩阵可由其维数与循环移位系数唯一确定。

    QC-LDPC码的奇偶校验矩阵H可表示为如下形式：

        (2)

其中：为一个的循环移位矩阵，。可知就是单位阵，零方阵用表示。把循环右移系数写成一个矩阵P，称为准循环基矩阵，如式(3)所示。当P确定后，校验矩阵H也随之确定。

          (3)

在基矩阵P中，若干个点(元素)p₁, p₂, …, p_2k构成一个环，则对应的H矩阵也存在与之对应的p个同样大小的环。显然，环的长度只能是大于或等于4的偶数。表示H中长为2k环的序列(p₁, p₂, …, p_2k)满足如下定理：

定理1^[12]：对于基矩阵P中的序列(p₁, p₂, …, p_2k)，其中p_i和p_i+1在同一行或同一列，p_i和p_i+2在不同行且不同列，则(p₁, p₂, …, p_2k)构成长为2k环的充要条件是：

           (4)

短环的存在使LDPC码在译码时不能快速收敛，甚至不能收敛，造成误比特率性能变差。因此，为了使QC-LDPC码的校验矩阵不含长为2k的环，就必须通过某种设计，使得式(4)不成立。虽然没有明确的标准指出无短环到底是不能有长度是几的环，但有一点是确定的，即码至少不能有四环。

下面给出四环检验定理，用以检验构造的矩阵是否含有四环：

定理2^[13]：给定M×N校验矩阵H，设辅助矩阵，当且仅当，辅助矩阵O除了主对角线元素以外的其他元素全为1或0时，校验矩阵H没有四环。

2  利用杨辉三角构造QC-LDPC码

传统的LDPC码编码时需要用到生成矩阵G，由于其本身不具有稀疏性，导致编码的运算次数和存储空间大大增加。本文采用具有下三角结构的校验矩阵，并未采用生成矩阵就可直接编码，大幅度降低了编码的复杂度。

将校验矩阵H分为信息部分H_a和校验部分H_b，即：

                (5)

其中：H_a大小为，H_b为准双对角线结构，即循环移位矩阵采用双对角线，大小为。该矩阵的具体形式为：

     (6)

式中：H_a由个大小为的循环移位矩阵构成，I和分别表示p阶单位阵和零矩阵。由此可以看到，对校验矩阵H的构造关键在于对信息部分H_a的构造。

2.1  杨辉三角结构

杨辉三角是大家所熟知的一个特别的“数字图形”，如图1所示。其构造方法为：第1行为1，以下各行两端都是1，除1以外的每个数等于它左右肩上两数之和，由此可以写出整个杨辉三角。因此，

图1  杨辉三角

Fig. 1  Yang Hui triangle

杨辉三角的最大特点就是数与数之间存在着紧密的“相关性”，依靠“初始值”和简单的运算法则即可得到任意大小的数字排列。

将这个三角形逆时针旋转45°，再改写成矩阵的形式，可以得到如下矩阵：

           (7)

考虑利用式(7)的结构特点构造信息部分H_a。

若H_a的基矩阵P直接由矩阵a定义，即a中元素代表循环移位系数p_ij，则构造的H显然存在大量四环，与设计要求不符。因此，提出一种无四环的QC-LDPC码构造方法，具体描述如下：

(1) 构造一个严格单增的正整数序列{x_i}，；

(2) 当i=1时，令，1≤j≤k；当j=1时，令p_i1=x_i，1≤i≤m；

(3) 当2≤i≤m且2≤j≤k时，令。构造完毕，从而获得H_a的基矩阵P。

通过上述构造方法可以得出以下结论：基矩阵P中的首行(首列)元素即为{x_i}中的前k(前m)个序列值；同行(同列)元素中，行(列)指数越大，元素值越大；对于校验部分H_b，其基矩阵中的元素不会与P中元素构成四环，因此只需验证H_a无四环。

若基矩阵P中不存在四环，则应满足如下定理：

定理3：设，且，，则

       (8)

证明：不失一般性，设n＞m，s＞t，则

＞     (9)

注意到0＜＜p和0＜＜p，所以式(8)对P中任意元素都成立，证毕。

由此，可以构造出无四环的QC-LDPC码。

例1  按照上述规则构造的2种杨辉型QC-LDPC码基矩阵如下：

当x_i=i时，{x_i}为等差数列，则

            (10)

当时，{x_i}为等比数列，则

           (11)

2.2  六环检验

图2所示为6种不同形状的六环^[6]。

图2  6种不同形状的六环

Fig. 2  Six different kinds of cycles of length six

如果只考虑信息部分H_a，利用定理3给出的方法和结论，可证明P中不包含形如图2(a)～(e)的六环；而由式(10)或(11)所示结构可以看出，矩阵中的元素关于主对角线对称，因此H必然存在以主对角线为对称轴的六环，形如图2(f)所示。

若同时考虑校验部分H_b，则H还会存在形如图2(a)的六环。

2.3  编码复杂度分析

利用LU分解法^[14]，令信息比特向量为，校验比特向量为，编码器输出行向量为c，它的长度，则有：

               (12)

根据校验等式可得：

           (13)

由于运算在GF(2)中进行，所以得到：

          (14)

将式(14)展开将得到m个等式，将各个等式相加得到：

         (15)

将式(15)代回到方程组式(14)的第(1)式可得：

        (16)

将式(16)代回到方程组式(14)的第(2)式可得，依此类推可得迭代等式：

      (17)

    得到了各个p_i后，通过就可求得校验比特向量p，令，编码完毕。

编码复杂度主要关注编码过程的运算量、运算复杂度和编码所需存储的参数^[6]。运算量即乘法和加法次数，运算复杂度即运算量与码长的变化关系。本文提出的杨辉型QC-LDPC码的迭代算法中，各个基矩阵都是稀疏矩阵，因此按照稀疏矩阵的运算方式可以大大减小运算量。现计算式(15)和式(17)的运算量如表1所示(其中，表示码率)：

表1  编码算法的运算量

Table 1  Computation of coding algorithm

从表1可以看到：计算各个校验分向量p_i的运算复杂度为O(N)，即运算复杂度与码长呈线性关系。根据表1计算出总的乘法次数为：

            (18)

分析式(18)可以得到，当码长N一定时，分组长度p越大则乘法运算量越小。总的加法次数为：

        (19)

根据上式，显然当码长N一定时，分组长度p越大则加法运算量越小。

由于杨辉型QC-LDPC码的构造采用代数构造法，校验矩阵中的元素由数学表达式计算得到，只需要存储一组序列和一个数学表达式即可，编码器的实际存储量需求非常小。

3  仿真与分析

在AWGN信道下进行仿真，码率R=1/2，译码采用BP算法，最大迭代次数为30，调制方式为BPSK。

仿真1：杨辉型QC-LDPC码的四环检验

利用例1构造的2种基矩阵生成校验矩阵的信息部分，校验部分采用准双对角线结构，选取p=64，码长N=512。2种QC-LDPC码分别命名为杨辉-1码和杨辉-2码，四环验证结果如图3所示。

图3  杨辉型QC-LDPC码的四环检验

Fig. 3  Prove of cycle of length four for Yang Hui’s codes

仿真结果表明：2种杨辉码的辅助矩阵O中，除了主对角线元素以外的其他元素全为1或0，满足定理2，验证了本文所提构造方法的正确性。

仿真2：杨辉码与随机LDPC码的比较

采用仿真1中的两类杨辉码，并选取MacKay码^[15]和PEG(Progressive Edge-Growth)码^[16]作为典型的随机码进行比较。2种随机码列重均为3，码长码率不变；其中对PEG码进行校验节点的度数分布优化，度分布多项式为。仿真结果如图4所示。

仿真结果表明，杨辉码的性能明显优于2种随机码，当误比特率达到10^-4时，信噪比增益为0.25~0.3 dB；2种杨辉码在信噪比小于1 dB时可以获得相一致的性能，但随着信噪比增大，杨辉-1码的增益显著。之所以出现这种现象，是由于2种码字采用不同的结构造成的。由式(11)的结构特点可以发现：矩阵的反对角线元素是一样的，这就会形成以次对角线为对称轴的六环，导致六环数目要多于杨辉-1码，影响了误比特率性能。

图4  杨辉码与随机码的比较

Fig. 4  Comparison of Yang Hui’s codes and random codes

仿真3：p值对杨辉码性能的影响

采用杨辉-1码结构，码长N=1 920，选取p分别为320，240和192。仿真结果如图5所示。

图5  p对杨辉码性能的影响

Fig. 5  Effect of different p for Yang Hui’s codes

仿真结果表明：不同p的杨辉码的性能差异明显。当p=320时，杨辉-1码的BER性能甚至不如仿真1中短码长的杨辉-2码。之所以出现显著的差异，是因为p越大即循环移位矩阵越大，则在同等码长下的准循环基矩阵尺寸越小，意味着比特节点的度数越小，导致译码时所获取的置信信息就越少，造成BER性能降低。同时还应注意到，从杨辉QC-LDPC码的特点可以看出，随着基矩阵的行(列)数增多，循环移位系数的最大值变大，这就要求p的取值增大，则构造出的码长越长。因此在设计基矩阵时，应在满足码长要求及合理的p约束下，尽可能地选取较大的行(列)指数，以获取更优的性能。

仿真4：杨辉码与IEEE 802.16e和DVB-S2标准LDPC码的比较。

采用杨辉-1码结构，选取p=540，码长N=5 400。对IEEE 802.16e，DVB-S2标准的LDPC码选取同码长码率的校验矩阵^[17]。仿真结果如图6所示。

图6  杨辉码与IEEE 802.16e, DVB-S2标准LDPC码的比较

Fig. 6  Comparison of Yang Hui’s codes, IEEE 802.16e-LDPC and DVB-S2-LDPC

仿真结果表明：杨辉码与IEEE 802.16e码的性能差异不大，二者的BER曲线始终呈现明显的快速衰落趋势；当信噪比小于0.6 dB时，3种码字可以获得相一致的性能，但随着信噪比增大，杨辉码的性能要好于DVB-S2码，当误比特率达到10^-6时，信噪比增益为0.2 dB。这是由于DVB-S2标准采用的双对角线结构会影响码的BER性能，仿真结果亦证实了文献[3]的结论。本文设计的杨辉码采用准双对角线结构进行迭代编码，不但编码简单，而且在AWGN信道下可以获得较好的性能。

4  结论

提出了一种基于杨辉三角结构确定循环移位系数的方法，构造了无四环的QC-LDPC码。该码的准循环基矩阵由数学表达式确定，构造方法简单，节省了编解码存储空间。研究结果表明：杨辉型QC-LDPC码实现高效编码的同时，在AWGN信道中能够获得较高的纠错能力，因此对信道编码理论的研究和应用具有一定的参考价值，下一步将对该码应用于多载波宽带通信系统进行深入研究。

参考文献：

[1] Gallager R G. Low-density parity-check codes[J]. IRE Trans on Inf Theory, 1962, 8(3): 21-28.

[2] IEEE P802.16e/D8, IEEE standard for local and metropolitan area networks Part 16: Air interface for fixed and mobile broadband wireless access systems[S].

[3] Draft ETSI EN 302 307 V1.1.1, European Standard (Telecommunication sseries) Digital Video Broadcasting (DVB)[S].

[4] CCSDS 131.0-P-1.1, Consultative Committee for Space Data Systems (CCSDS), Tm Synchronization and Channel Coding, Draft Recommendation for Space Data System Standard[S].

[5] GB20600, 中国数字电视地面广播标准[S].

GB20600, Chinese digital terrestrial television broadcasting standard[S].

[6] 肖扬. Turbo与LDPC编解码及其应用[M]. 北京: 人民邮电出版社, 2010: 1-248.

XIAO Yang. Turbo and LDPC codes and their applications[M]. Posts & TelecomPress, Beijing, 2010: 1-248.

[7] 张丽丽, 赵泽茂, 包建荣. 基于Z形及等差数列结构的QC-LDPC码构造[J]. 通信学报, 2010, 31(8A): 117-121.

ZHANG Lili, ZHAO Zemao, BAO Jianrong. Construct of QC-LDPC codes based on Z-shape and arithmetic progression sequence[J]. Journal on Communications, 2010, 31(8A): 117-121.

[8] 詹伟, 朱光喜, 彭立. 利用斐波那契数列构造QC-LDPC码的方法[J]. 华中科技大学学报(自然科学版), 2008, 36(10): 63-65.

ZHAN Wei, ZHU Guangxi, PENG Li. Design of QC-LDPC codes using Fibonacci sequence[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2008, 36(10): 63-65.

[9] 朱磊基, 汪涵, 施玉松, 等. 利用大衍数列构造QC-LDPC码的方法[J]. 西安电子科技大学学报(自然科学版), 2012, 39(3): 163-170.

ZHU Leiji, WANG Han, SHI Yusong, et al. A method of construct QC-LDPC codes using Dayan sequence[J]. Journal of Xidian University (Natural Science Edition), 2012, 39(3): 163-170.

[10] 张国华, 王新梅. 围长至少为8的QC-LDPC码的新构造: 一种显示框架[J]. 电子学报, 2012, 40(2): 331-336.

ZHANG Guohua, WANG Xinmei. Novel constructions of QC-LDPC codes with girth at least eight: An explicit framework[J]. Acta Electronic Sinica, 2012, 40(2): 331-336.

[11] HUANG Jenfa, HUANG Chunming, YANG Chaochin. Construction of one-coincidence sequence quasi-cyclic LDPC codes of large girth[J]. IEEE Trans on Inf Theory, 2012, 58(3): 1825-1836.

[12] Fossorier M P C. Quasi-cyclic low-density parity-check codes from circulant permutation matrices[J]. IEEE Trans on Inf Theory, 2004, 50(8): 1778-1793.

[13] Xiao Y, Lee M H. Low complexity MIMO-LDPC CDMA systems over multipath channels[J]. IEICE Trans Commun, 2006, 89(5): 1713-1717.

[14] MacKay D J C, Wilson S T, Davey M C. Comparison of constructions of irregular Gallager codes[J]. IEEE Transactions on Communications, 1998, 42(10): 1449-1455.

[15] MacKay D J C. Good error-correcting codes based on very sparse matrices[J]. IEEE Trans on Inf Theory, 1999, 45(2): 399-431.

[16] HU Xiaoyu, Evangelos Eleftheriou, Dieter Michael Arnold. Progressive edge-growth tanner graphs[C]//IEEE Global Telecommunications Conference. San Antonio, Texas, USA: Globecom, 2001: 995-1001.

[17] 肖扬, 范俊, 黄希. DVB-S2标准的LDPC码改进[J]. 铁道学报, 2011, 33(2): 52-59.

XIAO Yang, FAN Jun, HUANG Xi. Improvement in LDPC Codes in DVB2S2 standard[J]. Journal of the China Railway Society, 2011, 33(2): 52-59.

(编辑  陈爱华)

收稿日期：2013-03-16；修回日期：2013-05-12

基金项目：国家自然科学基金资助项目(60972042，61271250)

通信作者：张轶(1986-)，男，山西太原人，博士研究生，从事通信信号处理研究；电话：13572879005；E-mail: zhangyi1290@163.com