基于深度强化学习的置信传播译码算法

高源浩 刘乃金 鲁渊明

摘  要：文章通过深度强化学习的方法来寻求二进制线性编码的有效解码策略。在加性高斯白噪声的条件下，将置信传播（BP）解码算法中软信息的迭代看作是对软信息的连续决策，并将其映射到马尔可夫决策过程，用深度强化学习网络代替传统译码器，扩大探索空间以提高译码性能，从而实现对数据驱动的最佳决策策略的学习。结果表明，相较于传统BP解码器，在误码率=10-5时，学习型BP解码器在BCH码上取得大约0.75 dB的优势，这在一定程度上解决了以往研究中过于依赖数据的问题。

关键词：深度强化学习;置信传播译码;马尔可夫决策;最佳决策

中图分类号：TP18    文献标识码：A文章编号：2096-4706（2021）21-0098-05

Abstracts： This paper uses a deep reinforcement learning approach to find an efficient decoding strategy for binary linear codes. Under the condition of additive Gaussian white noise， the iteration of soft information in the belief propagation （BP） decoding algorithm is regarded as a continuous decision-making of soft information， which is mapped to the Markov decision-making process. The deep reinforcement learning network is used to replace the traditional decoder， expand the exploration space to improve the decoding performance， so as to realize the learning of the best data-driven decision-making strategy. The results show that compared with the traditional BP decoder， when the bit error rate is 10-5， the learning BP decoder has an advantage of about 0.75 dB in BCH code， which solves the problem of relying too much on data in previous research to a certain extent.

Keywords： deep reinforcement learning; belief propagation decoding; Markov decision-making; best decision-making

0  引  言

数字信号在传输过程中，由于受到各种干扰的影响，码元波形将变坏，接收端收到后可能发生错误判决。由乘性干扰引起的码间串扰，可以采用均衡的方法进行纠正。而加性干扰的影响则需要通过其他方法解决。在设计数字通信系统的时候，应该首先从合理选择调制制度、解调方法以及发送功率等方面考虑，使得加性干扰不足以影响到误码率要求。在仍不能满足要求时，就要考虑采用信道编码方法了。

為了改善通信的质量，研究者们尝试了很多办法。信道编码是人们在改善通信质量方面最早采用的方法之一，通过给原数据添加相关的冗余信息来对抗传输过程中的干扰。信道编码中以线性分组码应用最广，广泛应用于卫星通信、移动通信、存储设备、数字视频广播等领域，此外，线性分组码可以在传输效率与纠错能力之间进行权衡，允许其在更低的发射功率下保持同质量的服务。因此，提高线性分组码性能具有极其重要的意义。

纠错码的解码可以看作是一个分类问题，能够通过监督机器学习的方式得以解决。一般的想法是将解码器视为一个参数化的函数（比如，一个神经网络），通过数据驱动的优化来学习良好的参数配置。如果没有对编码方法的进一步限制，深度学习方法通常只对短码字有较好的效果，不适用于超过几百个码字长度的非结构化代码。对线性分组码来说，这个问题就大大简化了。人们只需学习一个决策区域即可，而无需学习每个码字所在的各个区域，然而，这仍然是一个极具挑战性的问题，因为一个好的编码方案通常具有复杂的决策区域，每一个码字都有大量相邻的码字。Tobias Gruber认为可以通过深度神经网络对随机码和结构化码（如polar码）进行一次性解码[1]。通过学习，发现结构化编码更容易学习。对于结构化编码，神经网络能够泛化到它在训练期间从未见过的码字。Tim OShea提出并讨论了深度学习（DL）在物理层面的几个新应用[2]。通过将通信系统解释为一个自动编码器，将通信系统设计视为一个端到端的重建任务，寻求在单一过程中同时优化发射器和接收器组件。EliyaNachmani提出一种基于改进信念传播算法的新型深度学习方法[3]。该方法通过给Tanner图的边分配权重的方式来概括标准的信念传播算法，然后使用深度学习技术对这些边进行训练。信念传播算法的一个众所周知的特性是对所传输码字性能的独立性。Amir Bennatan提出一个新的框架，将深度神经网络（DNN）应用于任意块长度的线性编码的软解码[4]。他们所提出的框架允许无约束的DNN设计，能够自由灵活地应用在其他背景下开发的强大设计，对抑制许多竞争性方法的过拟合具有鲁棒性，这源于其训练所需呈指数级增长的大量编码。结果表明，其性能有时接近有序统计解码（OSD）算法的性能。EliyaNachmani介绍了一个基于逐次松弛方法的循环神经解码器架构，在较稀疏的Tanner图表示的编码上也观察到了比标准信念传播得更好的性能改进。此外，他们还证明了神经信念传播解码器可以用来提高短BCH码的性能，或者是降低接近最佳解码器的计算复杂性。

