基于循环中国剩余定理和改进PEG算法的IRA码

黄　胜，敖　翔，庞晓磊，张　睿

(重庆邮电大学　光通信与网络重点实验室，重庆 400065)



基于循环中国剩余定理和改进PEG算法的IRA码

黄胜，敖翔，庞晓磊，张睿

(重庆邮电大学光通信与网络重点实验室，重庆 400065)

摘要:为了避免交织器产生的时延，通过改进的渐进边增长(PEG)算法和循环中国剩余定理构造了一种不规则重复累积(IRA)码。与常规的IRA码相比，提出的码字具有半随机半结构化形式，不需要设计交织器，且码长选择更加灵活。仿真结果显示，在码率为1/2的条件下，当误码率为10-6时，构造的IRA(1 000，500)码与PEG-IRA(1 000，500)码和基于剩余类数对的IRA(1 000，500)码相比，在对应的相同条件下分别取得了0.2 dB和0.1 dB左右的净编码增益提升；且在码率为3/4时，所构造的IRA(16 200，11 880)码比相同码长和码率的DVB-S2标准LDPC码净编码增益提高了约0.1 dB左右。

关键词:PEG算法；中国剩余定理；不规则重复累积码；净编码增益

低密度奇偶校验(Low Density Parity Check，LDPC)码[1]于1962年提出。近十几年来，LDPC码在纠错编码领域得到了重大发展，被认为是最有希望在广泛的信道范围接近香农极限的误差纠正技术[2]，和Turbo码一起，被广泛应用于编码领域。相比于Turbo码，LDPC码有很多优点，比如LDPC码具有线性译码复杂度[3]，而且当码长较大时，对于非规则LDPC在AWGN信道下几乎达到香农限的优异性能[4]。但是LDPC码的编码复杂度较高，与码长的二次方成正比，而Turbo码的编码复杂度仅码长呈正线性增加。

随着对Turbo码和LDPC码这两种码字的深入研究，学者们找到了一种既具有较低线性编码复杂度又有较低线性译码复杂度的好码字——重复累积(RA)码。RA码最初作为Turbo码中的一种独特的串行结构而被提出，因此也可以把RA码称作“Turbo相似码”[5]。后来又有学者在不规则LDPC码的基础上，设计出不规则RA(IRA)码[6]。

IRA码既可以看作Turbo码，也可以看作LDPC码。近年来，设计构造性能优异的IRA码已经成为了研究的热点[6-10]。由于初期RA码是在Turbo码的基础上提出的，因此传统的IRA码的编码方法需要设计交织器，从而将导致可能带来的时延问题。自从Yang等在文献[7]中提出了能够实现线性编码的LDPC码后，避免重复器、交织器、组合器的设计过程，通过直接设计H1子矩阵研究IRA码的思路受到了LDPC编码学者的亲睐，使得从LDPC码的角度来构造IRA码也受到了极大的关注[8-10]。其中文献[8]是通过PEG算法设计IRA码H1子矩阵，间接对交织器进行构造；文献[9]设计的QC-LDPC码基于等差数列，但是这种线性编码计算量的码型不一定能完全避免短环， 且H2只能构造规则的子矩阵，同时a值固定不可变，灵活性大大受限；文献[10]提出的H2子矩阵是半随机结构，性能优异但其构造受到有限乘群构造的限制而不灵活。同时，由于IRA码通过置信传播译码算法译码，不单要求H1不能含有短环，且H=[H1H2]矩阵中同样要避免短环的存在，否则将会降低译码器的收敛速度，破坏IRA码的误码率性能。

本文综合以上问题，利用循环中国剩余定理和改进的PEG算法构造出了一种新的IRA码。这类构造方法构造的码字在保留IRA码线性编码复杂度优点的基础上，有效地避免了短环的存在。此外，该码不仅有较低的错误平层，而且具有较低的构造复杂度和存储复杂度，从而降低了硬件实现的复杂度及成本。

1IRA码的LDPC结构

