海明码的计算和检错纠错
海明码
1.学习前提
学习海明码之前，我们要约定3个原则：
- 海明码只能检测出2位错，纠1位错(因此不要问如果3位错怎么办等幼稚问题)。
- 海明码默认进行偶校验(除非特殊说明使用奇校验)。
- 海明码是一串由0和1组成的序列(除01外没有其他的值，记住了！这是重点)
2.海明码的构成
海明码由信息位和校验位组成。
校验位：2的n次方的位置
信息位：不是2的n次方的位置
如下表所示：
| H7 | H6 | H5 | H4 | H3 | H2 | H1 | 海明码位置 |
|---|---|---|---|---|---|---|---|
| X4 | X3 | X2 | X1 | 信息位 | |||
| P2 | P1 | P0 | 校验位 |
3.求海明码例子
如：求信息1011的海明码？
1.算出校验位数k
2^k >= k + 信息位数 + 1
2^k >= k + 4 + 1 ======》k=3,即校验位3个
2.确定校验位在海明码中的位置
| H7 | H6 | H5 | H4 | H3 | H2 | H1 | 海明码位置 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 信息位 | |||
| P2 | P1 | P0 | 校验位 |
3.分组求校验码
我们需要确认H1,H2,H4这三个校验位都来校验哪些位置。
首先将下标1,2,4的二进制码写出来，并且最高位补到3位（前面算的k数）
如下所示：
| 1 | 2 | 4 |
|---|---|---|
| 001 | 010 | 100 |
然后我们将0替换为，作为通配表。*
| 1 | 2 | 4 |
|---|---|---|
| 1 | * 1* | 1 |
我们将1到7的二进制序列，列出来如下表
| 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|
| 111 | 110 | 101 | 100 | 011 | 010 | 001 |
将校验位的1,2,4用信息位来匹配
| 1 | 2 | 4 |
|---|---|---|
| 1 | * 1* | 1 |
| 末尾都是1 | 第二位是1 | 最高位是1 |
| 011（3） | 011（3） | 101（5） |
| 101（5） | 110（6） | 110（6） |
| 111（7） | 111（7） | 111（7） |
即：
H1所在位置的校验码，负责的是3,5,7信息位的校验；
H2所在位置的校验码，负责的是3,6,7信息位的校验；
H4所在位置的校验码，负责的是5,6,7信息位的校验；
4.使用偶校验来求校验码！！！！！
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PfRQd2l9-1681734744148)(…/AppData/Roaming/Typora/typora-user-images/image-20230417192220923.png)]
得到H1=1,H2=0,H4=0
所以正确的完整的海明码为：
| H7 | H6 | H5 | H4 | H3 | H2 | H1 | 海明码位置 |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 0 | 1 | 信息位 | |||
| 0 | 0 | 1 | 校验位 |
4.查错
先了解下原理：
首先我们先画个圆。然后按如下形式做交叉
在每个相邻部位，我们做相加处理
变成了如下形式
当我们如果发现偶校验出错，
比方说在 1 3 7 5 这个区域出错。
如果这个位置出错了，那么一定是 1 3 7 5 这四个位置中的一个位置出错(如果俩位出错则无法纠错，这个点一定要记住)
如果此时其他的俩个组 即：2，3，6，7 和 4，5，6，7偶校验都通过了的话。
也就证明只可能是1出错
所以我们可以将 1 的位数 做修改。如果是0变为1，如果是1变为。来达到纠错的目的。
但是如果2，3，5，7这个位置也出错了，4，5，6，7这个位置没有出错。
我们很容易就推导出，是 3 这个位置出错了。
我们就可以修改3的值，如果是0变为1或者如果是1变为0.
在此时我们会发现一个巧妙的规则！当我们把
1,3,5,7 设为P1,
2,3,6,7设为P2
4,5,6,7设为P3
时当如果哪组校验失败就为1
| P3 | P2 | P1 | 出错(第几)位数 |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 2 |
| 0 | 1 | 1 | 3 |
| 1 | 0 | 0 | 4 |
| 1 | 0 | 1 | 5 |
| 1 | 1 | 0 | 6 |
| 1 | 1 | 1 | 7 |
刚好是对应的二进制编码。就是这么绝。
所以：
======================================================================
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Bp6GvuVA-1681734744151)(…/AppData/Roaming/Typora/typora-user-images/image-20230417193747976.png)]
看题目给出的海明码到此分组时
H1,X3,X5,X7进行偶校验是0 还是1，其他组一样计算
然后根据三组的结果，任一组结果有1肯定就是错了，再根据结果的十进制知道是第几位出错了，取反就是纠错了。
5.纠错
查出错误位置后，直接0变1或者1变0就OK了
6.例2
44151)]
看题目给出的海明码到此分组时
H1,X3,X5,X7进行偶校验是0 还是1，其他组一样计算
然后根据三组的结果，任一组结果有1肯定就是错了，再根据结果的十进制知道是第几位出错了，取反就是纠错了。
5.纠错
查出错误位置后，直接0变1或者1变0就OK了
6.例2