本文中，我们从机器学习的角度研究了二进制线性码的解码。置信传播算法利用节点与节点之间相互传递信息来更新当前所有节点的状态。通过消息传播，将该节点的概率分布状态传递给相邻的节点，从而影响相邻节点的概率分布状态，经过一定次数的迭代，每个节点的概率分布将收敛于一个稳态。在实际的置信传播译码过程中，校验节点和变量节点之间的消息传递虽然存在重复信息，但是重复信息比较少，因此可以近似地认为每一次的迭代译码都只用上一次迭代后的对数似然比值进行计算，这满足于马尔可夫决策中状态的改变只与上一个状态有关，而与上一个状态之前的状态无关的特点。因此，可以将置信传播译码中软信息的迭代看作是对软信息的连续决策，并将其映射到马尔可夫决策过程。利用深度强化学习网络解决译码问题，通过自主探索逼近最佳性能。当前，BP解码已经得到了广泛的研究，例如文献[5-7]等。据调研，本文提出的BP解码方法仍然是较为新颖的。事实上，研究和探讨RL解码的参考文献很少[8，9]，只是涉及一些比较典型的工作。简单回顾一下迭代译码算法，它们都是基于连续的决策步骤，因此RL适用于这些算法。

1  信道解码原理

假设C是一个由M×N的奇偶校验矩阵H定义的一个（N，K）二进制线性分组码，其中N为码长，K为码的维度。该码字用于将信息编码成码字c=（c1，...，cN）T，然后在加性高斯白噪声（AWGN）信道上传输，传输码字经过信道得到接收碼字y，y的每一个分量yn=（-1）Cn+ωn，ωn～N（0，（2REb/N0）-1），R=K/N称作码率，将Eb/N0称为信噪比，用SNR表示。接收到的码字y经过硬判决得到结果z=（z1，...，zN）T， zN是通过对yN的符号进行映射得到的，映射规则为+1→0，-1→1。

当前，常用的高效迭代解码算法有两种，这两种算法的每一步都涉及决策过程：

（1）比特翻转解码算法。BF解码的一般思路是构建一个合适的度量，允许解码器根据编码约束条件下的可靠性对比特进行排序[10]。在其最简单的形式中，BF使用硬判决输出z，并在迭代地寻找翻转之后，找出能最大限度减少当前违反PC方程数量的位置。当前，BF解码在学术界得到了广泛的研究，在许多现代编码理论的文献中都有涉及，比如[11-14]。

（2）置信传播译码算法。BP算法是一种迭代算法，消息沿着由编码的tanner图表示的边进行传播。BP算法的大概流程为：

首先是初始化，可由式（1）（2）实现：

其中，Ki为校正因子，保证成立。如果大于0.5则为当前码字判决为0，反之判决为1，从而得到判决结果r。

4）校正子计算方法为s′=Hr=[s0，s1，s2，...，sn]，然后将smod 2得到校正子s。如果s不为0向量，则转至1）继续迭代过程直到译码成功或者达到译码最大次数上限。

2  马尔可夫决策过程

