3.3 差错控制

3.3.1 检错编码

3.3.1.1 汉明距离的概念与意义

比特翻转有自己的代数规律，我们定义第n位的比特翻转位 ${𝑇}_{𝑖}$，那么我们有 ${𝑇}_{𝑖}^2=id$，同时我们还有 ${𝑇}_{𝑖}\circ {𝑇}_{𝑗}={𝑇}_{𝑗}\circ {𝑇}_{𝑖}$

3.3.1.2 奇偶校验码

奇偶校验是最最简单的一种校验方式。而后续的海明校验中往往也包含奇偶校验的思想，不过我对现有教材不满意的点在于，并没有给出足够深层次的insight，让它更多成为一种想到的技巧，而不是某种结构的必然性。

我们可以把校验的本质看成一种判别式，它是一个接受任意比特流的函数，对每一个比特流返回一个布尔值。分别代码合法和非法。

我们的要求是： 对任意比特串，只要翻转其中任意一个比特，判别结果就必须改变。

我们希望一个合法码翻转了一位之后就一定变成非法码。但是之所以要求非法码翻转后就变成合法码是因为这样利用率最高。

由于翻转之后判别结果必须改变，我们要从一个n位比特串集合中选出一个合法集合 ，并且要求任意两个合法码字都不能只相差一个比特。

把全部 $2^{𝑛}$ 个比特串按照尾比特是否相同，配成如下的 $2^{\left\{𝑛-1\right\}}$ 对：

比如0000 配对 0001

0010配对0011

那么我们势必不可能同时把每一对中的两个比特都作为合法的。一对当中只能取一个。所以最多有一半的合法码。

而如果我们让合法码集取最大，那么就一定保证每个非法码都统一对应着一个合法码配对了。

首先存在一种判别法，能够每接受一条比特流信息就分成两类。而对于每条信息，这一条信息所有的比特翻转情况都刚好能被归为另一类。那么异或判定就是其中最简单的函数，一旦进行比特翻转，它的异或判定的结果就一定会变。

借助了判别法之后，我们思考如何构造信息来满足这样的判别法。那就是我们所有发出的信息都要满足该判别式。但是这样会限制我们能发出的信息。

最终我们能得出在这一编码中，一半的信息是正确的，一半的信息是错误的。

所以对于每条任意的信息。我们期望把它编码成正确的信息。

那么这一条信息本身拿到1个比特，剩下的位数就能用来表示信息了。

下面我们来证明，这种满足翻转判别式值变化，让合法码数量最大，的判别式本身就是奇偶校验判别，换言之，异或判别。因为任意一个比特串一定可以通过纯0比特串翻转得到。

我们如何让已知的信息编码成满足表达式的情况呢，对于一个 $2^{𝑛}$ 长的的编码，它的合法码情况是 $2^{𝑛-1}$ 也就是任意的n-1位比特流它都可以得到双射对应来表达。

但这样的可能情况太多了，我们想要一种简单的构造方式而非复杂的映射，

这理想情况就是在已有的信息流上追加位数，这被称为Systematic code

再通过追加一位编码，这样是有可能的么。

那就是用一位用作校验位。让校验位始终满足表达式约束。

接下来我们再介绍一种检错编码，它就是循环冗余CRC编码。

3.3.2 纠错编码

3.3.2.1 汉明码

如果我们吧这些信息对应成位置，冗余的比特就能不只用来检错而是纠错。

这次判别式产生的结果不在是布尔值，而是有n个结果，其中的第一组结果是不出错的。然后所有出错的结果被拆到余下n组里。理论上对于一个n位的比特流，只要确保它的各位翻转出现的结果出现在不同的结果组里就行了。

不过这样的判别式的确很多。其中存在一些这样的情况：同一种结果编码，对于不同的比特流，代表的是翻转不同位的结果。比如说111是合法的，000也是合法的，然后110和010的判定结果是是一样的，但是一个是翻转了第3位，一个是翻转了第2位，这非常不优雅。

我们期望最终的结果恰恰能刚好对应翻转位，无论原来的码字是什么，只要翻转的是同一个位置，判别结果就会按照同一种规律变化。其中一种结果用来对应无错误，剩下的n-1种结果都用来意一一对应表示错误的n-1个位置。

比如，我们定义一个7位码的判别式有8种输出，值域是{0,..,7}，其中0代表无错误，剩下的输出是几就代表第几位被翻转了。

转化成数学表达就是上

为了方便起见，我们记 ${𝑔}_{𝑖}=𝑓\circ {𝑇}_{𝑖}$

接下来我们来研究任意多次翻转。它最终一定能够写成多个翻转复合的形式，也就是 ${𝑇}_{𝑖}\circ \cdots \circ {𝑇}_{𝑗}$

我们考虑第二个任意翻转，也就是 ${𝑇}_{𝑘}\circ \dots \circ {𝑇}_{𝑙}$

这两个翻转的复合的结果就是，它们之间如果有重复翻转的归0，其他的翻转复合保留。那么这不就是模2加法，换言之，异或么。

我们定义全0比特是合法码，那么我们可以证明。

如果 $𝑥$ 是合法码，$𝑦$ 是合法码，那么 $𝑥\oplus 𝑦$ 也是合法码。 换言之，最终合法码是一个对异或封闭的集合。

接下来我们发现比特翻转的闭包刚好构成阿贝尔群。我们记所有的翻转行为和id翻转都是这个群上的元素。封闭性和结合性交换性单位元都是容易证明的，每一个元素的逆元就是它自身。

甚至它还是个向量空间，我们添加 {0,1} 作为标量域，它数乘的结果。0 倍翻转操作，表示不执行这个操作；1 倍翻转操作，表示执行一次这个操作。分配率显然满足了。

我们把翻转第i位记位 ${𝑇}_{𝑖}$ 会发现一种情况，那就是

n 个纠错比特本质上提供了 $2^{𝑛}$ 的信息，

对于一个比特流，我们想额外

我们继续发展奇偶校验的思想，怎么保证任意一条信息刚好被编码成了

假设我们发送7个比特中有三个冗余比特，那么 $2^3=8\ge 7+1$，我们就能确保存在一种编码使得纠错码的每个具体形态对应着一种纠错，同时剩下一种无错情况也能被表示。

你可能会问，在这一情况下纠错码如何发现自己的错误的。很简单，因为经过良好的设计，理论上翻转了某一个象征着某一位有错的编码形成的编码样态能够象征自己的编码。