基于LTE－QC结构的速率兼容LDPC码优化构造方法

李万臣，高毓亮，齐 欢

(哈尔滨工程大学信息与通信工程学院，哈尔滨150001)

低密度奇偶校验(Low Density Parity Check，LDPC)码是一种先进的具有逼近香农限的优良性能信道编码技术.最初由Gallager发现，经过数十年的沉寂，LDPC码被重新重视，Hagenauer在文献[1]中提出让校验矩阵通过删除不同的子矩阵来使码编码后的码字得到不同的码率.这种码被称作速率兼容删除型卷积码(RCPC).构造出的RCPC码解决了码率可变的问题，使用删除来改变码率的思路也为后来纠错码的发展提供了一条道路，例如速率1兼容低密度校验码(RC－LDPC)[2]和速率兼容删除型turbo码(RCPT)[3].因为LDPC的性能优越、形式简洁、在实际应用方面具有广阔的前景，近些年来其备受关注，可以应用于光纤通信、磁/光全存储、卫星数字视频和音频广播、图像压缩传输等，而且DVB－S2的标准草案中也采用可LDPC码，我们可以预想到，LDPC码及相应的速率兼容LDPC码以其优良的性能，也将给以后的无线移动通信事业带来巨大帮助.然而目前对于速率兼容LDPC码的研究还很有限，在现有的对于速率兼容LDPC码研究中往往也忽略了很多问题，致使LDPC码的译码性能有待进一步改善.

1 QC－LDPC和速率兼容LDPC码

准循环低密度奇偶校验码(Quasi Cyclic Low Density Parity Check Code，QC－LDPC)码是LDPC码的一个重要子类，因为具有准循环形式的校验矩阵，所以QC－LDPC有较低的编解码复杂度.又因为QC－LDPC码具有准循环形式生成矩阵，所以我们可以使用移位寄存器来进行编码.但是QCLDPC码中短环是不可避免的.所以在构造校验矩阵时，能否使矩阵中的环合理分布且使girth值尽量增大对于码字性能有很大的影响.

QC－LDPC需要较小的存储空间并且有效降低了编解码复杂度，因而对LDPC码的发展具有重要意义.目前，林舒的研究小组QC－LDPC码领域的深入研究中在利用有限几何法，在对一般QCLDPC码的复杂度及编码方法进行了全面分析的同时又构造了众多码字[4]，引入了行列分解技术[5]，并且有二阶域又有高阶域码字[6];Zhang小组和Vasic小组为了使得QC－LDPC码中的最短环长girth较大[7]都采用均衡不完全区组设计(Balanced Incomplete Block Design，BIBD)来对码字进行构造.

RC－LDPC码是Narayanan[8]首次提出的概念，为了满足不同码率的要求，在HARQ系统中，一般使用随机删除[9]方法来获得RC－LDPC码的删除矩阵，这种方法的实质是随机选择删除的比特位置从而获得高速率的LDPC码.但是这种方法的缺点是在译码端需要知道删除矩阵的位置，这就需要把这些删除矩阵的位置发送给接收端，从而造成系统资源的浪费.在文献[10]中主要介绍了用扩展和删除矩阵结合来构造RC－LDPC的方法，在文献[11]中主要介绍了使用顺序删除的方法来构造RC－LDPC码.这些构造方法因为使用了结构确定的RC－LDPC码.省去了额外开销(删除矩阵的传输)，便于硬件的实现，具有实际应用意义.

2 一种基于树结构展开的Tanner图短环计数算法

LDPC码的校验矩阵H具有稀疏的特性.并且对应于每一个校验矩阵H都有惟一的一个双向图(或称Tanner图(图1)[12].Tanner图是一种双向图)与其一一对应.在Tanner图中VB=(b1，b2…，bn)称为变量节点，其对应的是校验矩阵的列，Vc=(c1，c2，…，cn)是Tanner图的校验节点，其对应LDPC码校验矩阵的行.Tanner图中的环是指从某点出发又回到这一点为一个闭合回路，环长是指着这个闭合回路中的边的个数，在这个校验矩阵中最短环的值称为此矩阵的girth.

图1 Tanner图