马尔可夫决策过程，为确定或随机环境下的决策建模提供了一个数学框架。马尔可夫决策过程可以用来获得最优的决策策略，用数据驱动的最优度量的学习来替代启发式学习。

一个时不变的马尔可夫随机过程S0，S1，…，其状态转移概率仅受代理根据对过去状态的了解而采取的行动At影响。其中，s、s′∈S，a∈A，S和A是包含所有可能状态与动作的有限集合。代理同样会接收到一个奖励Rt=R（St，At，St+1），并且奖励只取决于状态St，St+1和动作At。这个代理的决策过程被描述为一个策略π：S→A，表示将观察到的状态映射到动作。我们的目标是找到一个最佳决策π*，使使得在每个可能的状态下以预期奖励返回一个最佳动作，其中，0<γ<1是未来奖励的衰减因子。

过渡和奖励概率已知的情况下，可以采用动态编程来计算最优策略;概率未知的情况下，如果假设状态和奖励是可观察的，则仍可以通过与环境的反复交互发现最优策略，这就是所谓的强化学习（RL）。下面介绍两种文献中最常用的RL方法：

（1）Q-learning。最直接的RL实例被称为Q-learning。其最优策略根据Q函数Q：S×A→R，通过式子：得到。Q函数用于衡量行动的质量，正式定义为当智能体处于状态s，采取行动a，然后采取最佳行动时的预期折现的未来奖励。Q函数的主要优点是，它可以从任何“足够随机”的代理的观察中反复估计。下文给出了Q-learning的伪代码，其中第5行中生成行动的一个探索策略为：

Input： learning rate α， discount factor γ

Output： estimated Q-function

Initialize Q（s， a） ← 0 for all s ∈ S， a ∈ A

Fori = 1， 2， … do

initialize starting state s          // restart the MDP

while s is not terminal do

choose action a             // ε-greedy

execute a， observe reward r and next state s

Q（s， a） ← （1-α）Q（s，a）+α（r+ γmaxa∈AQ（s， a））

s ←s

由此，我们发现Q函数能用式（9）递归的表示为：

这个表达式构成了Q-learning的理论基础，它在一定条件下收敛于真正的Q-函数。

（2）带有函数近似值的拟合Q-学习。对于标准的Q-learning，人们必须存储一个|S|×|A|的实值表。如果其中一个集合非常大，那么标准的Q-learning将难以实现。拟合Q-learning的想法是学习Q（s，a）的低复杂度近似值。将Qθ（s，a）作为Q函数的近似值，以θ为参数。拟合Q-learning在模拟MDP和更新当前参数之间交替进行，以获得对Q-函数的更好估计。假设我们已经模拟并存储了一个集合D中B个过往经验（s，a，r，s′）。更新参数θ是为了减少经验损失，可由式（10）表示：

下面给出拟合Q-learning的伪代码：

Input： learning rate α， batch size B

Output： parameterized estimate of the Q-function

Initialize parameters θ and D←?

Fori = 1， 2， … do

initialize starting state s          // restart the MDP

while s is not terminal do

choose action a             // ε-greedy

execute a， observe reward r and next state s

store transition（s， a， r， ） in D

s←

if |D| = B then

θ←θ-α▽θLD（θ）

empty D

其中，梯度下降是用來根据损失（1）更新参数θ的。通常选择Qθ（s，a）作为一个（深度）神经网络（NN），在这种情况下，θ是网络的权重，拟合Q-learning被称为深度Q-learning。深度Q-learning所采用的主要技巧是经验回放（experience replay），即将每次和环境交互得到的奖励与状态更新情况都保存起来，用于后面目标Q值的更新。通过经验回放得到的目标Q值与通过Q网络计算得到的Q值，二者之间肯定是存在一定误差的，我们可以通过梯度的反向传播来更新神经网络的参数w。我们使用了两个Q网络，一个当前Q网络Q用于选择动作，更新模型参数。另一个目标Q网络Q′用于计算目标Q值。目标Q网络的网络参数不需要迭代更新，而是每隔一段时间从当前Q网络Q复制过来（即延时更新），这样可以减少目标Q值与当前Q值的相关性。

