第四章 数据可靠传输和信道编码

4.1 离散无记忆信道和信道容量

在第二、三章中，我们已经将如何编码研究得比较清晰了，而接下来要考虑的问题就是如何将此编码传递出去。实际上传递的过程一般要通过电缆、网线等介质，它们都是信道。大家应该都有过断网，跳ping的经历，所以这些介质都是非常不靠谱的，也就是说在信号传递过程中，会有一定的错误概率：即把某个字母传递成了另一个字母。本章我们要研究的就是，如何使得传输过程中 出现错误的概率任意小 。

首先我们先给出信道与信道编码的严格定义：

定义1 设 \cal W,X,Y 均为有限集，我们称条件概率分布族 \{Q(y|x)|x\in\cal X,y\in Y\} ，或者矩阵 Q:=(P(Y=y_j|X=x_i))_{\cal||X||×||Y||} 是以 \cal X 为输入字母集， \cal Y 为输出字母集的一个 信道 ，记为 [{\cal X},Q(y|x),{\cal Y}] 。称 函数对 (f,\varphi) 是一个 信道码 ，其中 f:\cal W\to X^n ，而 \varphi:\cal Y^n\to W 。称 P_e:=P(W\ne \varphi f(W)) 为 错误概率 。

特别地，若信道满足 Q(y_1\cdots y_n|x_1\cdots x_n)=\prod\limits_{i = 1}^n {Q({y_i}|{x_i})} ，则称为 无记忆信道 。

注 无记忆信道的意义就是：把一个字母传输过信道时，它被传输成其他字母的概率并不会被之前的传输过程影响。

现在正式给出信道编码的目的。我们要做的就是在使得错误概率足够小(比如小于任意给定的 \varepsilon>0 )的条件下，使得输出的 Y 能够 尽可能地反映 X 中所携带的信息 。至于衡量 Y 中含有 X 的信息的度量标准，在第一章中我们已经给出过，它就是互信息。

假设 X\sim p(x) ，那么我们有

\[\begin{array}{l} I(X;Y) = \displaystyle\sum\limits_{x \in\cal X} {\sum\limits_{y \in\cal Y} {p(x,y)\log \frac{{p(x,y)}}{{p(x)p(y)}}} } \\\displaystyle = \sum\limits_{x \in\cal X} {\sum\limits_{y \in\cal Y} {p(x)Q(y|x)\log \frac{{p(x)Q(y|x)}}{{p(x)\sum\limits_{x \in\cal X} {p(x)Q(y|x)} }}} } \\\displaystyle = \sum\limits_{x \in\cal X} {p(x)\sum\limits_{y \in\cal Y} {Q(y|x)\log \frac{{Q(y|x)}}{{\sum\limits_{x \in\cal X} {p(x)Q(y|x)} }}} } \\ : = I(p;Q) \end{array}\]

最后一行是 定义 的意思，这样定义的原因是：由信道所给出的这种互信息由 p,Q 唯一确定，因此也可看作 p,Q 的函数。在信道编码问题中， Q 已经给定了。那么 p 在不断变动的情况下， I(p;Q) 的最大值(对 p 而言)就称为信道 [{\cal X},Q(y|x),\cal Y] 的 信道容量 。下面我们给出严格的定义：

定义2 称 \[C: = \mathop {\max }\limits_{p(x)} I(p;Q)\] 为一个离散无记忆信道的 信道容量 。

容易看出，求信道容量是一类 多元函数求极值 问题。在数学分析中我们已经学过多种计算方法，如 \rm Lagrange 乘数法等。接下来我们会看到，在计算信道容量时，有时也会用到定义和熵的概念，这也是一类新的方法。给出几个简单的例子：

例1 (二进无噪信道) 设 {\cal X}={\cal Y}=\{0,1\},Q=I_2 ，试求信道容量。

解 我们有

\[\begin{array}{l} \displaystyle I(p;Q) = p(0)[Q(0|0)\log \frac{{Q(0|0)}}{{p(0)Q(0|0) + p(1)Q(0|1)}}\\\displaystyle + Q(1|0)\log \frac{{Q(1|0)}}{{p(0)Q(1|0) + p(1)Q(1|1)}}]\\\displaystyle + p(1)[Q(0|1)\log \frac{{Q(0|1)}}{{p(0)Q(0|0) + p(1)Q(0|1)}}\\\displaystyle + Q(1|1)\log \frac{{Q(1|0)}}{{p(0)Q(1|0) + p(1)Q(1|1)}}]\\\displaystyle = p(0)\log \frac{1}{{p(0)}} + p(1)\log \frac{1}{{p(1)}} = H(X) \end{array}\]

