汉明纠错码.pptxVIP

纠错码 之汉明码 什么是汉明码 汉明码是一种可以有多个校验位，能够检测并纠正一位错误代码的纠错码。汉明码编码时，将要传递的信息分为几组，每组都有一位校验位，接收信息后，通过特定的方法检测出出错的位置并取反加以纠正。汉明码之所以能够纠错，是因为汉明码是一个多重校验码，也就是码字中的信息码位同时被多个校验码进行校验，通过这些码位对不同校验码的联动影响最终可以找出是哪一位出错了。 编码译码方法 1.计算校验位数 2.确定校验码位置 3.确定校验码 4.汉明码的校验与纠错 1.计算校验位数 汉明码编码时首先要确定编码所需的校验码位数。对于有N个有效信息位的信息，假设它需要添加r个校验位，则有以下关系式存在：N+r≤2r,满足此不等式的最小r即为需要的校验位数。 2.确定校验码位置 汉明码编码的第二步就是确定出校验码的位置。确定规则为：校验码必须在2n位置，而有效信息码的分布则是在除2n以外的其他位置。即，1,2,4,8等位置是校验码位置，而3,5,6,7,9,10等位置是有效信息码的位置。 3.确定校验码 校验码根据采用奇校验还是偶校验而不同。总的原则是：第k个校验码从当前位开始，每次连续校验k位后再跳过k位，然后再连续校验k位，再跳过k位，依此类推。最后根据所采用的是偶校验还是奇校验即可得出第i位校验码的值。 4.汉明码的校验与纠错 汉明码中所有信息码位均被至少两个校验码进行了校验，也就是至少校验了两次。其校验的方式是将各校验码对它所校验的位组进行“异或运算” ，也就是第3步中每个pi值校验的位。 若以pi(i=1,2,3···)表示校验码，bi(i=1,2,3···)表示信息码。 校验公式 G1=p1⊕b1⊕b2⊕b4⊕b5⊕…… G2=p2⊕b1⊕b3⊕b4⊕b6⊕b7⊕b10⊕b11⊕…… G3= p3⊕b2⊕b3⊕b4⊕b8⊕b9⊕b10⊕b11⊕…… G4= p4⊕b5⊕b6⊕b7⊕b8⊕b9⊕b10⊕b11⊕…… G5= p5⊕b12⊕b13⊕b14⊕b15⊕b16⊕b17⊕b18⊕b19⊕b20⊕b21⊕b11⊕b23⊕b24⊕b25⊕b26⊕…… 若采用偶校验 若整个码字不发生差错，在采用偶校验时，各校验组通过异或运算后的校验结果均应该是为0，亦即G1、G2、G3、G4等值均为0，因为此时1为偶数个，进行异或运算后就是0。 若出错，按照GnGn-1···G2G1的顺序排列出来（二进制），将二进制数转化为十进制数，对应的十进制数值即为发生错误的位。 若采用奇校验 若整个码字不发生差错，在采用奇校验时，各校验组通过异或运算后的校验结果均应该是为1，亦即G1、G2、G3、G4等值均为1，因为此时1为奇数个，进行异或运算后就是1。 若出错，先将GnGn-1···G2G1按位取反得到Gn’Gn-1’···G2’G1’，再按照Gn’Gn-1’···G2’G1’的顺序排列出来（二进制），将二进制数转化为十进制数，对应的十进制数值即为发生错误的位。 下面举一个例子进行说明 对于一个8位二进制信由8+r≤2r得r应取4。 编码 偶校验：采用偶校验时，由p1,1,0，0，0,0应有偶数个1，故p1为1；由p2,1,1,0,1,0应有偶数个1，故p2应为1；由p3,0,1,0, 1应有偶数个1，故p3应为0；由p4,0,1,0,1应有偶数个1，故p4应为0。故编码结果为111001000101。 奇校验：采用奇校验时，由p1,1,0，0，0,0应有奇数个1，故p1为0；由p2,1,1,0,1,0应有奇数个1，故p2应为0；由p3,0,1,0,1应有奇数个1，故p3应为1；由p4,0,1,0,1应有奇数个1，故p4应为1。故编码结果为001101010101。 检测与纠错：假设第二位发生错误 偶校验：采用偶校验时，接收的为101001000101。G1= 1⊕1⊕0⊕0⊕0⊕0=0；G2= 0⊕1⊕1⊕0⊕1⊕0=1；G3= 1⊕0⊕1⊕1⊕0⊕1=0；G4= 0⊕0⊕1⊕0⊕1=0；G4G3G2G1=0010，十进制数为2，故第二位出错，将第二位取反得到1。 奇校验：采用奇校验时，接收的为011101010101。G1= 0⊕1⊕0⊕0⊕1⊕1=1；G2= 1⊕1⊕1⊕0⊕1⊕0=0；G3= 0⊕0⊕1⊕1⊕0⊕1=1；G4= 1⊕0⊕1⊕0⊕1=1；G4G3G2G1=1101，按位取反得到0010，十进制数为2，故第二位出错，将第二位取反得到1。