基本思想:将有效信息位按某种规律分成若干组,每组安排一个校验位进行奇偶测试。在一个数据位组中加入几个校验位,增大数据代码间的码距,当某一位发生变化时会引起校验结果发生变化,不同代码微商的凑无会得到不同的校验结果。
校验码的位数:设位数为N位,其中有效信息为k位,校验位为r位,分成r组奇偶校验,能产生r位验错信息,这r位信息就构成了一个二进制数的指误字,能指出2∧r-1位错误。所以N=k+r<=2∧r-1
有效信息分组规律:若海明校验码有m位,最高为第m位,最低为第1位,即H[m]、H[m-1]... ... H[2]、H[1],其中中括号里面的数为位号数,位号数等于2的次方的那些位(即1(2^0)、2(2^1)、4(2^2)、... ...2^(r-1)位),作为奇偶校验位,并记为P1、P2……Pr,余下的位则为有效信息位。校验位与有效信息位之和为m。
每一位海明码由某些校验位所校验:即第i位由校验位位号之和等于i的那些校验位所校验。如下表:
海明校验 占用校 备注
码位号 验位号
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
海明码的编码、查找、纠错原理:
设有4位有效信息b1、b2、b3、b4和3位校验码P1、P2、P3
海明校验
码序号 1 2 3 4 5 6 7 出错位
含义 P1 P2 b1 P2 b2 b3 b4 指误字 无错误 1 2 3 4 5 6 7
第一组 * * * * G1 0 1 0 1 0 1 0 1
第二组 * * * * G2 0 0 1 1 0 0 1 1
第三组 * * * * G3 0 0 0 0 1 1 1 1
编码原理 : 若有效信息b1、b2、b3、b4=1011,则先将它分别填入第3、5、6、7位,再分组进行奇偶统计,分别将值填入校验位P1、P2、P3。这里分组采用偶校验,因此要确保三组校验位的取值都满足偶校验规则。例如第一组有P1b1b2b4,已含有偶数个1,因此P1应为0,以确保第一组为偶性。由此可得P1 P2 b1 P2 b2 b3 b4=0110011。
差错和纠错原理 :计算G1=P1⊕b1⊕b2⊕b4;G2=P2⊕b1⊕b3⊕b4;G3=P2⊕b2⊕b3⊕b4;得到的G1G2G3的值就是出错位的二进制码序号,如G1G2G2=001,说明出错位的码序号是1。