由于IRA码是一类特殊的LDPC码，因此它能用Tanner图和校验矩阵H这两种方式分别表达，其Tanner图具体见图1，校验矩阵H=[H1H2]具体用式 (1)表示。

图1　IRA码的LDPC码结构

(1)

式中：IRA码对应的校验矩阵H为m×(m+k)维矩阵，其中，H1是一个列重为[q1，q2，…，qk]，行重为a的随机子矩阵；H2是一个m×m的双对角线结构子矩阵。H1列重由重复器变量q确定，H1行重由组合器的参数a确定，H1里面的每个1元素的位置通过交织器来确定。因此，一旦得到H1子矩阵的同时，也间接地知道了重复器、组合器及其交织器的具体参数。本文从LDPC码的角度直接针对H1的设计，没有涉及交织器的设计，避免可能带来的时延。

2基于改进的PEG和循环中国剩余定理的IRA码构造

1)H1和Hb中的所有项置0。

2)通过PEG算法设计基矩阵Hb时，如果PEG算法中的候选最小度校验节点超过一个且候选校验节点的度d(cu)满足约束条件d(cu) ≤a(0≤u

(1)不管变量节点还是校验节点接收到前面的一层传递过来的ACE值，均从当前节点里面选取值最小的数。

(2)把(1)中传递过来的值和本身的ACE值加在一起，记为值z。且把加在一起的z值传递到与当前节点相互连接的下面所有节点。

3)从1)和2)中得到Hb基矩阵，对Hb的每项为1的元素进行下面步骤：

vtp=t+xmodLp

(2)

(3)

(4)

qtp=tmodLp

(5)

(6)

(7)

如果上述运算过程中得到有相邻行且同一列位置都为1的情况，则停止目前的计算且删除当前的H1矩阵，同时进行x+1操作，接着从3)重新开始。否则直接进行4)。

4)将H1和H2结合起来形成所构造的IRA码的校验矩阵H=[H1H2]。

引理1[13]:设gb为一个基矩阵Hb的围长，gc为由CRT扩展的校验矩阵H的围长，则gc≥gb。

基于引理1，再根据H2的双对角线结构及四环在校验矩阵H中的特点可知，只要H1任意相邻两行同列位置都不同时为1，那么所构造的IRA码不存在短环。

2.1IPEG-CRT算法得到H1矩阵的行列重分析

为了说明一般性，假设Hb第i行经过CRT扩展后有一行的行重为w(w不等于a)。

首先考虑w

w>a的情况同理可得。因此行重为a的基矩阵Hb与经过CRT扩展的H1行重都为a。

列重和行重的分析相似，同理可知当前列列重通过CRT扩展之后的列重不变，因此Hb与H1具有相同的信息节点度分布。

故Hb与H1具有相同的度分布。

2.2IPEG-CRT IRA码的存储复杂度分析

IPEG-CRTIRA码H=[H1H2]的存储复杂度分为两部分：1)H2为双对角线，只需已知第一行一个1和第二行两个1的位置，后面每行在第二行的基础上利用移位寄存器依次可得；2)H1仅考虑利用改进的PEG算法构造的基矩阵Hb，在Hb中的每个1元素行列标的基础上利用CRT结构可以唯一地确定H1矩阵中每个1元素的行列标，很大程度上降低了H1随机矩阵所需要的存储空间。相应地，这也一定程度上降低了硬件实现的复杂度。

通过上述分析可知，无论哪种方法设计的IRA码均具有线性编码复杂度，但是IPEG-CRT IRA码直接利用改进的PEG算法和中国剩余定理构造H1子矩阵，它具有半随机半结构化形式，而非随机构造。因此，所构造的IEPG-CRT IRA码具有较低的存储复杂度，一定程度上降低了硬件实现的复杂度以及所需要的实现成本。同时，所提出的算法在高信噪比区域能保持较低的错误平层以及消除短环。

3性能分析

