資源描述：
《crc 校驗(yàn)碼的計算方法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、CRC校驗(yàn)碼的計算方法CRC從原理到實(shí)現(xiàn)===============作者：SparkHuang(hcpp@263.net)日期：2004/12/8摘要：CRC(CyclicRedundancyCheck)被廣泛用于數(shù)據(jù)通信過程中的差錯檢測，具有很強(qiáng)的檢錯能力。本文詳細(xì)介紹了CRC的基本原理，并且按照解釋通行的查表算法的由來的思路介紹了各種具體的實(shí)現(xiàn)方法。1.差錯檢測數(shù)據(jù)通信中，接收端需要檢測在傳輸過程中是否發(fā)生差錯，常用的技術(shù)有奇偶校驗(yàn)(ParityCheck)，校驗(yàn)和(Checksum)和CRC(CyclicRedunda
2、ncyCheck)。它們都是發(fā)送端對消息按照某種算法計算出校驗(yàn)碼，然后將校驗(yàn)碼和消息一起發(fā)送到接收端。接收端對接收到的消息按照相同算法得出校驗(yàn)碼，再與接收到的校驗(yàn)碼比較，以判斷接收到消息是否正確。奇偶校驗(yàn)只需要1位校驗(yàn)碼，其計算方法也很簡單。以奇檢驗(yàn)為例，發(fā)送端只需要對所有消息位進(jìn)行異或運(yùn)算，得出的值如果是0，則校驗(yàn)碼為1，否則為0。接收端可以對消息進(jìn)行相同計算，然后比較校驗(yàn)碼。也可以對消息連同校驗(yàn)碼一起計算，若值是0則有差錯，否則校驗(yàn)通過。通常說奇偶校驗(yàn)可以檢測出1位差錯，實(shí)際上它可以檢測出任何奇數(shù)位差錯。校驗(yàn)和的思想也很簡
3、單，將傳輸?shù)南?dāng)成8位(或16/32位)整數(shù)的序列，將這些整數(shù)加起來而得出校驗(yàn)碼，該校驗(yàn)碼也叫校驗(yàn)和。校驗(yàn)和被用在IP協(xié)議中，按照16位整數(shù)運(yùn)算，而且其MSB(MostSignificantBit)的進(jìn)位被加到結(jié)果中。顯然，奇偶校驗(yàn)和校驗(yàn)和都有明顯的不足。奇偶校驗(yàn)不能檢測出偶數(shù)位差錯。對于校驗(yàn)和，如果整數(shù)序列中有兩個整數(shù)出錯，一個增加了一定的值，另一個減小了相同的值，這種差錯就檢測不出來。2.CRC算法的基本原理-------------------CRC算法的是以GF(2)(2元素伽羅瓦域)多項(xiàng)式算術(shù)為數(shù)學(xué)基礎(chǔ)的，聽起來很
4、恐怖，但實(shí)際上它的主要特點(diǎn)和運(yùn)算規(guī)則是很好理解的。GF(2)多項(xiàng)式中只有一個變量x，其系數(shù)也只有0和1，如：???1*x^7+0*x^6+1*x^5+0*x^4+0*x^3+1*x^2+1*x^1+1*x^0即：???x^7+x^5+x^2?+x+1(x^n表示x的n次冪)???GF(2)多項(xiàng)式中的加減用模2算術(shù)執(zhí)行對應(yīng)項(xiàng)上系數(shù)的加減，模2就是加減時不考慮進(jìn)位和借位，即：???0+0=0???0-0=0???0+1=1???0-1=1???1+0=1???1-0=1???1+1=0???1-1=0顯然，加和減是一樣的效果(故在
5、GF(2)多項(xiàng)式中一般不出現(xiàn)"-"號)，都等同于異或運(yùn)算。例如P1=x^3?+x^2+1，P2=x^3?+x^1+1，P1+P2為：???x^3?+x^2 +1?+x^3???????+x+1???------------------??????????x^2+xGF(2)多項(xiàng)式乘法和一般多項(xiàng)式乘法基本一樣，只是在各項(xiàng)相加的時候按模2算術(shù)進(jìn)行，例如P1*P2為：???(x^3+x^2+1)(x^3+x^1+1)???=(x^6+x^4+x^3????+x^5+x^3+x^2????+x^3+x+1)???=x^6+x^5+x
6、^4+x^3+x^2+x+1GF(2)多項(xiàng)式除法也和一般多項(xiàng)式除法基本一樣，只是在各項(xiàng)相減的時候按模2算術(shù)進(jìn)行，例如P3=x^7+x^6+x^5+x^2+x，P3/P2為：??????????????????????????????????????x^4+x^3??????????+1???????????????????------------------------------------------?????????????x^3+x+1)x^7+x^6+x^5+????????????x^2+x????????????
7、????????x^7??????+x^5+x^4????????????????????---------------------??????????????????????????x^6??????+x^4??????????????????????????x^6??????+x^4+x^3??????????????????????????---------------------????????????????????????????????????????????x^3+x^2+x??????????????????
8、??????????????????????????x^3??????+x+1????????????????????????????????????????????-----------------??????????????????????????????????????
