利用遗传算法构造QC－LDPC码*

郑丹玲，穆 攀，田 凯，袁建国

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

1 引言

低密度奇偶校验(Low Density Parity Check，LDPC)码因逼近Shannon限的优秀性能、低的译码复杂度，近些年来成为了编码领域的研究热点，特别是准循环LDPC(Quasi－cyclic LDPC，QC－LDPC)码。QC－LDPC码的奇偶校验矩阵H由循环置换矩阵或零矩阵构成[1]，同随机构造的LDPC码相比，QC－LDPC码有以下优点:首先，QC－LDPC码的编码可以通过简单的、呈线性复杂度的移位寄存器来实现;其次，QC－LDPC码可以由基础矩阵表示，同H矩阵相比，基础矩阵具有更小的尺寸，并且基础矩阵利用循环置换矩阵可以很容易地扩展为H矩阵。所以，QC－LDPC码具有编译码复杂度更低、硬件实现更简单、存储空间更少等优点，如何构造性能优异的QC－LDPC码一直以来都是人们研究的重点[2－3]。研究中发现，当 Tanner图中含有长度较小的环时，该码的纠错性能就会下降，环的数量和大小的分布同码的重量分布一样对LDPC码的性能有着重要影响。目前，已经有许多消除小环的LDPC码的构造方法被提出，这些方法主要分为代数构造[4－5]和随机构造[6－7]两类。

本文结合这两类方法，借助于遗传算法(Genetic Algorithm，GA)提出了一种新的消除短环的码字构造方法，简称GA－QC－LDPC码。该方法先使用遗传算法消除基础矩阵的四环得到六环的矩阵，再在此矩阵基础上，消除六环得到八环，此种方法多次利用，即可得到符合要求环长的基础矩阵。然后通过使用循环置换矩阵对基础矩阵扩展，得到具有准循环结构特性的LDPC码，准循环特性决定了它比随机构造方法使用的存储空间更小、编译码复杂度更低。仿真进一步显示，GA－QC－LDPC比基于欧式几何构造方法、Gallager随机构造方法和Mackay随机构造方法构造的LDPC码在纠错性能上更加优异。

2 采用遗传算法构造QC－LDPC码的方法

构造LDPC码的校验矩阵最大问题是要防止出现短环，在Tanner图中如果出现短环，其迭代译码时的信息在交换过程中就会变为相关的，阻止译码收敛或者收敛变慢，造成译码性能的急剧下降。此外，由文献[8－9]看出，Tanner图的最小环还与码的最小距离有关，girth越大，最小距离也随之增大，要增加码间的最小距离可以反映到增加girth上来。所以，构造性能良好的LDPC码，可以集中反映到构造大girth的LDPC码上来。给定一个基础矩阵，我们可以用下面定理检测短环是否存在。

定理1(短环存在定理):对于一个m×n的基础矩阵，存在短环的充分必要条件是

式中，s2k和s2k－1为基础矩阵中的短环上两个相邻位置元素，P为循环置换矩阵的阶数[1]。一般情况下，基础矩阵的阶数都比较小，因此，检测矩阵中所有的元素相对容易。

遗传算法作为一种优化搜索算法，从初始种群的产生开始，然后对个体进行选择复制、交叉和变异遗传操作以产生新的个体，选择可以将适应性好的个体复制到下一代作为种群迭代的父代，交叉操作将选中的两个个体的某段基因进行互换来产生新的个体，变异改变个体的某个基因产生新的个体。遗传算法可使种群朝着最优的方向发展。本文运用遗传算法可以不断增大Tanner图中的girth，具体方法是利用遗传算法消除基础矩阵中的四环得到girth=6的矩阵，在此基础上，消除六环得到girth=8的矩阵。总之，多次运用遗传算法可分步提高girth，如图1所示。

图1 遗传算法提高girth示意图Fig.1 Diagram of improving girth based on Genetic Algorithm

2.1 消除四环得到girth为6的基础矩阵方法

本小节运用遗传算法消四环得到girth为六环的基础矩阵，将基础矩阵进行扩展可得到H矩阵。

(1)候选个体初始化

随机产生N个个体，每个个体为一个m×n的候选个体矩阵，表示为si，组成初始种群。

(2)适应度函数

基础矩阵si中的girth尽可能地大，且矩阵si中环长为girth的环尽可能地少。根据定理1，计算候选个体矩阵中四环的数目，环数越少的个体适应性越好。如果种群中个体不存在四环，则结束迭代;否则，继续下一步操作。

对于某一个候选个体s，即m×n的矩阵，其四环搜索算法如下:

