扩张码 | Codeboy's Blog

形式陈述

本页固定二元 parity-check expander code。设 $C\subseteq\mathbb F_2^n$ 是线性码，其所选Tanner 校验表示给出二分图 $G=(L\mathbin{\dot\cup}R,E)$ ：左侧 $L=[n]$ 是变量，右侧 $R$ 是偶校验，所有左节点度数均为 $c$ 。给定常数 $\epsilon,\delta>0$ ，若每个 $S\subseteq L$ 、 $|S|\le\delta n$ 都满足

|N(S)|\ge\epsilon c|S|,

则称该表示为 $(c,\epsilon,\delta)$ 左扩张校验图，相应码称为 expander code。这里采用的是二分图一侧的邻点扩张；它与普通扩张图页面中的无向边扩张共享“小集合不能藏在瓶颈后”的思想，但常数、边界类型与归一化不可直接互换。

当 $\epsilon>1/2$ 时，扩张立即给出距离下界。若非零码字的支撑 $S$ 满足 $|S|\le\delta n$ ，每个相邻校验必须接触偶数个支撑变量，且不可能接触零个。因此从 $S$ 发出的 $c|S|$ 条边在每个 $N(S)$ 节点至少出现两条，得到

c|S|\ge2|N(S)|.

这与 $|N(S)|>c|S|/2$ 矛盾，故 $d_{\min}>\delta n$ 。证明真正使用的是“唯一邻居必然存在”：若邻域大于边数的一半，就有校验恰好看到一个错误变量，而合法码字不允许这种奇校验。

直觉

局部错误若集中在一小组变量上，扩张迫使它们暴露给许多不同校验。边不能大量挤在少数校验里，所以总会出现只被一个错误触碰的约束，它为识别错误提供不含歧义的证据。距离证明把这个图像用于两个合法码字之差；翻转译码则反复利用“错误集合暴露出足够多未满足校验”。

稀疏与扩张必须同时保留。完全二分图的邻域很大，却不提供线性边数的局部算法；一条稀疏长链边数很少，却允许大集合躲在窄边界后。真正的码族要求 $c,\epsilon,\delta$ 与块长无关，这才同时产生线性复杂度和线性最小距离。

例子与边界

取四个变量 $v_1,\ldots,v_4$ ，为每个无序对 $\{i,j\}$ 建一个校验 $v_i\oplus v_j=0$ 。右侧共有六个校验，每个变量度数 $c=3$ 。单点集合有三个邻居；任意两点集合与除补集中那一对以外的五个校验相邻，所以对 $|S|\le2$ ，最小归一化邻域为

\frac{|N(S)|}{c|S|}=\frac56.

所有成对相等约束给出 $C=\{0000,1111\}$ ，最小距离为四。这个小例子可直接核对“小支撑暴露大量校验”，但右侧校验数相对变量数很大、码率只有 $1/4$ ，不能替代渐近好构造。

文献还把小型内码放在约束节点，形成更一般的 Tanner/graph code；那时“校验满足”不再只是偶校验，距离和译码常数要连同内码距离重算。本页的二元 parity-check 版本不能无条件代表所有广义 expander code。反过来，一张图即使在平均意义上扩张，也未必满足“每个至多 $\delta n$ 的集合”这一对抗性量词。

推论与应用

若存在常数度、常数扩张的显式图族，便得到正相对距离且可用局部翻转在线性时间纠正常数比例对抗错误的码族。扩张还为 LP decoding、局部测试和级联码提供组合证书：证明只需计算小集合邻域，而不必枚举全部码字。

同一校验码可以有多种图表示，所以“码是 expander code”通常应理解为它拥有一张满足指定参数的校验图。声明结论时要列出左度、集合规模上界、邻域归一化与校验类型；只说“底层图是 expander”不足以恢复距离或译码半径。

参考资料

Michael Sipser and Daniel A. Spielman, “Expander Codes,” IEEE Transactions on Information Theory 42(6), 1996, 1710–1722.
Shlomo Hoory, Nathan Linial, and Avi Wigderson, “Expander Graphs and Their Applications,” Bulletin of the AMS 43, 2006, 439–561.
Gilles Zémor, “On Expander Codes,” IEEE Transactions on Information Theory 47(2), 2001, 835–837.

形式陈述 ​

反向链接

形式陈述