Coding Theory-Expander Codes

发表于 分类于 阅读次数： 评论数：

Introduction

Expander Code是一种特殊的Linear Code, 特殊之处在于它的check matrix对应某个(bipartite) expander graph的临接矩阵. 这样一来，编码的一些性质(如距离、解码)就可以和图的性质对应起来。

为了只会阐述方便，我们先约定一些记号:

  1. 用$G(L \cup R, E)$表示一个二分图, $L, R$分别表示左右两个点集。
  2. 定义点集$S$的邻居$N(S):=\{v| v \text{ is incident to some vertex } u\in S \}$.
  3. 定义点集$S$的唯一邻居$U(S) :=\{v| v \text{ is incident to exactly one vertex } u\in S \}$
  4. $d$-regular graph: 每个点的度都是$d$的图。
  5. $d$-left-regular graph:二分图的左边每个点的度都是$d$. 同理有$d$-right-regular graph.

Factor Graph of Linear Code

给定一个$[n, k]$ Binary Linear Code $C \subset F_2^n$和它的一个check matrix $H$, 我们可以按照下面的方式构造一个二分图:
$|L|=n, |R| = n-k$. 左边的每个点对应codeword的一个bit。右边的每个点对应check matrix的一行。为方便起见，左边的点集记作$\{u_1, u_2 \cdots, u_n\}$, 右边的点集记作$\{v_1, v_2 \cdots v_{n-k}\}$
要判断一个向量$x$是否属于$C$, 只需要给左边的点集分配一个权重: $w(u_i) = x_i$。 $x \in C$当且仅当

这个过程本质上就是$u$和$H$的每行的点积都是0. 如上构造的图称为$C$的 Factor Graph.

Expander Graphs and Expander Codes

定义$(n, m, d, \gamma, \alpha)$ Bipatite Expander 是一个$d$-left-regular的二分图, 满足$|L|=n, |R|=m$并且$\forall S \subset L$, 如果$|S| \leq \gamma n$, 那么有$ N(S) \geq \alpha |S|$.
也就是说，从左边取一个”足够小”的集合，它的邻居集合一定”足够大”.
Expand Codes就是一种特殊的线性码，它的factor graph正好是一个bipatite expander。因为其特殊的结构，我们更加容易分析它的最小距离，以及可以更快的编码/解码。

下面先证明一个引理:

引理1: 如果$G$是一个$(n, m, d, \gamma, (1-\epsilon)d)$的bipartite expander($\epsilon \lt 0.5$), 那么$\forall S\subset L$, 如果$|S| \leq \gamma n$, 那么有$|U(S)| \geq d(1-2\epsilon)|S| \gt 0$ 。
后面估计expander code的最小距离的时候会用到$|U(S)| \neq 0$这个性质。

证明:
首先根据bipartite expander的定义有$N(S) \geq (1-\epsilon)d|S|$. 因为$S$中每个点都和右边的$d$个点相连, 一共有$d|S|$条边, 其中有$|N(S)|$条为增加邻居数做出了贡献, 剩下的$d|S|- |U(S)|$条边, 每条边可能使得某个邻居变得不”唯一”(见introduction里唯一邻居的定义).
因此$|U(S)|\geq |N(S)|- (|d|S|-|N(S)|) = 2|N(S)|-d|S| \geq d(1-2\epsilon)|S|$.

利用上面的引理, 可以给出expander code的最小距离的一个下界。
定理1: 如果线性码$C$的factor graph $G$是一个$(n, m, d, \gamma, (1-\epsilon)d)$的bipartite expander, 那么$d(C) \geq 2\gamma (1-\epsilon)n$.

