一种新的LDPC码编码方法

王 健，刘绍华，杨仕平

(广州海格通信集团股份有限公司，广东广州510663)

0 引言

LDPC［1］是目前信息领域和通信界最热门的研究之一，也是现代编码理论的典型代表。LDPC是一种线性分组码，其校验矩阵只含有很少量的1，其余元素均为0，即其校验矩阵H是稀疏矩阵。LDPC码的设计以校验矩阵H的设计为核心考虑之一。应用时需要先设计校验矩阵H，再进行后续的编码。校验矩阵H对应的Tanner图中的环也称为H的环。研究表明，好的LDPC码应避免校验矩阵中含有短环，尤其应该避免存在长度为4的环。

LDPC码的编码方法有2类:随机化方法和结构化方法。随机化方法性能很好，但实现复杂度较高，常用的有pi旋转方法［2］等;结构化方法性能相对于随机化方法会有损失，但实现相对容易，最常用的是准循环方法［3－5］(QC 方法)。除此之外，还有有限几何码［6］(EG和 PG)等。其中 IEEE 802．16e、DVB-S2等标准中的LDPC码编码的方法均采用了QC方法［7－12］。该方法是把索引矩阵中每个元素扩展成循环移位矩阵来构造校验矩阵，其缺点在于对索引矩阵敏感，索引矩阵必须精心设计，且阶数通常比较大，否则性能会很差，所以设计起来比较困难。同时，引入双对角子矩阵迭代编码时，性能不佳，一般需引入准双对角矩阵。与双对角结构相比，准双对角结构的编码复杂度较高。因此，研究一种容易设计且编码复杂度低、存储空间小、性能佳的LDPC编码方法具有很大的应用价值。本文提出的LDPC码的模循环方法编码性能好，计算复杂度低，存储空间小，而且很容易设计，能够较广泛地在实际中应用。

1 方法论述

本文提出的模循环方法分2类讨论:① 需要对素数求模运算，称之为“素数模循环方法”;② 是对第1类的改进，不需要对素数求模，只需对2的幂次求模，称之为“2幂模循环方法”。下面先后讨论2种方法。

1．1 素数模循环方法

设q+1是素数，码长N=qk，码率 R=(kj)/k。下面构造行重为k，列重为j的规则校验矩阵H。首先设计索引矩阵A为:

按上述索引矩阵，把索引矩阵A中的每个数字axy扩展成为q阶(0，1)方阵 Eaxy，每个 Eaxy在位置(i，iaxy(modq+1))，i=1，2，3，．．．q 处的元素均是1，其余位置的元素均是0。然后构造校验矩阵H如下:

由于 q+1 是素数，所以 (axy，2axy，3axy，．．．，qaxy)mod(q+1)是(1，2，3，……，q)的排列，从而Eaxy每行每列均只有1个1，即单位置换阵。这样一来，便保证了校验矩阵H是行重为k，列重为j的规则校验阵。

下面讨论如何设计索引矩阵可以保证校验矩阵中无四环以及六环。主要体现为下述的定理1和定理2。在设计索引矩阵时，要满足定理1的条件，从而使得校验矩阵无四环;定理2的条件尽可能满足，使得校验矩阵无六环。通常情况下，索引矩阵阶数较小时，随机产生的索引矩阵满足定理1的条件的概率很大，满足定理2的条件的概率较前者小，但只需要适当调整索引矩阵，便可满足定理2的条件。

定理1:模循环方法校验矩阵H中无四环的充要条件是:在索引矩阵 A 中，任何 i，j，s，t，有 aisajtajsait≠0(modq+1)。

下面的定理给出了校验矩阵中无六环的充要条件。

定理2:校验矩阵H中无六环的充要条件是:在索引矩阵 A 中，任何的下标 i，j，k，s，t，p，有asiatjapk－askatiapj≠0(modq+1)。

为了方便索引矩阵的设计，接下来给出一类特殊的索引矩阵，本文称之为正交和索引矩阵。

设 b=(b1，b2，．．．，bk)，c=(c1，c2，．．．，cj)。令索引矩阵 A=(axy)j×k中，axy=bx+cy。即

