基本陷阱集优化的IRA-LDPC码设计*

2017-01-03孙康宁马林华

电讯技术 2016年12期

关键词：码字误码率校验

孙康宁，马林华,2，胡星

(1. 空军工程大学航空航天工程学院,西安 710038；2. 西安电子科技大学综合业务网理论及关键技术国家重点实验室,西安 710071)

基本陷阱集优化的IRA-LDPC码设计*

孙康宁**1，马林华1,2，胡星1

(1. 空军工程大学航空航天工程学院,西安 710038；2. 西安电子科技大学综合业务网理论及关键技术国家重点实验室,西安 710071)

具有非规则重复积累结构的低密度奇偶校验(IRA-LDPC)码是一种编码简单、性能优异的信道编码方法。陷阱集是影响码字性能的重要因素，尤其是基本陷阱集。为了进一步提高IRA-LDPC码的纠错性能，针对该码校验矩阵的特殊结构，分析了基本陷阱集的分布特点，提出了一种陷阱集优化的IRA-LDPC码构造方法，该方法依据码字结构特点对基本陷阱集进行了搜索和消除，降低了错误平层。仿真结果显示，优化后的0.5码率、1 024码长的码字在加性高斯白噪声信道下2.2 dB时误码率便达到10-7。

低密度奇偶校验码；非规则重复积累；基本陷阱集；校验矩阵

1 引言

低密度奇偶校验(Low-Density-Parity-Check,LDPC)码由Gallager[1]在1963年提出，并被证明是一种性能逼近香农限的好码[2-3]。LDPC当前的研究方向主要集中在编译码算法和码字构造。在编码算法方面，基于高斯消去的编码和基于近似下三角矩阵的编码是较为经典的编码方法。在译码算法方面，以置信度传播(Belief Propagation,BP)算法为代表的软信息迭代译码应用较为广泛。在校验矩阵构造方面，基于循环校验矩阵分解的构造方法[4]具有较好的纠错性能和较低的编码复杂度。此外，具有非规则重复积累(Irregular Repeat Accumulate,IRA)结构的低密度奇偶校验码也是一类性能优异的LDPC码，并且具有近似线性编码复杂度[5],简称IRA-LDPC码。

文献[6]证明了一定信噪比下当IRA-LDPC码码长趋于无限长时，采用最大似然译码可使其误码率趋近于零。由于其较好的纠错性能与较低的编码复杂度，欧洲数字视频广播(Digital Video Broadcasting,DVB)项目组采用IRA-LDPC码作为DVB-S2标准的信道编码技术，其64 800码长的码字距离香农限仅有0.7 dB，比DVB-S标准提高了3 dB。因此，影响IRA-LDPC码纠错性能的研究具有重要的意义。

文献[7]分析了度2节点和度序列对IRA-LDPC码纠错性能的影响，并给出了优化方法，性能上有一定的提高。文献[8]提出将改进的PEG(Progressive Edge Growth)法用于构造IRA-LDPC码中信息位对应的校验矩阵，获得了不错的纠错效果。文献[9]研究了IRA-LDPC码的图模型结构，并将图模型结构分析的理论应用于码字的构造上，取得了不错的性能。文献[10]提出了一种基于IRA-LDPC码的码率自适应方法，使得其应用更加灵活。

Richardson[11]指出，在高斯信道下，LDPC码均存在着错误平层，这主要是由陷阱集引起的，并且译码过程中绝大多数的突发译码错误都是由于基本陷阱集引起的，其含义见定义1、2。

与变量节点相连的边的数目称为变量节点的度。基本陷阱集大多由低度变量节点组成，如度2和度3节点。在IRA-LDPC码中，存在着大量的度2节点(M-1个)以及度3等低度节点，因此有必要针对IRA-LDPC码中低度节点产生的基本陷阱集进行分析，并将分析的结论应用于码字的构造上，提高其纠错性能，降低错误平层。

