LDPC码短环的置信传播改进算法 Belief Propagation Improvement Algorithm for LDPC Codes with Short Cycles

doi:10.12677/AAM.2023.121023

Advances in Applied Mathematics
Vol. 12 No. 01 ( 2023 ), Article ID: 60832 , 10 pages
10.12677/AAM.2023.121023

LDPC码短环的置信传播改进算法

王晓冰，杨卫华^*

●How to Cite this Article

太原理工大学数学学院，山西太原

收稿日期：2022年12月28日；录用日期：2023年1月21日；发布日期：2023年1月31日

摘要

低密度奇偶校验码(Low Density Parity Check Codes, LDPC codes)具有高效译码性能，列入了5GNR标准，在实际通信中被广泛使用。LDPC码的校验矩阵与Tanner图具有一一对应关系，当LDPC码对应的Tanner图是树时，置信传播算法译码结果等价于最大似然译码结果。但在实际应用中，LDPC码的Tanner图包含大量短环，运用置信传播算法时短环的存在会导致信息重复计算造成计算误差，其中四环的影响最为明显。为此大量学者研究寻找提高译码性能的改进算法，提出以牺牲计算量为代价降低或解决短环内信息传递的误差。为了解决短环问题，在工程中能得到更好的应用，本文在置信传播算法上做了改进，提出了改进的对数域置信传播算法，使其不损失原算法的译码性能，保证具有四环的Tanner图信息传递具有良好性能，并降低了置信传播译码算法的计算复杂度。

关键词

置信传播算法，LDPC码，Tanner图，短环

Belief Propagation Improvement Algorithm for LDPC Codes with Short Cycles

Xiaobing Wang, Weihua Yang^*

College of Mathematics, Taiyuan University of Technology, Taiyuan Shanxi

Received: Dec. 28^th, 2022; accepted: Jan. 21^st, 2023; published: Jan. 31^st, 2023

ABSTRACT

Low Density Parity Check Codes have high decoding performance and are included in the 5GNR standard, which is widely used in practical communication. The check matrix of LDPC codes has a one-to-one correspondence with the Tanner graph, and when the Tanner graph of LDPC codes is a tree, the decoding result of the belief propagation algorithm is equivalent to the maximum likelihood decoding result. However, in practice, the Tanner graph of LDPC codes contains a large number of short cycles, and the existence of short cycles in the belief propagation algorithm will lead to computational errors caused by double computation of information, among which the impact of four-cycle is most obvious. For this reason, a large number of scholars have researched to find improved algorithms to improve the decoding performance and reduce or solve the error of information transmission in short cycles at the expense of computation. In order to solve the short-cycle problem and get better application in engineering, this paper makes improvements on the belief propagation algorithm and proposes an improved log-domain belief propagation algorithm so that it does not lose the decoding performance of the original algorithm, ensures good performance of the Tanner graph information transfer with four-cycle, and reduces the computational complexity of the belief propagation decoding algorithm.

Keywords:Belief Propagation Algorithm, LDPC Codes, Tanner Graph, Short Cycles

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

LDPC码是近年信道编码领域的研究热点，目前在深空通信、光纤通信、卫星数字视频和音频广播等领域已经得到了广泛的应用。在2016年10月，3GPP确定采用LDPC码作为5G移动通信中增强宽带业务场景数据信道的纠错编码方案 [1]。

LDPC码是由Robert G. Gallager于1962年提出的一类具有稀疏校验矩阵的线性分组码，它不仅在中长码中可以逼近香农极限，具有良好的译码性能，而且译码复杂度较低、结构灵活 [2]。但最初提出之际，由于缺乏可行的译码算法导致结果不理想，此后的35年间LDPC码基本上无人问津，仅有少量学者对其进行了研究，其中Tanner在1981年给出了LDPC码的图表示，即后来所称的Tanner图，将LDPC码进行了推广 [3]。1996年MacKay和Neal等人对LDPC码重新进行了研究，提出了可行的译码算法，从而进一步发现了LDPC码所具有的良好性能，迅速引起强烈反响和极大关注 [4]。

