前言：海明码在传输的消息流中插入验证码，当计算机插入或者移动数据时，可能会产生数据位错误，以侦测并更正单一比特错误。由于汉明码简单，被广泛应用于内存。

1. 海明码

  海明码是由贝尔实验室的Richard Hamming设计的，是一种利用奇偶性来检错和纠错的方法。海明码的构成方法是在特定的数据位之间插入k个校验位通过扩大码距来实现检错和纠错。

• 奇偶性错
    根据之前讲述奇偶校验码的文章可知，利用奇偶性纠错的方法主要是利用位异或的方法。
• 特定数据位
    海明码中的校验码所在的特定的数据位是指2的幂次方的位置，比如第1、2、4、8位等等。

2. 编码方法

2.1 位置标记

  以1010110的数据为例，将其每一位分别进行标注
D7D6D5D4D3D2D11010110D_7\space D_6\space D_5\space D_4\space D_3\space D_2\space D_1\space \\ 1\space\space\space\space 0\space\space\space\space1\space\space\space\space 0\space\space\space\space 1\space\space\space\space1\space\space\space\space 0 D7​ D6​ D5​ D4​ D3​ D2​ D1​ 1    0    1    0    1    1    0
  在编码时需要明确以下几点：

• 海明码是原数据码+校验码
• 每个校验码的位置是2的幂次方，比如第1、2、4、8位

  则可以从左往右方向得到如下标注：
H11H10H9H8H7H6H5H4H3H2H1D7D6D5P4D4D3D2P3D1P2P1H_{11}\space H_{10}\space H_9\space H_8\space H_7\space H_6\space H_5\space H_4\space H_3\space H_2\space H_1 \\ D_7\space\space D_6\space\space D_5\space P_4\space D_4\space\ D_3\space D_2\space P_3\space D_1\space P_2\space P_1 H11​ H10​ H9​ H8​ H7​ H6​ H5​ H4​ H3​ H2​ H1​D7​  D6​  D5​ P4​ D4​  D3​ D2​ P3​ D1​ P2​ P1​
（其中，H为海明码的位置标注，P为校验码的位置标注。）

2.2 原始数据

  我们将原始数据以及校验码（初始化为0）填入海明码的位置，得到如下数据：
H11H10H9H8H7H6H5H4H3H2H1D7D6D5P4D4D3D2P3D1P2P11010‾0110‾00‾0‾H_{11}\space H_{10}\space H_9\space H_8\space H_7\space H_6\space H_5\space H_4\space H_3\space H_2\space H_1 \\ D_7\space\space D_6\space\space D_5\space P_4\space D_4\space\ D_3\space D_2\space P_3\space D_1\space P_2\space P_1 \\ 1\space\space\space\space\space 0\space\space\space\space\space 1\space\space\space\space \underline{0}\space\space\space\space 0\space\space\space\space 1\space\space\space\space 1\space\space\space\space \underline{0}\space\space\space\space 0\space\space\space\space \underline{0}\space\space\space\space \underline{0} H11​ H10​ H9​ H8​ H7​ H6​ H5​ H4​ H3​ H2​ H1​D7​  D6​  D5​ P4​ D4​  D3​ D2​ P3​ D1​ P2​ P1​1     0     1    0​    0    1    1    0​    0    0​    0​
此时初始校验码P4P3P2P1为0000。

2.2 校验码生成操作

  校验码的生成公式为：
新的校验码 = 上一次校验码 ⊕（当前数据位 &在海明码中的位置)\text{新的校验码 = 上一次校验码 }\oplus \text{（当前数据位 } \& \text{ 在海明码中的位置)} 新的校验码 = 上一次校验码 ⊕（当前数据位 & 在海明码中的位置)
 以上述数据为例，逐位计算校验码：

• D1
  此时上一次校验码为 0000，当前数据位D1为0，在海明码中占的位置是H3(即位置码为0011)，三者异或后得新的校验码为0000 = 0000 ^ (0 & 0011).
• D2
  此时上一次校验码为 0000，当前数据位D2为1，在海明码中占的位置是H5(即位置码为0101)，三者异或后得新的校验码为0101 = 0000 ^ (1 & 0101).
• D3
  此时上一次校验码为 0101，当前数据位D3为1，在海明码中占的位置是H6(即位置码为0110)，三者异或后得新的校验码为0011 = 0101 ^ (1 & 0110).