称这类索引矩阵为正交和索引矩阵。下面的定理3给出了如何设计正交和索引矩阵可以使得校验矩阵无四环，这个条件使用起来非常方便，所以在实际应用中可优先考虑使用正交和模版。

定理 3:若 b=(b1，b2，．．．，bk)，c=(c1，c2，．．．，cj)满足对任何的s，t，有 bs－ bt≠0(modq+1)，及cs－ct≠0(modq+1)，则正交和索引矩阵A对应的校验矩阵H无四环。

接下来给出应用素数模循环方法构造校验矩阵H的流程。

设q+1是素数，码长N=qk，码率R=(k－j)/k，目标是构造行重为k，列重为 j的规则校验矩阵H。

首先，设计j行 k列的索引矩阵A，须满足定理1的条件(若采用正交和索引矩阵，则须满足定理3的条件)，定理2的条件尽量满足;把索引矩阵A中的每个元素按素数模循环方法扩展成为q阶子方阵;由jk个子方阵构造校验矩阵H。

1．2 2幂模循环方法

在素数模循环方法中，需要对素数求模运算，这样实现起来相对困难，2幂模循环方法作为对素数模循环方法的继承和改进，克服了这一缺点，只需计算加法，乘法以及对2的幂次求模，实现起来相对容易。下面给出2幂模循环方法的描述。

设E为2m×2m的单位阵，a是一个奇数，定义E(a)如下:

令 g(i，a)≡ (2i－ 1)a(mod2m+1)，E(a)中第 i行的1的位置(纵坐标)是(g(i，a)+1)/2，即E(a)中的1的位置为(i，(g(i，a)+1)/2)。可以证明E(a)是单位置换阵。

设码长N=k2m，码率R=(k－j)/k。下面构造行重为k，列重为j的规则校验矩阵H。首先设计索引矩阵A为:

可以证明定理1对于上述的构造方法仍然是成立的。对于正交和索引矩阵，只要令 b=(b1，b2，．．．，bk)，c=(c1，c2，．．．，cj)中 bi全是奇数，ci全是偶数(或者中bi全是偶数，ci全是奇数)，于是得到全是奇数的索引矩阵，且定理3对应于下述的定理4，即满足条件的正交和索引矩阵对应的校验阵无四环。

定理4:对于2 幂模循环方法，若 b=(b1，b2，．．．，bk)，c=(c1，c2，．．．，cj)满足对任何的 i，j，s，t，则有:(bi－bj)(cs－ct)≠0(mod2m+1)。

则正交和索引矩阵A对应的校验矩阵H无四环。

接下来给出应用2幂模循环方法构造校验矩阵H的流程。

设码长N=k2m，码率 R=(k－j)/k，目标是构造行重为k，列重为j的规则校验矩阵H。

首先，设计j行k列的索引矩阵A(要求A种元素全是奇数)，须满足定理1的条件(若采用正交和索引矩阵，则须满足定理4的条件)，定理2的条件尽量满足。接着，把索引矩阵 A中的每个元素按2幂模循环方法扩展成为2m阶子方阵。最后，由jk个子方阵构造校验矩阵H。

2 可快速编码的模循环方法

在模循环方法的实际应用中，可采用双对角结构进行编码，双对角结构的引入可降低计算复杂度，加快编码速度。研究表明，双对角结构的引入通常会损伤码的性能，对QC方法而言，双对角结构的确会对其性能造成较大影响。仿真表明，双对角结构对本文提出的模循环方法影响不大，模循环方法采用双对角结构仍然性能优异。下面是引入双对角结构的模循环方法的描述。校验矩阵的结构为:

式中，

对于矩阵Hp，采用本文的素数模循环方法或2幂模循环方法生成即可。在下面给出的仿真中，本文的方法采用的便是双对角结构。

本文提出的模循环方法的索引矩阵通常只需要很小的阶数，设计起来非常容易，而且模循环方法对于索引矩阵不敏感，甚至随机的产生索引矩阵都能达到很好的性能;而IEEE 802．16e标准中使用的准循环方法，通常需要设计较大的索引矩阵，且对索引矩阵较敏感，需要精心设计索引矩阵，否则性能不好，所以设计起来比较困难。

