置信传播译码 | Codeboy's Blog

形式陈述

固定二元线性码的Tanner 图，并设码字通过二元输入的离散无记忆信道独立发送。对输出 $y_v$ ，采用

L_v^{\mathrm{ch}} =\log\frac{W(y_v\mid0)}{W(y_v\mid1)}

作为信道对数似然比。置信传播在有向边上维护两类消息。变量到校验的更新为

L_{v\to a} =L_v^{\mathrm{ch}} +\sum_{b\in N(v)\setminus\{a\}}L_{b\to v};

偶校验到变量的更新为

L_{a\to v} =2\operatorname{atanh} \left( \prod_{u\in N(a)\setminus\{v\}} \tanh\frac{L_{u\to a}}2 \right).

一次完整迭代交替完成两类更新。变量的暂定后验为

L_v^{\mathrm{post}} =L_v^{\mathrm{ch}}+\sum_{a\in N(v)}L_{a\to v},

据其符号作硬判决，并可在所有校验满足时提前停止。每条外发消息都排除收件邻居提供的旧消息；否则同一证据会在一步内被重复计算。

在有限无圈 factor graph 上，sum-product 给出的边缘分布是精确的。随机 LDPC 图在块长趋大且迭代轮数固定时，局部计算邻域以高概率无圈，因此可由树递推分析。对一张有限有圈图运行的 loopy BP 则是近似算法：更新式仍有定义，但不附带一般的收敛、唯一不动点或 MAP 最优保证。

直觉

变量节点把自己的信道证据与“其他校验怎样看我”相加，再把尚未包含目标校验的信息发过去。校验节点则回答：“若其余变量的软判断可信，为使奇偶和为零，这个变量应偏向哪一值？”正负号传播奇偶关系，绝对值表达置信强度。弱证据经过一致的多条路径可累积，冲突证据会互相抵消。

这与连续消除译码的固定串行条件化不同。BP 保留软消息并可并行或分层反复更新，早期没有必须永久接受的单个硬判决；SC 则按预定次序把先前估计代入后续 bit-channel。两者都利用图上的概率分解，但信息状态和调度语义并不相同。

例子与边界

考虑一个无圈的三元偶校验

x_1\oplus x_2\oplus x_3=0.

若 $x_2,x_3$ 发向校验的 LLR 分别为 $\log3$ 与 $\log2$ ，利用恒等式

\tanh\frac{\log r}{2}=\frac{r-1}{r+1}

可得两个双曲正切分别是 $1/2$ 与 $1/3$ 。校验发给 $x_1$ 的消息因此为

2\operatorname{atanh}(1/6) =\log\frac{1+1/6}{1-1/6} =\log(7/5).

若 $x_1$ 自身信道 LLR 为 $\log4$ ，其后验 LLR 为 $\log(28/5)>0$ ，故判为零。这里图是树，所以该组合恰是相应后验信息，而非独立性近似。

在 BEC 上，消息只需取“已知零、已知一、擦除”三种状态，BP 退化为 peeling：某校验只剩一个未知变量时即可恢复它。这个简化不能原样搬到 BSC 或软输出信道。有限图上的四圈会使消息很快携带自己的旧证据；trapping set 可能让所有 LLR 看似稳定却仍有错误。数值实现还要处理 $\operatorname{atanh}(1)$ 、LLR 饱和、量化、并行 flooding 与 layered schedule 的差别。

推论与应用

若图度有界，一轮 BP 访问每条边常数次，成本为 $O(n)$ ；固定轮数的总复杂度仍为线性。算法既能利用硬判决信道，也能直接吸收每个符号的软可靠度，这通常是它相对简单 bit-flipping 的主要性能来源。校验更新的 min-sum 近似把双曲函数替换为符号乘积与最小绝对值，便于硬件实现，但需要归一化或偏置补偿，不能把近似输出称为精确 sum-product。

BP 还是 Turbo 迭代译码、隐马尔可夫模型与一般 factor graph 推断的共同语言；在每个场景中，必须分别说明图是否有圈、局部因子是什么、消息是否归一化以及停止条件，而不能仅以“传递置信度”替代算法定义。

参考资料

Frank R. Kschischang, Brendan J. Frey, and Hans-Andrea Loeliger, “Factor Graphs and the Sum-Product Algorithm,” IEEE Transactions on Information Theory 47(2), 2001, 498–519.
Tom Richardson and Rüdiger Urbanke, Modern Coding Theory, Cambridge University Press, 2008, Chs. 3–4.
Niclas Wiberg, Codes and Decoding on General Graphs, Linköping University, 1996.

形式陈述 ​

反向链接

形式陈述