• D4
  此时上一次校验码为 0011，当前数据位D4为0，在海明码中占的位置是H7(即位置码为0111)，三者异或后得新的校验码为0011 = 0011 ^ (0 & 0111).
• D5
  此时上一次校验码为 0011，当前数据位D5为1，在海明码中占的位置是H9(即位置码为1001)，三者异或后得新的校验码为1010 = 0011 ^ (1 & 1001).
• D6
  此时上一次校验码为 1010，当前数据位D6为0，在海明码中占的位置是H10(即位置码为1010)，三者异或后得新的校验码为1010 = 1010 ^ (0 & 1010).
• D7
  此时上一次校验码为 1010，当前数据位D7为1，在海明码中占的位置是H11(即位置码为1011)，三者异或后得新的校验码为0001 = 1010 ^ (1 & 1011).
• 可得最终校验码为 0001.
    将其填入校验位可得最终海明码为：
  H11H10H9H8H7H6H5H4H3H2H1D7D6D5P4D4D3D2P3D1P2P11010‾0110‾00‾1‾H_{11}\space H_{10}\space H_9\space H_8\space H_7\space H_6\space H_5\space H_4\space H_3\space H_2\space H_1 \\ D_7\space\space D_6\space\space D_5\space P_4\space D_4\space\ D_3\space D_2\space P_3\space D_1\space P_2\space P_1 \\ 1\space\space\space\space\space 0\space\space\space\space\space 1\space\space\space\space \underline{0}\space\space\space\space 0\space\space\space\space 1\space\space\space\space 1\space\space\space\space \underline{0}\space\space\space\space 0\space\space\space\space \underline{0}\space\space\space\space \underline{1} H11​ H10​ H9​ H8​ H7​ H6​ H5​ H4​ H3​ H2​ H1​D7​  D6​  D5​ P4​ D4​  D3​ D2​ P3​ D1​ P2​ P1​1     0     1    0​    0    1    1    0​    0    0​    1​
  (注：海明码的校验和位置关系很大，上述校验过程数据是从左往右排列的。同样数据在从右往左排列情况下，校验码也不一样。)

3. 海明码校验特点分析

3.1 海明码校验位数确定

  通过之前的操作可以发现校验码和海明码每位数据位置息息相关，也就是相当于生成一个初始的海明码后，检查每位数据位，并将该位数据位进行异或处理。这就要求校验码必须能够表达出所有位置。

  假设有n位数据，生成了k位校验码。分析可得最后生成的海明码是n+k位。k位数据能够表达的最大位置数值是2^k-1。若满足上述要求，校验码能够表达出所有位置信息，则必须有：
2k−1≥n+k2^k-1 \geq n+k 2k−1≥n+k
在上述数据位数为7位情况下，得出校验位为4位。

3.2 纠正一位错

  海明码纠正一位错误，实际上可以理解为异或操作的特点(AB=C,CB=A,C^A=B)。假设位置B是数据出错的那一位，A1是未计算位置B的校验码，算上位置B后(此时假设位置B为1)，得到原始校验码C1。干扰出现后位置B的数据从1变为了0，此时检测端计算出来校验码为C2，与C1不同，两者进行异或计算之后可得位置B的信息，对该位进行取反纠错。
A1⊕B=C1A1=C2C2⊕C1=A1⊕C1=BA_1 \oplus B = C_1 \\ A_1 = C_2 \\ C_2 \oplus C_1 = A_1 \oplus C_1 = B A1​⊕B=C1​A1​=C2​C2​⊕C1​=A1​⊕C1​=B

  若出现两位或者两位以上的数错误，可得
A1⊕B1⊕B2=A1⊕B3=C1(设B1⊕B2=B3)A1=C2C2⊕C1=A1⊕C1=B3A_1 \oplus B_1 \oplus B_2 = A_1 \oplus B_3= C_1 \space\text{(设}B_1 \oplus B_2 = B_3\text{)} \\ A_1 = C_2 \\ C_2 \oplus C_1 = A_1 \oplus C_1 = B_3 A1​⊕B1​⊕B2​=A1​⊕B3​=C1​ (设B1​⊕B2​=B3​)A1​=C2​C2​⊕C1​=A1​⊕C1​=B3​
位置B3实际上是由位置B1与B2组合可得，由于组合方法多种多样，不能确定唯一位置。

总结：
1.海明码只能纠正一位错误
2.n位数据码,k位校验码的海明码必须满足关系2^k-1 >= n + k