本文首先简要介绍了IRA-LDPC码的校验矩阵结构；其次，根据IRA-LDPC码的结构特点，分析了IRA-LDPC码基本陷阱集的分布规律，并根据分布规律消除了部分小规模的基本陷阱集；最后，对提出的优化基本陷阱集的码字进行了性能仿真。

2 IRA-LDPC码基本结构

IRA-LDPC码的校验矩阵H可分为两部分：

H=[H1,H2]。

(1)

式中：H1为信息位所对应的M×(N-M)维的校验矩阵；H2为校验位所对应的M×M维校验矩阵，采用如式(2)中所示的双对角线结构：

(2)

采用这样的结构，可以采用贪婪算法实现一部分校验位的线性求解，从而降低整个编码过程的复杂度。整个校验矩阵中的度2变量节点占变量节点总数的M-1/N，存在1个度为1的变量节点。H1中不含度2节点，且多采用PEG[12]法构造，以保证码字构造的随机性。由于H2结构固定，因此优化IRA-LDPC码结构设计主要集中在构造H1的过程中，要满足某个度序列的要求，也只能对H1进行调整。

3 基本陷阱集分析

定义1[13]：(w,v)陷阱集T是指一个由w个变量节点组成的集合，并且满足在这w个变量节点及v个校验节点组成的子图中，包含v个度为奇数的校验节点，变量节点个数w表示陷阱集的大小。

定义2[13]：在(w,v)陷阱集T中，如果每一个校验节点的度为1或2，则称之为基本陷阱集。

在二进制删除信道(Binary Erasure Channel，BEC)和加性高斯白噪声(Additive White Gaussian Noise，AWGN)信道下，引起LDPC码错误平层的主要原因是陷阱集的存在[13]，且大多数错误都是由于基本陷阱集引起的。基本陷阱集由低度变量节点组成，如度2和度3节点。且一般来说，w、v的值越小，译码过程中越容易出现因陷阱集T引起的误码。

就IRA-LDPC码而言，由于存在大量低度变量节点，因此在构造H1的过程中要尽量避免基本陷阱集的产生。

在IRA-LDPC码校验矩阵中，由于H2采用双对角线结构，因此所有度2变量节点和一个度1变量节点及其相连校验节点的Tanner图组成一条首尾不闭合的“2链”，如图1所示，实心圆代表变量节点，空心方形代表校验节点。

图1 IRA-LDPC码中“2链”Tanner图

Fig.1 The Tanner of “2 chains” in IRA-LDPC codes

随机挑选“2链”中任意n个不包含度1的相邻变量节点，都会形成一个(n,2)陷阱集；挑选“2链”中任意n个包含度1的相邻变量节点，也会形成一个(n,1)陷阱集，这部分陷阱集是无法消除的，因此，本文致力于在构造过程中消除有度3节点参与的基本陷阱集,且v≤1。

通常，基本陷阱集由低度变量节点及其相邻校验节点组成的环所构成[13]。设所构造的码字低度变量节点对应的校验矩阵整体围长为girth，这其中存在大量如图2所示的规模大于等于girth/2的陷阱集，即a≥girth/2。

图2 (a,0)和(a,1)基本陷阱集

Fig.2 The elementary trapping sets of (a,0)and(a,1)

然而，由于IRA-LDPC码字的双对角线结构，任意相邻的度2变量节点组成的都是首尾不封闭的“2链”，这使得不会存在如图2(a)所示的完全由度2变量节点构成的陷阱集，因此，可将限定规模内的基本陷阱集分成以下几种情况：

情况1：有1个度3变量节点参与

由于校验位所对应的变量节点采用双对角线结构，因此，对于一个度3变量节点所对应的列，任意两个非零元素的行坐标之差为a-1时，就会引入一个由a-1个度2变量节点和1个度3变量节点组成的陷阱集(a,1)。即如果度3变量节点所对应列的3个非零元素的任意两个的行坐标为ci、cj满足|ci-cj|≡a-1，则存在一个如图2(b)所示的(a,1)陷阱集。