证明:
根据线性码的性质，只需要证明重量最小的codeword重量不会小于$2\gamma (1-\epsilon)n$.
假设有一个codeword $r \in C$, $wt(r) \lt 2\gamma (1-\epsilon)n$. 按之前判断向量是否属于$C$的方法给左边的点分配权值:$w(u_i) = r_i$. 令$S := \{u_i| r_i = 1 \}$, $U(S)$中的parity check条件不可能被满足，因为每个条件只对应左边一个1。所以我们只要证明$U(S)$非空，即可推出矛盾。

  • 如果$|S| \leq \gamma n$, 根据上面的引理直接可以推出$U(S)$非空。
  • 如果$|S| \gt \gamma n$, 那么可以找到$S$的一个子集$S’$, $|S’| = \gamma n$, 根据引理$|U(S’)| \geq d(1-2\epsilon)\gamma n$. 考虑$U(S’)$中的哪些点不属于$U(S)$, 一定是因为有些 $S \backslash S’$中的那些点又连边到$U(S’)$中的点, 破坏了它们的”唯一性”. 因为$|S| = wt(r) \lt 2\gamma(1-\epsilon)n$, 所以$|S\backslash S’| \lt (1-2\epsilon)n$。最多破坏$d|S\backslash S’|\lt d(1-2\epsilon)\gamma n \leq |U(S’)|$这么多点的”唯一性”, 因此至少还存在一些$U(S’)$中的点属于$U(S)$.

Encoding Algorithm for Expander Codes

Expander Code的encoding和线性码是一样的，只需要做一次矩阵乘法, 时间复杂度是$O(n^2)$. [3]目前已经有可以做到$O(n)$时间的算法.

Decoding Algorithm for Expander Codes

假设$C$对应$(n, m, d, \gamma, (1-\epsilon)d)$ expander, 且满足$\epsilon \lt \frac{1}{4}$。 当收到向量$r$, 错误位数小于$\gamma(1-2\epsilon)n$的时候，可以用下面的算法恢复:

  1. 给左边的点赋权值, $w(u_i) := r_i$.
  2. 找到某个$u_i \in L$, $N(u_i)$中不满足parity check 条件的比满足的多。如果找不到，算法结束。
  3. 反转$r$的第$i$个bit, 相应地，反转$w(u_i)$. 跳到第2步。

通俗地讲，就是依次检查每个bit, 如果某个bit对应的parity check条件不满足的个数要比满足的多，那么反转这个bit，可以使得满足的parity check条件变多, 显然算法会在有限步内终止。 假设实际发送的是$r’, d(r, r’) \lt \gamma(1-2\epsilon)n$. 要证明算法可行，我们要证明两件事:

  1. 如果算法返回的解$\in C $，那么一定是和$r$距离最近的那个, 即实际发送的$r’$. 我们只要证明任意时刻$d(r, r’) \leq \gamma n \lt d(C)$, 也就是说算法执行过程中$r$不会偏离$r’$太远.
    证明:
    因为$r’$满足所有parity check条件, 一开始$d(r, r’) \lt \gamma(1-2\epsilon)n$, 不满足的parity check条件数$\lt d(1-2\epsilon)\gamma n$. 而在算法执行的过程中，不满足的parity check条件只会越来越少。
    假设某时刻发生了$d(r, r’) \gt \gamma n$. 因为算法每次迭代只会改变一个bit, 那么一定存在一个时刻$d(r, r’) = \gamma n$. 设$S:=\{i|r_i \neq r_i’\}$, 由引理1 $|U(S)| \geq d(1-2\epsilon)\gamma n$, 且$U(S)$对应的parity check条件都是没有满足的。 因此又得出不满足的parity check条件数至少是$d(1-2\epsilon)\gamma n$, 导致矛盾。

  2. 算法不会在某一步”卡主”. 也就是说，不会存在某个极端的情况，对于$\forall u_i, N(u_i)$中满足parity check条件的和不满足的恰好一样多。 我们证明，如果$d(r, r’) \leq \gamma n$, 一定存在一个$u_i \in L$, $N(u_i)$中不满足parity check条件的个数大于$d/2$(自然$N(u_i)$中不满足的多于满足的).
    证明:
    令$S:=\{i|r_i \neq r_i’\}$, $|S| \leq \gamma n$, 根据引理1有$|U(S)| \geq d(1-2\epsilon)|S| \gt \frac{d}{2}|S|$ (这里用到$\epsilon \lt \frac{1}{4} $). 根据鸽笼原理$S$中一定存在一个点$u_i$, $U(S)$中和$u_i$相连的点大于$d/2$, 这些点对应的parity check条件都是不满足的。

Reference

  1. Notes from CMU, https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes8.pdf
  2. Wikipedia https://en.wikipedia.org/wiki/Expander_code
  3. Spielman, D. (1996). “Linear-time encodable and decodable error-correcting codes”. IEEE Transactions on Information Theory. 42 (6): 1723–31. CiteSeerX 10.1.1.47.2736. doi:10.1109/18.556668.