计算机系统基础知识——校验码之海明码(Hamming Code)

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

1. 海明码

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

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

2. 编码方法

2.1 位置标记

??以1010110的数据为例，将其每一位分别进行标注
$$\begin{gathered} D_7{D}_6{D}_5{D}_4{D}_3{D}_2{D}_1 \\ 1010110 \end{gathered}$$
??在编码时需要明确以下几点：

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

??则可以从左往右方向得到如下标注：
$$\begin{gathered} H_{11}{H}_{10}{H}_9{H}_8{H}_7{H}_6{H}_5{H}_4{H}_3{H}_2{H}_1 \\ {D}_7{D}_6{D}_5{P}_4{D}_4{D}_3{D}_2{P}_3{D}_1{P}_2{P}_1 \end{gathered}$$
（其中，H为海明码的位置标注，P为校验码的位置标注。）

2.2 原始数据

??我们将原始数据以及校验码（初始化为0）填入海明码的位置，得到如下数据：
$$\begin{gathered} H_{11}{H}_{10}{H}_9{H}_8{H}_7{H}_6{H}_5{H}_4{H}_3{H}_2{H}_1 \\ {D}_7{D}_6{D}_5{P}_4{D}_4{D}_3{D}_2{P}_3{D}_1{P}_2{P}_1 \\ 101\underline{0}011\underline{0}0\underline{0}\underline{0} \end{gathered}$$
此时初始校验码P4P3P2P1为0000。

2.2 校验码生成操作

??校验码的生成公式为：
$$\text{新的校验码 = 上一次校验码 }?\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.
  ??将其填入校验位可得最终海明码为：
  $$\begin{gathered} H_{11}{H}_{10}{H}_9{H}_8{H}_7{H}_6{H}_5{H}_4{H}_3{H}_2{H}_1 \\ {D}_7{D}_6{D}_5{P}_4{D}_4{D}_3{D}_2{P}_3{D}_1{P}_2{P}_1 \\ 101\underline{0}011\underline{0}0\underline{0}\underline{1} \end{gathered}$$
  (注：海明码的校验和位置关系很大，上述校验过程数据是从左往右排列的。同样数据在从右往左排列情况下，校验码也不一样。)

3. 海明码校验特点分析

3.1 海明码校验位数确定

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

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

3.2 纠正一位错

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

??若出现两位或者两位以上的数错误，可得
$$\begin{gathered} A_1?B_1?B_2=A_1?B_3=C_1\text{(设}{B}_1?B_2=B_3\text{)} \\ {A}_1=C_2 \\ {C}_2?C_1=A_1?C_1=B_3 \end{gathered}$$
位置B3实际上是由位置B1与B2组合可得，由于组合方法多种多样，不能确定唯一位置。

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