Expander Code 相关调研

老板给我的寒假任务。
Expander 的一个经典应用——Expander Code。

Expander Code，于 $1996$ 年由 M. Sipser 和 D. A. Spielman 引入。作为 expander 的一个经典的应用，expander code 有着非常高效且简单的编码与解码算法。同时，expander 与低密度奇偶校验码（Lower Density Parity Check, LDPC）密切相关——随机 LDPC code 有高概率就是 expander code。

编码理论中的基本定义

Defn（纠错码）：对于 $\mathbb F_2^n$ 的一个子集 $\mathcal C$，我们称其为 $(n,k,d)$ 纠错码如果 $|\mathcal C|=2^k$ 且：

$\forall C_1,C_1\in \mathcal C, d_H(C_1,C_2)\ge d$

其中 $d_H(C_1,C_2)=\sum_{i=1}^n [C_{1,i}\ne C_{2,i}]$ 表示 $C_1$ 与 $C_2$ 间的汉明距离。

我们称参数 $d$ 为纠错码的「距离」。

更进一步，如果 $\mathcal C$ 在加法和数乘下构成 $\mathbb F_2^n$ 的子空间，则亦称 $\mathcal C$ 为线性编码。

一个重要的事实是：线性编码的距离就是集合中非 $0$ 编码 $\ell_1$ 范数的最小值：

Thm（线性编码的距离）：设 $\mathcal C$ 是一个 $\mathbb F_2^n$ 的线性编码，则其距离 $d$ 等于：

$d=\min_{C\in \mathcal C\text{ and} C\ne 0}\sum_{i=1}^n C_i$

Proof：先写出 $d$ 的定义：

$d=\min_{C_1,C_2\in \mathcal C\text{ and }C_1\ne C_2}d_H(C_1,C_2)$

又因为 $d_H(C_1,C_2)=d_H(C_1-C_2,0)$，且 $\mathcal C$ 是线性编码，可得 $0,C_1-C_2\in \mathcal C$。故：

$d=\min_{C\ne 0}d_H(C,0)=\min_{C\in \mathcal C\text{ and }C\ne 0}\sum_{i=1}^n C_i$

得证。$\Box$

Expander Code

接下来我们给出 expander code 的定义。

Defn（Parity Check Expander Code）：对于 $d$ 左部正则的 $(\alpha n,(1-\epsilon)d)$-expander $G$，其右部点集大小为 $m$，则由 $G$ 定义的 expander code $\mathcal C$ 为：

$\mathcal C=\{C\mid \forall i\in[m],\sum_{j\in N(i)}C_j=0\}$

其中的加法与数乘是定义在 $\mathbb F_2$ 上的。把这个话翻译一下也就是说：左部点基里的每个点都挂着 $0,1$ 中的一个数，而右部点集里的每个点上都挂着一个对其邻居点的约束。可以显而易见的发现 expander code 是线性编码，因为其约束可以写为 $MC=0$ 这样一个齐次线性方程组的形式。

这个玩意被称为 parity check expander code，是因为对于 $C$ 的约束条件中要求 $C$ 中 $1$ 的数量为偶数。

下文若无特殊说明，我们均用 expander code 指代 parity check expander code。

M. Sipser 和 D. A. Spielman 的结果

在 SS96 这篇文章中 M. Sipser 和 D. A. Spielman 给出了一个超级简单的可以在线性时间内解码 expander code 的算法。

大致的想法就是对于一个左部点 $v$，如果 $N(v)$ 中有超过一半的 parity check 没有被满足，我们就将 $v$ 上的比特翻转。

串行版本

在合理的限制下，这一算法的时间复杂度是线性的，更准确的来说，只需要不超过 $m$ 次翻转，就可以完成解码。

Thm（SS96 算法的适用条件）：对于一个左部 $d$ 正则的 $(\alpha n,(1-\epsilon)d)$-bipartite expander 图 $G=([n]\cup[m],E)$。如果 $\epsilon< \dfrac 14$，则对于任意的至多有 $(1-2\epsilon)\alpha n$ 处错误的 codeword $C$，该算法都可以在 $m$ 次翻转操作以内将 $C$ 修正。

Proof：我们称这一算法出于状态 $(x,y)$，如果左部点当前有 $x$ 处错误（我们设错误点集为 $S$），而右部点有 $y$ 个 parity check 没有被满足。