情况2：有2个度3变量节点参与

根据IRA-LDPC码结构特点，设v1、v2为任意两个度3的变量节点，与其相连的边的集合分别为{e1,e2,e3}、{e4,e5,e6}。以变量节点v1为根节点，展开其相邻节点的Tanner图，并记录所经过的路径，从{e1,e2,e3}开始，追踪深度最大为2a-4，一旦某条路径深度大于2a-4，则放弃该条路径；一旦路径经过除v2外的其他度3变量节点，则放弃该条路径。即如果全部满足下列条件，则存在一个如图2(c)所示的(a,0)陷阱集。

(1)有一条路径可以连通e1、e4；

(2)有一条路径可以连通e2、e5；

(3)有一条路径可以连通e3、e6；

(4)除根节点和目的节点外，路径上所有变量节点数量之和为a-2；

(5)根节点到目的节点的任意一条路径长度不超过2a-4。

情况3：有3个度3变量节点参与

与由2个度3变量节点参与时的情况类似，只是当有3个度3变量节点参与时，根节点和目的节点之间的路径上会存在1个度3变量节点。即如果全部满足下列条件，则存在一个如图2(d)所示的(a,1)陷阱集。

(1)有一条路径可以连通e1、e4；

(2)有一条路径可以连通e2、e5；

(3)有一条路径可以连通e3、e6；

(4)除根节点和目的节点外，路径上所有变量节点数量之和为a-2；

(5)根节点到目的节点的任意一条路径长度不超过2a-4；

(6)所有路径经过度3变量节点的数量为1。

4 基本陷阱集优化

本文构造了基于优化陷阱集的IRA-LDPC码，搜索陷阱集的规模为a，步骤如下：

Step 1 初始化校验位所对应的校验矩阵H2，使其满足式(2)所示的双对角线结构；

Step 2 利用PEG法构造信息位所对应的校验矩阵H1，并使整体度序列满足优化的IRA-LDPC码度序列，在分配度3节点边时，避免出现度3节点所在列的非零元素行坐标出现|ci-cj|≤a-1的情况，以消除图2(b)所示的(a,1)陷阱集；

Step 3 按照上节所述情况2、3中陷阱集的搜索方法，记录所有(a,0)、(a,1)陷阱集；

Step 4 找到的陷阱集进行两两分组，将两个陷阱集中度3变量节点的其中一条边进行交换，如图3所示，以消除陷阱集；

Step 5 如果陷阱集总数为奇数，则删除剩余的1个陷阱集中度3变量节点的任意一条边。

图3 (a,0)和(a,1)基本陷阱集消除

Fig.3 Deleting the elementary trapping sets of (a,0)and(a,1)

5 性能仿真

在加性高斯白噪声信道下，对本文构造的IRA-LDPC码、未进行优化的IRA-LDPC码以及文献[7]和文献[8]构造的IRA-LDPC码性能进行了仿真。具体仿真参数设置为：码长分别为1 024和2 048，码率为0.5；信道环境为加性高斯白噪声信道，调制方式为BPSK调制；采用对数似然译码算法进行译码，最大迭代次数为100次。译码过程中出现100个错误帧时计算此时的误码率和误帧率，结果比较如图4和图5所示。

图4 1 024码长误码率比较

Fig.4 Comparison of BER for the length of 1 024

图5 1 024码长误帧率比较

Fig.5 Comparison of FER for the length of 1 024

