Coding Theory-Some Bounds

本节主要介绍关于编码的一些上下界。

The Main Coding Theory Problem

定义$A_q(n, d)$为长度为$n$, 最小距离是$d$的编码, size最大能是多少。$B_q(n, d)$为长度为$n$, 最小距离是$d$的线性码, size最大能是多少。确定它们的值或者上下界成为The Main Coding Theory Problem.

首先是几个非常trivial的bound:

$B_q(n, d) \leq A_q(n, d) \leq q^n$.
$B_q(n, 1) = A_q(n, 1) = 1$.
$B_q(n, n) = A_q(n, n) = n$.

前两个非常显然, 最后一个因为$d=n$, 那么每个codeword的任意位互不相同。只考虑第一位互不相同，最多就只能选$n$个codeword。因此上界是$n$. 而$\{(a, a, \cdots, a) \mid a \in F_q\}$就可以达到$n$.

下面引入一个extended code的概念:

$\overline{C} := \{(c_1, c_2, \cdots, c_n, -\sum_{i=1}^n{c_i}) \mid (c_1, c_2, \cdots, c_n) \in C\}$

就是在最后增加一位, 是前面的所有位的和取负。设$H$是$C$的check matrix, 容易验证$\overline{C}$的一个check matrix $\overline{H}=
\begin{pmatrix}
& 0 \\
H & \vdots \\
& 0 \\
1 \cdots 1 & 1
\end{pmatrix}$

Theorem 1: 假设$d$是一个奇数。

存在$(n, M, d)_2$-code当且仅当存在$(n+1, M, d+1)_2$-code. $A_2(n, d) = A_2(n+1,d+1)$.
证明：
假设$C$是$(n, M, d)_2$-code, 考虑它的extended code $\overline{C}$. 显然$d \leq d(\overline{C}) \leq d+1$. 考虑任意$u,v \in C, d(u, v) = d$. 由于$d$是奇数, $\overline{u}, \overline{v}$除了$u,v$不同的位置不同, 最后一位扩展位也不同。因此$d(\overline{u}, \overline{v}) = d+1$. 从而说明$\overline{C}$是$(n+1, M, d+1)_2$-code.
反过来，如果$C$是$(n+1, M, d+1)_2$-code, 那么存在$u,v \in C, d(u, v)=d+1$. 找到$u,v$不相同的某一位，把$C$中所有codeword删去这一位, 得到新的码$C’$。因为只删去了一位，那么距离最多减少1，因此$d(C’) \geq d$, 而$d(u’, v’)=d$, 所以$d(C’) = d$.
存在$[n, M,d]_2$-code当且仅当存在$[n+1, M, d+1]$-code. $B_2(n, d) = B_2(n+1,d+1)$.
证明：
如果$C$是linear code, 那么$\overline{C}$也是，必要性得证。
如果$C$是$[n+1, M, d+1]_2$-code, 那么存在$x \in C, wt(x) = d+1$. 选择$x$非0的某一位, 把$C$中所有codeword删去这一位, 得到新的码$C’$, 显然$C’$也是linear code. 之后同上一条去掉某一位的论证。

Some Lower Bounds

本节主要讨论关于$A_q(n, d), B_q(n, d)$的一些下界。

Sphere-Covering Bound

定义$S(u, r):= \{v \in C \mid d(u,v) \leq r \}$. 显然$|S(u, r)| = \sum_{i=0}^{r} \binom{n}{i}(q-1)^i$. 也就是以$u$为圆心，$r$为半径的球。
考虑达到最优大小$A_q(n,d)$的码$C$, $|C| = A_q(n, d)$, 有$\bigcup_{u \in C}{S(u, d-1)} = F_q^n$. 因为如果这些球并起来不是整个空间，那么存在一个点不在任意一个球内，这个点和$C$内的任意codeword距离都至少是$d$, 那么这个点加入$C$可以得到更大的码。所以有

$A_q(n, d) \geq \frac{q^n}{\sum_{i=0}^{d-1} \binom{n}{i}(q-1)^i}$

Gilbert–Varshamov Bound

Theorem:
如果

$\sum_{i=0}^{d-2} \binom{n-1}{i}(q-1)^i \lt q^{n-k}$

那么存在$[n, k]$ linear code $C$, $d(C) \geq d$.
证明:
考虑构造一个$(n-k) \times n$的”check matrix” $H$, 这里加引号是因为并不要求$H$的行是线性无关的, 但是任意$d-1$列是线性无关的。那么$H$的null space对应的就是一个维数至少是$k$, 距离至少是$d$的线性码。任取generator matrix $G$的$k$行就可以得到维数恰好是$k$, 距离至少是$d$的线性码。
下面考虑一列一列构造这样的$H$:

随便选一个$u_1 \in F_q^{n-k}$, 作为第1列。
对$2\leq i \leq n$, 选取$u_i$作为第$i$列, 要求$u_i$不能使$\{u_1, u_2, \cdots, u_{i-1}\}$中任意$d-2$个的线性组合。
显然如果构造顺利, 我们就找到了符合要求的$H$, 但是我们还得证明第二步中一定存在一个符合要求的$u_i$.
因为$\{u_1, u_2, \cdots, u_{i-1}\}$中任意$d-2$个的线性组合构成的空间大小不超过 $\sum_{j=0}^{d-2} \binom{i-1}{j}(q-1)^j \leq \sum_{j=0}^{d-2} \binom{n-1}{j}(q-1)^j \lt q^{n-k}$ 所以每次总能找到符合要求的$u_i$.

Hamming Bound

Binary Hamming Code

Binary Hamming Code是一种特殊的linear code, 它的长度是$2^r-1$, check matrix $H$大小是$r \times (2^r-1)$每一列恰好是$1, 2 \cdots (2^r-1)$的二进制表示。
首先我们验证一下$H$的行线性无关: 一共$r$行, 考虑$(0, \cdots, 0, \underbrace{1}_{i^{th} bit}, 0, \cdots, 0)^T$所在的列, 这一列只有一个$1$. 一共有$r$由单个$1$组成的列，且这些列的$1$所在的行都不一样。显然这$r$行线性无关。

下面是Binary Hamming Code的一些性质。
如果$C$是Binary Hamming Code, check matrix $H$大小是$r \times (2^r-1)$, 记作$Ham(r, 2)$.

$dim(Ham(r, 2)) = 2^r-1-r$。
$d(Ham(r, 2)) = 3$. 因此只能恢复一个错误。
证明:
根据linear code的性质, 只要证明$H$任意$2$列线性无关，存在$3$列线性相关。前者显然, 因为任意两列互不相同。后者只要取$(1, 0, 0, \cdots ,0)^T, (0, 1, 0, \cdots ,0)^T, (1, 1, 0, \cdots, 0)^T$所在的列。

Binary Hamming Code的Decoding也可以沿用linear code的Syndrome Decoding那一套。
$e_j := (0,\cdots ,0, \underbrace{1}_{j^{th} bit}, 0, \cdots, 0)$, $H = (h_1, h_2, \cdots, h_{2^r-1})$, 则$e_j H^T = h_j$.
如果收到的$w$只有$1$个错误, 那么$wH^T$恰好就是$H$的某一列，假设是第$k$列, 那么出错的就是第$k$位。

Extended Binary Hamming Code

扩展海明码记作$\overline{Ham(r, 2)}$, 定义见线性码的扩展，就是在最后增加一位parity check位。
因为$Ham(r, 2)$是$(n, M, 3)$-code, 所以根据Theorem 1的证明, $Ham(r, 2)$是$(n+1, M, 4)$-code, $d(\overline{Ham(r, 2)}) = 4$.

Weight Distribution Of Hamming Code

部分重量分布表
如何计算？
我们知道Hamming Code的check matrix $H$, 可以计算出$C^{\perp}$的重量分布，再利用MacWilliams’ Identity计算出$C$的分布.
也可以通过$Hx = 0$计算出generator matrix $G$, 直接计算$C$的重量分布。
通过观察可以发现$A_i = A_{n-i}$. 因为$H$的每行都有偶数个$1$, 如果$uH^T = 0$, 那么$\overline{u}H^T = 0$, $\overline{u}$是$u$的每一位取反。

Singleton Bound and MDS Codes

Singleton Bound

Singleton Bound: $A_q(n, d) \leq q^{n-d+1}$.
证明: 任意编码$C$, 满足$d(C) = d$, 考虑删掉所有codeword的最后$d-1$位, 那么它们还是互不相同的. 而长度为$n-d+1$的codeword只有$q^{n-d+1}$个, 所以$|C| \leq q^{n-d+1}$.
另外, 如果$C$是$[n, k, d]$-linear code, 可以推出$|C|=q^k \leq q^{n-d+1} \rightarrow k+d \leq n+1$.

MDS Codes

MDS Codes就是使得Singleton Bound取等号的编码。

Theorem 2:
设$C$是$[n, k, d]$-linear code, 以下几条等价:

$C$是MDS Code.
check matrix $H$的任意$n-k$列线性无关。
generator matrix $G$的任意$k$行线性无关。
$C^{\perp}$是MDS code.

证明:

(1),(2)显然等价。
把$G$看做$C^{\perp}$的check matrix, 推出(3),(4)等价。
(1)推出(4). 只要证明$d(C^{\perp})=k+1$. 假设存在$u \in C^{\perp}, wt(u) \leq k$. 也就是说$u$至少有$n-k$个分量是0. 因为$H$是$C^{\perp}$的generator matrix, 所以存在$(n-k) \times 1$的向量$v$, 满足$u = vH$. 设$J := \{j \mid u_j = 0\}$, 令$J’$是$J$的一个大小为$n-k$的子集, $H_{J’}$是取出$J’$对应的那些列的构成的矩阵($(n-k) \times (n-k)$ ). 由(2)$H_{J’}$是满秩的, $0 = u_{J’} = vH_{J’}$, 可以推出$v = 0$, 从而$u = 0$. 因此不存在$u, wt(u) \leq k$, 也就是说$d(C^{\perp}) \geq k+1$.
$C=(C^{\perp})^{\perp}$, 同上(4)可以推出(1).