改进的多进制QC―LDPC码构造算法

摘 要：针对随机构造多进制LDPC码编码复杂度高的问题，基于具有线性编码复杂度的多进制LDPC码的编码方法，提出了一种改进的QC-LDPC码校验矩阵构造算法。仿真结果表明，该算法构造的多进制LDPC码不仅可以获得较高的编码增益，而且具有低编码复杂度、校验矩阵存储简单等优点。

关键词：准循环低密度奇偶校验码；多进制低密度奇偶校验码；高编码增益；低编码复杂度

1 引言

由于多进制低密奇偶校验码（Low-Density Parity-Check Codes，LDPC）[1]与二进制LDPC码相比，具有更高的编码增益、较强的抗突发错误能力以及更适合应用于高频带利用率的通信系统等优势，因此近年来得到了信道编码领域研究者的高度重视。虽然多进制LDPC码具有显著的优势，但其高编译码复杂度阻碍了其实用化进程，导致多进制LDPC码没有得到广泛的应用。根据不同的校验矩阵结构，LDPC码的构造方法主要可以分为两大类：随机构造方法及结构构造方法。随机构造方法[2]具有纠错性能好、码长及码率构造灵活等优点，但校验矩阵构造算法及相应的编译码算法复杂度较高，尤其对于多进制LDPC码，其编译码运算均是基于伽罗华域上的运算，复杂度更高，硬件难以实现；而结构构造算法[3]虽然码长及码率的取值受限，灵活性较差，但具有构造简单、编译码算法复杂度低等优点，因此成为了主流的多进制LDPC码校验矩阵构造算法。由于LDPC码的校验矩阵构造方式直接影响其纠错性能，并且一定程度上决定了编译码算法复杂度，因此文章提出了一种具有低编码复杂度的多进制准循环LDPC码（Quasi-Cyclic-LDPC，QC-LDPC）的构造算法，该算法不仅可以获得较高的编码增益，而且具有线性编码运算复杂度、矩阵存储简单等优势。

2 改进的多进制QC-LDPC码构造算法

令 表示QC-LDPC码的校验矩阵，

（1）

其中， 0表示p×p维的零阵，I表示p×p维的单位阵，编码长度为n=p×L，编码码率为r=（1-J/L）。

子矩阵 ，其中gcj，l为有限域系数， 表示

GF（q）域上的有限域元素gcj，l构成的矩阵，0？燮gcj，l？燮q-1。如果有限域系数gcj，l=0，则子矩阵Hj，l为零阵；如果gci，j≠0，则子矩阵Hj，l为矩阵

向右循环移位Sj，l次构成的矩阵，即 ， ，1？燮l？燮L，其中，Sj，l为循环移位系数， 表示移位系数构成的矩阵，0？燮sj，l？燮p-1。根据式（2）所示的避免长度为2i短环的充分必要条件，随机选择移位系数sj，l。

（2）

其中，2？燮m？燮i，1？燮jk？燮J，1？燮jk+1？燮J，1？燮lk？燮L，j0=jm。

算法具体步骤如下：

2.1 对于给定的LDPC码度分布，具有下三角结构的二进制基矩阵WJ×L如式（1）所示，大小为J×L维，基矩阵可由如PEG算法、EBF算法等校验矩阵的随机构造算法生成。如果矩阵中的元素为“0”，则由一个p×p维的零阵替代该位置；如果矩阵中的元素为“1”，则首先随机的从集合{1，…， q-1}中选取一个元素作为有限域系数gcj，l的值，然后由一个p×p维的单位阵I或者 的循环移位矩阵替代该位置。

2.2 基于式（2）选取移位系数的原则，可通过连续的试探法确定移位系数矩阵SJ×L中的移位系数Sj，l。

（1）如果基矩阵WJ×L第j列和第l行的元素wj，l的值为“0”，即，wj，l=0，1？燮j？燮J，1？燮l？燮L，则sj，l=0；

（2）如果基矩阵WJ×L第j列和第l行的元素wj，l的值为“1”，即，wj，l=1，1？燮j？燮J，1？燮l？燮L，则随机的从集合{0，1，…，p-1}中选取一个移位系数Sj，l的值，对于给定的围长，根据式（2）判断是否满足约束条件。如果满足约束条件，则可以确定移位系数sj，l的值；如果不满足约束条件，则重新执行步骤B。

（3）根据基矩阵WJ×L、循环移位矩阵SJ×L及有限域系数矩阵GcJ×L，则可以确定校验矩阵H。如果wj，l=0，则子矩阵Hj，l=0p×p，即H（（j-1）*p+1：j*p），（l-1）*p+1：j*p）=0p×p；如果wj，l=1，则Hj，l=gcj，lIp×p（Sj，l），即H（（j-1）*p+1：j*p），（（l-1）*p+1：j*p）=gcj，lIp×p（Sj，l）。

3 仿真结果及分析

（a）误码率 （b）误帧率

图1 改进QC-LDPC与PEG算法的性能（q=16）

图1显示了PEG及改进的QC-LDPC码构造算法构造的LDPC码字误码率和误帧率性能仿真曲线。其中，码率r=1/2、2/3、3/4，q为16，LDPC码的信息位长均为768比特，即信息位的符号长度分别为192和92，译码采用BP译码算法，为给硬件实现提供参考，最大译码迭代次数取25，调制方式为BPSK调制，信道为高斯白噪声信道，两种构造算法构造码字的比特节点服从相同的度分布。由图1可见，虽然采用改进的QC-LDPC构造方法构造出的具有下三角结构的LDPC码误码率、误帧率的性能略差于应用PEG构造方法构造出的LDPC码，但性能差距非常小，表明两个LDPC码编码增益基本一致。

4 编码复杂度分析

虽然提出的QC-LDPC码的性能不能超越PEG-LDPC码，但其优势在于具有更低的编码复杂度及存储复杂度。

从编码复杂度的角度看，提出的QC-LDPC码既可以采用迭代的编码方法，也可以采用QC-LDPC码的编码方法，无论是哪种编码方法，均具有线性的编码复杂度。

同时，QC-LDPC码的构造方法属于结构化构造方法，所构造的LDPC码具有准循环结构，存储矩阵时只需存储一个p×p的单位阵I、一个J×L的多进制系数矩阵GcJ×L及一个J×L的循环移位系数矩阵SJ×L即可。而随机构造的同样大小的校验矩阵，则需要存储一个p×J×p×L大小的校验矩阵。可见该方法构造的LDPC码与随机构造方法相比具有更简单的矩阵存储结构。

此外，因其该构造方法有一定的码结构，克服了随机构造算法（如PEG）构造中长码时搜索时间过长的缺陷。

5 结束语

文章提出的多进制QC-LDPC码构造算法所构造出的LDPC码不仅具有线性的编码复杂度及矩阵构造和存储简单的优点，同时具有较强的纠错能力。

参考文献

[1]杨民，张文彦，钟杰，等.准循环多进制LDPC码构造[J].电子信息学报，2013，35（2）：297-302.

[2]黎勇，王琳，陈俊斌.基于PEG算法的多进制LDPC码的设计与仿真[J].重庆邮电学院学报，2006，18（2）：175-177.

[3]Zhao S， Ma X， Zhang X， et al. A Class of Non-binary LDPC Codes with Fast Encoding and Decoding Algorithms. IEEE Transactions on Communications. 2013， 61（1）：1-6.