奇偶校验码、海明校验码和循环冗余校验码（CRC）

1、奇偶校验码、海明校验码和循环冗余校验码（CRC ）奇偶校验码是 奇校验码 和 偶校验码 的统称.它们都是通过在要校验的编码上加位校验位组成.如果是 奇校验 加上校验位后,编码中1的个数为 奇数个如果是 偶校验 加上校验位后,编码中1的个数为 偶数个平奇偶校验是将若字符组成个信息块，对该信息块的字符中对应的位分别进奇偶校验，下表给出了平奇偶校验例。例:原编码 奇校验 偶校验0000 0000 1 0000 00010 0010 0 0010 11100 1100 1 1100 01010 1010 1 1010 0如果发 奇数 个位传输出错,那么编码中1的个数就会发变化.从校验出错误.要求从新传

2、输数据.前应的 奇偶校验码 有3种.平奇偶校验码对每个数据的编码添加校验位,使信息位与校验位处于同.垂直奇偶校验码把数据分成若组,组数据排成,再加校验码.针对每列采 奇校验 或 偶校验例:有32位数据10100101 00110110 11001100 10101011垂直奇校验 垂直偶校验数据 10100101 1010010100110110 0011011011001100 1100110010101011 10101011校验为00001011 11110100平垂直奇偶校验码就是同时平校验和垂直校验例:奇校验 奇平 偶校验 偶平数据 10100101 1 10100101 00011

3、0110 1 00110110 011001100 1 11001100 010101011 0 10101011 1校验 00001011 0 11110100 1然后是 海明校验码海明码也是利奇偶性来校验数据的.它是种多重奇偶校验检错系统,它通过在数据位之间插k个校验位,来扩码距,从实现检错和纠错.设原来数据有n位,要加k位校验码.怎么确定k的呢?k个校验位可以有pow(2,k)(代表2的k次)个编码,其中有个代表是否出错.剩下pow(2,k)-1个编码则来表到底是哪位出错.因为n个数据位和k个校验位都可能出错所以k满 pow(2,k)-1 = n+k设 k个校验码为 P1,P2Pk, n

4、个数据位为D0,D1Dn产的海明码为 H1,H2H(n+k)如有8个数据位,根据pow(2,k)-1 = n+k可以知道k最是4那么得到的海明码是H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1D7 D6 D5 D4 P4 D3 D2 D1 P3 D0 P2 P1然后怎么知道Pi校验哪个位呢.可以列个校验关系表海明码 下标 校验位组H1(P1) 1 P1H2(P2) 2 P2H3(D0) 1+2 P1,P2H4(P3) 4 P3H5(D1) 1+4 P1,P2H6(D2) 2+4 P2,P3H7(D3) 1+2+4 P1,P2,P3H8(P4) 8 P4H9(D4)

5、 1+8 P1,P4H10(D5) 2+8 P2,P4H11(D6) 1+2+8 P1,P2,P4H12(D7) 4+8 P3,P4从表中可以看出P1校验 P1,D0,D1,D3,D4,D6P2校验 P2,D0,D2,D3,D5,D6P3校验 P3,D1,D2,D3,D7P4校验 P4,D4,D5,D6,D7其实上表很有规律很容易记要知道海明码Hi由哪些校验组校验可以把i化成 进制数 数中哪些位k是1,就有哪些Pk校验如H7 7=0111 所以由P1,P2,P3H11 11=1011 所以由P1,P2,P4H3 3=0011 所以由P1,P2那看看Pi的值怎么确定如果使偶校验,则P1=D0 x

6、or D1 xor D3 xor D4 xor D6P2=D0 xor D2 xor D3 xor D5 xor D6P3=D1 xor D2 xor D3 xor D7P4=D4 xor D5 xor D6 xor D7其中xor是异或运算奇校验的话把偶校验的值取反即可.那怎么校验错误呢.其实也很简单.先做下运算.G1 = P1 xor D0 xor D1 xor D3 xor D4 xor D6G2 = P2 xor D0 xor D2 xor D3 xor D5 xor D6G3 = P3 xor D1 xor D2 xor D3 xor D7G4 = P4 xor D4 xor D5

7、xor D6 xor D7如果偶校验那么 G4G3G2G1 全为0是表错误(奇校验全为1)当不全为0表有错 G4G3G2G1 的进制值代表出错的位.如 G4G3G2G1 =1010 表H10(D5)出错了.把它求反就可以纠正错误了.下举个较完全的例:设数据为01101001,试4个校验位求其偶校验式的海明码.传输后数据为011101001101,是否有错?P1=D0 xor D1 xor D3 xor D4 xor D6=1 xor 0 xor 1 xor 0 xor 1=1P2=D0 xor D2 xor D3 xor D5 xor D6=1 xor 0 xor 1 xor 1 xor 1=

