Hamming编码.doc

? 2.6.2海明校验海明校验的基本思想将有效信息按某种规律分成若干组，每组安排一个校验位，做奇偶测试，就能提供多位检错信息，以指出最大可能是哪位出错，从而将其纠正。实质上，海明校验是一种多重校验。海明校验的特点它不仅具有检测错误的能力，同时还具有给出错误所在准确位置的能力。 校验位的位数 校验位的位数与有效信息的长度有关 设: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 ? 11P占位 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=P3b2⊕b3⊕b4? ? ? ? ? ? ? P3b2b3b4=0011G2=P2⊕b1⊕b3⊕b4 ? ? ? ? ? ? P2b1b3b4=1111G1=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。