893fb895954e208092dd71b7782b5a4b
海明码校验

1 引言

  海明码(Hamming Code),是在电信领域的一种线性调试码,以发明者理查德·卫斯里·海明的名字命名。海明码在传输的消息流中插入验证码,当计算机存储或移动数据时,可能会产生数据位错误,以侦测并更正单一比特错误。由于海明码编码简单,所以被广泛应用。本文将具体介绍海明码的编码过程以及校验原理。

2 确定校验码位数

  在进行编码之前,首先需要确定校验码的位数有多少。海明码确定校验码位数公式如下:
  2^r ≥ k+r+1。
其中,P为校验码的位数,k为明文信息的位数。
  例如:二进制编码01101001,共有8位则k = 8;根据公式可以得出:
  2^r ≥ 8+r+1
  可以解出r = 4。因此需要校验码的位数为4位。

3 确定校验码位置

  在确定校验码位数之后,下一步需要确定校验码的位置,即校验码要加在原始数据的什么位置。与奇偶校验和CPC冗余校验不同,海明码的校验码并不是加在数据末尾,而是插入在数据中的。
  海明码校验方式的校验码在二进制串中的位置为2的整数幂位置,剩下的位置为数据位。
  例如:对于第2节中的二进制编码01101001,校验码位置如下表所示:

位置H 12 11 10 9 8 7 6 5 4 3 2 1
编码 D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1
数据 0 1 1 0 P4 1 0 0 P3 1 P2 P1

其中,H代表编码后的数据,D代表原始数据,P代表校验码。

4 计算校验位数值

  想要确定校正位的数值,就首先必须知道哪些信息需要校正位来校正。校正的原则:想要校正第几(i)位,则应该满足对应的那几个校正位相加等于i。例如3=1+2;7=1+2+4。

位置 占用校验位 表达式
1 1 1=1
2 2 2=2
3 1, 2 3=1+2
4 4 4=4
5 1, 4 5=1+4
6 2, 4 6=2+4
7 1, 2, 4 7=1+2+4
8 8 8=8
9 1, 8 9=1+8
10 2, 8 10=2+8
11 1, 2, 8 11=1+2+8
12 4, 8 12=4+8

  根据占用的校验位可以得出P1,P2,P3,P4参与的校验信息位,得到如下表格:

校验位 参与校验信息位
P1 H3, H5, H7, H9, H11
P2 H3, H6, H7, H10, H11
P3 H5, H6, H7, H12
P4 H9, H10, H11, H12

则得到:

top Created with Sketch.