8、0P3=D1 xor D2 xor D3 xor D7=0 xor 0 xor 1 xor 0=1P4=D4 xor D5 xor D6 xor D7=0 xor 1 xor 1 xor 0=0所以得到的海明码为0 1 1 0 0 1 0 0 1 1 0 1传输后为011101001101G1 = P1 xor D0 xor D1 xor D3 xor D4 xor D6=1G2 = P2 xor D0 xor D2 xor D3 xor D5 xor D6=0G3 = P3 xor D1 xor D2 xor D3 xor D7=0G4 = P4 xor D4 xor D5 xor D6 x

9、or D7=1所以1001代表9即H9出错了,对它求反011001001101 和我们算的样.由此可见 海明码 不但有检错还有纠错能下说下最后种 CRC即 循环冗余校验码CRC码利成多项式为k个数据位产r个校验位进编码,其编码长度为n=k+r所以称 (n,k)码.CRC码泛应于数据通信领域和磁介质存储系统中.CRC理论常复杂,般书就给个例题,讲讲法.现在简单介绍下它的原理:在k位信息码后接r位校验码,对于个给定的(n,k)码可以证明(数学琢磨证明过程)存在个最次幂为 n-k=r 的多项式g(x)根据g(x)可以成k位信息的校验码,g(x)被称为 成多项式C(x)=C(k-1)C(k-2)C0表

10、k个信息位把C(x)左移r位,就是相当于 C(x)*pow(2,r)给校验位空出r个位来了.给定个 成多项式g(x),可以求出个校验位表达式r(x)C(x)*pow(2,r) / g(x) = q(x) + r(x)/g(x)C(x)*pow(2,r)去除成多项式g(x)商为q(x)余数是r(x)所以有C(x)*pow(2,r) = q(x)*g(x) + r(x)C(x)*pow(2,r) + r(x)就是所求的n位CRC码,由上式可以看出它是成多项式g(x)的倍式.所以如果得到的n位CRC码去除g(x)如果余数是0,就证明数据正确.否则可以根据余数知道 出错位 .在CRC运算过程中,四则运

11、算采 mod 2运算(后介绍),即不考虑进位和借位.所以上式等价于C(x)*pow(2,r) + r(x) = q(x)*g(x)继续前先说下基本概念吧.1.多项式和进制编码x的最次幂位对应进制数的最位.以下各位对应多项式的各幂次.有此幂次项为1,为0.x的最幂次为r时,对应的进制数有r+1位例如g(x)=pow(x,4) + pow(x,3) + x + 1对应进制编码是 110112.成多项式是发送和接受的个约定,也是个进制数,在整个传输过程中,这个数不会变.在发送,利 成多项式 对信息多项式做 模2运算 成校验码.在接受利 成多项式 对收到的 编码多项式 做 模2运算 校验和纠错.成多项

12、式应满:a.成多项式的最位和最低位必须为1b.当信息任何位发错误时,被成多项式模2运算后应该使余数不为0c.不同位发错误时,应该使余数不同.d.对余数继续做模2除,应使余数循环.成多项式很复杂不过不我们成下给出些常的成多项式表N K 码距d G(x)多项式 G(x)7 4 3 x3+x+1 10117 4 3 x3+x2+1 11017 3 4 x4+x3+x2+1 111017 3 4 x4+x2+x+1 1011115 11 3 x4+x+1 1001115 7 5 x8+x7+x6+x4+1 11101000131 26 3 x5+x2+1 10010131 21 5 x10+x9+x8

13、+x6+x5+x3+1 1110110100163 57 3 x6+x+1 100001163 51 5 x12+x10+x5+x4+x2+1 10100001101011041 1024 x16+x15+x2+1 110000000000001013.模2运算a.加减法法则0 +/- 0 = 00 +/- 1 = 11 +/- 0 = 11 +/- 1 = 0注意:没有进位和借位b.乘法法则利模2加求部分积之和,没有进位c.除法法则利模2减求部分余数没有借位每商1位则部分余数减1位余数最位是1就商1,不是就商0当部分余数的位数于余数时,该余数就是最后余数.例 11101011)1100000

14、101111101011101010110010(每商1位则部分余数减1位,所以前两个0写出)0000010(当部分余数的位数于余数时,该余数就是最后余数)最后商是1110余数是010好了说了那么多没的理论.下讲下CRC的实际应例:给定的成多项式g(x)=1011,(7,4)CRC码对C(x)=1010进编码.由题可以知道下列的信息:C(x)=1010,n=7,k=4,r=3,g(x)=1011C(x)*pow(2,3)=1010000C(x)*pow(2,3) / g(x) = 1001 + 011/1011所以r(x)=011所以要求的编码为1010011例2:上题中,数据传输后变为1000011,试纠错机制纠错.1000011 / g(x) = 1011 + 110/1011不能整除,所以出错了.因为余数是110查1011出错位表可以知道是第5位出错.对其求反即可.循环冗余校验码CRC（Cyclic Redundancy Code）采种多项式的编码法。把要发送的数据位串看成是系数只能为“1”或为“0”的多项式。个k位的数据块可以看成Xk-1到X0的k项多项式的系数序列。例如，“110001”有6位，表多项式是“X5 +X4+