本文仿真过程：首先编码后利用BPSK 调制，接着经过加性高斯白噪声(AWGN)信道，最后把信道中输出的数据解调后通过置信传播(BP)译码算法恢复原始数据，迭代次数选为50次。

通过改良的度分布[7]构造IRA码，首先令IPEG-CRT IRA码H1子矩阵信息节点的度分布φ(x)=0.238 02x+0.209 97x2+0.034 92x3+0.120 15x4+0.015 87x6+0.004 80x13+0.376 27x14以及a=8(校验节点度分布dc=8)。再根据改进的PEG算法构造125×125阶基矩阵Hb，令s=1，L=4，然后利用公式CRT扩展后得到校验矩阵子矩阵H1，其维数是500×500，最后得到码率为1/2及码长为1 000的校验矩阵H=[H1H2]。为了可以更好地分析本文构造的IRA码的优越性，本文把所构造的IPEG-CRT IRA码在相同条件下与基于PEG算法构造的IRA码、基于剩余类数对构造的IRA码及随机交织器进行比较，仿真结果如图2所示。由图2可知当误码率为10-6时，在1/2码率的情况下，所构造的IPEG-CRT IRA码同基于PEG算法构造的IRA码、基于剩余类数对构造的IRA码相比，均有不同程度的性能提升。当误码率是10-6时，在1/2码率的条件下，所构造的(1 000，500)IPEG-CRT IRA码与文献[8]的(1 000，500)PEG-IRA码相比具有0.2 dB左右NCG的改善，比文献[10]的基于剩余类数对构造的(960，480)IRA码NCG提高了0.1 dB左右，且码长选择更加灵活。同时误码率性能远比随机交织构造的IRA码优秀，且不会存在交织器时延问题。

图2　IPEG-CRT IRA码与其他IRA码性能比较

为了充分说明本文所构造的IRA码的性能和应用潜力，同样根据改进后的PEG算法构造维数为810×2 430的基矩阵Hb，令s=1，L=5，然后利用公式CRT扩展后得到维数4 050×12 150的校验矩阵子矩阵H1，最后得到码率为3/4及码长为16 200的H=[H1H2]。将其与DVB-S2标准LDPC码对比，图3为仿真结果。通过图3表明，在误码率等于10-6情况下，本文构造的IRA码性能优于DVB-S2标准LDPC码，净编码增益提升了约0.1dB。

图3　IPEG-CRT IRA码与DVB-S2标准LDPC码性能比较

4小结

首先通过改进的PEG算法构造出IRA码H1子矩阵的基矩阵，然后利用循环中国剩余定理来构造IRA码。IPEG-CRT方法除了具备常规IRA码较低线性编码复杂度的优势，还在避免短环的同时降低了错误平层，且降低了传统构造IRA码的存储复杂度，这样在很大程度上节省了系统所需要的存储空间，从而减少了硬件实现的成本和复杂度。仿真结果表明，在对应的同等条件下，本文所构造的IRA码优于剩余类数对IRA码和PEG-IRA码。除此之外，优于DVB-S2标准LDPC码，并且不需要设计交织器，可以作为代替卫星通信领域的DVB-S2标准LDPC码的一种选择方案。

参考文献：

[1]GALLAGER R. Low-density parity-check codes[J].IRE transactions on information theory，1962，8(1)：21-28.DOI:10.1109/TIT.1962.1057683.

[2]范文同，马林华，林志国，等. 一类环长至少为10的准循环LDPC码 [J]. 电视技术，2015，39(19)：59-62.DOI：10.16280/j.videoe.2015.19.015.

[3]FOSSORIER M P C，MIHALJEVIC M，INAI H. Reduced complexity iterative decoding of low-density parity check codes based on belief propagation[J]. IEEE transactions on communications，1999，47(5)：673-680.DOI：10.1109/26.768759.

[4]CHUANG S Y，FORNEY Jr G D，RICHARDSON T J，et al. On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit[J]. IEEE communications letters，2001，5(2)：58-60.DOI：10.1109/4234.905935.

