汉明码简介

汉明码（也叫海明码），常用于数据传输中的校验编码。汉明码具有一位纠错能力，其主要特点如下：

1. 数据分组校验

2. 校验位在$2^x$位

3. 校验位个数和值的确定

4. 校验码的解码和纠正

说白了就是每个校验位负责一组数据的奇偶校验，然后整个数据分成了好几组，最后将各组的校验整合得到整个数据中出现错误的那一位。

编码

假设数据有n位，其中校验码有x位，那么编码后的数据应该有n+x位。x位校验码一共有$2^x$种取值，其中一种取值表示数据正确，则剩下的$((2^x) - 1)$种取值表示有一位数据出错。不难推出如下不等式：

$$ ((2^x) - 1) >= (n+x) $$

使得不等式成立的x的最小值就是汉明码的校验位数。

• 例如0101 0011数据有8位，则代入不等式可以得到“$((2^x) - 1) >= (8+x)$”，所以x=4。

• 原始数据0101 0011经过编码之后变成了12位数据，其中第$2^k$位是校验位，其余位为数据位，如下所示：

• 然后对他们进行分组，首先观察其位置编码：

• 将最低位是1的数据分为第一组：P1, D1, D2, D4, D5, D7

  将第二低位是1的数据分为第二组：P2, D1, D3, D4, D6, D7

  将最三低位是1的数据分为第三组：P4, D2, D3, D4, D8

  将最高位是1的数据分为第四组：P8, D5, D6, D7, D8

  再根据每个分组的数据位和偶校验的规则计算校验位具体数值

1
2
3
4
5

P1 = D1 ^ D2 ^ D4 ^ D5 ^ D7 // 0 ^ 1 ^ 1 ^ 0 ^ 1
P2 = D1 ^ D3 ^ D4 ^ D6 ^ D7 // 0 ^ 0 ^ 1 ^ 0 ^ 1
P3 = D2 ^ D3 ^ D4 ^ D8 // 1 ^ 0 ^ 1 ^ 1
P4 = D5 ^ D6 ^ D7 ^ D8 // 0 ^ 0 ^ 1 ^ 1
// 计算得到：P1 = 1, P2 = 0, P3 = 1, P4 = 0

• 原始数据0101 0011经过编码变成1001 1010 0011

解码

• 汉明码只能对一位数据进行检测和纠正（但是在计算机网络传输过程中，绝大多数情况下都是仅发生一位数据错误，因此汉明码校验仍然在广泛使用），假设收到的数据为1001 1010 0010，此时接收方并不知道数据是否有效，需要对该数据进行汉明码校验，具体如下：

  首先对校验码进行校验计算

1
2
3
4
5

P1_Check = P1 ^ D1 ^ D2 ^ D4 ^ D5 ^ D7 // 1 ^ 0 ^ 1 ^ 1 ^ 0 ^ 1
P2_Check = P2 ^ D1 ^ D3 ^ D4 ^ D6 ^ D7 // 0 ^ 0 ^ 0 ^ 1 ^ 0 ^ 1
P3_Check = P3 ^ D2 ^ D3 ^ D4 ^ D8 // 1 ^ 1 ^ 0 ^ 1 ^ 0
P4_Check = P4 ^ D5 ^ D6 ^ D7 ^ D8 // 0 ^ 0 ^ 0 ^ 1 ^ 0
// 计算得到：P1_Check = 0, P2_Check = 0, P3_Check = 1, P4_Check = 1

• 按照对应高低位将校验计算的结果进行排列，得到P4P3P2P1 = 1100，

  该数据表示P4和P3校验位检测到数据出错，而P1和P2校验位检测到数据正常（即D2, D3, D4 D8和D5, D6, D7, D8中各有一个数据出现错误，而D1, D2, D4, D5和D1, D3, D4, D6, D7均正常）

  所以可以推测出出现错误的是D8表示的数据，即第12位数据位出错，0b1100对应十进制正好为12，只需要将对应位取反即可得到正确数据。