Sipser–Spielman 翻转译码器

形式陈述

给定二元扩张码的左 $c$ -正则校验图和接收词 $y$ ，先标出综合非零的校验。若某变量 $v$ 的 $c$ 个邻接校验中，未满足者严格多于 $c/2$ ，就翻转 $y_v$ ；更新受影响校验的状态并继续，直到全部校验满足，或不存在可翻转变量。前者输出当前码字，后者若仍有未满足校验则报告译码失败。严格多数不可改成“至少一半”：恰好一半时翻转并不减少未满足校验数。

设当前未满足校验数为势函数 $U(y)$ 。翻转一个有 $u>c/2$ 个未满足邻居的变量后，这 $u$ 个校验变为满足，其余 $c-u$ 个满足校验变为不满足，故

\Delta U=(c-u)-u=c-2u<0.

每次至少下降一，所以无论最终译码是否成功，翻转次数都不超过初始未满足校验数 $U_0\le cn$ 。线性实现还假定 $c$ 与右侧校验最大度数均有常数上界，并且没有孤立校验节点；此时初始化遍历 $O(n)$ 条边，每次翻转只触发常数个邻居计数更新，可用桶或队列维护候选变量，总时间为 $O(n)$ 。仅有总边数 $O(n)$ ，不能保证逐次更新高程度校验的代价仍为常数。

顺序算法的保证须固定邻域归一化。Sipser–Spielman 原论文的 Theorem 10 分析顺序算法；下列带取整的推广形式见 Viderman 的 Theorem 3.6，原论文 Theorem 11 则是并行版。若校验图是 $(c,\epsilon,\delta)$ -expander，即每个 $|S|\le\delta n$ 的变量集有至少 $\epsilon c|S|$ 个校验邻居，并且 $3/4<\epsilon\le1$ ，令 $K=\lfloor\delta n\rfloor\ge1$ 。顺序 Flip algorithm 能纠正任意满足

|E_0|<(2\epsilon-1)\lfloor\delta n\rfloor

的对抗错误。这个严格不等号关系到有限长度的边界。固定实际发送的码字，记当前错误支撑为 $S$ 、 $v=|S|$ 。在 $1\le v\le K$ 时，设 $N_1(S)$ 为只接触一个错误变量的校验数。由于其他邻居至少接触两条从 $S$ 发出的边，

N_1(S)\ge2|N(S)|-cv\ge(2\epsilon-1)cv>cv/2.

这些校验全部未满足，因此至少有一个错误变量连接严格多数未满足校验，算法不会在非零错误处卡住。初始时 $U_0\le c|E_0|<(2\epsilon-1)cK$ ；若某一步误翻正确变量而首次使错误数达到 $K$ ，上式却要求当时 $U\ge(2\epsilon-1)cK$ ，与 $U$ 持续下降矛盾。故错误数始终小于 $K$ ，终止时只能为零。这里控制的是相对于同一个发送码字的错误集合，包括可能被误翻进去的坐标。后续 LP 或其他翻转算法具有不同的扩张阈值，不能把 $\epsilon>2/3$ 等改进倒写成原始算法定理。

直觉

五个邻接校验中四个未满足时翻转变量，使未满足数从四降到一 — Sipser–Spielman 的严格多数翻转

一个错误 bit 会切换它参加的每条奇偶校验。如果小错误集合扩张良好，大量校验只看到一个错误，于是错误变量附近倾向于聚集未满足校验；正确变量即使连接其中一些，也难以获得严格多数。算法把这种局部不平衡当作方向信号，每次选择能使全局综合重量下降的坐标。

势函数下降只证明终止，不单独证明终点正确。错误图样可能落入另一个码字，使综合为零；也可能形成没有严格多数变量的局部极小值。扩张假设的作用正是排除规定半径内的这些坏终点，并保证整个过程中相关变量集合始终落在可用的规模范围内。

例子与边界

用五个变量组成环，并在相邻变量间放相等校验

x_i\oplus x_{i+1}=0,\qquad i\in\mathbb Z/5\mathbb Z.

从全零码字得到接收词 00100。第三个变量相邻的两条校验都未满足，故 $u=2>c/2=1$ ；第二、四个变量各见一条满足和一条未满足校验，不能翻转。翻转第三位后变为 00000，未满足校验从两条降为零。

这个五环只演示一步更新，并不是满足经典常数的扩张码族。若接收词为 01010，多个变量的局部计数会相互影响，不能凭单错轨迹推断成功。顺序版一次翻一个变量；并行版若同时翻转所有候选者，候选之间共享校验会改变势函数分析，需要单独定理。软输出信道的可靠度没有进入此算法，因而它通常不如 BP 充分利用观测。

严格半径不能无条件改成闭区间。取长度二重复码 $C=\{00,11\}$ ，唯一校验为 $x_1\oplus x_2=0$ 。此时 $c=1$ 、 $\epsilon=1$ 、 $\delta=1/2$ ，所有大小至多 $K=1$ 的变量集都满足扩张条件，但接收词 01 距两个码字都只有一位。两个变量都是可翻转候选，任一固定选择都会对其中一个可能的发送码字译错；错误数一恰等于 $(2\epsilon-1)K$ 。

推论与应用

Flip algorithm 展示了组合扩张如何直接变成可执行的 adversarial decoder：没有概率独立假设，保证对所有给定重量内的错误图样成立。它也启发了 Gallager bit-flipping、weighted bit-flipping 和更复杂的局部搜索；这些变体会使用阈值、软可靠度或并行日程，但应分别证明进展量。

在实现中，维护每个变量的未满足邻居计数，并在校验切换时只更新其相邻变量，可避免每轮扫描全图。线性复杂度依赖边数为 $O(n)$ ；若校验度随块长增长，或每次重新计算全部综合，理论上的局部算法便不再等于实际线性实现。

参考资料

Michael Sipser and Daniel A. Spielman, “Expander Codes,” IEEE Transactions on Information Theory 42(6), 1996, 1710–1722, §V.A, Theorem 10 与 Fig. 2；并行版见 §V.B, Theorem 11。
Michael Viderman, “Linear Time Decoding of Regular Expander Codes,” Innovations in Theoretical Computer Science, 2012, 168–182；ECCC 2011 预印本 §3.1, Theorem 3.6，严格小于 $(2\epsilon-1)\lfloor\delta n\rfloor$ 的顺序翻转保证。
Michael Viderman, “LP Decoding of Expander Codes: A Simpler Proof,” Information Processing Letters 113(17), 2013, 612–615.

形式陈述 ​

反向链接

形式陈述