因此 C = \mathop {\max }\limits_{p(x)} H(X) = \log ||{\cal X}||=1\rm bit ，当且仅当 p 为均匀分布时取得。□

例2 (对称信道) 设 {\cal X = \cal Y}=\{0,1\} ， \[Q = \left[ {\begin{array}{*{20}{c}} {1 - \varepsilon }&\varepsilon \\ \varepsilon &{1 - \varepsilon } \end{array}} \right]\] ，求信道容量。

解 计算可得

\begin{array}I(p;Q)=-[p(0)(1-\varepsilon)+p(1)\varepsilon]\log [p(0)(1-\varepsilon)+p(1)\varepsilon]\\-[p(0)\varepsilon+p(1)(1-\varepsilon)]\log [p(0)\varepsilon+p(1)(1-\varepsilon)]\\-\varepsilon\log\varepsilon-(1-\varepsilon)\log(1-\varepsilon)\\=H(Y)-h(\varepsilon)\le \log||{\cal Y}||-h(\varepsilon)=1-h(\varepsilon).\end{array}

其中 h 为第一章中的 二进熵函数 。显然等号成立当且仅当输出分布 Y=\mu=(\frac{1}{2},\frac{1}{2}) 是均匀分布。由此，我们反解输入分布：设 \xi Q=\mu ，则当 \varepsilon\ne\frac{1}{2} 时， Q 可逆， \xi 有唯一解，用 \rm Cramer 法则解之可得 \xi=(\frac{1}{2},\frac{1}{2}) 也是均匀分布。当 \varepsilon=\frac{1}{2} 时 |Q|=0 ， 不可逆。此时解得： \xi_1+\xi_2=1 ，即只要 \xi 是一个输入分布即可，也就是任何输入分布均可达到信道容量。□

注 \xi Q=\mu 有时不一定有解，这时需采取其他方法。参看下面的例子：

例3 (对称删除信道) 设 \[{\cal X}=\{0,1\},{\cal Y}=\{0,1,2\},Q = \left[ {\begin{array}{*{20}{c}} {1 - \varepsilon }&0&\varepsilon \\ 0&{1 - \varepsilon }&\varepsilon \end{array}} \right]\] 。试求信道容量。

解 类似例2，可得 \[I(p;Q) = H(Y) - h(\varepsilon )\] ，但是这次不一定存在使 Y 服从均匀分布的初始分布了，原因是由于一般没有(这里利用的是线性方程组有解当且仅当系数矩阵的秩等于增广矩阵的秩)

\[r\left[ {\begin{array}{*{20}{c}} {1 - \varepsilon }&0&{\displaystyle\frac{1}{3}}\\ 0&{1 - \varepsilon }&{\displaystyle\frac{1}{3}}\\ \varepsilon &\varepsilon &{\displaystyle\frac{1}{3}} \end{array}} \right] = 2\] ，

于是只能利用定义进行计算了，事实上

\[\begin{array}{l} H(Y) = - (1 - \varepsilon )p(0)\log (1 - \varepsilon )p(0) - (1 - \varepsilon )p(1)\log (1 - \varepsilon )p(1) - \varepsilon \log \varepsilon \\ \le - (1 - \varepsilon )\log\displaystyle \frac{{1 - \varepsilon }}{2} - \varepsilon \log \varepsilon \end{array}\]

其中等号成立当且仅当 X 服从均匀分布，其推导与二进熵函数类似。于是

\[C = - (1 - \varepsilon )\log \frac{{1 - \varepsilon }}{2} - \varepsilon \log \varepsilon + \varepsilon \log \varepsilon + (1 - \varepsilon )\log (1 - \varepsilon ) = 1 - \varepsilon \] 。□

上述三个例子都是很经典的计算信道容量的方法。在本节的最后，我们再对上面的结果作一些推广，这就是下面的定理：

定义3&定理1 如果一个信道的矩阵是个方阵，且它的每一行都是其他行的置换，每一行都是其他列的置换，那么称这个信道为对称信道(与高等代数中对称矩阵的定义不同)。设矩阵的行为 r=(r_1,\cdots,r_k) ，则 C=\log||\cal Y||-h(r) 。其中 \[h(r): = - \sum\limits_{i = 1}^k {{r_i}\log {r_i}} \] 。当矩阵非退化时达到信道容量的出口分布与入口分布都为均匀分布。