假设 $x\le \alpha n$，并设 $z=\#\{v\in N(S)\mid \text{The parity check on }v\text{ holds.}\}$。则由 expander 的性质：

$y+z\ge (1-\epsilon)dx$

又因为对于每个不满足的 parity check 的右部点，其至少与错误点集 $S$ 间有一条边；而对于每个满足的 parity check 但是与 $S$ 之间有边的右部点，其至少与错误点集 $S$ 间有两条边。故：

$dx\ge y+2z$

综合这两个不等式可得：

$y\ge (1-2\epsilon)dx$

这表明在 $S$ 中至少有一个点 $v$，使得在 $N(v)$ 中至少有 $(1-2\epsilon)d>\dfrac d2$ 个 parity check 没有被满足，算法可以继续。

这一算法唯一可能失效的情况是：还存在左部点是错误的，但是没有一个点 $v$，使得在 $N(v)$ 中至少有 $\dfrac d2+1$ 个 parity check 没有被满足。由以上的讨论知，当 $|S|=x\le \alpha n$ 时，这种情况不会出现。所以唯一有可能出错的情况是 $|S|=x>\alpha n$ 时发生的。

如果 $x>\alpha n$，则 $y>(1-2\epsilon)dx>(1-2\epsilon)\alpha dn$。但是注意到初始的时候 $y'\le (1-2\epsilon)\alpha dn$，而且每次翻转我们都保证了其邻居点中不满足的 parity check 数量严格大于满足的 parity check 数量，所以翻转后不满足的 parity check 数量会严格减少，故不可能突然间 $y>(1-2\epsilon)\alpha dn$。

所以这个算法是有效的，上面的讨论也给出了时间复杂度的证明方法：因为不满足的 parity check 数量会严格减少，所以至多 $m$ 次就会减少到 $0$。$\Box$

这个算法被称为 belief-propagation algorithm，「超过一半」这一方法可以扩展，改为设定一个阈值 $h$，每次翻转那些在 $N(v)$ 中有超过 $h$ 个 parity check 不满足的点 $v$。

阅读以上证明过程，我们可以提炼出一个非常有用小结论。

Thm（expander $\to$ unique expander）：设二分图 $G$ 是一个 $(c,d,1-\epsilon,\delta)$-expander，则 $G$ 也是一个 $(c,d,1-2\epsilon,\delta)$-unique expander。

其中 unique expander 的定义为：

Defn（Unique Expander）：称一个二分图 $G$ 为一个 $(c,d,\alpha,\delta)$-unique expander，当且仅当 $G$ 是左部 $c$ 正则的，右部 $d$ 正则的。且对于任何大小不超过 $\alpha|L|$ 的左部点集的子集 $S$，都有：

$|N^1(S)|\ge \delta |S|$

其中 $N^1(S):=\{v\in N(S)\mid e(v,S)=1\}$。

并行版本

belief-propagation algorithm 有一个很直接的并行版本：在串行本版中，我们每次只能翻转一个比特，即使有好多比特都满足要求。如果我们有线性级别个处理器，那么我们在一次迭代中可以反翻转所有满足要求的比特。

可以证明这个并行算法的时间复杂度为 $O(\log n)$，具体而言：

Thm（并行版本的复杂度）：设 $\mathcal C$ 是一个 $(c,d,3/4+\epsilon,\delta)$-expander code，设算法某一步前错误位置集合为 $S$，则经过这一步后，$S$ 的大小至多是原来的 $(1+4\epsilon)/2$ 倍。因此 belief-propagation algorithm 的并行版本时间复杂度为 $O(\log n)$。

Proof：$\Box$

Michael Viderman 的结果

Find Erasures and Decode Algorithm

Viderman 给出了另一个简单的组合算法，这一算法思想是找到错误集合 $\text{corr}$ 的一个超集，在这个超集的基础上执行 flip 操作。

对于这一算法的正确性，我们有如下两个定理：

Thm 1（Find Erasures 的正确性）：

Thm 2（Decode From Erasures 的正确性）：

ε>1/2 的必须性

Vid13a 中还论述了 expander code 中 $\epsilon >\dfrac 12$ 的必须性，具体来说：

