海明 校驗(yàn) 碼常用 校驗(yàn) 碼 奇偶 校驗(yàn) 碼、海明 校驗(yàn) 碼、CRC 校驗(yàn) 碼

《海明 校驗(yàn) 碼常用 校驗(yàn) 碼 奇偶 校驗(yàn) 碼、海明 校驗(yàn) 碼、CRC 校驗(yàn) 碼》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、海明校驗(yàn)碼常用校驗(yàn)碼奇偶校驗(yàn)碼、海明校驗(yàn)碼、CRC校驗(yàn)碼版權(quán)聲明:轉(zhuǎn)載時(shí)請以超鏈接形式標(biāo)明文章原始出處和作者信息及本聲明海明校驗(yàn)碼常用校驗(yàn)碼(奇偶校驗(yàn)碼、海明校驗(yàn)碼、CRC校驗(yàn)碼)計(jì)算機(jī)系統(tǒng)運(yùn)行時(shí),各個(gè)部之間要進(jìn)行數(shù)據(jù)交換.為確保數(shù)據(jù)在傳送過程正確無誤,常使用檢驗(yàn)碼.我們常使用的檢驗(yàn)碼有三種.分別是奇偶校驗(yàn)碼、海明校驗(yàn)碼和循環(huán)冗余校驗(yàn)碼(CRC)。奇偶校驗(yàn)碼奇偶校驗(yàn)碼最簡單,但只能檢測出奇數(shù)位出錯(cuò).如果發(fā)生偶數(shù)位錯(cuò)誤就無法檢測.但經(jīng)研究是奇數(shù)位發(fā)生錯(cuò)誤的概率大很多.而且奇偶校驗(yàn)碼無法檢測出哪位出錯(cuò).所以屬于無法矯正錯(cuò)誤的校驗(yàn)碼。奇偶校驗(yàn)碼是奇校驗(yàn)碼和偶校驗(yàn)碼的統(tǒng)稱.它

2、們都是通過在要校驗(yàn)的編碼上加一位校驗(yàn)位組成.如果是奇校驗(yàn)加上校驗(yàn)位后,編碼中1的個(gè)數(shù)為奇數(shù)個(gè)。如果是偶校驗(yàn)加上校驗(yàn)位后,編碼中1的個(gè)數(shù)為偶數(shù)個(gè)。例:原編碼奇校驗(yàn)偶校驗(yàn)00000000100000001000100001011100110011100010101010110100如果發(fā)生奇數(shù)個(gè)位傳輸出錯(cuò),那么編碼中1的個(gè)數(shù)就會(huì)發(fā)生變化.從而校驗(yàn)出錯(cuò)誤，要求從新傳輸數(shù)據(jù)。目前應(yīng)用的奇偶校驗(yàn)碼有3種.水平奇偶校驗(yàn)碼對每一個(gè)數(shù)據(jù)的編碼添加校驗(yàn)位,使信息位與校驗(yàn)位處于同一行.垂直奇偶校驗(yàn)碼把數(shù)據(jù)分成若干組,一組數(shù)據(jù)排成一行,再加一行校驗(yàn)碼.針對每一行列采用奇校驗(yàn)或偶校驗(yàn)例:有3

3、2位數(shù)據(jù)10100101001101101100110010101011垂直奇校驗(yàn)垂直偶校驗(yàn)數(shù)據(jù)1010010110100101001101100011011011001100110011001010101110101011校驗(yàn)0000101111110100水平垂直奇偶校驗(yàn)碼就是同時(shí)用水平校驗(yàn)和垂直校驗(yàn)例:奇校驗(yàn)奇水平偶校驗(yàn)偶水平數(shù)據(jù)101001011101001010001101101001101100110011001110011000101010110101010111校驗(yàn)000010110111101001海明校驗(yàn)碼海明碼也是利用奇偶性來校驗(yàn)數(shù)據(jù)的.它是一種