在Tanner图中将某一变量节点按树结构展开，变量节点和校验节点依次分层排列.当在Tanner图中展开层中某一变量节点或者检验节点出现的次数大于等于两次时那么就构成了环.如图2所示.

图2 树形结构中的短环

展开层第三层的变量节点v5出现的次数大于两次，那么我们可以看出v1，c2，v5，c2构成了一条闭合回路.环长为4.如果一个从变量节点展开的环长度为2k，其中一个分支的长度为2k－m，那么我们只需把另一个支路展开到m层这个环就可以形成.为了使展开层数最少，我们令m=k，也即把两个分支都展至第k层.所以，在Tanner图中我们只需要把变量节点展开到第k层就可以对长度为2k的短环进行计数.对所展开到的第k层上的相同节点两个为一组的进行环的统计.为了防止重复展开，在对某一节点展开时，该节点的父节点不出现在其子节点中.

假设v1，v2，…，vn是Tanner图G的n个变量节点，我们使用C2K(G)表示在Tanner图G中长度为2k的环的个数，节点展开支第k层时能够构成环的总数，也即相同节点之间两两组合在一起的数目记为C2k(vi).我们把Tanner图G以变量节点vi(1≤i≤n)为根节点展开到第k，假设在第k层上出现了m个不同的节点，它们出现的次数分别是t1，t2…，tmi，那么将Tanner图G按树形结构依次展开到第k层后，所得到的环长为2k的环的总个数为

3 速率兼容LTE－QC－LDPC码的构造

由于LDPC一般采用置信传播BP算法，如果有短环存在会影信息传播的独立性，使译码反复迭代，译码的收敛速度变慢从而影响译码性能.而在QC－LDPC码中短环的存在是不可避免的[13].要想构造出性能优良的LDPC码，必须考虑短环的问题.在传统RA码中串行输出是其很大的一个缺点，这影响了码字的吞吐量，从而影响码字的性能，为了克服串行输出这一缺点出现了基于单次扩展的可以并行输出的重复累积码，这种方法其实就是QC－LDPC码与RA码的结合，其校验矩阵H具有如式(1)所示的形式这种结构可以实现校验比特的并行计算，数据吞吐量得到大幅度提高.

式(2)中0表示单位矩阵，－1表示全零矩阵.hij为置换矩阵.

式(2)所示矩阵具有稀疏特性并且包含有准循环结构，所以它是QC－LDPC的一种.虽然这种RA码具有良好性能，但是其左半部分并不是完全下三角结构，这就使得它无法进行线性时间编码.从而导致了在构造速率兼容码时，这种RA码无法进行结构扩展.

本文在IEEE 802.16e[14]国际标准的基础上将其中的一列删除，在最右侧补上一列，即得到与原结构相比基本没有性能损失的、并且具有完全下三角形式的矩阵，即可线性时间编码的母码.其结构如式(3)所示.这种形式的矩阵通过顺序增加或者删除其中的行和列很容易的就可以得到信道所需要的码率实现速率兼容[15]，再用生成树的方法寻找其中的短环，删除部分六环，构造了一种优化六环的LTE－QC－LDPC码，很好提高了码字的译码性能.

将上文所示的结构展成具体的矩阵如表1所示，码率为1/2，分块校验矩阵大小为12×24，子块是扩展因子为48的48×48的方阵.数字代表循环移位的次数，具体的校验矩阵在表1中给出.对其进行短环检测并且去除一部分六环，以至于不删除太多信息节点.

表1校验矩阵

4 实验仿真与分析

为验证本文优化方法的有效性和先进性，这里执行了一系列仿真实验.所有仿真实验均在Intel Pentium(R)CPU 2.20GHz、2G内存的计算机上进行，编程环境为Matlab7.1.表1为应用树形结构短环检测表1所得到四环、六环和八环的个数.

表1 检测矩阵中各长度环的个数

由于短环对采用置信传播BP算法影响较大，使译码重复迭代，译码的收敛速度变慢，本文重点对长度为六的短环进行处理.又由于六环点数太多，全部去除会带来较大的信息损失，所以本文主要去掉形状如图3所示的六环进行删除.

图3 六环结构

