2.2.2 置信传播译码算法

1．算法原理

LDPC码的译码一般采用迭代结构，其译码器结构如图2-2所示。LDPC码译码器包括变量节点译码器与校验节点译码器，通过交织与解交织操作在两个译码器之间传递外信息，经过多次迭代后，变量节点译码器的输出进行判决，得到最终译码结果。

LDPC码典型的译码算法是置信传播（belief propagation,BP）算法。BP算法是在变量节点与校验节点之间传递外信息，经过多次迭代后算法收敛。它是一种典型的后验概率（a posteriori probability,APP）译码算法，经过充分迭代逼近最大后验（maximum a posteriori,MAP）译码性能。

给定二元离散无记忆对称信道（B-DMC）W:X →y,X =｛0,1｝→｛±1｝，假设似然概率为，则信道软信息为

反解得到两个似然概率为

定理2.1 比特软估计值为，其中t 是双曲正切函数。

证明 由于采用二进制相移键控（binary phase-shift keying,BPSK）调制，因此信号的软估计值可以表示为

将式（2-8）代入式（2-9），可得

证毕。

另外，利用双曲正切的反函数可得

下面分析校验节点向变量节点传递的外信息。令表示变量节点i取值为1时第 j个校验方程满足约束的概率。显然，这个校验方程如果满足约束，则剩余的变量节点有奇数个比特取值为1。因此，这个概率表示为

其中，Pj,i＇表示变量节点i＇取值为1时，校验节点 j的估计概率。相应地，当变量节点i的取值为0时，满足校验节点 j的约束的概率为。

设Ej,i表示当变量节点i取值为1时从校验节点 j到所连接的变量节点i传递的外信息，计算式为

将式（2-12）代入式（2-13）可得

其中，Mj,i＇是变量节点i＇向校验节点 j传递的外信息，其定义为

注意，式（2-14）的连乘中要去掉从变量节点i传来的外信息，这样可以避免自环。

根据定理2.1可得

再利用式（2-11），外信息可以进一步变换为

或者得到等价变换形式，即

然后，分析变量节点向校验节点传递的外信息。假设各边信息相互独立，则从变量节点i向校验节点 j发送的外信息可以表示为

其中，Li是信道接收的对数似然比（logarithm likelihood ratio,LLR）信息。需要注意的是，上述外信息计算中，需要去掉从校验节点 j传来的外信息，这样不会产生自环，避免信息之间相关。

变量节点对应的比特LLR为

相应的判决准则为

注意，比特 LLR Λi需要将信道软信息与所有校验节点的外信息叠加。根据上述描述，BP算法可以总结如下。

（1）根据式（2-7）计算信道软信息Li序列，初始化变量节点到校验节点的外信息Mj,i=Li，并传递到校验节点。

（2）在校验节点处，根据式（2-17）计算校验节点到变量节点的外信息Ej,i，并传递到变量节点。

（3）在变量节点处，根据式（2-19）计算变量节点到校验节点的外信息Mj,i，并传递到校验节点。

（4）根据式（2-20）计算比特 LLR，并利用式（2-21）判决准则得到码字估计向量ˆc。

（5）如果迭代次数达到最大值Imax或者满足校验关系，则终止迭代；否则，返回第（2）步。

BP算法在变量节点的计算是累加所有的信道信息与外信息；而在校验节点的计算则是将所有基于外信息得到的软估计值相乘，再求解反双曲正切函数。因此，BP算法也称为和积算法。

BP算法在校验节点处的计算式（2-17）可以简化。首先，将Mj,i＇分解为两项，即

其中，sgn(x)是符号函数。利用这一分解，可以得到

这样，式（2-17）可以写为

可以将式（2-24）中的连乘改写为求和，推导如下。

定义函数

由于该函数满足，因此可知θ(x)=θ-1(x)。代入式（2-25），可得

这样，符号连乘可以用每个变量节点到校验节点的外信息Mj,i＇的硬判决模2加得到，而函数θ(x)可以查表得到。

上述校验节点外信息计算式还可以进一步简化。考虑到最小项决定了乘积结果，因此式（2-27）可近似为

这种算法在变量节点涉及求和运算，在校验节点只涉及最小化运算，因此被称为最小和（minimum sum,MS）算法。与标准BP算法相比，最小和算法性能稍有损失，但外信息计算得到了大幅简化。

对于BP算法或MS算法，由于外信息都是沿变量节点与校验节点的连边传递，因此，单次迭代的计算量为

一般地，LDPC码的平均度分布为，则BP算法的计算复杂度为O(ImaxNlog 2 N)。

BP算法和MS算法是软信息译码算法，如果只考虑硬判决信息，可以进一步简化为比特翻转算法。这时算法复杂度更低，但性能损失较大。

2．消息传递机制

从实用化角度来看，BP算法的消息传递机制非常重要。一般而言，BP算法的消息传递机制可分为4种，简述如下。

（1）全串行译码

全串行译码是标准的 BP 译码，在一次迭代过程中，变量节点按顺序启动，等所有外信息都计算完成后，再按照连边顺序在校验节点按顺序计算相应外信息。基于这种方法的硬件译码器只需要一个计算单元就能够完成译码，但需要存储所有外信息，空间资源消耗大。

（2）全并行译码

全并行译码也称为洪泛调度，需要采用硬件电路实现全部的计算单元，这样每个变量节点、校验节点都可以单独启动，快速计算与传递外信息。这种译码器结构能够获得最高的吞吐量，但硬件资源开销大，并且码长很长时，Tanner图连边非常多，芯片内部单元间的布局非常复杂。

（3）部分并行译码

部分并行译码是全串行译码和全并行译码的折中，采用硬件电路实现一组译码单元，每次迭代时，同时读取一组变量节点与校验节点信息，并行运算并相互传递外信息。这种机制能够达到译码性能与吞吐量、硬件资源开销的较好折中，是LDPC码译码器常用的消息传递机制。

（4）洗牌译码

LDPC码的洗牌译码方案[7]与Turbo码类似，它的基本思想是校验节点尽早利用变量节点更新后的外信息计算输出信息。令分别表示第l次与第l 1- 次迭代变量节点向校验节点传递的外信息，表示第l次迭代校验节点向变量节点传递的外信息。则校验节点外信息计算式修正为

显然，式（2-30）中，变量节点向校验节点传递的外信息按序号分为了两组，即i＇＜i与i＇＞i。前者外信息已经更新，因此采用第l次迭代结果；而后者由于外信息还未更新，因此采用前一次，即第l-1次迭代的结果。由于用到了最新的外信息计算结果，这种机制可以与前3种机制组合，加速译码收敛。