步骤1:在矩阵s中的第i1(i1=1，2，…，m)行，对于第 j1(j1=1，2，…，n)列，如果 s(i1，j1)≠0，则跳至步骤2;否则，继续步骤1，直到j1＞n时跳到第i1＞m时结束;

步骤2:对于第 j2(j2＞ j1)列，如果 s(i1，j1)≠0，则跳至跳至步骤3;否则，继续步骤2，直到j2＞n时跳至步骤1;

步骤3:对于第i2(i2＞ i1)行，如果 s(i2，j2)≠0且s(i2，j1)≠0，则跳至步骤4;否则，继续步骤3，直到i2＞m时跳至步骤2;

步骤4:如果满足 s(i2，j2)－ s(i2，j1)+s(i1，j2)－s(i1，j1)=0(模 P)，则四环个数 girth4_num=girth4_num+1;否则跳至步骤3。

(3)选择

选出一个含girth=4最少的个体矩阵直接遗传至下一代，并复制该个体一次。将girth=4含环数最多的个体直接淘汰，保持种群规模不变。

(4)交叉

对其余个体，随机选取一对个体sa和sb，进行单点交叉，产生两个新的个体sx和sy。本小节中的交叉方式主要分为行向量单点交叉和列向量单点交叉两种。

1)行向量单点交叉

将基础矩阵sa和sb表示为

式中，ra(i)和rb(i)是长度为n的行向量。

矩阵sa和sb的行向量表示形式为

矩阵A和B单点交叉后产生的新个体为

式中，X、Y即为矩阵sx、sy的行向量表示形式。

2)列向量单点交叉

将基础矩阵sa和sb表示为

式中，ca(i)和cb(i)是长度为m的列向量。矩阵sa和sb列向量单点交叉后产生的新个体为

行向量交叉会产生重量为0或1的列向量，导致误码率的增加。因此，本文采用列向量单点交叉方式，交叉概率设为0.9。

(5)变异

对种群中的所有候选个体，随机变异矩阵中某一四环上的任意元素，即将该元素变为随机生成的某个数，变异概率设为0.1。

2.2 消除六环得到girth为8的基础矩阵方法

将2.1节最终产生的种群作为本节中候选的初始种群。消除六环的方法与消除四环的方法基本相同，不同点在于:一是交叉操作可能会产生新的四环，所以交叉操作被禁止;二是变异操作更改为:对所有候选个体，随机删除矩阵中某一六环上的元素，即将非零元素变为“0”。为了减小低重量码字对性能的影响，选择重量较大列的非零元素进行删除操作。

消除八环得到girth为10的基础矩阵的方法同以上方法。

2.3 复杂度分析

本文提出的基于girth选择遗传算法构造LDPC码方法的复杂度主要集中在适应度评价函数上，即搜索短环的过程中。本节主要介绍其时间复杂度，即搜索短环消耗的时间。

假设一个种群中有N个候选个体矩阵，每一个候选个体为m×n的矩阵，所有的候选个体矩阵在初始化时所有元素都为非零值。搜索四环的复杂度如式(7)所示:

在六环检测过程中，候选个体矩阵中元素已经不全是非零值。随着种群迭代次数的增加，非零元素会相应减少，故假设迭代一次后候选个体矩阵的行重和列重分别为ρ和γ，搜索六环的复杂度如式(8)所示:

由式(8)可得，搜索六环的复杂度与种群大小N、候选个体矩阵的行数m和列数n、行重ρ和列重γ有关。一般情况下，基础矩阵都是非常小的矩阵，所以搜索短环相对容易。

3 仿真及性能分析

本文所进行的仿真都采用二进制相移键控(Binary Phase Shift Keying，BPSK)调制方式、置信传播(Belief－Propagation，BP)译码算法，在加性高斯白噪声(Additive White Gaussian Noise，AWGN)信道下进行性能仿真。首先，对(530，265)GA－QC－LDPC码在不同译码迭代次数(Iteration分别为1、5、10、20和50)下的纠错性能进行对比分析，仿真性能曲线如图2所示。由图2可知净编码增益(Net Code Gain，NCG)随着迭代次数的增大而提高，但当迭代次数增加到一定值时，NCG的变化非常小。考虑到增加迭代次数会增加译码的时间，因此，本文选择最大译码迭代次数为20次。

图2 不同迭代次数下GA－QC－LDPC码性能对比Fig.2 Performance comparison of GA －QC －LDPC codes with different iterations

图3 是关于 GA－QC－LDPC(610，305)码在girth分别为4、6、8和10下的误码率(Bit Error Rate，BER)和误帧率(Frame Error Rate，FER)性能比较。从图中可以看出，girth分别为4、6、8和10时，在Eb/N0=3 dB的情况下，所对应的BER分别约为2.0×10－3、9.8 ×10－4、6.6 ×10－5和5.4 ×10－6，印证了随着girth不断增加，码的纠错性能越来越好。