定义4&定理2 如果一个信道的矩阵的每一行都是其他行的置换，每一列的和相等，那么称这个信道为弱对称信道。其信道容量也为 \log||{\cal Y}||-h(r) (意义与定理1相同)。达到信道容量时，输入分布与输出分布都是对称分布。

定义5&定理3 如果一个信道的矩阵的每一行都是其他行的置换，那么称这个信道为准对称信道。其信道容量 C\le\log||{\cal Y}||-h(r) (意义与定理1相同)。等号成立当且仅当输出分布是均匀分布。而达到信道容量时，输入分布是均匀分布，但输出分布不一定是均匀分布。

注 定理1，2和定理3分别应当看作例2和例3的更一般的情形。

由等式 I(X;Y)=H(X)-H(X|Y) ，我们还可得到：

定理4 0\le C\le \min\{\log||\cal X||,\log||Y||\} 。其中 C 是信道容量。

4.2 \rm Lagrange 乘数法

由于我们知道互信息是凹函数，于是有如下的定理：

定理5 对离散无记忆信道 [{\cal X},Q(y|x),\cal Y] ，其输入分布 p^* 能到达信道容量的充要条件是

\[D(Q(y|x)||{p^{\rm{*}}}(y))\left\{ {\begin{array}{*{20}{c}} { = C,}&{{p^*}(x) > 0,}\\ { \le C,}&{{p^*}(x) = 0.} \end{array}} \right.\]

其中 p^*(y)=\sum\limits_x {{p^*}(x)Q(y|x)} ， C 是信道容量。

注 达到信道容量的输入分布未必是唯一的，但输出分布是唯一的。

基于定理4，我们可以使用 \rm Lagrange 乘数法来求得一些简单信道的容量和分布的精确解。但是 \rm Lagrange 乘数法的计算量比较大，很多时候使用起来甚为不便。

4.3(*) 数值方法

先给出一个结果。

给定两个闭凸集 A,B ，我们可以采用如下的方法求 d(A,B) ：先在 A 中任取一点 a_1 ，随后在 B 中找点 b_1 ，使得 d(a_1,b_1)=d(a_1,B) ，再固定 b_1 ，在 A 中找点 a_2 ，使得 d(a_2,b_1)=d(A,b_1) 。以此类推下去，只要 距离测度 d 满足一定条件 ，上述算法就能最终收敛到 d(A,B) ，且 (a_n,b_n) 也收敛到一对最小值点。

注意到：概率分布集( \cal X 上的所有概率分布所成之集)实际上是一个闭凸集，而相对熵是一种满足“一定条件”的距离测度。因此上述算法对于求信道容量是适用的，下面再略微深入探讨一些细节。

利用贝叶斯公式，我们可将信道容量改写为：

\[\begin{array}{l} \displaystyle C = \mathop {\max }\limits_{p(x)} I(p;Q) = \mathop {\max }\limits_{p(x)} \sum\limits_{x \in\cal X} {\sum\limits_{y \in\cal Y} {p(x)Q(y|x)\log \frac{{Q(y|x)}}{{\sum\limits_{x \in\cal X} {p(x)Q(y|x)} }}} } \\\displaystyle = \mathop {\max }\limits_{p(x)} \sum\limits_{x \in\cal X} {\sum\limits_{y \in\cal Y} {p(y)Q(x|y)\log \frac{{Q(x|y)}}{{p(x)}}} } \\\displaystyle \mathop = \limits^? \mathop {\max }\limits_{p(x)} \mathop {\max }\limits_{Q'(x|y)} \sum\limits_{x \in\cal X} {\sum\limits_{y \in\cal Y} {p(y)Q(x|y)\log \frac{{Q'(x|y)}}{{p(x)}}} }\\ = - \mathop {\min }\limits_{pQ} \mathop {\min }\limits_{Q'Q} D(pQ||Q'Q) \end{array}\]

