海明码究竟是什么?海明码校验方法一览

时间:2020-08-06 14:47:38 来源: 百度百科


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

校验方法

如果一条信息中包含更多用于纠错的位,且通过妥善安排这些纠错位使得不同的出错位产生不同的错误结果,那么我们就可以找出出错位了。在一个7位的信息中,单个位出错有7种可能,因此3个错误控制位就足以确定是否出错及哪一位出错了。

汉明码SECDED(single error correction, double error detection)版本另外加入一检测比特,可以侦测两个或以下同时发生的比特错误,并能够更正单一比特的错误。因此,当发送端与接收端的比特样式的汉明距离(Hamming distance)小于或等于1时(仅有1 bit发生错误),可实现可靠的通信。相对的,简单的奇偶检验码除了不能纠正错误之外,也只能侦测出奇数个的错误。

下列通用算法可以为任意位数字产生一个可以纠错一位的汉明码:

1.从1开始给数字的数据位(从左向右)标上序号, 1,2,3,4,5...

2.将这些数据位的位置序号转换为二进制,1, 10, 11, 100, 101,等。

3.数据位的位置序号中所有为二的幂次方的位(编号1,2,4,8,等,即数据位位置序号的二进制表示中只有一个1)是校验位

4.所有其它位置的数据位(数据位位置序号的二进制表示中至少2个是1)是数据位

5.每一位的数据包含在特定的两个或两个以上的校验位中,这些校验位取决于这些数据位的位置数值的二进制表示

(1) 校验位1覆盖了所有数据位位置序号的二进制表示倒数第一位是1的数据:1(校验位自身,这里都是二进制,下同),11,101,111,1001,等

(2) 校验位2覆盖了所有数据位位置序号的二进制表示倒数第二位是1的数据:10(校验位自身),11,110,111,1010,1011,等

(3) 校验位4覆盖了所有数据位位置序号的二进制表示倒数第三位是1的数据:100(校验位自身),101,110,111,1100,1101,1110,1111,等

(4) 校验位8覆盖了所有数据位位置序号的二进制表示倒数第四位是1的数据:1000(校验位自身),1001,1010,1011,1100,1101,1110,1111,等

(5) 简而言之,所有校验位覆盖了数据位置和该校验位位置的二进制与的值不为0的数。

采用奇校验还是偶校验都是可行的。偶校验从数学的角度看更简单一些,但在实践中并没有区别。校验位一般的规律可以如下表示:

观察上表可发现一个比较直观的规律:第i个检验位是第2^(i-1)位,从该位开始,检验2^(i-1)位,跳过2^(i-1)位……依次类推。例如上表中第3个检验位p4从第23-1=4位开始,检验4、5、6、7共4位,然后跳过8、9、10、11共4位,再检验12、13、14、15共4位……[1]

编码原理

奇偶校验是一种添加一个奇偶位用来指示之前的数据中包含有奇数还是偶数个1的检验方式。如果在传输的过程中,有奇数个位发生了改变,那么这个错误将被检测出来(注意奇偶位本身也可能改变)。一般来说,如果数据中包含有奇数个1的话,则将奇偶位设定为1;反之,如果数据中有偶数个1的话,则将奇偶位设定为0。换句话说,原始数据和奇偶位组成的新数据中,将总共包含偶数个1. 奇偶校验并不总是有效,如果数据中有偶数个位发生变化,则奇偶位仍将是正确的,因此不能检测出错误。而且,即使奇偶校验检测出了错误,它也不能指出哪一位出现了错误,从而难以进行更正。数据必须整体丢弃并且重新传输。在一个噪音较大的媒介中,成功传输数据可能需要很长时间甚至不可能完成。虽然奇偶校验的效果不佳,但是由于他只需要一位额外的空间开销,因此这是开销最小的检测方式。并且,如果知道了发生错误的位,奇偶校验还可以恢复数据。 如果一条信息中包含更多用于纠错的位,且通过妥善安排这些纠错位使得不同的出错位产生不同的错误结果,那么我们就可以找出出错位了。在一个7位的信息中,单个数据位出错有7种可能,因此3个错误控制位就足以确定是否出错及哪一位出错了。[2]

一般来说,若汉明码长为n,信息位数为k,则监督位数r=n-k。若希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置,则要求

2r-1≥n或2r≥k+r+1[3]

现以数据码1101为例说明汉明码编码原理,此时D4=1、D3=1、D2=0、D1=1,在P1编码时,先将D4、D3、D1的二进制码相加,结果为奇数3,汉明码对奇数结果编码为1,偶数结果为0(奇数位。若奇数结果编码为0.偶数结果为1,则叫偶数位),因此P1值为1,D4+D2+D1=2,为偶数,那么P2值为0,D3+D2+D1=2,为偶数,P3值为0。这样,参照上文的位置表,汉明码处理的结果就是1101001。在这个4位数据码的例子中,我们可以发现每个汉明码都是以三个数据码为基准进行编码的。下面就是它们的对应表:

汉明码

编码用的数据码

P1

D8、D4、D1

P2

D8、D2、D1

P3

D4、D2、D1

从编码形式上,我们可以发现汉明码是一个校验很严谨的编码方式。在这个例子中,通过对4个数据位的3个位的3次组合检测来达到具体码位的校验与修正目的(不过只允许一个位出错,两个出错就无法检查出来了,这从下面的纠错例子中就能体现出来)。在校验时则把每个汉明码与各自对应的数据位值相加,如果结果为偶数(纠错代码为0)就是正确,如果为奇数(纠错代码为1)则说明当前汉明码所对应的三个数据位中有错误,此时再通过其他两个汉明码各自的运算来确定具体是哪个位出了问题。

还是刚才的1101的例子,正确的编码应该是1101001,对应D4 D3 D2 D1 P3 P2 P1。如果第三个数据位在传输途中因干扰而变成了1,就成了1111001, 即 D2=1。检测时,P1=D4+D3+D1=1+1+1的结果是奇数3,除以2余数1,原来第一位纠错代码为1,正确。P2=D3+D2+D1的结果是奇数3,除以2余数1,而原来第二位纠错代码为0,有错误。P3=D3+D2+D1的结果是奇数3,除以2余数1,而原来第三位纠错代码为0,有错误。可推断是第2位出现错误。

关键词:海明码 校验方法

关于我们 加入我们 广告服务 网站地图

All Rights Reserved, Copyright 2004-2020 www.ctocio.com.cn

如有意见请与我们联系 邮箱:5 53 13 8 [email protected]

豫ICP备20005723号    IT专家网 版权所有