wiki
海明码（Hamming Code）是由贝尔实验室的 Richard Hamming 设计的，是一种利用奇偶校验来检错和纠错的校验方法。方法是在数据位插入 k 个校验位，通过扩大码距来实现检错和纠错。
1. 理论构成
设数据位有 n 位置，校验位有 k 位，则 n 与 k 需要满足关系：2k - 1 ≥ n + k。
按照如下规则进行编码：
设 k 个校验位为 Pk,Pk-1,...,P1，n 个数据位为 Dn-1,Dn-2,...,D1,D0，对应的海明码为 Hn+k,Hn+k-1,...,H1，那么：
- Pi 在海明码的第 2i-1 位置，即 Hj=Pi，且 j=2i-1，数据位则依序从低到高占据海明码中剩下的位置
- 海明码中任何一位都是由若干个校验位来校验的。其对应关系如下：被校验的海明码的下标等于所有参与校验该位的校验位的下标之和，而校验位由自身校验。
2. 理论设计
对于 8 位的数据位，可计算，其校验位需要 4 个（24 - 1 = 15 ≥ 8 + 4 = 12）。由此可知：
- 数据位可表示为 D7,D6,...,D0
- 校验位可表示为 P4,P3,P2,P1
- 海明码可表示为 H12,H11,...,H1
编码过程如下：
- 确定数据位、校验位在海明码中的位置：
- 确定校验关系，默认为偶校验（奇校验需要取反即可）：
- 检验错误，对海明码的数据进行差错检查很容易，如下：
若采用默认偶检验，则 G4G3G2G1 全为 0 时表示接收到的数据无错误（奇校验全为 1）。当不全为 0 时，可判断发生了错误，而且它的十进制指出了发生错误的位置，如 G4G3G2G1 = 1010，说明 H10(D5) 出错，可将其取反来纠正错误。
3. 实战
假设一个数据为 11001001，可知需要 4 个校验位。数据位如上，现在计算校验位。根据上述说明，使用异或计算可求出相应校验位：
P1 = D0 ⊕ D1 ⊕ D3 ⊕ D4 ⊕ D6 = 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 = 0
P2 = D0 ⊕ D2 ⊕ D3 ⊕ D5 ⊕ D6 = 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 = 1
P3 = D1 ⊕ D2 ⊕ D3 ⊕ D7 = 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0
P4 = D4 ⊕ D5 ⊕ D6 ⊕ D7 = 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0
异或求值也可以换一种计算方式，把校验位的 0 替换为 *，写成通配符形式：
将对应位数的的海明码，写成二进制形式：
将与通配符匹配的数据写在其下方，可见与异或求值一致：
纠错计算就是用纠错码与相应位数异或，由于该纠错码就是使用相应位数计算而来，因此值是一样的，所以异或结果必然是 0：
G1 = P1 ⊕ D0 ⊕ D1 ⊕ D3 ⊕ D4 ⊕ D6 = 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 = 0
G2 = P2 ⊕ D0 ⊕ D2 ⊕ D3 ⊕ D5 ⊕ D6 = 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0
G3 = P3 ⊕ D1 ⊕ D2 ⊕ D3 ⊕ D7 = 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0
G4 = P4 ⊕ D4 ⊕ D5 ⊕ D6 ⊕ D7 = 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0
来自 Glett的码字间