海明校验码

  由Richard Hamming于1950年提出、目前还被广泛采用的一种很有效的校验方法,是只要增加少数几个校验位,就能检测出二位同时出错、亦能检测出一位出错并能自动恢复该出错位的正确值的有效手段,后者被称为自动纠错。它的实现原理,是在k个数据位之外加上r个校验位,从而形成一个k+r位的新的码字,使新的码字的码距比较均匀地拉大。把数据的每一个二进制位分配在几个不同的偶校验位的组合中,当某一位出错后,就会引起相关的几个校验位的值发生变化,这不但可以发现出错,还能指出是哪一位出错,为进一步自动纠错提供了依据。

基本思想

  将有效信息按某种规律分成若干组,每组安排一个校验位,做奇偶测试,就能提供多位检错信息,以指出最大可能是哪位出错,从而将其纠正。实质上,海明校验是一种多重校验。

特点 

  它不仅具有检测错误的能力,同时还具有给出错误所在准确位置的能力 但是因为这种海明校验的方法只能检测和纠正一位出错的情况。所以如果有多个错误,就不能查出了。  假设为k个数据位设置r个校验位,则校验位能表示2^r个状态,可用其中的一个状态指出 "没有发生错误",用其余的2 ^r -1个状态指出有错误发生在某一位,包括k个数据位和r个校验位,因此校验位的位数应满足如下关系: 

  2^r ≥ k + r + 1

  按上述不等式,可计算出数据位k与校验位r的对应关系: 

k值
最小r值
1~4
3
5~11
4
12~26
5
27~57
6
58~120
7

   在海明码中, 位号数(1、2、3、……、n)为2的权值的那些位,即:1(2^0)、2(2^1)、4(2^2)、8(2^3)、…2^r-1位,作为奇偶校验位,并记作: P1、P2、P3 、P4、…Pr,余下各位则为有效信息位。例如: N=11 K=7 r=4 相应海明码可示意为位号 1 2 3 4 5 6 7 8 9 10 11P占位 P1 P2 × P3 × × × P4 × × ×其中×均为有效信息,海明码中的每一位分别被P1P2P3P4… Pr 中的一至若干位所校验,其规律是:第i位由校验位位号之和等于i的那些校验位所校验如:海明码的位号为3,它被P1P2(位号分别为1,2)所校验,海明码的位号为5,它被P1P3(位号分别为1,4)所校验。归并起来: 形成了4个小组,每个小组一个校验位,校验位的取值,仍采用奇偶校验方式确定。

原文地址:https://www.cnblogs.com/hibernation/p/3363362.html