信息论 | 2 信道编码

在一个有噪声的信道里, 接收的信息可能和发送的信息有出入.

1. 设计编码 (source coding 是减少冗余, 而 channel coding 则是增加冗余).
2. 编码 (讯息 \(\mapsto\) 编码).
3. 解码 (收到的编码 \(\mapsto\) 还原的讯息).

5 Channel coding

5.1 The nearest neighbour method

重复编码 (repetition code) 就是将讯息重复 \(N\) (奇数) 遍, 比如 \(0\to000\), \(1\to111\). 在解码时, 对于每三个连续的比特, 如果 \(0\) 多就解码成 \(0\), 如果 \(1\) 多就解码成 \(1\) (即与这三个比特的 Hamming 距离最近的 \(000\) or \(111\)). 这种方法的缺点是效率太低.

假设有讯息集合 \(\{0,1\}^m\), 分别给予编码 \(\{c_1,\dots,c_k\}\). 我们假设解码采用 nearest neighbour 方法, 即寻找与收到的编码 (Hamming 距离) 最近的编码 \(c_i\). 如果我们希望任意一个编码被扰动 \(t\) 比特后, 都能解码出正确的讯息, 则这些编码的 Hamming 距离应当满足 \[ d_H(c_i,c_j) \geq 2t+1,\quad\textsf{对任意}\;i\neq j. \] 如果编码空间为 \(\{0,1\}^n\) (即编码长度不超过 \(n\)), 则我们要做的就是找到最小的 \(n\), 使得存在 \(k=2^m\) 个编码满足上述不等式.

• 显然有 \(n\geq2t+1\) 且 \(2^n\geq 2^m\).

• (Sphere packing bound) 每个编码 \(c_i\) 的 \(t\)-闭球 (与它的 Hamming 距离不超过 \(t\) 的编码) 的体积为 \(\sum_{i=0}^t{n\choose i}\). 则 \(n\) 至少应当满足 \[ \frac{2^n}{\sum_{i=0}^t{n\choose i}} \geq 2^m. \]

下面寻找上界, 即什么样的 \(n\) 一定能构造出满足条件的编码. 稍微改变一下问题: \(d_H(c_i,c_j)\geq\delta n\) (常数 \(0<\delta<\frac12\)).

想法: 从 \(\{0,1\}^n\) 上的一个概率分布中生成 \(k=2^m\) 个编码, 然后计算这些编码满足不等式的概率. 如果该概率严格大于零, 则 \(\{0,1\}^n\) 上一定存在这样的编码满足不等式.

先考虑 \(\{0,1\}^n\) 上的均匀分布. 对于 \(k=2\) 的情形, 我们有 (生成一个编码, 落在 \(\delta n\)-球外的概率) \[ P = 1 - \frac{\sum_{i=0}^{\delta n}{n\choose i}}{2^n} =: 1-p, \] 一般地, 对于 \(k=2^m\) 的情形, 有估计

• (Chernoff bound) \(P(d_H(c_i,c_j)<\delta n)<\e^{-\mathcal{O}(n)}\), 对于给定的 \(i\neq j\).

• (对立事件 / bad event 的概率) \[ \Align{ P(d_H(c_i,c_j)<\delta n,\textsf{存在}\;i\neq j) &< \sum_{i\neq j} P(d_H(c_i,c_j)<\delta n) \\ &< {2^n\choose 2} \e^{-\mathcal{O}(n)}. } \] 只要该概率严格小于 \(1\) 即可.

最终解得的上界称为 Gilbert-Varshamov bound, 即 \[ n\geq c\cdot m, \] 其中 \(c\) 为常数.

5.2 Hamming codes

当 \(n\) 比较大时, nearest neighbour 方法效率极低, 不可接受. 我们需要设计更聪明的编码方式.

考虑 \(\Bbb{F}_2\) 上的矩阵 (以 \(1,2,\dots,7\) 的二进制作为列向量; 称为校验矩阵) \[ H = \pmqty{ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ }_{3\times7}, \] 它的零空间的维数为 \(\dim\operatorname{Null}(H)=7-\rank{H}=4\), 因此 \(\operatorname{Null}(H)\subset\Bbb{F}_2^7\) 一共有 \(2^4=16\) 个 \(7\) 维的向量. 下面我们考虑其中任意两个不同向量的 Hamming 距离的下界.

• Hamming 距离是实内积 \(\lr{-,-}\) 诱导的度量, 其取值在 \(\R\) 中.

任取 \(v,w\in\operatorname{Null}(H)\). 注意到 \(d_H(v,w)=d_H(v-w,0)\), 故只用考虑 \(d_H(v,0)\) (\(0\neq v\in\operatorname{Null}(H)\)).