对于LDPC码译码问题，Gallager博士提出了基于硬判决以及软判决的两种译码方案，硬判决译码方案也称为Gallager硬判决译码算法，例如比特翻转(Bit-Flipping, BF)译码算法；而软判决译码采用了后验概率信息，并通过迭代运算，使得LDPC码的性能得以逼近香农限 [2]。本文以基于软判决的译码算法——置信传播(Belief Propagation, BP)译码算法为基础进行研究。置信传播算法是基于Tanner图的迭代译码算法，在迭代过程中，“消息”通过Tanner图中变量节点和校验节点之间的连边进行传递，在多次迭代后进行译码判决。但在使用BP译码算法的过程中，Tanner图不可避免会出现短环，使消息在迭代过程中被重复计算，大大影响了BP译码的性能。大量学者对于如何消除或减弱置信传播算法中环造成的影响展开了研究。对于包含环的网络，BP算法又被称为循环置信传播算法(Loopy Belief Propagation, LBP)，又经简化得到最大积算法和最小和算法。Pearl (1988)指出在树图结构上，使用BP算法进行信息传递可以得到精确解，并证明了在多环图中最大积算法的不动点是后验概率的邻域最大值，具有局部最优性质 [5]。Weiss (2000)得到对于单环图，BP算法也可以达到收敛的结果 [6]。Weiss (2001)分析了对于具有任意拓扑和任意概率分布的图，最大积算法基于不动点的赋值是后验概率的邻域最大值，并且对于不连通的树和单环图，最大后验概率(Maximum a posteriori probability, MAP)赋值是强局部最优赋值 [7]。Kschischang (2001)将因子图的全局函数分解为局部函数的乘积，并把因子图与和积算法结合起来，得到基于贝叶斯网的BP算法 [8]。Heskes (2004)证明了LBP的不动点与Bethe自由能的极值一一对应 [9]。Mooij和Kappen (2007)基于压缩映射，提出了在商赋范空间上基于马尔可夫网的和积算法收敛到唯一不动点的充分条件 [10]。Tatikonda和Jordan (2012)将LBP的收敛性与计算树上吉布斯序列的弱极限的存在联系起来 [11]。时至今日，环的存在仍是BP译码问题中的一大难点。因此，在LDPC码应用BP算法的过程中，需要尽量降低短环的影响，比如LDPC码的约束里要求尽量不要有四元环。Raveendran (2014)提出了概率域上基于BP算法对短环的改进方案，提高了包含短环的LDPC码的译码正确率 [12]。

BP译码算法有着非常好的译码性能，许多LDPC码的译码改进算法都是建立在BP译码算法的基础上，但计算量较大，因此有学者将概率似然比函数引入到BP译码算法中，在此基础上得到了对数域置信传播算法(Log Likelihood Radio Belief Propagation, LLR BP)，LLR BP算法是在对数域上计算后验概率信息，将BP算法中大量的乘积运算转化为加法运算，易于工程实现 [13]。

一般情况下假设在迭代过程中节点之间的信息传递是彼此独立的，但考虑到短环内的信息具有关联性，对短环内的迭代过程做了改进，把短环内的节点集看作一个整体，计算其联合概率，这样就避免了由于环的存在造成信息的重复传递，从而降低了信息误差。在不降低译码性能的前提下，本文引入了对数似然函数，将消除四环误差影响的迭代算法应用于LLR BP算法中，在对数域中进行计算，与原算法相比，改进后的算法在保证译码性能没有下降的同时，减少了大量的乘法运算，处理速度更快，因此具有更好的实际应用价值。

本文的组织结构如下：第二节基于Tanner图对LDPC码的背景进行了简单介绍，并阐述了基于概率域的BP译码算法流程，第三节对LLRBP算法进行改进，给出了基于对数域的LDPC码短环译码的改进方案以及算法流程。

2. 预备知识

2.1. LDPC码和Tanner图

LDPC码是一类由校验矩阵H定义的线性分组码，每一个码字都包含在H矩阵的零空间中，对于任意一组码字 $c = {c_{1}, \dots, c_{n}}$ ，都需满足 $H c^{T} = 0$ 的校验关系。校验矩阵H可以用Tanner图表示，Tanner图由校验节点集、变量节点集以及边集组成。变量节点集中的节点代表码元，分别与LDPC码校验矩阵的列一一对应；校验节点集中的节点代表校验方程，分别与校验矩阵的行一一对应。Tanner图是二部图，校验节点集任意节点间无边相连，变量节点集任意节点间无边相连，若变量节点与校验节点之间有边相连，则校验矩阵中对应的位置为1，否则为0。因校验矩阵具有稀疏性，大部分元素为0，仅有少部分元素为1，因此也称为稀疏校验矩阵。校验矩阵的每一列中非零元素的个数称为列重，每一行中非零元素的个数称为行重。校验矩阵的列重和行重与Tanner图中变量节点和校验节点的度保持一致，若校验矩阵的列重是常数 $γ$ ，行重是常数 $β$ ，则称LDPC码为 $(γ, β)$ -正则LDPC码，否则称为非正则LDPC码。

Tanner图中的环是由校验节点与变量节点交错连接构成的闭合路径，环长定义为它所包含的边的数量，所有环中最小的环长称为围长(girth)。Tanner图作为二部图，其中的环由变量节点与校验节点交错组成，所以不可能生成奇数长的环，因此Tanner图中的环都是偶数环，且环长大于等于4。

对LDPC码的校验矩阵与校验方程举例如下：

