海明校验

海明校验 ①海明校验的基本思想 将有效信息按某种规律分成若干组，每组安排一个校验位，做奇偶测试，就能提供多位检错信息，以指出最大可能是哪位出错，从而将其纠正。实质上，海明校验是一种多重校验。 ②海明校验的特点 它不仅具有检测错误的能力，同时还具有给出错误所在准确位置的能力。 一．校验位的位数 校验位的位数与有效信息的长度有关 设:N--为校验码的位数 K--是有效信息位 r--校验位（分成r组作奇偶校验，能产生r位检错信息） 海明码应满足 N=K＋r≤2r－1 若r=3 则N=K＋r≤7 所以K≤4   二．分组原则` 在海明码中， 位号数（1、2、3、……、n）为2的权值的那些位，即： 1(20)、2(21)、4(22)、8(23)、…2r-1位，作为奇偶校验位 并记作: P1、P2、P3 、P4、…Pr，余下各位则为有效信息位。 例如： N=11 K=7 r=4 相应海明码可示意为 位号   1  2   3   4   5   6   7   8   9   10   11 P占位 P1 P2 × P3 × × × P4   ×   ×   × 其中×均为有效信息，海明码中的每一位分别被P1P2P3P4… Pr 中的一至若干位所校验，其规律是： 第i位由校验位位号之和等于i的那些校验位所校验 如：海明码的位号为3，它被P1P2（位号分别为1,2）所校验 海明码的位号为5，它被P1P3（位号分别为1,4）所校验 归并起来: 形成了4个小组，每个小组一个校验位，校验位的取值，仍采用奇偶校验方式确定。 如表 2·6 、表2·7所示：      三．编码、查错、纠错原理 以4位有效信息(b1、b2、b3、b4)和3位校验位(P1、P2、P3)为例: K=4 r=3 海明序号 1   2   3   4   5   6   7 海明码     P1 P2 b1 P3 b2 b3 b4 根据表2-8可以看到 （1）每个小组只有一位校验位，第一组是P1、第二组是P2、第三组是P3。 （2）每个校验位校验着它本身和它后面的一些确定位。    1.编码原理（采用偶校验） 1)若有效信息b1b2b3b4=1011 先将它们分别填入第3、5、6、7位 2)再分组进行奇偶统计，分别填入校验位P1、P2、P3的值 如：第一组有：P1b1b2b4 因b1b2b4含偶数个1，故P1应取值为0       第二组有：P2b1b3b4 因b1b3b4含奇数个1，故P2应取值为1       第三组有：P3b2b3b4 因b2b3b4含偶数个1，故P3应取值为0       海明编码为:P1P2b1P3b2b3b4=0110011 2.查错与纠错 因为分三组校验，每组产生一位检错信息、3组共3位检错信息，便构成一个指误字，上例指误字由G1G2G3组成。 其中： G3=P3⊕b2⊕b3⊕b4              P3b2b3b4=0011 G2=P2⊕b1⊕b3⊕b4             P2b1b3b4=1111 G1=P1⊕b1⊕b2⊕b4            P1b1b2b4=0101 采用偶校验，在没有出错情况下G1G2G3=000。由于在分组时，就确定了每一位参加校验的组别,所以指误字能准确地指出错误所在位。 如：若第3位b1出错，由于b1参加了第一组和第二组的校验，必然破坏了第一组和第二组的偶性，从而使G1和G2为1。 因为b1未参加第三组校验，故G3=0，所以构成的指误字G3G2G1=011它指出第3位出错。 反之：若G3G2G1=111 则说明海明码第7位b4出错。因为只有第7位b4参加了3个小组的校验，破坏了三个小组的偶性。 假定： 源部件发送海明码为：0110011 接收端接收海明码为：0110011 则: 三个小组都满足偶校验，这时G3G2G1=000，表明收到信息正确，可以从中提出有效信息1011参与运算处理。 纠错：若接收端收到的海明码为0110111，分组检测后指误字G3G2G1=101，它指出第5位出错，则只须将第5位变反，就可还原成正确的数码0110011。