4、多重奇偶校驗(yàn)檢錯(cuò)系統(tǒng),它通過在數(shù)據(jù)位之間插入k個(gè)校驗(yàn)位,來擴(kuò)大碼距,從而實(shí)現(xiàn)檢錯(cuò)和糾錯(cuò).設(shè)原來數(shù)據(jù)有n位,要加入k位校驗(yàn)碼.怎么確定k的大小呢?k個(gè)校驗(yàn)位可以有pow(2,k)(代表2的k次方)個(gè)編碼,其中有一個(gè)代表是否出錯(cuò).剩下pow(2,k)-1個(gè)編碼則用來表示到底是哪一位出錯(cuò).因?yàn)閚個(gè)數(shù)據(jù)位和k個(gè)校驗(yàn)位都可能出錯(cuò)，所以k滿足pow(2,k)-1=n+k。設(shè)k個(gè)校驗(yàn)碼為P1,P2.Pk,n個(gè)數(shù)據(jù)位為D0,D1.Dn產(chǎn)生的海明碼為H1,H2.H(n+k)。如有8個(gè)數(shù)據(jù)位,根據(jù)pow(2,k)-1=n+k可以知道k最小是4。那么得到的海明碼是:H12H11H10H9H

5、8H7H6H5H4H3H2H1D7D6D5D4P4D3D2D1P3D0P2P1然后怎么知道Pi校驗(yàn)?zāi)膫€(gè)位呢.自己可以列個(gè)校驗(yàn)關(guān)系表海明碼下標(biāo)校驗(yàn)位組H1(P1)1P1H2(P2)2P2H3(D0)1+2P1,P2H4(P3)4P3H5(D1)1+4P1,P2H6(D2)2+4P2,P3H7(D3)1+2+4P1,P2,P3H8(P4)8P4H9(D4)1+8P1,P4H10(D5)2+8P2,P4H11(D6)1+2+8P1,P2,P4H12(D7)4+8P3,P4從表中可以看出P1校驗(yàn)P1,D0,D1,D3,D4,D6P2校驗(yàn)P2,D0,D1,D2,D3,D5,D6

6、P3校驗(yàn)P3,D2,D3,D7P4校驗(yàn)P4,D4,D5,D6,D7其實(shí)上表很有規(guī)律很容易記，要知道海明碼Hi由哪些校驗(yàn)組校驗(yàn)，可以把i化成二進(jìn)制數(shù)數(shù)中哪些位k是1,就有哪些Pk校驗(yàn)如H77=0111所以由P1,P2,P3H1111=1011所以由P1,P2,P4H33=0011所以由P1,P2那看看Pi的值怎么確定，如果使用偶校驗(yàn),則P1=D0xorD1xorD3xorD4xorD6P2=D0xorD1xorD2xorD3xorD5xorD6P3=D1xorD2xorD3xorD7P4=D4xorD5xorD6xorD7其中xor是異或運(yùn)算，奇校驗(yàn)的話把偶校驗(yàn)的值取反

7、即可.那怎么校驗(yàn)錯(cuò)誤呢.其實(shí)也很簡單.先做下面運(yùn)算.G1=P1xorD0xorD1xorD3xorD4xorD6G2=P2xorD0xorD1xorD2xorD3xorD5xorD6G3=P3xorD1xorD2xorD3xorD7G4=P4xorD4xorD5xorD6xorD7循環(huán)冗余校驗(yàn)碼CRC碼利用生成多項(xiàng)式為k個(gè)數(shù)據(jù)位產(chǎn)生r個(gè)校驗(yàn)位進(jìn)行編碼,其編碼長度為n=k+r所以又稱(n,k)碼.CRC碼廣泛應(yīng)用于數(shù)據(jù)通信領(lǐng)域和磁介質(zhì)存儲(chǔ)系統(tǒng)中.CRC理論非常復(fù)雜,一般書就給個(gè)例題,講講方法.現(xiàn)在簡單介紹下它的原理:在k位信息碼后接r位校驗(yàn)碼,對于一個(gè)