海明校验
☆海明码是什么？
海明码是一种可以对数据校验，并至多可以校正一位出错的校验方法。
海明码有以下特点：
- 海明码使用多重奇偶校验
- 海明码可以校正一位出错，并且可以指出出错的位置。
- 即使，校验位出错，对海明码的校验也没有影响。
- 海明码的校验位长度有规定。
海明码有n位数据和k位校验码组成n+k位，即p = n + k。海明码可生成k位的指示码$G_kG_{k-1}…G_1$
☆ 海明码的生成：
假如有4个要传输的数据位，即n=4。
海明码的校验位数k与数据位数n需满足：$2^k\ge n+1$（稍后解释） ，因此k取3。
于是我们有4位数据位，3位校验位，共七位。将3位校验位放到第2^i-1^ （i=1,2,3,…）位置上，数据位放到校验位的空隙中。如下表所示：
| 索引（从1开始） | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 数据位/校验位(k表示校验位，n表示数据位) | k1 | k2 | n1 | k3 | n2 | n3 | n4 |
| 实际数据 | 待定 | 待定 | 1 | 待定 | 0 | 1 | 1 |
接着计算校验位 k1, k2, k3
根据使用的校验方式不同，选择不同的校验方式（奇校验 / 偶校验），以偶校验为例：
$k_1=p_3\oplus p_5\oplus p_7=0$
$k_2=p_3\oplus p_6\oplus p_7=1$
$k_1=p_5\oplus p_6\oplus p_7=0$
这样我们得到：
| 索引（从1开始） | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 数据位/校验位(k表示校验位，n表示数据位) | k1 | k2 | n1 | k3 | n2 | n3 | n4 |
| 实际数据 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
k~1~ (001) 是 3 (011), 5 (101), 7 (111) 的偶校验位
k~2~ (010)是 3 (011), 6 (110), 7 (111) 的偶校验位
k~3~ (100) 是 5 (101), 6 (110), 7 (111) 的偶校验位
每个校验位的生成方法可归纳如下：首先校验位和数据位的索引变化成二进制形式，因为校验位只出现在2^i-1^ （i=1,2,3）的位置，因此校验位索引的二进制形式只有一个位置是1。对于其他的数据位，如果其索引的二进制形式的某个位置为1，且这个位置与某个校验位索引为1的位置相同，那么这个数据位就要参与这个校验位的生成。
☆ 海明码的检验与校正：
当我们收到一个带海明校验的数据，我们对所有的校验位进行校验，并将得到的结果作为指示位$G_kG_{k-1…G_1}$。
对于上面的例子
| 索引（从1开始） | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 数据位/校验位(k表示校验位，n表示数据位) | k1 | k2 | n1 | k3 | n2 | n3 | n4 |
| 实际数据 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
$G_1 = k_1\oplus p_3\oplus p_5\oplus p_7=0$
$G_2 = k_2\oplus p_3\oplus p_6\oplus p_7=0$
$G_3 = k_3\oplus p_5\oplus p_6\oplus p_7=0$
由于$G_3 G_2 G_1=000$ ，因此数据无误。
若第六位出错，$G_3 G_2 G_1=110$ 刚好指出了错误的位置，我们只要将第六位取反即可纠正。
☆ 海明码的原理^[1]^：
海明码由n位数据位和k位校验位组成，校验位可以指出数据出现错误的地方。
k位校验位可以表示 2^k^ 中状态，因此若要能指出每一位可能发生错误的地方，2^k^ >= n
又因为，校验位必须还可以表示数据没有出错的情况，因此校验位还要多出一个状态。
综上，校验位数k和海明码数n需满足 2^k^ >= n+1
海明码是如何分布的，为什么是这样分布的？
海明校验码的k个校验位$k_1,k_2,…k_i,…,k_n$ 的第i位（i = 1, 2, …, n）分别分布在第2^i-1^ 位上。
这是因为，当k = 3时，有一位校验位传输出错的话，则校验位与数据为进行奇偶校验的结果有3中，001，010，100，如果想要处理这种情况，只要令校验位位于001，010，100的位置就可以了。
海明码如何能指出错误的位置，为什么？
对于一个三位校验指示码$G_3G_2G_1$ ，
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| —— | —— | —— | —— | —— | —— | —— |
| k1 | k2 | n1 | k3 | n2 | n3 | n4 |G1等于1意味着001，011，111，101，必然有一个出错，因此$G_1=p_1\oplus p_3\oplus p_5\oplus p_7$ 。
同理，G2等于1意味着010，011，110，111，必有一个出错 ，即$G_2=p_2\oplus p_3\oplus p_6\oplus p_7$
$G_3=p_4\oplus p_5\oplus p_6\oplus p_7$
因此当n1出错时，G1=1,G2=1,G3=0，即011B = 3D，可以指出错误的位。
（参考文献 1 解释得更加详细！）
Reference
[1] 海明校验码是怎么实现的？: https://www.zhihu.com/question/29169628/answer/837787585 (这个讲得很好，循序渐进)