从图4和图5可以看出，不论是误码率还是误帧率，本文提出的基本陷阱集优化的IRA-LDPC码均具有一定的优势，与文献[8]构造的LDPC码相比，提出的码字在信噪比大于1.5 dB时体现出了明显的优势，10-5误码率时性能提高约0.15 dB，10-6误码率时性能提高约0.4 dB；与未进行优化的IRA-LDPC码相比，本文所构造的码字在信噪比为0.5～2.5 dB环境下纠错性能较好，2 dB时误码率可降低一个数量级，误帧数量降低约90%；与文献[7]中构造的LDPC码相比，本文构造的IRA-LDPC码在信噪比为0.5～2.5 dB的范围内在误码率和误帧率上均具有一定优势，且在2.2 dB时误码率优先降至10-7数量级。图6和图7是在码长为2 048、码率为0.5时对各类码字的误码率和误帧率的仿真。

图6 2 048码长误码率比较

Fig.6 Comparison of BER for the length of 2 048

图7 2 048码长误帧率比较

Fig.7 Comparison of FER for the length of 2 048

由上述2 048码长时的性能仿真图可以看出，本文提出的码字在信噪比大于1 dB时性能优势开始体现，10-6误码率时性能较未优化的IRA-LDPC码、文献[7]和文献[8]优化的码字分别提高约0.1 dB、0.06 dB和0.1 dB，10-4误帧率时性能也提高了约0.14 dB、0.1 dB和0.12 dB。

6 结论

本文分析了IRA-LDPC码基本陷阱集的结构特点，并将其应用于码字构造过程中，提出了一种基本陷阱集优化的IRA-LDPC码构造方法。仿真结果显示，本文优化的IRA-LDPC码在纠错性能上较未优化的IRA-LDPC码以及文献[7]和文献[8]中构造的码字均有一定提高。此外，本文构造的码字在高信噪比下依然存在一定的错误平层现象，这可能是由于本文仅针对(a,0)、(a,1)陷阱集进行分析优化，而对于更大规模陷阱集的快速搜索和优化问题，仍需在下一步的研究中改进。

[1] GALLAGER R G.Low density parity-check codes[J].IEEE Transactions on Information Theory,1962,8(1):21-28.

[2] MACKEY D J C.Good error-correcting codes based on very sparse matrices[J].IEEE Transactions on Information Theory,1999,45(2):399-431.

[3] 袁建国,李媛媛,梁梦琪,等. 利用完备差集构造QC-LDPC 码[J]. 电讯技术,2016,56(5):471-475. YUAN Jianguo,LI Yuanyuan,LIANG Mengqi,et al. Constructing QC-LDPC codes by using perfect difference families[J]. Telecommunication Engineering,2016,56(5):471-475.(in Chinese)

[4] HUANG Q,DIAO Q J,LIN S. Circulant decomposition:cyclic,quasi-cyclic and LDPC codes[C]//Proceedings of 2010 International Symposium on Information Theory and its Applications.Taichung,Taiwan,China:IEEE,2010:383-388.

[5] JIN H,KHANDEKARAND A,MCELIECE R.Irregular repeat-accumulate codes[C]//Proceedings of Second International Conference on Turbo and Related Topics.Breast,France:Springer Press,2000:1-8.

[6] DIVSALAR D,JIN H,MCELIECE R.Coding theorems for Turbo-like codes[C]//Proceedings of 36th Annual Allerton Conference on Communication Control and Computing. Monticelo:IEEE,2001:201-210.

[7] 黎新,傅强,文磊.IRA码结构优化与高斯逼近分析[J].四川大学学报(工程科学版),2007,39(5):159-163. LI Xin,FU Qiang,WEN Lei. Analysis for gaussian approximation and structure optimization of IRA codes[J].Journal of Sichuan University(Engineering Science Edition),2007,39(5):159-163.(in Chinese)

[8] 胡军锋,张海林,白洁,等. 短长度非规则重复累积码的构造[J].吉林大学学报(工学版),2010,40(1):255-259. HU Junfeng,ZHANG Hailin,BAI Jie,et al. Construction of short-length irregular repeat-accumulate code[J].Journal of Jilin University(Engineering and Technology Edition),2010,40(1):255-259.(in Chinese)

