基于遗传算法改进的LDPC码译码器结构

徐光宪，郭若蕾，陶志勇

(辽宁工程技术大学电子与信息工程学院，辽宁 葫芦岛 125105)

0 引言

在过去的60年中，信道编码作为一种重要的纠错和信道保护技术得到了广泛的应用。通过适当的编码方法，将精心设计的冗余添加到传输的消息中，信道编码可以显著降低信道噪声带来的随机或突发错误，从而为传输质量提供强有力的保护。到目前为止，BCH码[1]、Turbo码[2]、LDPC码[3]、Polar码[4]等多种信道编码已被广泛采用和部署在无线通信、深空通信、固态驱动器等众多通信和存储系统中。

目前LDPC码的译码方法主要采用的是BP迭代译码算法，它采用外信息迭代的方法来译码，其计算复杂度低，可实行完全的并行操作，适合硬件实现，具有高速译码的潜力；但是BP译码器与最大似然译码器相比，得到的译码结果较差，造成译码准确性低，因此人们一直探索更接近最大似然译码算法的改进译码算法。

随着新兴的人工智能时代的来临，深度神经网络(deep neural network，DNN)[5]已经成为最流行和最重要的人工智能技术。最近在信道码的研究领域，已经有不少的工作将深度学习的算法和信道编码联合起来设计信道码的译码算法。文献[5]中提出，利用加权BP(belief propagation)译码器，在高信噪比下，BP算法的译码性能可提高0.9 dB；但该方法的译码算法需要大量的乘法运算，在一定程度上增加了译码的复杂度。Lougosch和Gross在文献[5]的基础上，提出一种改进的神经网络结构[6]，与文献[5]相比，主要的区别是使用偏移最小和算法代替和积算法，从而消除了使用乘法的需要，使参数量减少，复杂度降低。文献[7]提出一种基于深度神经网络的信道解码方法，结果表明，由所有可能的码字训练的神经网络解码器可以获得最大的后验性能；但是由于二进制码字的指数型性质，其复杂度很高。为了减少译码的复杂性，文献[8]提出一种分离子块的深度学习极化码解码网络，该方法与传统算法相比，算法时延大大降低。

上述的改进译码器结构主要考虑用神经网络(如文献[9]的MLP、CNN、RNN)等来实现接近最大似然译码，但其译码性能仍有待提高。因此针对LDPC码的BP译码器比最大似然译码器译码准确性低，提出了基于遗传算法改进的LDPC码译码器结构。

1 LDPC译码原理和遗传算法

1.1 LDPC码

LDPC码是一类前向纠错性能良好的(N,K)线性分组码，可由相应的校验矩阵决定，其中，N代表码长，其值和校验矩阵总列数大小相等，M代表校验序列长度，其值与校验矩阵总行数大小相等，K代表信息序列长度，K=N-M。对于校验矩阵，每行均与一个校验方程相互对应，而每列均与码字c=(c1,c2,…，cN)的一位相互对应，且校验矩阵H和码字c满足关系：H·cT=0,如式(1)所示：

除了用校验矩阵表示LDPC码外，还可用Tanner图[10]进行表示，Tanner图是校验矩阵的图形表示，可以直观的表述信息元与码字的关系。图1是式(1)校验矩阵H的Tanner图，方形c=(c1,c2,c3,c4,c5)为校验节点，校验节点表示校验方程，对应H的行，圆形b=(b1,b2,…，b10)为变量节点，对应H的列，ci和bj之间相连的边表示H中值为1的元素，即第j行第i列元素hi,j=1，Tanner图形象明了地表示了变量节点和校验节点之间的关系。

图1 校验矩阵的Tanner图表示Fig.1 Tanner graph representation of the check matrix

1.2 BP译码算法

BP译码算法可以在概率域或对数域进行译码[11-13]。概率域译码的缺陷是存在大量的乘法，复杂度较高，将译码转化到对数域中进行，大量的乘法可以变为加法运算，从而减少运算时间[14]。本文采用对数域的译码方法，首先定义对数似然比(likelihood rate，LLR)消息如下：

(2)

(3)

(4)

(5)

译码算法的具体过程如下：

步骤1 初始化，计算信道传递给变量节点的初始概率似然比消息L(Pi),i=1,2,…，n，对于变量节点i以及与其相邻的校验节点j∈M(i)而言，在AWGN信道中得到变量节点传递给校验节点的初始消息为：

L(0)(qij)=L(Pi)

(6)

步骤2 迭代处理

1) 校验节点的消息处理，对所有的校验节点j以及与其相邻的变量节点i∈N(j)，在第l次迭代中，计算变量节点传向校验节点的消息：

(7)

2) 变量节点的消息传递，对所有的变量节点i以及与其相邻的校验节点j∈M(i)，在第l次迭代中，计算校验节点传向变量节点的消息：

(8)

步骤3 译码判决，对所有的变量节点计算硬判决消息：

(9)

(10)

步骤4 停止

1.3 遗传算法