Thm（Proposition D.1 of Vid13a，$\epsilon>1/2$ 的必须性）：存在 $c,d\ge 2$，与 $0<\delta<1$ 都是常数，以及无限多个正整数 $n$，使得存在一个大小为 $n+2$ 的 $(c+1,d,1/2,0.9\delta)$-expander code $\mathcal C'$，使得 $\Delta(\mathcal C')\le 2$（于是乎 $\mathcal C'$ 没有办法被解码，即使只有 $1$ 处的错误）。

Proof：取一个大小为 $n$ 的 $(c,d,3/4,\delta)$-expander code $\mathcal C$，其中 $c,d,\delta$ 都是常数，且 $c+1<d$。（实际上随机的 expander code 就满足这些性质）

我们尝试构造一个大小为 $n+2$ 的 $(c+1,d,1/2,0.9\delta)$-expander code $\mathcal C'$，具体构造方式如下：

我们在 $\mathcal C$ 的左部点集中加两个点 $n+1,n+2$；而对于右部点集，不妨设 $t=\dfrac{(n+2)(c+1)}d-\dfrac {nc}d$ 是整数，则相应的要往右部点集里加 $t$ 个点 $u_1,u_2,\ldots,u_t$。

对于边集，我们在原先的边集 $E$ 的基础上再加入如下边：

$N_{\mathcal C'}(u_i)=\{(i-1)(d-2)+j\mid j\in[d-2]\}\cup \{n+1,n+2\},\, \forall 1\le i\le c+1; \\ N_{\mathcal C'}(u_i)=\{(d-2)(c+1)+(i-1)d+j\mid j\in[d]\},\, \forall c+2\le i\le t.$

显然得到的新二分图是 $(c+1,d)$-正则的。并且由这个新二分图定义的 code $\mathcal C'$ 满足：$0^n11\in \mathcal C'$，所以 $\Delta(\mathcal C')\le 2$。剩下的工作是说明这个新图有着对应的扩展性。

对于任何一个大小至多为 $0.9\delta (n+2)$ 的集合 $S\subset [n+2]$，令 $S_1=S\cap [n],S_2=S\backslash S_1$。

假设 $n$ 充分大，则有：$|S|\le 0.9\delta (n+2)\le \delta n$，所以 $|S_1|\le |S|\le \delta n$。由原图的 vertex expansion 性质，有：$|N_{\mathcal C}(S_1)|\ge \dfrac 34 c|S_1|\ge \dfrac{c+1}2|S_1|$。

对于 $S_2$ 部分：若 $|S_2|=0$，则 $|N_{\mathcal C'}(S_2)|=0$；若 $|S_2|=1\text{ or }2$，则 $|N_{\mathcal C'}(S_2)|\ge c+1$，总是有 $|N_{\mathcal C'}(S_2)|\ge \dfrac{c+1}2|S_2|$ 成立。

又注意到：$N_{\mathcal C}(S_1)\subset N_{\mathcal C'}(S_2)$ 且 $N_{\mathcal C}(S_1)\cap N_{\mathcal C'}(S_2)=\varnothing$，所以：

$|N_{\mathcal C'}(S)|=|N_{\mathcal C'}(S_1\cup S_2)|\ge |N_{\mathcal C}(S_1)|+|N_{\mathcal C'}(S_2)| \\ \ge \dfrac{c+1}2|S_1|+\dfrac{c+1}2|S_2|=\dfrac{c+1}2|S|$

所以 $\mathcal C'$ 是一个 $(c+1,d,1/2,0.9\delta)$-expander code，且有 $\Delta(\mathcal C')\le 2$。

这样就完成了证明。$\Box$

陈雪、程宽、李新与欧阳铭晖的结果

在 CCLO23 这篇文章中陈雪、程宽、李新与欧阳铭晖结合了 SS96 与 Vid13a 中的结果，并且运用猜测 expansion 的 idea，进一步改进了 expander code。

文章具体细节的研读请看：。

参考文献

[SS96] M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710–1722, 1996.

[Vid13a] Michael Viderman. Linear-time decoding of regular expander codes. ACM Trans. Comput. Theory, 5(3), August 2013.

[Vid13b] Michael Viderman. Lp decoding of codes with expansion parameter above 2/3. Inf. Process. Lett., 113(7):225–228, April 2013.

[CCLO23] Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang. 2023. Improved Decoding of Expander Codes. IEEE Trans. Inf. Theor. 69, 6 (June 2023), 3574–3589.