置信传播/和积算法

置信传播（belief propagation，BP）在因子图上的规范化形态即和积算法（sum-product algorithm），由 Kschischang、Frey 与 Loeliger 在 2001 年统一：前向–后向算法、Viterbi、FFT、Kalman 滤波与 Pearl 的贝叶斯网络传播，全部是"因子图上边缘化"的实例。LDPC 译码是它最著名的应用——Gallager 1962 年的概率译码正是树上精确、环上近似的同一套消息更新。量子侧，综合征 BP 把稳定子校验当因子，是量子 LDPC 译码的起点算法。

因子图与边缘化

设多元函数可分解为局部因子的乘积 $g(x_1,\dots ,x_n)={\prod }_s{f}_s(X_s)$（$X_s$ 为 $f_s$ 所涉变量集）。因子图是二部图：变量节点 $x$、因子节点 $f$，$f$ 与其所涉变量相连。一大类推断问题化为同一形式——边缘化：

$g_i(x_i)={\sum }_{x_1,\dots ,x_{i-1},x_{i+1},\dots ,x_n}g(x_1,\dots ,x_n).$

LDPC 译码正是实例：码的后验分布按Tanner 图分解为校验因子与信道因子的乘积，

$P(\mathbf{x}\mid \mathbf{y})\propto {\prod }_{c}1[{⨁}_{j\in N(c)}{x}_j=0]\cdot {\prod }_{j}P(y_j\mid x_j),$

最大后验译码即求其边缘/众数Kschischang, Frey & Loeliger 2001 (IEEE Trans. Inf. Theory)。

两条消息更新式（从边缘化推导）

在树上求 $g_i(x_i)$ 有高效做法：以 $x_i$ 为根，先把”叶子方向的子树”逐层折叠成消息。定义变量到因子与因子到变量两类消息：

$m_{x\to f}(x)={\prod }_{h\in N(x)\setminus f}{m}_{h\to x}(x),$

$m_{f\to x}(x)={\sum }_{\{x^{\prime }:x^{\prime }\in N(f)\setminus x\}}f\left(X_f\right){\prod }_{x^{\prime }\in N(f)\setminus x}{m}_{x^{\prime }\to f}(x^{\prime }).$

推导：树以 $f$–$x$ 边为界分成两半。$x$ 这一半对 $x_i$（$x$ 本身或更深处）的贡献，等于除 $f$ 外各相邻因子贡献的乘积——因子互不共享变量（树上无环），子问题独立，得第一条。$f$ 这一半对 $x$ 的贡献：固定 $x$，对 $f$ 的其余变量求和，被求和的分解式里，每个 $x^{\prime }$ 又只牵连自己一侧的子树，其贡献恰是消息 $m_{x^{\prime }\to f}$，得第二条。初始消息取常数（无信息），迭代至收敛后边缘由邻接消息合成：

$g(x_i)\propto {\prod }_{f\in N(x_i)}{m}_{f\to x_i}(x_i).$

树上精确：按上述折叠次序求和等价于按消元顺序做精确边缘化，结果与求和次序无关；总计算量 $O(|E|\cdot |\mathcal{X}|)$ 每轮。有环图上（loopy BP）消息不再对应无交子树，折叠论证失效，算法变为近似——LDPC 码的 Tanner 图有环，girth 越大局部树近似越深（见tanner-graphs）。

LDPC 特化：对数域与 tanh 规则

二进制情形在对数域最省。设变量先验为信道对数似然比 ${\lambda }_j=\log \frac{P(y_j\mid x_j=0)}{P(y_j\mid x_j=1)}$。变量更新是简单的求和：

${\nu }_{v\to c}={\lambda }_v+{\sum }_{c^{\prime }\in N(v)\setminus c}{\mu }_{c^{\prime }\to v},$

校验更新是tanh 规则：

${\mu }_{c\to v}=2{\tanh }^{-1}\left({\prod }_{v^{\prime }\in N(c)\setminus v}\tanh \frac{{\nu }_{v^{\prime }\to c}}{2}\right).$

推导：对消息定义概率差 $\delta =P(0)-P(1)$。由 $\lambda =\log \frac{P(0)}{P(1)}$ 得 $P(0)=\frac{e^{\lambda /2}}{e^{\lambda /2}+e^{-\lambda /2}}$ 型的双曲表示，即 $\delta =\tanh (\lambda /2)$。校验节点输出偶校验指示函数下的分布，其概率差可用 $\pm 1$ 变量 $z=1-2x$ 计算：

$P(\oplus =0)-P(\oplus =1)={\sum }_{\mathbf{x}}({\prod }_{v^{\prime }}{P}_{v^{\prime }}(x_{v^{\prime }}))(-1{)}^{\sum x_{v^{\prime }}}={\prod }_{v^{\prime }}(P_{v^{\prime }}(0)-P_{v^{\prime }}(1))={\prod }_{v^{\prime }}{\delta }_{v^{\prime }},$

第二步是把”带符号的乘积求和”按变量逐个分解（每个变量贡献 $P(0)-P(1)$）。于是 $\tanh ({\mu }_{c\to v}/2)={\prod }_{v^{\prime }}\tanh ({\nu }_{v^{\prime }\to c}/2)$，取 $2{\tanh }^{-1}$ 即得。∎ 这正是 Gallager 1962 概率译码的更新式；把消息符号化、阈值化就退化为比特翻转Gallager 1962 (IRE Trans. Inf. Theory)。收敛行为可用密度演化系统分析（见ldpc-classical）。

量子侧：综合征 BP

量子码的译码问题同构地映射到因子图：变量节点是错误比特 $(e_X,e_Z)\in {\mathbb{F}}_2^{2n}$，因子节点是稳定子生成元，综合征是测量到的 $\pm 1$ 本征值序列，因子取”错误与生成元辛内积=综合征”的示性函数Roffe 2019 (Contemporary Physics)。困难在于简并性：多个等价错误给出同一综合征，BP 的消息更新被”同因异果”干扰而病态，实践中以 OSD 后处理兜底（见bp-osd-decoding）；对简并性与 BP 收敛关系的系统分析见 Rabeti–MahdavifarRabeti & Mahdavifar 2026 (arXiv)。

延伸阅读

• tanner-graphs
• ldpc-classical
• bp-osd-decoding
• decoding-overview
• qldpc-overview