$H = (\begin{array}{l} 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{array}) \begin{array}{l} c_{1} : v_{1} \oplus v_{4} = 0 \\ c_{2} : v_{2} \oplus v_{3} = 0 \\ c_{3} : v_{1} \oplus v_{3} \oplus v_{5} = 0 \\ c_{4} : v_{4} \oplus v_{5} = 0 \end{array}$

该校验矩阵H对应一个非正则LDPC码，图1表示为该校验矩阵的Tanner图，该图不包含4长环，仅包含6长环，因此该图是一个围长为6的Tanner图，图中的方形节点为校验节点，圆形节点为变量节点，该图包含的长为6的环路径为： $c_{1} \to v_{4} \to c_{4} \to v_{5} \to c_{3} \to v_{1} \to c_{1}$ ，如加粗线条所示。

Figure 1. Tanner graph of the checkmatrix

图1. 校验矩阵的Tanner图

2.2. 置信传播算法

置信传播译码算法又称为和积译码算法，是在概率域上通过后验概率迭代运算实现消息传递，包含了较多的乘法运算，具有较高的算法运算量。置信传播译码是LDPC码的基本译码算法，很多改进的译码算法均是在置信传播译码的基础上得到的。

假设传递的码字 $c = {c_{1}, \dots, c_{n}}$ 经过映射后得到 $x = {x_{1}, \dots, x_{n}}$ ，由信道译码后接收到的序列为 $y = {y_{1}, \dots, y_{n}}$ ，译码判决得到码字 $\hat{c}$ 。在Tanner图中，变量节点用 $v_{i}$ 表示，校验节点用 $c_{j}$ 表示。在初始状态下 $v_{i}$ 接受到的信息，称为局部证据，设为 $P_{i} (0) = P r (x_{i}^{(0)} = 0 | y_{i})$ 。

定理1 (Gallager定理) [2]：在消息传递过程中，第t次迭代时变量节点 $v_{i}$ 向校验节点 $c_{j}$ 发送的信息中

包含偶数个1的概率为 $\frac{1 + \prod_{v_{i} \in N (c_{j}) \ v_{k}} (2 v_{i j}^{(t - 1)} (0) - 1)}{2}$ ，变量节点 $v_{i}$ 向校验节点 $c_{j}$ 发送的信息中包含奇数个1的概率为 $\frac{1 + \prod_{v_{i} \in N (c_{j}) \ v_{k}} (1 - 2 v_{i j}^{(t - 1)} (0))}{2}$ 。

BP译码的具体过程如下所示：

1) 首先初始化变量节点的信息，每个变量节点的初始信息是接受到的局部证据：

$q_{i j}^{(0)} (0) = P_{i} (0) = P r (x_{i}^{(0)} = 0 | y_{i})$ (1)

$q_{i j}^{(0)} (1) = P_{i} (1) = P r (x_{i}^{(0)} = 1 | y_{i})$ (2)

2) 节点迭代更新过程：

第t次迭代校验节点更新方程，根据定理1得：

$r_{j i}^{(t)} (0) = \frac{1 + \prod_{v_{k} \in N (c_{j}) \ v_{i}} (2 q_{k j}^{(t - 1)} (0) - 1)}{2}$ (3)

$r_{j i}^{(t)} (1) = \frac{1 + \prod_{v_{k} \in N (c_{j}) \ v_{i}} (1 - 2 q_{k j}^{(t - 1)} (0))}{2}$ (4)

其中 $r_{j i}^{(t)} (0)$ 表示为对于校验节点 $c_{j}$ ，在已知其相连的除 $v_{i}$ 外的所有变量节点取值的概率条件下，第j个校验方程被满足的概率。

第t次迭代变量节点更新方程：

$q_{i j}^{(t)} (0) = k_{i j} q_{i j}^{(0)} (0) \prod_{c_{k} \in N (v_{i}) \ c_{j}} r_{k i}^{(t)} (0)$ (5)

$q_{i j}^{(t)} (1) = k_{i j} q_{i j}^{(0)} (1) \prod_{c_{k} \in N (v_{i}) \ c_{j}} r_{k i}^{(t)} (1)$ (6)

其中 $k_{i j}$ 是归一化常数，保证了 $q_{i j}^{(t)} (0) + q_{i j}^{(t)} (1) = 1$ 。 $q_{i j}^{(t)} (0)$ 表示为对于变量节点 $v_{i}$ ，在已知与其相连的除 $c_{j}$ 外的所有校验节点的校验方程是否被满足的概率条件下， $v_{i}$ 取值为0的概率； $q_{i j}^{(t)} (1)$ 是同条件下， $v_{i}$ 取值为1的概率。

3) 计算变量节点的后验概率：

$q_{i}^{(t)} (0) = k_{i j} q_{i j}^{(0)} (0) \prod_{c_{k} \in N (v_{i})} r_{k i}^{(t)} (0)$ (7)

$q_{i}^{(t)} (1) = k_{i j} q_{i j}^{(0)} (1) \prod_{c_{k} \in N (v_{i})} r_{k i}^{(t)} (1)$ (8)