3  基于深度强化学习的置信传播算法

我们提出了一种利用深度强化学习来改善置信传播算法的方案。利用软信息进行译码简单来说就是通过每一次的迭代去更新各个信息节点的对数似然比值，然后进行判决，判断译码是否正确。当前对数似然比值仅与上次迭代过程中的对数似然比值有关，而与之前的状态无关（即在tanner图上进行数据传递），tanner图如图1所示。因此，可以将利用软信息进行译码的过程与马尔科夫决策过程相类比，将软判决译码映射到马尔科夫决策过程中去（有些文献里也用c表示校验节点，即图1中的s节点）。

 本方案的基本流程为：

（1）利用接收码字初始化各个信息节点的对数似然比值，作为初始状态S0。

（2）根据既定的探索策略选择一个动作At，更新变量节点的对数似然比值。

（3）根据动作选择，变量节点转变为新的状态s′和反馈奖励r。

（4）利用神经网络生成拟合的Q值并更新神经网络参数。

（5）根据新的状态s′生成判决结果x，判决HTx是否为0（或者是否到最大迭代步数），是则结束，否则转步骤（2）。

本方案的基本参数设定为：

（1）状态空间S。取所有变量节点的对数似然比值作为状态，由于对数似然比值是一个连续值，因此状态空间是一个连续的状态空间，我们需要引入神经网络来拟合Q-学习中的Q值。

（2）动作空间A。任选其中一个变量节点，取一个改变值Δ（V ），选择在原来对数似然比的基础上+Δ（V ）/-Δ（V ）两种动作，则At一共有2N种动作。本方案中取Δ（V ）= 0.01。

（3）信道选择。AWGN信道，信噪比SNR满足SNR=10lg（10Eb/N0），白噪声服从高斯分布，且均值为0，方差为噪声平均功率。因为假定的AWGN信道只有高斯白噪声，所以在信噪比SNR设定完成后就能直接在传输码字上添加确定的噪声，之后获得接收码字。

4  仿真结果

本方案所采用的开发工具是PyCharm和MATLABR2020a。传统的置信传播方法采用MATLAB语言实现，而基于深度强化学习的置信传播算法则采用Python语言开发，开发环境为Python3.8，主要使用了torch库（用于引入神经网络）和matplotlib库（用于绘图）。编码方案为BCH（63，45），其中，输入为63维，输出为126维，所以该神经网络是非常复杂的，其探索空间也是比较大的。该网络一共有三层：输入层（63，64）、中间层（64，64）、输出层（64，126），激活函数为relu，探索率下限设置为0.1。

图2展示了采取三种不同探索率下限来对比误码率的结果，其中x轴为SNR（即信噪比Eb/N0取对数后的结果），单位为dB，y轴为误码率BER（之后的图表x，y轴也相同）。如果神经网络训练稳定之后，误码率会随着神经网络探索率下限的降低而升高，在SNR小于10 dB的范围内，SNR-BER曲线符合我们的预期。同时，我们采取不同的网络结构来对比误码率的结果，例如去掉中间层（64，64），如图3所示。可以看到，神经网络层数越多，误码率越低，在SNR<10 dB的区间内，SNR-BER基本符合预期。

 同时，我们也完成了基于深度强化学习的BCH（63，45）译码，并用训练结果（BF_RL）与用BP方法实现的BCH（63，45）码字解码（BP）相对比，如图4所示，从图中可以看出基于深度强化学习的BCH（63，45）译码明显优于传统的BP算法，在BER为10-5时有大约0.75 dB的优势。

 最后，我们针对比特翻转译码使用强化学习方法对文献[14]进行了简单复现（BF_RL），并将本文使用的基于深度强化学习的置信传播译码方法进行了对比，如图5所示，结果显示在（7，3）线性分组码中优势比较明显，在BER为10-5时大约有2 dB增益。

 5  结  论

