【2-11】海明码

前言

前面的内容主要介绍了传输数据主体的各个方面的内容，却鲜少提及差错检测与纠错。今天我们介绍纠错码——海明码。

1. 奇偶校验

我们的主人公海明——Richard Wesley Hamming ，最早系统性论述和推动了奇偶校验位技术。

奇偶校验的工作原理是通过设置规则来检查一组给定的位中1的数量。如果采用奇校验，那么每个数据单元（如字节）中1的总数必须是奇数；如果采用偶校验，则这些1的总数必须是偶数。

具体来说，奇校验的工作方式如下：

• 如果数据单元中1的数量已经是奇数，则校验位设置为0；
• 如果数据单元中1的数量是偶数，则校验位设置为1，以使总数变为奇数。

然而奇偶校验只能检测出一位bit的错误，而且检出后还不能纠错。

Hamming就开始思考有没有更有效的纠错方法。

2. 海明距离

海明距离也叫码距，也就是两个码字不同的比特数。这个距离也被称为汉明距离。.

为什么要计算码距呢？因为数据和数据的差异影响到我们检错的难度。就比如：

我们有2个编码 00、01，信道有一定的不稳定性，会产生1bit的错误，即0变成1,1变成0.

这个时候我们在接收端收到00时，我们无法确定是原来就是00，还是说01出错变成了00.这就是因为编码太相似导致的结果，可我们必须精确描述这种现象，于是我们引入了 码距 这个概念！

所以我们该怎么办呢？ 用 00、11来编码，这样码距是2,1位出错后很容易发现问题。

3. 两只手能表示多少个数？

我们人类喜欢掰着手指头数数，其实手指计数也是一种编码规则。可我们人类为了方便，保持手指数数的连贯性，往往伸出来几个就会代表几。

那么我们双手最多可以表示多少个数呢？其实是1024个数！怎么回事呢？可以看下面这个视频：

“屈指可数”是多少？ 屈指可数背后的数学原理，子集与映射的奇妙关系！

4. 海明不等式

我们很容易就能感受到，如果我们仅仅把前面的二进制编码对应到的位利用起来，就可以当做1024个数字的“下标”，这种感觉就像：

也就是说，我们用3个比特对0到7进行了编码，其中0被舍弃了，因为2的n次方无法得出0。假设我们使用的校验位的比特的位数是k，那么我们一共编码了几个位置呢？答案是 $2^k-1$，再假设我们一共有 $m$ 个位置表示实际要传输的数据，我们就轻而易举地得出了海明不等式：

$$2^k-1\ge m+k$$

5. 海明码编码规则

1. 在海明码中，校验位被放置在所有2的幂次方的位置上，即第1位、第2位、第4位、第8位等。这些位置上的比特用于校验其他数据位。
2. 计算校验位：每个校验位负责检查一组特定的数据位。具体来说，校验位 $P_i$ 负责检查那些在二进制表示中包含 $i$ 的位置上的数据位。例如，校验位 $P_1$ 负责检查所有奇数位。
3. 每个校验位的值是它所负责的数据位的奇偶校验结果。
4. 组合数据位和校验位：将计算好的校验位插入到数据位中相应的位置，形成完整的海明码。

所以我们在校验时，一定要把 $D_1{D}_2$ 等数据对应到2进制的位置写出来，才能更好去对应。有时候我们对校验位也直接写成：$P_1{P}_2{P}_3\cdot \cdot \cdot$ 这种样式。

5.1. 编码举例

假设我们需要传输 1001011 ，第一个问题，我们需要几个校验位呢？

我们可以看到，数据位是7，也就是海明不等式中的 $m=7$，根据海明不等式可得：

$$\begin{gathered} 2^k-1\ge 7+k \\ {2}^k\ge 8+k \\ k最小取4 \end{gathered}$$

所以我们引入四个校验位，并把四个校验位放在2的n次方的位置上：

接下来，假设收发双方规定使用偶校验来填充所有的校验位。由于校验位与数据位的关系如下：

• 3 = 1+2
• 5 = 1+4
• 6 = 2+4
• 7 = 1+2+4
• 9 = 1+8
• 10 = 2+8
• 11 = 1+2+8

所以位置1对应的是数据 3、5、7、9、11 的比特的偶校验。偶校验要求1的个数是偶数，我们可以看到，目前3、5、7、9、11 对应的比特是 10101 ，也就是3个1，所以位置1的校验结果是1。故此整体上1的个数为偶数。

接下来，我们位置2，它对应 3、6、7、10、11 ，也就是 10111 ，所以2是0.
位置4对应 5、6、7，也就是 001 ，所以位置4是1
位置8对应 9、10、11，也就是 011，所以位置8是0.

故我们填写上所有的校验位：

5.2. 纠错举例

假设我们传输的 10110010011 出现了1bit传输错误，也就是传输成了下面的结果，我用红色标记出数据位错误的部分：

由于2和4能校验6，所以我们这次偷懒只计算这两位：

位置2对应 3、6、7、10、11 ，也就是 11111 ，所以2是1
位置4对应 5、6、7，也就是 011 ，所以位置4是0

故而得出：

与收到的校验位进行对比，发现2和4出现了错误。

由于 2+4 = 6，故第6位出错了，由于二进制只有0和1，所以1出错了，原数据位应是0。这样，我们就复原了真实的数据。

后记

由于信道在发展得过程中，变得越来越可靠，尤其是光纤的出现，信道出现n位比特出错的概率已大大降低。且网络带宽也逐年提高，尤其是分组交换使得重传的数据减少，故现代计算机网络多用检错技术而不用纠错技术，出错重传即可。下一讲，我们会重点讨论检错技术——CRC校验。

文中有任何错误、遗漏，烦请各位老铁在评论区指出，共同学习进步。

修改记录