对于计算复杂度而言，考虑常用的1/2码率的情形，设码长为n，本文的2幂模循环方法采用双对角结构时，乘法的计算次数为2n次，加法计算次数是2．5n次，对2的幂次求模可直接移位实现。且模循环方法只需设计并储存4×4的索引矩阵。IEEE 802.16e标准中采用的准循环LDPC码，编码时乘法次数约为11．6n次，加法次数约为10．6n次，需要设计并储存12×24的矩阵。所以本文的方法计算复杂度较低，存储量较小。

3 仿真结果及分析

下面的仿真条件均为码长2 048(其中IEEE 802.16e标准的码长是2 016)，码率1/2，采用BPSK调制以及归一化BP译码算法，归一化因子为0．8，加入白噪声信道。

本文的2幂模循环方法和pi旋转编码均引入双对角结构，即校验矩阵H=［HpHd］，Hd是双对角矩阵。pi旋转编码Hp由随机置换阵旋转而得，属于半随机方法。本方法中Hp则由如下索引矩阵A生成:

各种LDPC码编码方法的性能比较如图1所示，本文的2幂模循环方法与IEEE 802．16e标准相比性能接近，但本方法只需计算乘法4 096次，加法5 120次，而 IEEE 802．16e标准需计算乘法约23 340次，加法约21 370次，所以本文方法的计算复杂度低得多。

图1 各种LDPC码编码方法的性能比较

与其他方法相比，本文方法性能均占优。在10－5量级，本文方法可以比pi旋转方法性能好约0.1 dB，比PG和OOC方法好约0.3 dB，比EG方法好约0.7dB，且本方法存储空间小，编码复杂度低，较为实用。

上述仿真中本文的2幂模循环方法所设计的LDPC码的校验矩阵无四环和六环，使得迭代译码时信息交换充分，且校验矩阵构造方法极大的降低了校验矩阵各行的相关性，从而使得性能较好。

4 结束语

提出了一类新的LDPC码的编码方法——模循环方法，并给出了2类模循环方法:① 素数模循环方法;②2幂模循环方法。其中2幂模循环方法实现起来更加简单。提出的模循环方法简化了设计流程，在实际的工程实现当中，能够在保持良好性能的同时，可以大大降低计算复杂度，并且占用的存储量较小，比较实用。

［1］ GALLAGER R G．Low-density Parity check Codes［M］．MA:MIT Press，1963．

［2］ 张忠培，史治平，王传丹．现代编码理论与应用［M］．北京:国防工业出版社，2007．

［3］ MAC P C．Quasi-cyclic Low-density Parity-check Codes From Circulant Permutation Matrices［J］．IEEE Transactions on Information Theory，2004，50(8):1 788－1 792．

［4］ 肖 扬，徐 丹．准循环LDPC好码设计［J］．系统工程与电子技术，2009，31(5):1 011－1 016．

［5］ MYUNG S，YANG K C，KIM J．Quasi-cyclic LDPC Codes for Fast Encoding［J］．IEEE Transactions on Information Theory，2005，51(8):2 894－2 901．

［6］ KOU Y，LIN S，FOSSORIER M．Low Density Parity Check Codes Based on Finite Geometries:A Rediscovery and New Results［J］．IEEE Transactions Information Theory，2001，47(10):2 711－2 736．

［7］ 肖 扬．Turbo与LDPC编解码及其应用［M］．北京:人民邮电出版社，2010．

［8］ 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］，2005．

［9］ DVB-S2．Standard Draft ETSI EN 302 307 V1．1．1［S］，2004．

［10］ XIAO Y，KIM K．Good Encodable Irregular Quasi-cyclic LDPC Codes［C］ ∥11th IEEE Singapore International Conference on Communication Systems(ICCS 2008)，2008:1 291－1 296．

［11］ CCSDS131．1．1 － 0 － 2．Low Density Parity Check Codes for Use in Near-earth and Deep Space Applications［S］，2007．

［12］GB20600．数字电视地面广播标准［S］，2006．