校验码-海明码+详细解释

海明码

（也叫汉明码）具有一位纠错能力。
本文以1010110这个二进制数为例解释海明码的编码和校验方法。

---

1. 确定校验码的位数x

设数据有n位，校验码有x位。则校验码一共有2^x种取值方式。其中需要一种取值方式表示数据正确，剩下2x-1种取值方式表示有一位数据出错。因为编码后的二进制串有n+x位，因此x应该满足
2^x-1 ≥　n+x　　　
使不等式成立的x的最小值就是校验码的位数。在本例中，n=7，解得x=4。

---

2. 确定校验码的位置

校验码在二进制串中的位置为2的整数幂。剩下的位置为数据。如图所示。
D是数据位。H是校验位

校验位Pi放在H（2^(i-1)的位置

---

3. 计算校验码的值

1. 数据位的海明码下标写出来如上图的3567

2. 将下标用2进制表示

3. 如下图进行异或运算：注意：取非零位对应的数据进行运算

4. 得到P1,P2，P3的值
   根据：H3 = H1+H2 （右下标之和等于左下标。）

      H5 = H1+H4
   
      H6 = H2 + H4
   
      H7 = H1 + H2 + H4
   

可得：P1（H1） = H3 ⊕ H5 ⊕ H7 （⊕表示异或，即：与H1有关的信息码进行异或）
P2（H2） = H3 ⊕ H6 ⊕ H7

       P3（H4） = H5 ⊕ H6 ⊕ H7

计算可得：P1 = 0，P2 = 1，P3 = 0

所以：最终海明码： H7 H6 H5 H4 H3 H2 H1 = 1 1 0 0 1 1 0

---

5. 纠错

设检测位G1，G2，G3：

则有：G1 = P1 ⊕ H3 ⊕ H5 ⊕ H7 ；

       G2 = P2 ⊕ H3 ⊕ H6 ⊕ H7；

       G3 = P3 ⊕ H5 ⊕ H6 ⊕ H7；

当偶校验时：G3 G2 G1 值皆为0则数据无误，若G3 G2 G1不全为0说明数据传输有误，且其十进制指出了错误发生的位置。

（例：G3 G2 G1 = 101，其十进制为 5 ，即：H5 发生了错误，H5的位置为D1，则说明D1传输错误，则将D1的位置取反，即可纠错。）

所以海明码定义：具有纠正一位错误的能力。