图3 不同girth的GA－QC－LDPC码仿真性能对比Fig.3 Performance comparison of GA －QC －LDPC codes with different girth

最后将GA－QC－LDPC码与基于欧式几何构造方法[10]、Gallager随机构造方法[11]和 Mackay 随机构造方法[12]进行比较，如图4所示。从图4中我们可以看出，在BER为10－6时，GA－QC－LDPC码同其他构造方法相比有不同程度的性能提升，与基于欧式几何、Gallager和Mackay随机构造方法相比，净编码增益分别提升了0.15 dB、0.5 dB和0.2 dB。

图4 GA－QC－LDPC码与其他LDPC码的纠错性能比较Fig.4 Performance comparison between GA －QC －LDPC code and other LDPC codes

通过上述仿真可知，本文提出的算法具有优于随机构造方法的性能。此外，由于GA－QC－LDPC码具有准循环性，因此其编码复杂度要低于随机构造方法。

4 结束语

本文研究了基于Gallager和Mackay的随机构造方法，发现随机构造方法构造的校验矩阵不具有确定的数学结构，导致编译码复杂度高、存储困难、硬件难以实现等缺陷，为此，提出了一种使用遗传算法构造QC－LDPC码的方法，通过分步、多次使用遗传算法设计出大girth、具有准循环特性的LDPC码，克服了随机码因无数学结构造成的不足。仿真结果在验证了QC－LDPC码的性能随着girth的增加而提升的同时，也表明本文构造出的GA－QCLDPC码具有比RS和两种典型随机方法构造的LDPC码更好的纠错性能。

在今后的研究工作中，可以在本文提出的算法基础上，考虑其他的方式来替代遗传算法中的变异操作。因为本文中是通过将环上的元素置零以此来实现消除短环的目的，这种方法会减小校验矩阵的行重和列重，导致出现低重量的码字，降低LDPC码的纠错性能。

[1]Fossorier M P C.Quasi－cyclic low－density parity－check codes from circulant permutation matrices[J].IEEE Transactions on Information Theory，2004，50(8):1788 －1793.

[2]黄胜，庞晓磊.基于中国剩余定理和贪婪算法扩展的QC－LDPC 码[J].电讯技术，2014，54(11):1528－1533.HUANG Sheng，PANG Xiaolei.QC － LDPC Codes Based on Chinese Remainder Theorem and Greedy Algorithm[J].Telecommunication Engineering，2014，54(11):1528 －1533.(in Chinese)

[3]Huang Qin，Diao Qinju.Cyclic and Quasi－ Cyclic LDPC Codes on Constrained Parity－Check Matrices and Their Trapping Sets[J].IEEE Transactions on Information Throry，2012，59(1):2648 －2671.

[4]Wang Lei，Zhang Xing.QC － LDPC Codes with Girth Eight Based on Independent Row－Colunm Mapping Sequence[J].IEEE Communications Letters，2013，17(11):2140－2143.

[5]刘原华，张美玲.一种可快速编码的QC－LDPC码构造新方法[J].电讯技术，2013，53(1):55 －59.LIU Yuanhua，ZHANG Meiling.A New Design Method for Quasi－cyclic LDPC Codes with Fast Encoding Ability[J].Telecommunication Engineering，2013，53(1):55 －59.(in Chinese)

[6]Jiang Xueqin，Xia Xianggen.Efficient Progressive Edge －Growth Algorithm Based on Chinees Remainder Theorem[J].IEEE Transactions on Communications，2014，62(2):442－451.

[7]Sharon E，Litsyn S.Constructing LDPC codes by error minimization progressive edge growth[J].IEEE Transactions on Communications，2008，56(3):359 －368.

[8]Tanner R M.Minimum－distance bounds by graph analysis[J].IEEE Transactions on Information Theory，2001，47(2):808－821.

[9]Hu X Y，Vetterli M.Low－delay low－complexity errorcorrecting codes on sparse graphs[D].Switzerland:Swiss Federal Insitute of Technology Lausanne(EPFL)，2002.

[10]Yu Kou，Shu Lin，Fossorier M P C.Low －Density Parity －Check Codes Based on Finite Geometries[J].IEEE Transactions on Information theory，2001，47(7):2711 －2736.

[11]Gal1ager R G.Low －density parity－check codes[J].IEEE Transactions on Information Theory，1962(8):21 －28.

[12]MacKay D J C.Good error－correcting codes based on very sparse matrices[J].IEEE Transactions on Information Theory，1999，45(2):399 －431.