遗传算法最早由美国密执安大学的Holland教授提出，遵循适者生存、优胜劣汰的原则，是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法[15]。遗传算法以模拟一个人工种群的进化开始，通过选择、交叉和变异等机制，在每次迭代中保留一组候选个体，经过重复迭代进化后，使其适应度达到近似最优的状态。适应度展示了个体生存在环境中的能力。在每一代中，一些个体由于高适应性而存活，一些个体因其较差的存活性能而被淘汰。

一般的遗传算法都包含三个基本操作：复制、交叉和变异。复制是从一个旧种群中选择生命力强的个体产生新种群的过程。交叉和变异的操作需要改变才能产生后代。交叉是在两个选定的个体中交换部分基因来产生它们的后代。突变是改变了一个个体的部分基因，从而形成它的后代。这些动作的目的是保持更健康的个体或在种群中产生更健康的个体。经过多次进化，种群更倾向于适应环境。

2 改进的译码器

2.1 BP-CNN译码器

在实际通信系统中，由于滤波、过采样和信道衰落等因素，信道有时在噪声样本中表现出相关性，如果译码器没有设计成处理噪声相关，那么信道码在传输的过程中不具备令人满意的性能。针对信道噪声中存在相关性解码问题，本文引用CNN来去除传统BP译码器在译码中的估计误差，从而得到更准确的噪声估计。

BP-CNN译码器结构如图2所示，首先通过信道编码器将一组均匀分布的长度为K的x比特编码为长度为N的二进制码字u，然后通过BPSK调制将码字u映射到符号向量s，其次在接收端y被接收。通常在BP解码前存在BPSK软解调器，以计算所发送符号的对数似然比：

(11)

(12)

图2 BP-CNN译码器结构Fig.2 The structure of BP-CNN decoder

CNN是一种多层前馈神经网络，其基本结构包括：输入层、卷积层、池化层、全连接层和输出层。以计算机视觉为例，从图像识别[16-17]、目标检测[18]等高级任务到图像去噪[19]、图像超分辨率[20]等低级任务，深度卷积神经网络在各种应用中都得到了验证，表明CNN具有很强的局部特征提取能力，且其性能明显优于传统方法。因此在模型中，将噪声看作是一个特征，利用CNN在解码中恢复出真实的信道噪声。如图3所示，将CNN每一层的输入改为一维向量。详细的参数设置列于表1。

图3 CNN结构Fig.3 The structure of CNN

表1 CNN的参数

2.2 GABP-CNN译码器

BP-CNN译码器结构比传统的BP译码器结构在译码性能上有所提升，但还有进步的空间。因此在BP-CNN译码器结构的基础上，提出一种基于遗传算法改进的译码器结构，称为GABP-CNN(genetic algorithm belief propagation-convolutional neural network)译码器。

GABP-CNN译码器旨在将遗传算法引入到BP译码算法中。由上述遗传算法的过程可知，需要一个初始的种群，又由于BP译码算法是在Tanner图上进行消息传递的迭代译码算法，因此如图4所示，可以把所有的变量节点作为一个整体，每个变量节点作为一个个体，变量节点传递给校验节点的消息作为基因，通过这种方式，遗传算法改变了基因空间中的个体基因，从而导致个体空间中的相关个体得到改进，进而使整个种群变得越来越健康，从而译码性能可以得到提升。

图4 图1的基因表述Fig.4 Gene expression of fig.1

在Tanner图中，不同的个体的信息不能直接交换，因为基因与个体的关系非常密切，所以这里不能使用遗传算法中的交叉操作。为了充分利用遗传算法的优势，在每次BP迭代过程中都使用复制和变异来形成新的一代。

由于在第l次BP迭代结束时，用于试探译码的信息L(qi)表示该基因的可靠性。因此|L(qi)|的值越大，qi就越有可能是1或0。因此，定义它为衡量个体对环境的生存能力，即适应度：

Fitness=|L(qi)|

(13)

由于基因操作直接作用于BP译码，因此该算法不能直接给出单个个体与基因的变异概率，需要通过选择参数和变异参数来实现基因操作，下面给出变异参数m(λ)和选择参数s(λ)的定义。

设定

(14)

通过模拟一次BP迭代来定义选择参数和变异参数，设：

(15)

可得：

(16)

(17)

(18)

式(16)—式(18)中，m和n分别是每列和每行中1的平均个数。选择参数用作选择器，它被用来决定哪些个体生存下来，哪些个体在下一代中减少或改变。突变参数用于选择所选个体中的哪些基因进行突变，并决定突变的方向。这样，选择和突变参数都是衡量个体及其基因可靠性的指标。

3 实验验证

3.1 实验环境与数据集

实验环境使用Ubuntu64位操作系统，内存为32 GB，CPU为Intel Core i7-6850k，GPU为GeForce GTX Titan-X，编程语言为python，框架为Tensorflow。为了评估GABP-CNN译码器的译码性能，通过蒙特卡洛方法进行实验。选取码长为576,码率为3/4的LDPC码作为训练数据，奇偶校验矩阵来自文献[16]。该数据经过高斯信道传输得到，信噪比的范围为1～5 dB，选取150个码字作为min-batch的大小(每个SNR分配30个码字)。测试数据是经过编码，BPSK调制并在高斯信道上传输后得到的随机二进制信息。使用标准正态分布中的随机值初始化神经网络的权重。