4) 译码判决：若 $q_{i}^{(t)} (0) > q_{i}^{(t)} (1)$ ，则 ${\hat{c}}_{i} = 0$ 否则 ${\hat{c}}_{i} = 1$ 。若 $H \hat{c}$ 满足 $H \hat{c} = 0$ 则译码成功，停止算法，否则转回步骤2)继续迭代，直到迭代次数达到预先设定的最大迭代次数。

3. 改进的LLR算法

3.1. 短环改进算法

BP短环译码算法 [12] 虽然对于包含大量长为4的短环的LDPC码译码正确率起到了很大的改善作用，有效降低了信息的重复计算，但是信息传递准确率的提高是以计算量的增加为代价的。同时概率BP译码算法包含了大量的连乘运算，实现时具有较高的计算复杂度，资源消耗大，引入对数似然比函数，将概率信息用对数似然比表示，可以将大量的乘法运算转化为加法运算，降低计算复杂度。为此，本文将改善的BP算法应用于LLR BP中，能够在保证译码正确率的前提下，降低算法的计算量，起到更好的实际应用效果。

Figure 2. A Tanner graph with girth = 4, and the nodes in the short cycle and the set of neighbor nodes

图2. 围长为4的Tanner图，短环内的节点与其邻节点集

图2为一个围长为4的Tanner图。本文主要关注短环内的信息传递过程，假设环内的变量节点分别为 $v_{1}$ 和 $v_{2}$ ，校验节点分别为 $c_{1}$ 和 $c_{2}$ ，环外的节点信息集根据它们与环内节点的连边分为四个变量集，短环外连接 $v_{1}$ 的校验节点集称为 $N_{v_{1}}$ ，连接 $v_{2}$ 的校验节点集称为 $N_{v_{2}}$ ，连接 $c_{1}$ 的校验节点集称为 $N_{c_{1}}$ ，连接 $c_{2}$ 的校验节点集称为 $N_{c_{2}}$ 。

假设短环内的节点集之间传递的消息不具有独立性，它们之间相互影响，短环内的节点集与其环外的邻节点集之间传递的信息具有弱依赖性。对于短环内的变量节点，以 $v_{1}$ 为例，在第t次迭代过程中接收到的信息时是由观测节点 $y_{1}$ 和所有与 $v_{1}$ 相连的校验节点决定的：

$\ln \frac{P r (v_{1 k}^{(t)} = 0)}{P r (v_{1 k}^{(t)} = 1)} = \ln \frac{P r (v_{1}^{(0)} = 0, c_{11}^{(t)} = 0, c_{21}^{(t)} = 0, c_{j 1}^{(t)} = 0 | y_{1} : c_{j} \in N_{v_{1}})}{P r (v_{1}^{(0)} = 1, c_{11}^{(t)} = 1, c_{21}^{(t)} = 1, c_{j 1}^{(t)} = 1 | y_{1} : c_{j} \in N_{v_{1}})}$

根据假设，环内与环外的信息传递具有弱依赖性：

$\ln \frac{P r (v_{1 k}^{(t)} = 0)}{P r (v_{1 k}^{(t)} = 1)} = \ln \frac{P r (v_{1}^{(0)} = 0, c_{11}^{(t)} = 0, c_{21}^{(t)} = 0 | y_{1}) P r (c_{j 1}^{(t)} = 0 : c_{j} \in N_{v_{1}})}{P r (v_{1}^{(0)} = 1, c_{11}^{(t)} = 1, c_{21}^{(t)} = 1 | y_{1}) P r (c_{j 1}^{(t)} = 1 : c_{j} \in N_{v_{1}})}$

环外校验节点传递给 $v_{1}$ 的信息具有独立性，可以将 $P r (c_{j 1}^{(t)} = 0 : c_{j} \in N_{v_{1}})$ 写成乘积的形式，其中设 $P r (c_{j 1}^{(t)} = 0) = r_{j 1}^{(t)} (0)$ ，则：

$\ln \frac{P r (v_{1 k}^{(t)} = 0)}{P r (v_{1 k}^{(t)} = 1)} = \ln \frac{P r (v_{1}^{(0)} = 0, c_{11}^{(t)} = 0, c_{21}^{(t)} = 0 | y_{1}) \prod_{c_{j} \in N_{v_{1}}} r_{j 1}^{(t)} (0)}{P r (v_{1}^{(0)} = 1, c_{11}^{(t)} = 1, c_{21}^{(t)} = 1 | y_{1}) \prod_{c_{j} \in N_{v_{1}}} r_{j 1}^{(t)} ( 1 )}$

根据贝叶斯原理，上式可以写作：

