前言
在计算机运行过程中，由于种种原因致使数据在存储过程中可能出现差错。为了能及时发现错误并及时纠正错误，通常使用一些编码方式。
奇偶校验
奇偶校验是一种添加一个奇偶位用来指示之前的数据中包含有奇数还是偶数个1的检验方式。
对于一个二进制数：
新数据：
即
在传输过程中，如果只有1位（奇数个位）发生了改变（包括校验位），那么将可以检测出来错误。但是如果有偶数个位发生了改变，那么校验位将是正确的，因此不能检测错误。而且，即使出现了错误，也不知道是哪一位出现了错误，数据必须整体丢弃并且重新传输。
汉明码
简介
汉明码的实质上是多重奇偶校验，通过巧妙的分组，实现了校验并纠正一位错误的能力。
编码纠错理论
任何一种编码是否具有检测能力和纠错能力，都与编码的最小距离有关。所谓编码最小距离，是指在一种编码系统中，任意两组合法代码之间的最少二进制位数的差异。
根据纠错理论得：
即编码最小距离L越大，则其检测错误的位数D越大，纠正错误的位数C也越大，且纠错能力恒小于或等于检错能力。
所以，如果我们在信息编码中增加若干位检测位，增大L，显然便能提高检错和纠错能力。汉明码就是根据这一理论提出的具有一位纠错能力的编码。
关于编码最小距离
例1.1
假设我们的一种编码系统是所有的3位二进制数，即
那么对于任何一个数据，比如我们传输
- 第一位0变为1：
- 第二位1变为0：
- 第三位0变为1：
显然，这三种数据都在集合当中，我们检验不出错误。
此时就是，
例1.2
可以看出，我们的编码最小距离为2，
比如，我们传输数据
- 第一位0变为1：
- 第二位1变为0：
- 第三位0变为1：
但是，
对于出错数据
- 第一位0变为1：
- 第二位0变为1：
- 第三位1变为0：
所以是会有两种情况，故，无法纠错。
例1.3
则，
核心公式
设欲检测的二进制代码为n位，为使其具有纠错能力，需增添k位检测位，组成 n + k 位的代码。为了能准确对错误定位以及指出代码没错，新增添的检测位数 k应满足：
变换一下：
k位检测位可以提供
这样是不是更好理解。
由此求出不同代码长度 n，所需检测位的位数 k：
| n | K（最小） |
|---|---|
| 1 | 2 |
| 2~4 | 3 |
| 5~11 | 4 |
| 12~26 | 5 |
| 27~57 | 6 |
| 58~120 | 7 |
分组
k的位数确定后，便可由它们所承担的检测任务设定它们在传送代码中的位置及它们的取值。
设
- ··········
这种小组的划分有以下特点：
- 每个小组
- 每两个小组
- 每3个小组
- 依次类推。
特点似乎有点不明所以，总结起来就是：
- ······
稍后，我们会明白这样设计的缘由。
现在我们需要传递一个4位二进制数，记为
那么根据前面的核心公式
| 二进制序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 名称 |
则，根据配偶原则：
例2
令
故 0101的汉明码应为
纠错过程
汉明码的纠错过程实际上就是对配偶原则（或者奇）的检验，根据新数据的状态，便可直接指出错误的位置。直接看例子：
例3
已知，传送的正确汉明码是
| 二进制序号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 发送的汉明码 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 接收的汉明码 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
检测：
可见，
那如何找出错误呢？
这里是假设只出现一位错误，因为此时的
- 因为
- 那现在错误的范围就缩小到了，
- 显然，第6位是错的。
此时，更加巧合的是：二进制数
换句话说，检测出的信息所表示的数就是出错的位置。
韦恩图
我们用韦恩图来表示一下刚刚找错误位的过程：
刚刚找 6的过程不就是：
这样可以理解之前设计的原因了吧。
参考文献
唐朔飞. 计算机组成原理[M]. 第3版. 高等教育出版社, 2020.
__EOF__
