汉明码 Hamming Code

发表于 分类于

数据传输的过程中，数据丢失或者人为干扰时就可能会出现数据接收者接收到的数据出现差错

为了保证的数据的完整性或错误纠正有几种解决方案:

  • 错误检测方案: 奇偶校验(只能检测奇数位错误)、校验和(checksum)、循环冗余校验(CRC)、哈希...
  • 错误检测+纠错的方案: 汉明码(单bit错误检测和纠正)、BCH码(多bit错误检测和纠正)...

汉明码是一种用于检测和纠正单比特错误的编码技术

编码步骤

  1. 先计算出 汉明码的长度

    公式为 $2^k >= N + k + 1$其中 N为数据长度， k为 汉明码的长度

  2. 根据长度填入原数据，冗余位留空

    冗余位即汉明码要填入2的幂次位置，所以 1($2^0$)、2($2^1$)、4($2^2$)、8($2^3$)...格要留空

  3. 计算冗余位的值

    1. 根据原数据中bit为1的每一位所在的索引位置(从左往右从1开始), 计算出对应的二进制值
    2. 根据二进制值做XOR(异或)运算得出 冗余位该填入的值, 得到的二进制数从右往左填充入冗余位

  4. 冗余位与数据原值合并得到最后编码结果

例子

计算原数据10101111的汉明码

  1. 计算汉明码的长度 $2^k >= 8 + k + 1$ 得到k=4 满足条件(其中8为10101111的长度)

    所以有4个冗余位, 汉明码的长度 4 + 8 = 12

    1 2 3 4 5 6 7 8 9 10 11 12
     

  2. 接着再将原数据的值填入表格

    重点: 汉明码要填在2的幂次的位置, 所以 1($2^0$)、2($2^1$)、4($2^2$)、8($2^3$)格要留空

    1 2 3 4 5 6 7 8 9 10 11 12
    1 0 1 0 1 1 1 1

  3. 计算出冗余位的值

    1. 根据原值索引转化出对应二进制
    1 2 3 4 5 6 7 8 9 10 11 12
    1 0 1 0 1 1 1 1
    3 => 0011 6 =>0110 9 => 1001 10 => 1010 11 => 1011 12 => 1100
    1. 根据得到的二进制数执行XOR异或运算
      0b0011 ^ 0b0110 ^ 0b1001 ^ 0b1010 ^ 0b1011 ^ 0b1100 = 0b0001
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
       | 8 4 2 1
    ---|----------
    3  | 0 0 1 1
    6  | 0 1 1 0
    9  | 1 0 0 1
    10 | 1 0 1 0
    11 | 1 0 1 1
    12 | 1 1 0 0
    ---|----------
    XOR| 0 0 0 1

    对应 得出 索引1填入1, 索引2填入0, 索引4填入0 索引8填入0

  4. 填入冗余位与数据原值组合得出最终的编码 101001001111

    1 2 3 4 5 6 7 8 9 10 11 12
    1 0 1 0 0 1 0 0 1 1 1 1

纠错

数据接收者拿到汉明码后 可以通过汉明码中 bit为1的位根据对应的索引转换成二进制，并进行XOR

  • 如果 结果为 0 则代表 没错误无需纠正
  • 如果 结果非0 则得到的结果为 错误的位的索引号

还是之前的例子 原数据10101111 得出的汉明码 101001001111

验证101001001111

1
2
3
4
5
6
7
8
9
10
11
   |
---|----------
1  | 0 0 0 1
3  | 0 0 1 1
6  | 0 1 1 0
9  | 1 0 0 1
10 | 1 0 1 0
11 | 1 0 1 1
12 | 1 1 0 0
---|----------
XOR| 0 0 0 0

结果为0000表示该汉明码正确

修改汉明码中的一位改为101001001110 如何得到修改了哪一位并修正?

  1. 取出汉明码中的为1的位并根据所在的索引转为二进制
1 2 3 4 5 6 7 8 9 10 11 12
1 0 1 0 0 1 0 0 1 1 1 0 
1
2
3
4
5
6
7
8
9
10
   |
---|----------
1  | 0 0 0 1
3  | 0 0 1 1
6  | 0 1 1 0
9  | 1 0 0 1
10 | 1 0 1 0
11 | 1 0 1 1
---|----------
XOR| 1 1 0 0

得到了 0b1100 即 十进制的12 表示第12位错误 即101001001110有错误 第12位 0应改为1
101001001111

多个bit错误

汉明码只能检测和纠正单个bit的错误

例如 原数据10101111 得出的汉明码 101001001111，
此时 把汉明码 第12位改为0 第11位改为0 为101001001100

1
2
3
4
5
6
7
8
9
   |
---|----------
1  | 0 0 0 1
3  | 0 0 1 1
6  | 0 1 1 0
9  | 1 0 0 1
10 | 1 0 1 0
---|----------
XOR| 0 1 1 1

修改两位比特位导致校验冲突，结果111即7，而第7位并没有被修改过

参考

  • https://yaojordan.medium.com/%E8%A8%88%E6%A6%82-hamming-code-%E6%BC%A2%E6%98%8E%E7%A2%BC-78102d680c78
  • https://zh.wikipedia.org/wiki/%E6%B1%89%E6%98%8E%E7%A0%81