$\ln \frac{P r (v_{1 k}^{(t)} = 0)}{P r (v_{1 k}^{(t)} = 1)} = \ln \frac{P r (v_{1}^{(0)} = 0 | y_{1}) P r (c_{11}^{(t)} = 0, c_{21}^{(t)} = 0 | y_{1}, v_{1}^{(0)} = 0) \prod_{c_{j} \in N_{v_{1}}} r_{j 1}^{(t)} (0)}{P r (v_{1}^{(0)} = 1 | y_{1}) P r (c_{11}^{(t)} = 1, c_{21}^{(t)} = 1 | y_{1}, v_{1}^{(0)} = 1) \prod_{c_{j} \in N_{v_{1}}} r_{j 1}^{(t)} ( 1 )}$

由于观测节点 $y_{1}$ 与校验节点 $c_{11}^{(t)}, c_{21}^{(t)}$ 独立无关，因此可以将 $y_{1}$ 从联合概率的条件项中提出：

$\ln \frac{P r (v_{1 k}^{(t)} = 0)}{P r (v_{1 k}^{(t)} = 1)} = \ln \frac{P r (v_{1}^{(0)} = 0 | y_{1}) P r (c_{11}^{(t)} = 0, c_{21}^{(t)} = 0 | v_{1}^{(0)} = 0) \prod_{c_{j} \in N_{v_{1}}} r_{j 1}^{(t)} (0)}{P r (v_{1}^{(0)} = 1 | y_{1}) P r (c_{11}^{(t)} = 1, c_{21}^{(t)} = 1 | v_{1}^{(0)} = 1) \prod_{c_{j} \in N_{v_{1}}} r_{j 1}^{(t)} (1)}$ (9)

短环BP改进算法着重于节点之间的联合概率计算，设 $P r (c_{11}^{(t)} = 0, c_{21}^{(t)} = 0 | v_{1}^{(0)} = 0) = γ_{v_{1} = 0}^{(t)}$ 表示在给定信道概率下， $c_{11}^{(t)} = 0, c_{21}^{(t)} = 0$ 的联合概率，则(9)式可以写作：

$\ln \frac{P r (v_{1 k}^{(t)} = 0)}{P r (v_{1 k}^{(t)} = 1)} = \ln \frac{q_{1 k}^{(0)} (0) γ_{v_{1} = 0}^{(t)} \prod_{c_{j} \in N_{v_{1}}} r_{j 1}^{(t)} (0)}{q_{1 k}^{(0)} (1) γ_{v_{1} = 1}^{(t)} \prod_{c_{j} \in N_{v_{1}}} r_{j 1}^{(t)} ( 1 )}$

以 $P r (v_{1 k}^{(t)} = 0) = q_{1 j}^{(0)} (0) γ_{v_{1} = 0}^{(t)} \prod_{c_{k} \in N_{v_{1}}} r_{k 1}^{(t)} (0)$ 为例，计算 $γ_{v_{1} = 0}^{(t)}$ 。首先设 $p_{0}^{(t)} (c_{1})$ 表示事件在第t次迭代过程中，变量节点集 $N_{c_{1}}$ 发送给 $c_{1}$ 的信息有偶数个1的发生概率，则 $p_{0}^{(t)} (c_{1}) = \frac{1 + \prod_{v_{i} \in N_{c_{1}}} (2 q_{i 1}^{(t - 1)} (0) - 1)}{2}$ ；同理， $p_{0}^{(t)} (c_{2})$ 表示事件在第t次迭代过程中，变量节点集 $N_{c_{2}}$ 发送给 $c_{2}$ 的信息有偶数个1的发生概率，则 $p_{0}^{(t)} (c_{2}) = \frac{1 + \prod_{v_{i} \in N_{c_{2}}} (2 q_{i 2}^{(t - 1)} (0) - 1)}{2}$ 。 $p_{1}^{(t)} (c_{1})$ 和 $p_{1}^{(t)} (c_{2})$ 分别表示为变量节点集 $N_{c_{1}}$ 和 $N_{c_{2}}$ 发送给 $c_{1}$ 和 $c_{2}$ 的信息有奇数个1的发生概率。 $γ_{v_{1} = 0}^{(t)}$ 中有两项联合概率的乘积因子为0，将剩余两项表示为 $α_{v_{1} = 0}^{(t)}$ 和 $β_{v_{1} = 0}^{(t)}$ ，则：

$\begin{matrix} γ_{v_{1} = 0}^{(t)} = α_{v_{1} = 0}^{(t)} + β_{v_{1} = 0}^{(t)} \\ = p_{0}^{(t - 1)} (c_{1}) p_{0}^{(t - 1)} (c_{2}) P r (v_{21}^{(t - 1)} = 0, v_{22}^{(t - 1)} = 0 | v_{1}^{(0)} = 0) \\ + p_{1}^{(t - 1)} (c_{1}) p_{1}^{(t - 1)} (c_{2}) P r (v_{21}^{(t - 1)} = 1, v_{22}^{(t - 1)} = 1 | v_{1}^{(0)} = 0) \end{matrix}$

