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

tech2025-04-22 9

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

1. 海明码

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

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

2. 编码方法

2.1 位置标记

以1010110的数据为例，将其每一位分别进行标注 $D_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$ 在编码时需要明确以下几点：

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

则可以从左往右方向得到如下标注： $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$ （其中，H为海明码的位置标注，P为校验码的位置标注。）

2.2 原始数据

我们将原始数据以及校验码（初始化为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}$ 此时初始校验码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. 将其填入校验位可得最终海明码为：

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}

(注：海明码的校验和位置关系很大，上述校验过程数据是从左往右排列的。同样数据在从右往左排列情况下，校验码也不一样。)

3. 海明码校验特点分析

3.1 海明码校验位数确定

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

假设有n位数据，生成了k位校验码。分析可得最后生成的海明码是n+k位。k位数据能够表达的最大位置数值是2^k-1。若满足上述要求，校验码能够表达出所有位置信息，则必须有： $2^k-1 \geq 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的信息，对该位进行取反纠错。 $A_1 \oplus B = C_1 \\ A_1 = C_2 \\ C_2 \oplus C_1 = A_1 \oplus C_1 = B$

若出现两位或者两位以上的数错误，可得 $A_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$ 位置B3实际上是由位置B1与B2组合可得，由于组合方法多种多样，不能确定唯一位置。

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

最新回复(0)