在AWGN信道下使用BP译码算法对上述几种码字进行性能仿真.图4是未去六环TE－QCLDPC码与802.16e中规定的RA码的误码性能比较图.从图4中可以看出没有经过六环处理的LTE－QC－LDPC码在误码性能上没有比802.16e中规定的RA码优越.两个误码性能相差很小.

图4 未去六环的LTE-QC-LDPC码和802.16eRA码误码率性能对比

从仿真结果可以看出，因为去除了部分六环，使得误码性能曲线收敛速度加快，在误码率在时大约提高了0.12 dB.在误码率为10时，大约提高了0.16 dB，由此可见，经过六环优化LTE－QC－LDPC码性能比未经六环优化的LTE－QC－LDPC码和802.16e中规定的RA码有明显提高，这证明去六环的LTE－QC－LDPC码是一种性能优良的好码.

图5 误码性能对比仿真图

5 结语

针对现有的LTE－QC结构的LDPC码中存在大量的短环影响译码性能的问题，本文使用了生成树的方法对校验矩阵进行了短环检测，并在尽量减少对原始信息丢失的前提下，对其中一种形状的六环进行删除，得到了经过六环优化后的校验矩阵，仿真结果表明，所得到的校验矩阵在误码性能方面跟802.16e中规定的RA码误码率性能比较时，性能有所提高，说明经过六环优化后的码字是一种一种性能优良的好码.

[1]HAGENAUER J.Rate－compatible punctured convolutional codes(RCPC codes)and their applications[J].IEEE Trans.on Communications，1988，36(4):389－400.

[2]LIJ，NARAYANA K.Rate－compatible low density parity check codes for capacity approaching ARQ scheme in packet data communications[C]//IEEE CIIT，US Virgin Islands，2002:201－206.

[3]ROWITCH N，MILSTEIN L B.On the performance of hybrid FEC/ARQ systems using rate compatible punctured turbo(RCPT)codes[J].IEEE Trans.on Communications，2000，48(6):948－959.

[4]Z.L，L.CHEN.Efficient Encoding of Quasi－Cyclic Low－Density Parity－Check Codes[C]//IEEE Trans.Communications，[S.l.]:[s.n.]，2006，54(2):71－81.

[5]JUN X，LEI C.Construction of Regular and Irregular LDPC Codes:Geometry Decomposition and Masking[J].IEEE Trans.Information Theory，2007，53(3):121－134.

[6]LING Q Z，LAN L.Construction of Nonbinary Cyclic，Quasi－Cyclic and Regular LDPC Codes:A Finite Geometry Approach[C]//IEEE Trans.Communications，[S.l.]:[s.n.]，2008，56:378－387.

[7]VASIC B，MILENKOVICO.Combinatorial Constructions of Low－Density Parity－Check Codes for Iterative Decoding[J].IEEE Trans.Information Theory，2004，50(6):1156－1176.

[8]RICHARDSON T，URBANKE R.The capacity of low－density Parity－check codes under message－passing Decoding[J].IEEE Transactions on information Theory，2001(2):599－618.

[9]王继康，周荷琴.删余低密度奇偶校验码的分析与设计[J].电子与信息学报，2007，29(9):2149－2153.

[10]YAZDANIM，BANILHASHWMIA.On construction of ratecompatible low－density parity－check codes[C]//IEEE Comm.Letters，[S.l.]:[s.n.]，2004，8(3):159－161.

[11]袁东风，张海刚.LDPC码理论与应用[M].北京:人民邮电出版社，2008:64－66.

[12]TANNER R M.a recursive approach to Low Complexity Codes[J].IEEE Transactions On information Theory，1981，27:533－547.

[13]KYEONGCHEOL Y.Quasi－Cyclic LDPC Codes for Fast Encoding[J].IEEE Transactions on information theory，2005，51(8):167－179.

[14]RASHIDPOUR，JAMALI S H.Low－density parity－check codes with simple irregular semi－random parity－check matrix finite－length applications[C]//14th IEEE Proceedings on Personal，Indoor and Mobile Radio Communications，[S.l.]:[s.n.]，2003:439－443.

[15]李 炜，赵旦峰，钱晋希.MSK系统中迭代相位同步补偿方法[J].哈尔滨商业大学学报:自然科学版，2011，27(4):602－604，608.