$α_{v_{1} = 0}^{(t)}$ 和 $β_{v_{1} = 0}^{(t)}$ 的表达式如下所示：

对于t = 1，2次迭代，

$α_{v_{1} = 0}^{(1)} = P_{2} (0) p_{0}^{(0)} (c_{1}) p_{0}^{(0)} (c_{2})$ ， $β_{v_{1} = 0}^{(1)} = P_{2} (1) p_{1}^{(0)} (c_{1}) p_{1}^{(0)} ( c 2 )$

$α_{v_{1} = 0}^{(2)} = P_{2} (0) Δ^{(2)} (0) \prod_{c_{j} \in N_{v_{2}}} r_{j 2}^{(1)} (0)$ ， $β_{v_{1} = 0}^{(2)} = P_{2} (1) Δ^{(2)} (1) \prod_{c_{j} \in N_{v_{2}}} r_{j 2}^{(1)} ( 1 )$

对于t > 2次迭代，

$α_{v_{1} = 0}^{(t)} = Δ^{(t)} (0) \prod_{c_{j} \in N_{v_{2}}} r_{j 2}^{(t - 1)} (0) \prod_{c_{j} \in N_{v_{1}}} r_{j 1}^{(t - 2)} (0) α_{v_{1} = 0}^{(t - 2)}$

$β_{v_{1} = 0}^{(t)} = Δ^{(t)} (1) \prod_{c_{j} \in N_{v_{2}}} r_{j 2}^{(t - 1)} (1) \prod_{c_{j} \in N_{v_{1}}} r_{j 1}^{(t - 2)} (0) β_{v_{1} = 0}^{(t - 2)}$

其中，

$Δ^{(t)} (0) = p_{0}^{(t - 1)} (c_{1}) p_{0}^{(t - 1)} (c_{2}) p_{0}^{(t - 2)} (c_{1}) p_{0}^{(t - 2)} ( c 2 )$

$Δ^{(t)} (1) = p_{1}^{(t - 1)} (c_{1}) p_{1}^{(t - 1)} (c_{2}) p_{1}^{(t - 2)} (c_{1}) p_{1}^{(t - 2)} ( c 2 )$

因此 $γ_{v_{1} = 0}^{(t)} = α_{v_{1} = 0}^{(t)} + β_{v_{1} = 0}^{(t)}$ ，同理可推得 $γ_{v_{1} = 1}^{(t)} = α_{v_{1} = 1}^{(t)} + β_{v_{1} = 1}^{(t)}$ 的具体表达式。

综上所述， $P r (v_{i j}^{(t)} = 0) = q_{i j}^{(0)} (0) γ_{v_{i} = 0}^{(t)} \prod_{c_{k} \in N_{v_{i}} \ c_{j}} r_{k i}^{(t)} (0)$ ，其中 $q_{i j}^{(0)} (0) = P r (v_{i}^{(0)} = 0 | y_{i})$ ， $P r (v_{i j}^{(t)} = 1)$ 的推导过程与 $P r (v_{i j}^{(t)} = 0)$ 相似，

$\begin{matrix} P r (v_{i j}^{(t)} = 1) = q_{i j}^{(0)} (1) P r (c_{11}^{(t)} = 1, c_{21}^{(t)} = 1 | v_{1}^{(0)} = 1) \prod_{c_{k} \in N_{v_{i}} \ c_{j}} r_{k i}^{(t)} (1) \\ = q_{i j}^{(0)} (1) γ_{v_{i} = 1}^{(t)} \prod_{c_{k} \in N_{v_{i}} \ c_{j}} r_{k i}^{(t)} ( 1 ) \end{matrix}$

则变量节点 $v_{i}$ 向短环外的校验节点 $c_{j}$ 传递信息的更新方程为：

$\ln \frac{P r (v_{i j}^{(t)} = 0)}{P r (v_{i j}^{(t)} = 1)} = \ln \frac{q_{i j}^{(0)} (0) γ_{v_{i} = 0}^{(t)} \prod_{c_{k} \in N_{v_{i}} \ c_{j}} r_{k i}^{(t)} (0)}{q_{i j}^{(0)} (1) γ_{v_{i} = 1}^{(t)} \prod_{c_{k} \in N_{v_{i}} \ c_{j}} r_{k i}^{(t)} (1)}$ (10)

对于LLR BP算法中短环内变量节点的后验概率计算公式为：

$\ln \frac{q_{i}^{(t)} (0)}{q_{i}^{(t)} (1)} = \ln \frac{q_{i j}^{(0)} (0) γ_{v_{i} = 0}^{(t)} \prod_{c_{k} \in N_{v_{i}}} r_{k i}^{(t)} (0)}{q_{i j}^{(0)} (1) γ_{v_{i} = 1}^{(t)} \prod_{c_{k} \in N_{v_{i}}} r_{k i}^{(t)} (1)}$ (11)