[9] LEI Q,WEN L,CHEN B. Analysis of graphical model and construction algorithm of IRA-Like codes[C]//Proceedings of Asia-Pacific Conference on Information Theory. Beijing:IEEE,2010:112-118.

[10] BENMAYOR D,MATHIOPOULOS P T,PHILIP C.Rate-compatible IRA codes using quadratic congruential extension sequences and puncturing[J].IEEE Communication Letters,2010,14(5):441-443.

[11] RICHARDSON T.Error floors of LDPC codes[C]//Proceedings of 41st Annual Allerton Conference on Communication Control and Computing. Monticelo:IEEE,2003:110-119.

[12] HU Y,ELEFTHERIOU E,ARNOLD D M.Regular and irregular progressive edge growth Tanner graphs[J].IEEE Transactions on Information Theory,2005,51(1):386-398.

[13] SINA K,REZA A,AMIR H.A PEG construction of finite-length LDPC codes with low error floor[J].IEEE Communication Letters,2012,16(8):1288-1291.

SUN Kangning was born in Zibo,Shandong Province,in 1991. He is now a graduate student. His research concerns channel coding and anti-interference communication.

Email:15353744007@163.com

马林华(1965—)，男，陕西汉中人，2006年于西安电子科技大学获博士学位，现为教授、博士生导师，主要研究方向为无线自组织网络和信道编码;

MA Linhua was born in Hanzhong,Shaanxi Province,in 1965. He received the Ph. D. degree from Xidian University in 2006. He is now a professor and also the Ph.D. supervisor. His research concerns wireless ad hoc networks and channel coding.

Email:lang_max@163.com

胡星(1990—)，男，河南南阳人，博士研究生，主要研究方向为多信道接入技术。

HU Xing was born in Nanyang,Henan Province,in 1990. He is currently working toward the Ph.D. degree. His research concerns multi-channel access technology.

Email:xingxing111@163.com

Construction of IRA-LDPC Codes with Elementary Trapping Sets Optimized

SUN Kangning1,MA Linhua1,2,HU Xing1

(1.Aeronautics and Astronautics Engineering Institute,Air Force Engineering University,Xi′an 710038,China；2.The State Key Laboratory of Integrated Services Networks,Xidian University,Xi′an 710071,China)

Irregular repeat accumulate low-density-parity-check(IRA-LDPC) codes have low encoding-complexity and good performance in correcting errors. Trapping sets are key factors to the performance of the codes,especially the elementary trapping sets. In order to improve the error-correcting capacity,according to the characteristic of the structure for parity matrix,the distribution of elementary trapping sets is analyzed,and a construction method of IRA-LDPC codes is proposed. This method based on the construction of the codes can search and eliminate the elementary trapping sets,which lowers the error-floor. As can be seen from the simulation,the bit error rate(BER) reaches 10-7at 2.2 dB with optimized IRA-LDPC codes with 1 024 code-length and 0.5 code-rate in additive white Gaussian noise(AWGN) channel.

LDPC codes；irregular repeat accumulate；elementary trapping sets；parity-check matrix

10.3969/j.issn.1001-893x.2016.12.013

孙康宁，马林华，胡星.基本陷阱集优化的IRA-LDPC码设计[J].电讯技术，2016,56(12):1376-1380.[SUN Kangning,MA Linhua,HU Xing.Construction of IRA-LDPC codes with elementary trapping sets optimized[J].Telecommunication Engineering,2016,56(12):1376-1380.]

2016-04-12；

2016-06-28 Received date:2016-04-12；Revised date：2016-06-28

综合业务网理论及关键技术国家重点实验室(西安电子科技大学)开放研究课题(INS-15-13)

Foundation Item:The Open Foundation of The State Key Laboratory of Integrated Services Networks(Xidian University)(INS-15-13)

TN911.22

1001-893X(2016)12-1376-05