• 若 \(d_H(v,0)=1\), 即只有一位是 \(1\), 这是不可能的, 因为这意味着 \(H\) 的某列为零.
• 若 \(d_H(v,0)=2\), 即只有两位是 \(1\), 这也是不可能的, 因为这意味着 \(H\) 的某两列相等.
• 因此 \(d_H(v,w)\geq3\).

因此, 如果用 \(\operatorname{Null}(H)\) 中的向量编码的话, 可以做到任意编码被扰动 \(1\) 位后都能还原正确信息.

这种编码称为 Hamming \((7,4)\) 编码, 其中 \(7\) 代表一个编码的长度, \(4\) 表示所有编码构成 \(4\) 维 \(\Bbb{F}_2\)-线性空间.

• Hamming 编码满足 sphere packing bound 的取等条件, 即它严丝合缝地填满了整个空间, 给出了最优的编码长度.
• 使得 sphere packing bound 取等的编码称为完美编码 (perfect code).

一般地, 有 Hamming \((n=2^u-1,m=2^u-1-u)\) 编码, 可以做到任意编码被扰动 \(1\) 位后都能还原正确信息. 此时需要构造校验矩阵 \(H\in M_{u\times n}(\Bbb{F}_2)\).

• Encoding 的目的是构造一个同构 \(\Bbb{F}_2^m\overset\sim\to\operatorname{Null}(H)\). 取 \(\operatorname{Null}(H)\) 的基底 \(G=(q_1,\dots,q_m)\), 考虑映射 \[ \Bbb{F}_2^m \ni a \mapsto Ga \in \Bbb{F}_2^n \] 即可. 此外, 我们希望编码过程更简单一些, 即 \(Ga=\pmqty{a \\ *}\) (\(Ga\) 的前 \(m\) 行恰好为 \(a\)), 只需对 \(G\) 进行初等行变换, 变成 \(\tilde{G}=\pmqty{I_m \\ A_{u\times m}}\) 形式即可, 与此同时, \(H\) 需要列重排为 \(\tilde{H}=\pmqty{B_{u\times m}&I_u}\). 为了保证 \(\tilde{H}\tilde{G}=0\), 需要有 \[ A + B = 0,\;\textsf{即}\; A=B. \]

  • 该过程对于任意线性码都成立.

• Decoding 是非常简单的: 设接收到的编码为 \(w\), 它既可能满足 \(w\in\operatorname{Null}(H)\) (正确), 也可能是 \(w=v+e_i\) 其中 \(v\in\operatorname{Null}(H)\) (扰动一位). 编码正确等价于 \(Hw=0\), 而 \[ H(v+e_i) = He_i = \textsf{$H$ 的第 $i$ 列}, \] 根据 \(He_i\) 确定 \(i\) 便知哪一位错误.

Hamming \((7,4)\) 编码的一个生成矩阵 (\(\mathrm{Null}(H)\) 的基底矩阵) 为 \[ G = \pmqty{ 1 & 1 & 0 & 1 \\ & 1 & 1 & 0 & 1 \\ && 1 & 1 & 0 & 1 \\ &&& 1 & 1 & 0 & 1 }, \] 这样的编码称为循环码 (cyclic code).

5.3 Error correcting codes

下面考虑一般的纠错码.

• 线性码 (linear code), 即所有编码构成 \(\Bbb{F}_2\) 上的线性空间. 记作 \([n,m,d]\), 其中 \(n\) 为编码长度, \(m\) 为线性空间维数, \(d\) 为任意两个编码的 Hamming 距离的最小值.
  • Hamming 码也可以记作 \([2^{u}-1,2^{u}-1-u,3]\).
  • Hamming 码是完美码.
• 一般的编码记作 \((n,M,d)\), 其中 \(n\) 为编码长度, \(M\) 为不同编码的数量, \(d\) 为任意两个编码的 Hamming 距离的最小值.

给一个编码 \((n,M,d)\), 记编码为 \((c_1,\dots,c_M)\). 将开头为 \(0\) 的编码提出来, 再将开头为 \(1\) 的编码提出来, 然后将第一位删掉, 分别记作 \((d_1,\dots,d_{M'})\) 和 \((e_1,\dots,e_{M''})\). 这两者内部的 Hamming 距离最小值仍旧为 \(d\), 而编码数量总有一个大于等于 \(M/2\) 的, 故可以得到编码 \((n-1,{\geq}M/2,d)\).

给一个编码 \((n,M,d)\), 且 \(d\) 为奇数. 设 \(1\) 的个数为奇数的编码为 \((d_1,\dots,d_{M'})\), 个数为偶数的编码为 \((e_1,\dots,e_{M''})\). 由于 Hamming 距离的最小值为奇数, 该最小值 \(d_H(x,y)\) 只能当 \(x=d_i\), \(y=e_j\) (一个奇数一个偶数) 时取到. 在所有 \((d_i)\) 前补一个 \(1\), 所有 \((e_i)\) 前补一个 \(0\), 则可以得到编码 \((n+1,M,d+1)\).