3.2. LLR译码改进算法

结合3.1的内容，现将LDPC码的置信传播改进译码算法给出，图3为该算法的流程图，如下所示：

1) 首先初始化概率似然比信息：

$L (P_{i}) = \ln \frac{P_{i} (0)}{P_{i} (1)} = \ln \frac{P r (v_{i}^{(0)} = 0 | y_{i})}{P r (v_{i}^{(0)} = 1 | y_{i})}$ (12)

2) 节点迭代更新方程，设 $q_{i j}^{(t)} = \ln \frac{q_{i j}^{(t)} (0)}{q_{i j}^{(t)} (1)}$ ， $r_{j i}^{(t)} = \ln \frac{r_{j i}^{(t)} (0)}{r_{j i}^{(t)} (1)}$ ，变量节点接收到信息为0或为1的概率和为1，即 $q_{k j}^{(t)} (0) + q_{k j}^{(t)} (1) = 1$ ，则：

$\begin{matrix} r_{j i}^{(t)} = \ln \frac{r_{j i}^{(t)} (0)}{r_{j i}^{(t)} (1)} = \ln \frac{1 + \prod_{v_{k} \in N (c_{j}) \ v_{i}} (2 q_{i j}^{(t - 1)} (0) - 1)}{1 + \prod_{v_{k} \in N (c_{j}) \ v_{i}} (1 - 2 q_{i j}^{(t - 1)} (0))} = \ln \frac{1 + \prod_{v_{k} \in N (c_{j}) \ v_{i}} (1 - 2 q_{i j}^{(t - 1)} (1))}{1 - \prod_{v_{k} \in N (c_{j}) \ v_{i}} (1 - 2 q_{i j}^{(t - 1)} (1))} \\ = 2 \tanh^{- 1} [\prod_{v_{k} \in N (c_{j}) \ v_{i}} (1 - 2 q_{i j}^{(t - 1)} (1))] = 2 \tanh^{- 1} [\prod_{v_{k} \in N (c_{j}) \ v_{i}} (\frac{q_{i j}^{(t - 1)} (0) - q_{i j}^{(t - 1)} (1)}{q_{i j}^{(t - 1)} (0) + q_{i j}^{(t - 1)} (1)})] \end{matrix}$

因此第t次迭代校验节点更新方程为：

$r_{j i}^{(t)} = 2 \tanh^{- 1} (\prod_{v_{k} \in N (c_{j}) \ v_{i}} \tanh \frac{q_{k j}^{(t - 1)}}{2})$ (13)

第t次迭代变量节点更新方程进行以下改进：

设 $ϒ_{v_{i}} = \ln \frac{γ_{v_{i} = 0}^{(t)}}{γ_{v_{i} = 1}^{(t)}}$ ，由式(10)得到短环内的变量节点更新方程：

$q_{i j}^{(t)} = \ln \frac{q_{i j}^{(0)} (0) γ_{v_{i} = 0}^{(t)} \prod_{c_{k} \in N_{v_{i}} \ c_{j}} r_{k i}^{(t)} (0)}{q_{i j}^{(0)} (1) γ_{v_{i} = 1}^{(t)} \prod_{c_{k} \in N_{v_{i}} \ c_{j}} r_{k i}^{(t)} (1)} = L (P_{i}) + \sum_{c_{k} \in N_{v_{i}} \ c_{j}} r_{k i}^{(t)} + ϒ_{v_{i}}$ (14)

短环外变量节点更新方程不变，由式(5)和式(6)计算可得：

$q_{i j}^{(t)} = \ln \frac{P_{i} (0) \prod_{c_{k} \in N (v_{i}) \ c_{j}} r_{k i}^{(t)} (0)}{P_{i} (1) \prod_{c_{k} \in N (v_{i}) \ c_{j}} r_{k i}^{(t)} (1)} = L (P_{i}) + \sum_{c_{k} \in N (v_{i}) \ c_{j}} r_{k i}^{(t)}$ (15)

3) 计算变量节点的后验概率：

由式(11)计算得到短环内的变量节点后验概率：

$q_{i} = \ln \frac{q_{i j}^{(0)} (0) γ_{v_{i} = 0}^{(t)} \prod_{c_{k} \in N_{v_{i}}} r_{k i}^{(t)} (0)}{q_{i j}^{(0)} (1) γ_{v_{i} = 1}^{(t)} \prod_{c_{k} \in N_{v_{i}}} r_{k i}^{(t)} (1)} = L (P_{i}) + \sum_{c_{k} \in N_{v_{i}}} r_{k i}^{(t)} + ϒ_{v_{i}}$ (16)

由式(7)和式(8)计算得到短环外的变量节点后验概率：