性能评价指标为比特错误率(bit error rate，BER)，BER是在一个时间间隔内由错误比特数与传送总比特数的比值，定义为：

(19)

式(19)中，A是待译码的码字的数量，acc是能够正确译码的码字数量。

3.2 实验分析

本文提出的GABP-CNN译码器是在BP-CNN译码器的基础上进行改进的，因此先证明BP-CNN译码器比传统BP译码器的有效性，再进而证明GABP-CNN译码器在其基础上译码性能的提升。

3.2.1BP-CNN译码器性能分析

图5给出了使用BPSK调制的并通过加性高斯白噪声信息传输，设置码长为310，码率为1/2，迭代次数为50的BP译码器和BP-CNN译码器的误码性能和信噪比的关系。从图中我们可以看出改进的译码器性能要优于BP译码器。在误码率为10-4时可以提高解码性能3.5 dB。

除了纠错性能之外，BP-CNN译码器还减少了平均迭代次数，简化了解码器的复杂性，如图6所示。我们的性能分析和与相关工作的比较表明，尽管BP-CNN译码器中CNN的训练需要大量的数据，一定程度上增加了译码器的复杂性，但是可以通过强大的计算设备来满足，在BP和BP-CNN译码器整体复杂度相当的情况下，BP-CNN译码器的10次迭代与BP译码器的50次迭代的效果几乎一样，所以进一步证明了BP-CNN译码器能简化复杂性，提高译码性能。

3.2.2GABP-CNN译码器性能分析

首先对码长为310，码率分别为1/2，2/3的LDPC码进行译码仿真，编码后的信息采用BPSK，调制后的信息进入AWGN信道，最大迭代次数设为20次，得到的仿真结果如图7所示。

图5 两种译码器的译码性能对比 Fig.5 The comparison of decoding performance of the two decoders

图6 两种译码器的复杂度对比Fig.6 The comparison of the complexity of the two decoders

图7 码率对译码性能的影响Fig.7 The effect of code rate on decoding performance

图7给出了BP-CNN译码器和GABP-CNN译码器的误码率曲线的仿真结果。通过曲线可以看出，当误码率达到10-3时，在码率为1/2和2/3下，GABP-CNN相对于BP-CNN的性能增益分别约为0.03 dB和0.02 dB。在低信噪比下，两种译码器的性能相近，但在高信噪比下，GABP-CNN译码器相比于BP-CNN译码器表现出来更好的性能。

接着给出码率为1/2，迭代次数为20，码长为310和630的LDPC码在不同信道条件下的译码纠错性能，得到不同码长下的误码率仿真结果，如图8所示。

由图8可以看出，GABP-CNN译码器性能优于BP-CNN译码器。当误码率为10-4时，在310和630比特码长下，GABP-CNN相对于BP-CNN的误码率性能增益分别约为0.002 dB和0.000 3 dB，而且随着误码率的下降性能差异会更明显。所以加入遗传算法改进的译码器在较高信噪比下对误码率有

一定的改善。

然后给出码长为310，码率为1/2，迭代次数分别为5，10和20次的LDPC码在不同信道条件下的译码纠错性能，得到不同迭代次数下误比特率与信道中信噪比的关系图，如图9所示。

从图9中可以看出，迭代次数越大，误码率越低，译码性能也越好。相较于BP算法和BP-CNN算法，改进后的P-BP-CNN算法随着信噪比的增加可带来一定的性能增益。在0～1 dB的范围内，即小信噪比范围，提出的算法对误码率的改进不大，但随着信噪比的增大，LDPC码的误码率得到了明显的改善，证明所提出的结构对提升译码性能是有贡献的。

最后给出传统BP译码器、BP-CNN译码器与GABP-CNN译码器在码长为310，码率为1/2，迭代次数为20的情况下系统误码率以及运行时间如图10和表2所示。

图8 码长对译码性能的影响Fig.8 The effect of code length on decoding performance

图9 迭代次数对译码性能的影响Fig.9 The effect of the number of iterations on decoding performance

图10 不同译码器的译码性能对比Fig.10 The comparison of decoding performance of different decoders

表2 不同译码器的运行时间

由对比可以看出，相同条件下GABP-CNN译码器较传统BP译码器运行时间略多，但是在图10的仿真过程过程中可以看出，GABP-CNN译码器的译码性能最优。

4 结论

本文在传统BP译码器的基础上，提出了基于遗传算法改进的译码器结构，该结构是在引入卷积神经网络去除BP译码器的噪声估计的基础上，将遗传算法应用到BP译码中来获得最优的变量节点以提高其译码性能。仿真实验结果表明，与标准的BP译码器相比，本文提出的GABP-CNN译码器可以获得更好的纠错性能，同时通过训练具有损失函数的深度神经网络可以获得较低的误码率性能，尤其是在高信噪比环境下译码性能有较大的提升；但是改进的译码器结构在提高译码性能的情况下，系统运行时间上较传统BP译码器略多。因此，如何调整各种参数，保证译码性能提高的同时尽量减少系统的运行时间，是下一步重要的研究方向。