现在值得关注的问题就是第三行中的等号打了个问号。这个等式是不是对的？如果是对的，那么我们就成功将信道容量的计算问题变成了两个闭凸集 \{pQ\},\{Q'Q\} 之间的距离(最小相对熵)计算问题，这样我们就圆满地解决了问题。

事实上，打问号的等式是正确的，我们有如下的引理保证：

引理1 \[\sum\limits_{x \in\cal X} {\sum\limits_{y \in\cal Y} {p(y)Q(x|y)\log \frac{{Q'(x|y)}}{{p(x)}}} } \le I(p;Q)\] ，且等号成立当且仅当 Q' 和 Q 是同一分布，即 Q'(x|y)=Q(x|y) 恒成立。

于是，任意给定了一种条件分布 p(x) 后，由引理1，我们马上可以找到使得相对熵最小的 Q' ，实际上它正是 \[Q'(x|y) = \frac{{p(x)Q(y|x)}}{{\sum\limits_{x \in X} {p(x)Q(y|x)} }}\] 。随后我们再固定 Q' ，重新选择适当的 p_1(x) ，使得该分布达到 \[\mathop {\min }\limits_{p_1Q} D(p_1Q||Q'Q)\] 就行了。

计算过程过于暴力，在此从略，事实上 \[{p_1}(x) = \frac{{p(x){e^{D(Q(y|x)||pQ(y))}}}}{{{A_1}}}\] 。式中指数上面的条件熵中 x 应看成 固定的 ； A_1 是适当的常数，它使得 p_1 确实是一个概率分布。

现在我们已经迭代了一步了，从 p(x) 迭代得到了 p_1(x) ，以此类推不难一直迭代下去。那么根据本节开头提到的此算法的收敛性，最终 p_k(x) 就会收敛到 达到信道容量的概率分布 。

4.4 信道编码定理

类似于第二章中曾做的那样，我们现在来研究码率、信道容量与误差概率(即 R,C,P_e )之间的关系。首先重新明确几个定义：

定义6 设 [{\cal X},Q(y|x),\cal Y] 为离散无记忆信道，我们称如下三个部分组成一个 (M,n) 码：

(1)信源消息集 {\cal W}=\{1,2,\cdots,M\} ；

(2)编码函数 f:\cal W\to X^n ；

(3)译码函数 \varphi :\cal Y^n\to W 。

我们称 R:=\frac{\log M}{n} 为此编码的 码率 。

定义7 当信源输出第 i 个消息时， 误差概率 定义为

\lambda_i:=P(\varphi(Y^n)\ne i|X^n=x^n(i))=\sum\limits_{{y^n} \in {\cal Y^n}} {P({y^n}|{x^n}(i))I(\varphi ({y^n}) \ne i)} ，

（也就是在 X^n 是第 i 个消息编出的码的 条件 下，从 Y^n 译出的码不是 i 的概率）

其中 I 是示性函数，即若 \varphi(y^n)\ne i ， I 就输出 1 ，否则输出 0 。

一个 (M,n) 码的 最大误差概率 定义为 \[{\lambda ^{(n)}}: = \mathop {\max }\limits_{i \in\cal W} {\lambda _i}\] ；

平均误差概率 定义为 \[{P_e}: = \frac{1}{M}\sum\limits_{i = 1}^M {{\lambda _i}} \] 。

定义8 称码率 R 可达 ，如果存在一个 (2^{nR},n) 码使得 \[\mathop {\lim }\limits_{n \to \infty } {\lambda ^{(n)}} = 0\] 。一个离散无记忆信道的 最大可达速率 定义为 \[\mathop {\sup }\limits_{R\rm 可达} R\] 。(实际上它就是信道容量，稍后会给出)

接下来像第二章一样，我们定义联合典型序列，并利用联合典型序列证明信道编码定理。

定义9 (联合典型序列) 设 \{(X_i,Y_i)\} 独立同分布，公共分布为 p(x,y) ，则定义 n 长联合典型序列集为：

\[\begin{array}{l} W_\varepsilon ^{(n)}: = \{ ({x^n},{y^n}):| - \frac{1}{n}\log p({x^n}) - H(X)| < \varepsilon ,| - \frac{1}{n}\log p({y^n}) - H(Y)| < \varepsilon ,\\ | - \frac{1}{n}\log p({x^n},{y^n}) - H(X,Y)| < \varepsilon \} \end{array}\]

其中 p(x^n)=p(x_1)\cdots p(x_n) ，其他同理。

下面给出联合典型序列的一些性质，这与第二章中的弱典型序列是类似的。

定理6 联合典型序列满足以下性质：

(1) \[\mathop {\lim }\limits_{n \to \infty } P(({X^n},{Y^n}) \in W_\varepsilon ^{(n)}) = 1\] ，即当 n 充分大时任取一个 n 长联合序列，很可能就是联合典型序列；

(2)任给 \varepsilon>0 ，当 n 充分大时有 \[(1 - \varepsilon ){2^{n[H(X,Y) - \varepsilon ]}} \le ||W_\varepsilon ^{(n)}|| \le {2^{n[H(X,Y) + \varepsilon ]}}\] ，即联合典型序列只占所有联合序列中相当小的比例(趋于 0 )；

利用这两个性质，我们就可以证明信道编码定理了(证明太长，从略)

定理7 (信道编码定理) 对信道容量为 C 的离散无记忆信道，若码率 R<C ，则 R 是可达的，即存在一列 (2^{nR},n) 码使得 \[\mathop {\lim }\limits_{n \to \infty } {\lambda ^{(n)}} = 0\] 。

定理7' (信道编码反定理) 对信道容量为 C 的离散无记忆信道，任何一列 (2^{nR},n) 码若满足 \[\mathop {\lim }\limits_{n \to \infty } {\lambda ^{(n)}} = 0\] ，则必有 R\le C 。

推论1 C=\mathop {\sup }\limits_{R\rm 可达} R ，即 信道容量就是最大可达速率 。

4.5 译码规则

本节中假设 \varphi 是 \cal Y\to X 的映射，因为反正编码的时候也是一一对应的，找到了 \cal X 中的元素就相当于找到了原消息。

怎样的译码规则能够较好地翻译出原信息？先来看下面的例子：

例4 设信道矩阵 \[Q = \left[ {\begin{array}{*{20}{c}} {0.9}&{0.1}\\ {0.1}&{0.9} \end{array}} \right]\] 。如果我们把译码规则规定为 \varphi(0,1)=(1,0) ，则错误概率高达 90\% ，而如果 \varphi(0,1)=(0,1) ，则错误概率只有 10\% 。

从上面的例子看出，一个好的译码规则应当把每个输出的 y ，译为 最可能 射到 y 的那个 x 上。比方说，上面的例子若改成 \[Q = \left[ {\begin{array}{*{20}{c}} 0&1\\ 1&0 \end{array}} \right]\] ，那我们一眼就可以看出：应该把 1 译为 0 ， 0 译为 1 ，因为如果输出是 0 ，那么 只可能 ( 最可能 )是从 1 传输过去的。

综合以上的讨论，可以给出第一种译码规则，称为 最大后验概率 译码规则：对于每个 y ，我们选择 使得 \[p(x|y)\] 最大的那个 x ，作为 \varphi(y) 。但是后验概率一般来说比较难以确定，所以这种方法只是一种比较自然的想法，实现起来并不方便。

本节再给出一种容易实现的译码规则，称为 极大似然 译码规则。它的思想是：对于每个 y ，我们选择 使得 \[p(x)Q(y|x)\] 最大的 x 来作为 \varphi(y) 。由于 p,Q 均已知，这个规则计算起来相对简单一些。特别地，如果 p 是均匀分布，则只需找使得 Q(y|x) 最大的 x 作为 \varphi(y) 。

例5 设信道矩阵为 \[Q = \left[ {\begin{array}{*{20}{c}} {\displaystyle\frac{1}{2}}&{\displaystyle\frac{1}{3}}&{\displaystyle\frac{1}{6}}\\ {\displaystyle\frac{1}{6}}&{\displaystyle\frac{1}{2}}&{\displaystyle\frac{1}{3}}\\ {\displaystyle\frac{1}{3}}&{\displaystyle\frac{1}{6}}&{\displaystyle\frac{1}{2}} \end{array}} \right]\] ，输入分布为均匀分布，求极大似然译码规则。

解 对于每个 y 我们只需选择使得 Q(y|x) 最小的 x 作为对应，它也就是 Q 中每一列中最大的数所在的行数。即：先来看 y=0 ，那么 Q(0|x) 就是 Q 的第一列，而 Q(0|0)=\frac{1}{2} 最大，所以 \varphi(0)=0 。同理可得 \varphi(0,1,2)=(0,1,2) 。□

注 如果 p 不是均匀分布，则应把 Q 换成 {\rm diag}\{p_1,\cdots,p_k\}Q 进行判断。

4.6 线性分组码

定义10 (二元域) 令 GF_2:=\{0,1\} ，在其上定义加法与乘法为：

0\oplus1=1\oplus0=1,0\oplus0=1\oplus1=1,10=01=00=0,11=1,

则容易验证 GF_2 对于加法与乘法成为一个域，称为二元域。

我们要讨论的线性分组码便是一种具有代数结构的码，本节就在较为简单的二元域上进行讨论。首先给出线性码的一些相关概念：

定义11 记 {\cal U=X}=GF_2 ，则 \cal U^k\to X^n 的一个映射 f 称为 线性码 ，特别地若 f 是单射，则称为 唯一可译线性码 。 f 在两个空间的两组基下的 表示矩阵 G 的 转置 称为线性码的 生成矩阵 。

那么自然要问，线性码有什么优越之处？事实上，如果 n>k ，那么我们实际上将一个低维向量编码成了一个高维向量。而如果进一步， G=(I\space A) ，则编出来的码字的前 k 位与之前是完全相同的，这样我们就可以 构造特定的 A ，使得能够利用 A 来做一些检验。

下面我们对此思想作深入探讨。

定义12 设 G 是生成矩阵，若矩阵 H 满足 GH'=0 ，则称 H 是校验矩阵。特别地，如果 G=(I\space A) ，则一般规定 H=(A'\space I) ，并且称由这样的 G 编出的码是 系统码 。

注 实际上应该是 H=(-A',I) ，但由于我们 在二元域上 考虑，所以有 -1=1 。

定理8 设 G=(I\space A) 是生成矩阵， H=(A'\space I) 是其校验阵。则 C 是 G 编出的码字当且仅当 CH'=0 。

证明 C 是 G 生成的码字即 C'\in{\rm Im}G' 。而由条件 GH'=0 ，可知 {\rm Im}G'\subset{\rm Ker}H ，又 G' 满秩(这是由于 G=(I\space A) )，故 {\rm dimIm}G'={\rm dimKer}H (此处是由解空间的维数公式)，从而上面的包含关系实际上是 相等 。因此 C 是 G 生成的码字

\begin{array} \\\Leftrightarrow C'\in {\rm Im}G' \\\Leftrightarrow C'\in {\rm Ker}H \\\Leftrightarrow HC'=0 \\\Leftrightarrow CH'=0.\space\space□ \end{array}

注 这应该是我给出的第一个严格的证明……实际上这门课的许多定理挺折磨的，要么太简单了没必要证，要么太难了搞不赢证明TnT。

定义13 若两个生成矩阵 G,G' 等价，则称它们编出的码等价。

注 从定义13知道，一个满秩阵 G 未必能编出系统码，但其编出的码与系统码 是等价的 。

下面我们来具体研究如何利用线性码进行译码与纠错。

定义14 设 G 不是零矩阵，则称非零码字中非零元的数量为该码字的 汉明重 。一个编码中所有非零码字的汉明重的最小值称为 G 的 最小汉明重 。

定义15 设 x=(x_1,\cdots,x_n),y=(y_1,\cdots,y_n) 是两码字。则定义

d(x,y):=\sum\limits_{i = 1}^n {({x_i} \oplus {y_i})}

为它们的 汉明距离 。

注1 求和号表示的是普通的加法，而求和号里面是二元域的加法。

注2 可以证明，汉明距离确实是一个距离，即满足严格正定性、对称性和三角不等式。

注3 由上述定义可知，一个线性码的最小汉明重等于 码字集中的 最小汉明距离。

定理9 设 H 是 G 的校验矩阵，则 H 的任意 t 列线性无关且存在 t+1 列线性相关当且仅当 G 的最小汉明重为 t+1 。

证明 G 的最小汉明重为 t+1 ，当且仅当线性方程组 HX=0 的 任意 解的非零分量数不低于 t+1 ，并且 可以取到 t+1 。而这就当且仅当 H 的 任意 t 列线性无关 (前半句) ，且 存在 t+1 列线性相关 (后半句)。□

现在来看译码时如何纠错。设输入 x^n=(x_1,\cdots,x_n) ，输出 y^n=(y_1,\cdots,y_n) 。如果 y^n 适合 y^nH'=0 ，那么我们就认为输入的码字就是 y^n (当然这其实也不一定，但是信道 恰好把一个码字变为另一个码字 的概率也不是很大)；而如果 y^nH'\ne0 ，那说明传输一定发生了错误。

我们定义一个向量 E:=(e_1,\cdots,e_n) ，其中如果第 i 位发生错误，就令 e_i=1 ，否则令 e_i=0 。于是有 y^n=x^n+E ( 时刻不要忘记我们是在二元域上讨论的 ，这也是二元域加法定义的好处)。记 S=y^nH' ，则 S=(x^n+E)H'=EH' ，即 S 是一个只与 发生错误的位置 有关的 向量 ，称为监督子，校验子或伴随式， E 称为 错误图样 。

不过即使如此，不同的错误图样仍然有可能诱导出不同的伴随子，究其原因， S=EH' 式取转置即得 HE'=S ，而 H 的列数肯定大于行数，因此解必不唯一(应该是的吧？O_0)。于是我们仍然需要给出一种译码规则，把 y^n 映到一个码字。这就是 最小距离 译码规则：我们选择使得 d(x^n,y^n) 达到最小的那个 x^n\in {\rm Im}G' 作为 y^n 的译码。这是为什么呢？

因为假设每个字母翻译错的概率为 p ，那么结合实际来看， p 是个很小的数。计算可知，恰好传输错 t 位的概率为 p^t(1-p)^{n-t} ，显然有

\[{p^1}{(1 - p)^{n - 1}} > > {p^2}{(1 - p)^{n - 2}} > > \cdots > > {p^t}{(1 - p)^{n - t}} > > \cdots \]

所以传输过程中错的位数应该很少，错得越少的概率越大。因此我们就选那个与 y^n 相差位数最少的码字作为译码结果。

下面给出线性码的检测与纠错能力的一些结果：

定理10 对于最小汉明重为 d 的 (n,k) 线性码，

(1)若 d=2e+1 ，则该码能纠正 e 个错误；

(2)若 d=l+1 ，则该码能检测 l 个错误；

(3)若 d=e+l+1(e<l) ，则该码能在纠正 e 个错误的同时检测 l 个错误。

证明 (1)设输入 x^n=(x_1,\cdots,x_n) ，输出 y^n=(y_1,\cdots,y_n) ，假设发生了 e 个错误，即 d(x^n,y^n)=e ，又对任意其他码字 z ， d(x,z)\ge d=2e+1 。从而由三角不等式得： d(y^n,z^n)\ge e+1>e=d(x^n,y^n) ，从而根据最小距离译码规则必把 y^n 译为 x^n 。

(2)假设发生了 l 个错误，则 d(x^n,y^n)=l 。而对任意码字 z ， d(x^n,z)\ge l+1 ，于是立即知道 y^n 不是码字，这就发现了错误。

(3)结合(1)(2)即得。□

在本节(本章)的最后我们来构造一类最小汉明重为 3 (即能纠正 1 位错误)的线性码：汉明码。假设传输中恰好出现了 1 位错误，那么就有 n 种可能的错误图样 \varepsilon_1,\cdots,\varepsilon_n ( \varepsilon_i 是标准单位行向量 (0,\cdots,0,1,0,\cdots,0) )，而这些错误图样作用在 H 上，必须不能为 0 ，且必须是互不相同的(这样可以唯一分辨出是哪一位发生错误， 因为 \varepsilon H' 得到的就是 H' 的某一列，如果这些列互不相同那就可以唯一确定得到的是哪一列了，也就可以确定是哪一位发生了错误 )。

而一个伴随式 S=EH' 共有 2^{n-k} 种可能的组合，于是一个能检测 1 个错误的码，其列数必须满足 2^{n-k}\ge n+1 。而如果取到等号， n 就是满足这个条件的最好( 最小 )的(校验矩阵的)列数。 汉明码就是取等时的这一类线性码,并且它的所有列恰好是 GF_2^n 中的全部元素。例如 (7,4) 汉明码，其校验矩阵为：

\[H = \left[ {\begin{array}{*{20}{c}} 0&0&0&1&1&1&1\\ 0&1&1&0&0&1&1\\ 1&0&1&0&1&0&1 \end{array}} \right]\]

如果 H 的右侧是单位阵，则称为 系统汉明码 。显然把上图中的 H 作若干次列对换即可变为系统汉明码(这样并不会改变码的性质)。

终于搞完了 ^\wedge \nabla^\wedge

这应该是考试最重点的一章了吧