置信传播译码 | 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).

初始化校验到变量的 LLR 为零，等价于无额外偏好的二分量消息。采用同步调度时，每轮先由上一轮校验消息计算全部变量消息，再计算全部新校验消息；同时给定最大轮数与停止容差。变量的暂定后验为

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 最优保证。

概率域消息与一般有限因子

LLR 的边界由概率域更新定义。更一般地，设每个变量取值于有限集合，目标分布满足

p(x)\propto\prod_v\psi_v(x_v)\prod_a\psi_a(x_{N(a)}),

其中所有因子非负且全局归一化常数严格为正。变量—因子二分图在 $v$ 出现在 $\psi_a$ 中时连边。消息更新为

m_{v\to a}(x_v)\propto\psi_v(x_v) \prod_{b\in N(v)\setminus\{a\}}m_{b\to v}(x_v),

m_{a\to v}(x_v)\propto \sum_{x_{N(a)\setminus\{v\}}} \psi_a(x_{N(a)}) \prod_{u\in N(a)\setminus\{v\}}m_{u\to a}(x_u).

每次可除以消息各分量之和归一化。二元校验译码取 $\psi_v(b)=W(y_v\mid b)$ ， $\psi_a$ 为偶校验成立的指示函数；对两个分量取对数比，就得到前面的 LLR 式。确定性消息对应零分量与无穷 LLR，应按这些非负乘积、求和处理，不能直接计算不定式 $\infty-\infty$ 。若归一化总和为零，应报告约束或数值不相容，不能输出一份伪后验。

有限树上的精确性来自逐边切开后两侧变量不再重叠，消息恰好把发送侧变量求和消去。选根后先向根、再从根向外各传一遍，便把全部因子的信息送到每个变量；归一化后的 $\psi_v\prod_a m_{a\to v}$ 才是精确边缘。一般因子的求和可能很贵；Turbo 分量的 trellis 因子利用前向—后向动态规划完成这一步，并非把整条 trellis 当成一个二元奇偶校验。

直觉

变量更新与校验更新依次组合排除收件邻居自身证据的软消息 — BP 译码的交替外在消息

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

这与连续消除译码的固定串行条件化不同。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 访问每条边常数次，加上 $n$ 个变量的初始化与输出，成本为 $O(n+|E|)=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.

形式陈述 ​

概率域消息与一般有限因子 ​

反向链接

形式陈述

概率域消息与一般有限因子