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.

每次至少下降一，所以只要算法走到正确码字，翻转次数受初始未满足校验数 $O(n)$ 控制；有界度下可用邻接表增量维护候选变量，总时间为 $O(n)$ 。

经典 Sipser–Spielman 保证使用固定归一化（原论文 Theorem 11；Viderman 2012 的引言按下式重述）。若校验图是 $(c,\epsilon,\delta)$ -expander，即每个 $|S|\le\delta n$ 的变量集有至少 $\epsilon c|S|$ 个校验邻居，并且 $\epsilon>3/4$ ，则顺序 Flip algorithm 能纠正任意满足

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

的对抗错误。证明同时控制错误变量与可能被误翻的正确变量所形成的集合；这也是半径中出现 $2\epsilon-1$ 而不只是距离一半的原因。后续 LP 或其他翻转算法具有不同的扩张阈值，不能把 $\epsilon>2/3$ 等改进倒写成原始算法定理。

直觉

一个错误 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 充分利用观测。

推论与应用

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, Theorem 11.
Michael Viderman, “Linear Time Decoding of Regular Expander Codes,” Innovations in Theoretical Computer Science, 2012, 168–182；引言按 $(c,\epsilon,\delta)$ 归一化重述 Flip algorithm 的 $(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.

形式陈述 ​

形式陈述