$q_{i} = \ln \frac{q_{i}^{(t)} (0)}{q_{i}^{(t)} (1)} = \ln \frac{P_{i} (0) \prod_{c_{k} \in N (v_{i})} r_{k i}^{(t)} (0)}{P_{i} (1) \prod_{c_{k} \in N (v_{i})} r_{k i}^{(t)} (1)} = L (P_{i}) + \sum_{c_{k} \in N (v_{i})} r_{k i}^{(t)}$ (17)

4) 译码判决：若后验概率 $q_{i} > 0$ ，则 ${\hat{c}}_{i} = 0$ 否则 ${\hat{c}}_{i} = 1$ 。若 $H \hat{c}$ 满足 $H \hat{c} = 0$ 则译码成功，停止算法，否则转回步骤2)继续迭代，直到迭代次数达到预先设定的最大迭代次数。

Figure 3. Processing flow of improved algorithm

图3. 改进算法处理流程图

4. 总结

概率域BP译码算法存在的问题在于包括大量乘法运算，这会导致计算量过大，造成数值溢出等问题。置信传播算法的Tanner图是树时可以达到最优译码结果，但Tanner图一旦存在环，尤其是短环则将会大大降低码的性能。本文将改进后的短环BP算法与对数域BP算法结合起来，给出了短环内变量节点的更新方程和后验概率，将计算方程中的乘积算子通过对数的形式改为和算子，不但避免了短环造成的部分数值溢出、信息重复计算等问题，也降低了计算量，对LDPC码短环问题在实际应用过程中具有重要意义。本文研究也具有一定的局限性，例如需要对Tanner图中存在的四环进行鉴别区分，对于环内环外的节点集使用不同的更新方程和后验概率计算公式。接下来的研究工作将对围长大于4的Tanner图进行改进，提出能彻底解决LDPC码短环问题的方案并尽量降低计算复杂度。

文章引用

王晓冰,杨卫华. LDPC码短环的置信传播改进算法
Belief Propagation Improvement Algorithm for LDPC Codes with Short Cycles[J]. 应用数学进展, 2023, 12(01): 203-212. https://doi.org/10.12677/AAM.2023.121023

参考文献

1. Kang, P., Xie, Y., Yang, L. and Yuan, J. (2020) Enhanced Quasi-Maximum Likelihood Decoding Based on 2d Modified Min-Sum Algorithm for 5G LDPC Codes. IEEE Transactions on Communications, 68, 6669-6682. https://doi.org/10.1109/TCOMM.2020.3015213

2. Gallager, R. (1962) Low-Density Parity-Check Codes. IRE Transactions on Information Theory, 8, 21-28. https://doi.org/10.1109/TIT.1962.1057683

3. Tanner, R. (1981) A Recursive Approach to Low Complexity Codes. IEEE Transactions on Information Theory, 27, 533-547. https://doi.org/10.1109/TIT.1981.1056404

4. MacKay, D.J. and Neal, R.M. (1997) Near Shannon Limit Perfor-mance of Low Density Parity Check Codes. Electronics Letters, 33, 457-458. https://doi.org/10.1049/el:19970362

5. Pearl, J. (1988) Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers, Burlington.

6. Weiss, Y. (2000) Correctness of Local Probabil-ity Propagation in Graphical Models with Loops. Neural Computation, 12, 1-41. https://doi.org/10.1162/089976600300015880

7. Weiss, Y. and Freeman, W.T. (2001) On the Optimality of So-lutions of the Max-Product Belief-Propagation Algorithm in Arbitrary Graphs. IEEE Transactions on Information The-ory, 47, 736-744. https://doi.org/10.1109/18.910585

8. Kschischang, F.R., Frey, B.J. and Loeliger, H.A. (2001) Factor Graphs and the Sum-Product Algorithm. IEEE Transactions on Information Theory, 47, 498-519. https://doi.org/10.1109/18.910572

9. Heskes, T. (2004) On the Uniqueness of Loopy Belief Propagation Fixed Points. Neural Computation, 16, 2379-2413. https://doi.org/10.1162/0899766041941943

10. Mooij, J.M. and Kappen, H.J. (2007) Sufficient Conditions for Convergence of the Sum-Product Algorithm. IEEE Transactions on In-formation Theory, 53, 4422-4437. https://doi.org/10.1109/TIT.2007.909166

11. Tatikonda, S. and Jordan, M.I. (2012) Loopy Belief Propagation and Gibbs Measures. arXiv preprint arXiv: 1301.0605.

12. Raveendran, N. and Srinivasa, S.G. (2014) An Analysis into the Loopy Belief Propagation Algorithm over Short Cycles. 2014 IEEE Interna-tional Conference on Communications (ICC), Sydney, 10-14 June 2014, 2009-2014. https://doi.org/10.1109/ICC.2014.6883618

13. Richardson, T. and Urbanke, R. (2008) Modern Coding Theory: Frontmatter. Cambridge University Press, Cambridge. https://doi.org/10.1017/CBO9780511791338

NOTES

^*通讯作者。

期刊菜单