奇偶校驗碼、海明校驗碼和循環(huán)冗余校驗碼（CRC）

1、奇偶校驗碼、海明校驗碼和循環(huán)冗余校驗碼（CRC ）奇偶校驗碼是 奇校驗碼 和 偶校驗碼 的統(tǒng)稱.它們都是通過在要校驗的編碼上加位校驗位組成.如果是 奇校驗 加上校驗位后,編碼中1的個數(shù)為 奇數(shù)個如果是 偶校驗 加上校驗位后,編碼中1的個數(shù)為 偶數(shù)個平奇偶校驗是將若字符組成個信息塊，對該信息塊的字符中對應的位分別進奇偶校驗，下表給出了平奇偶校驗例。例:原編碼 奇校驗 偶校驗0000 0000 1 0000 00010 0010 0 0010 11100 1100 1 1100 01010 1010 1 1010 0如果發(fā) 奇數(shù) 個位傳輸出錯,那么編碼中1的個數(shù)就會發(fā)變化.從校驗出錯誤.要求從新傳

2、輸數(shù)據.前應的 奇偶校驗碼 有3種.平奇偶校驗碼對每個數(shù)據的編碼添加校驗位,使信息位與校驗位處于同.垂直奇偶校驗碼把數(shù)據分成若組,組數(shù)據排成,再加校驗碼.針對每列采 奇校驗 或 偶校驗例:有32位數(shù)據10100101 00110110 11001100 10101011垂直奇校驗 垂直偶校驗數(shù)據 10100101 1010010100110110 0011011011001100 1100110010101011 10101011校驗為00001011 11110100平垂直奇偶校驗碼就是同時平校驗和垂直校驗例:奇校驗 奇平 偶校驗 偶平數(shù)據 10100101 1 10100101 00011

3、0110 1 00110110 011001100 1 11001100 010101011 0 10101011 1校驗 00001011 0 11110100 1然后是 海明校驗碼海明碼也是利奇偶性來校驗數(shù)據的.它是種多重奇偶校驗檢錯系統(tǒng),它通過在數(shù)據位之間插k個校驗位,來擴碼距,從實現(xiàn)檢錯和糾錯.設原來數(shù)據有n位,要加k位校驗碼.怎么確定k的呢?k個校驗位可以有pow(2,k)(代表2的k次)個編碼,其中有個代表是否出錯.剩下pow(2,k)-1個編碼則來表到底是哪位出錯.因為n個數(shù)據位和k個校驗位都可能出錯所以k滿 pow(2,k)-1 = n+k設 k個校驗碼為 P1,P2Pk, n

4、個數(shù)據位為D0,D1Dn產的海明碼為 H1,H2H(n+k)如有8個數(shù)據位,根據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其實上表很有規(guī)律很容易記要知道海明碼Hi由哪些校驗組校驗可以把i化成 進制數(shù) 數(shù)中哪些位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)出錯了.把它求反就可以糾正錯誤了.下舉個較完全的例:設數(shù)據為01101001,試4個校驗位求其偶校驗式的海明碼.傳輸后數(shù)據為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即 循環(huán)冗余校驗碼CRC碼利成多項式為k個數(shù)據位產r個校驗位進編碼,其編碼長度為n=k+r所以稱 (n,k)碼.CRC碼泛應于數(shù)據通信領域和磁介質存儲系統(tǒng)中.CRC理論常復雜,般書就給個例題,講講法.現(xiàn)在簡單介紹下它的原理:在k位信息碼后接r位校驗碼,對于個給定的(n,k)碼可以證明(數(shù)學琢磨證明過程)存在個最次冪為 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)余數(shù)是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)如果余數(shù)是0,就證明數(shù)據正確.否則可以根據余數(shù)知道 出錯位 .在CRC運算過程中,四則運

11、算采 mod 2運算(后介紹),即不考慮進位和借位.所以上式等價于C(x)*pow(2,r) + r(x) = q(x)*g(x)繼續(xù)前先說下基本概念吧.1.多項式和進制編碼x的最次冪位對應進制數(shù)的最位.以下各位對應多項式的各冪次.有此冪次項為1,為0.x的最冪次為r時,對應的進制數(shù)有r+1位例如g(x)=pow(x,4) + pow(x,3) + x + 1對應進制編碼是 110112.成多項式是發(fā)送和接受的個約定,也是個進制數(shù),在整個傳輸過程中,這個數(shù)不會變.在發(fā)送,利 成多項式 對信息多項式做 模2運算 成校驗碼.在接受利 成多項式 對收到的 編碼多項式 做 模2運算 校驗和糾錯.成多項

12、式應滿:a.成多項式的最位和最低位必須為1b.當信息任何位發(fā)錯誤時,被成多項式模2運算后應該使余數(shù)不為0c.不同位發(fā)錯誤時,應該使余數(shù)不同.d.對余數(shù)繼續(xù)做模2除,應使余數(shù)循環(huán).成多項式很復雜不過不我們成下給出些常的成多項式表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減求部分余數(shù)沒有借位每商1位則部分余數(shù)減1位余數(shù)最位是1就商1,不是就商0當部分余數(shù)的位數(shù)于余數(shù)時,該余數(shù)就是最后余數(shù).例 11101011)1100000

14、101111101011101010110010(每商1位則部分余數(shù)減1位,所以前兩個0寫出)0000010(當部分余數(shù)的位數(shù)于余數(shù)時,該余數(shù)就是最后余數(shù))最后商是1110余數(shù)是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:上題中,數(shù)據傳輸后變?yōu)?000011,試糾錯機制糾錯.1000011 / g(x) = 1011 + 110/1011不能整除,所以出錯了.因為余數(shù)是110查1011出錯位表可以知道是第5位出錯.對其求反即可.循環(huán)冗余校驗碼CRC（Cyclic Redundancy Code）采種多項式的編碼法。把要發(fā)送的數(shù)據位串看成是系數(shù)只能為“1”或為“0”的多項式。個k位的數(shù)據塊可以看成Xk-1到X0的k項多項式的系數(shù)序列。例如，“110001”有6位，表多項式是“X5 +X4+