在本文中，我们提出了一个新颖的二进制线性码BP解码的RL框架。研究表明，如果适当选择状态和行动空间，BP解码可以映射到马尔科夫决策过程。原则上，这可以实现数据驱动的最佳BP决策策略的学习。标准的（基于表格的）和装有NN函数近似器的Q-learning都被用来从数据中学习好的决策策略。结果表明，我们所提出的学习型BP解码器具有一定的优势，然而，优势仅仅局限在中短码字上，长码字始终面临状态空间和动作空间过大的问题。因此，利用强化学习进行长码字的解码仍然是一个极具挑战性的问题，这将是我们之后的研究方向。

参考文献：

[1] GRUBER T，CAMMERER S，HOYDIS J，et al. On deep learning-based channel decoding [C]//2017 51st Annual Conference on Information Sciences and Systems （CISS）.Baltimore：IEEE，2017：1-6.

[2] OSHEA T，HOYDIS J. An introduction to deep learning for the physical layer [J].IEEE Transactions on Cognitive Communications and Networking，2017，3（4）：563-575.

[3] NACHMANI E，BEERY Y，BURSHTEIN D. Learning to decode linear codes using deep learning [C]// 2016 54th Annual Allerton Conference on Communication， Control， and Computing （Allerton）.Monticello：IEEE，2016：341-346.

[4] BENNATAN A，CHOUKROUN Y，KISILEV P. Deep learning for decoding of linear codes-a syndrome-based approach [C]//2018 IEEE International Symposium on Information Theory （ISIT）.Vail：IEEE，2018：1595-1599.

[5] NACHMANI E，MARCIANO E，LUGOSCH L，et al. Deep learning methods for improved decoding of linear codes [J].IEEE Journal of Selected Topics in Signal Processing 2018，12（1）：119-131.

[6] NACHMANI E，BEERY Y，Burshtein D. Learning to decode linear codes using deep learning [C]//2016 54th Annual Allerton Conference on Communication， Control， and Computing （Allerton）. Monticello：IEEE，2016：341-346.

[7] LIANG F，SHEN C，WU F. An iterative BP-CNN architecture for channel decoding [J]. IEEE Journal of Selected Topics in Signal Processing，2018，12（1）：144-159.

[8] Wang X B，Zhang H Z，Li R，et al. Learning to flip successive cancellation decoding of polar codes with LSTM networks [C]//2019 IEEE 30th Annual International Symposium on Personal， Indoor and Mobile Radio Communications （PIMRC）. Istanbul：IEEE，2019：1-5.

[9] CARPI F，H?GER C，MARTAL? M，et al. Reinforcement learning for channel coding： Learned bit-flipping decoding [C]//2019 57th Annual Allerton Conference on Communication， Control， and Computing （Allerton）. Monticello：IEEE，2019：922-929.

[10] Ryan W，Lin S. Channel codes： classical and modern [M]. Cambridge university press，2009.

[11] BOSSERT M，HERGERT F. Hard-and soft-decision decoding beyond the half minimum distance---An algorithm for linear codes （Corresp.） [J]. IEEE transactions on information theory，1986，32（5）：709-714.

[12] KOU Y，LIN S，FOSSORIER M P C. Low-density parity-check codes based on finite geometries： a rediscovery and new results [J].IEEE Transactions on Information theory，2001，47（7）：2711-2736.

[13] Zhang J T，FOSSORIER M P C. A modified weighted bit-flipping decoding of low-density parity-check codes [J].IEEE Communications Letters，2004，8（3）：165-167.

[14] JIANG M，ZHAO C M，SHI Z H，et al. An improvement on the modified weighted bit flipping decoding algorithm for LDPC codes [J].IEEE Communications Letters，2005，9（9）：814-816.

作者簡介：高源浩（1997—），男，汉族，重庆铜梁人，硕士研究生在读，研究方向：基于强化学习的线性分组码译码方法。