[5]JIN H. Analysis and design of turbo-like codes[D]. California ：California Institute of Technology，2001.

[6]鹿增辉，方勇，霍迎秋. 基于滑窗置信传播算法的联合信源信道编码[J]. 电视技术，2015，39 (11)：99-103.DOI：10.16280/j.videoe.2015.11.023.

[7]YANG M，RYAN W E，LI Y. Design of efficiently encodable moderate-length high-rate irregular LDPC codes[J]. IEEE transactions on communications，2004，52(3)：564-571.DOI：10.1109/TCOMM.2004.826367.

[8]CHEN P J，ZHU L X，HU Q，et al. PEG algorithm based interleavers design for systematic IRA codes[C]//Proc. 8th International Symposium on Antennas，Propagation and EM Theory (ISAPE). Kunming：IEEE，2008：1458-1461.DOI：10.1109/ISAPE.2008.4735505.

[9]彭立，朱光喜，吴晓晓. 基于等差数列的LDPC码编码器设计[J]. 电子学报，2007，35(5)：950-954.

[10]彭立，张琦，王渤，等. 针对 IRA-LDPC 码类的半随机半代数结构设计[J]. 通信学报，2014，35 (3)：77-84.DOI：10.3969/j.issn.1000-436x.2014.03.009.

[11]HU X Y，ELEFTHEIOU E，ARNOLD D M. Progressive edge-growth Tanner graphs[C]//Proc. 2001 Global Telecommunications Conference (GLOBECOM′01). San Antonio：IEEE，2001：995-1001.DOI：10.1109/GLOCOM.2001.96556.

[12]TIAN T，JONES C R，VILLASENOR J D，et al. Selective avoidance of cycles in irregular LDPC code construction[J]. IEEE transactions on communications，2004，52(8)：1242-1247.DOI：10.1109/TCOMM.2004.833048.

[13]JIANG X Q，XIA X G，LEE M. Efficient progressive edge-growth algorithm based on chinese remainder theorem[J]. IEEE transactions on communications，2014，62(2)：442-451.DOI：10.1109/TCOMM.2014.011114.130285.

责任编辑：许盈

IRA codes based on cyclic Chinese remainder theorem and improved PEG algorithm

HUANG Sheng, AO Xiang, PANG Xiaolei, ZHANG Rui

(KeyLaboratoryofOpticalCommunicationsandNetwork,ChongqingUniv.ofPostsandTelecommunications,Chongqing400065,China)

Abstract:In order to avoid the delay generated by the interleaver, a kind of irregular repeat accumulation (IRA) code is built by the improved progressive edge growth (PEG) algorithm and the cyclic Chinese remainder theorem. Compared with regular IRA codes, the proposed code has the quasi-randomized and semi-structured forms, and does not need to design the interleaver, and the code length selection is more flexible. The simulation results show that when the bit error rate is 10-6, the net coding gain(NCG) of the proposed IRA(1 000,500) code with the code rate of 1/2 is about 0.2 dB and 0.1 dB higher than those of the PEG-IRA(1 000,500) code and the IRA(1 000,500) code based on residue class respectively. In addition, the NCG of the proposed IRA(16 200, 11 880) code is about 0.1 dB more than that of the DVB-S2 standard LDPC code with the same conditions correspondingly with the code rate of 3/4 and the bit error rate(BER) of 10-6.

Key words:PEG algorithm; CRT; IRA code; NCG

中图分类号：TN911.22

文献标志码：A

DOI：10.16280/j.videoe.2016.05.009

基金项目：国家自然科学基金项目(61571072)；重庆市基础与前沿研究计划项目(cstc2015jcyjA40015)

收稿日期：2015-12-15

文献引用格式：黄胜，敖翔，庞晓磊，等. 基于循环中国剩余定理和改进PEG算法的IRA码[J].电视技术，2016，40(5)：36-39.

HUANG S，AO X，PANG X L，et al. IRA codes based on cyclic Chinese remainder theorem and improved PEG algorithm [J].Video engineering，2016，40(5)：36-39.