CRC16算法原理

1、CRC算法及C實(shí)現(xiàn)學(xué)習(xí)體會(huì)2008-09-20 15:21:13 閱讀161評(píng)論0 字號(hào)：大中小訂閱一、CRC算法原理CRC校驗(yàn)的基本思想是利用線性編碼理論，在發(fā)送端根據(jù)要傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個(gè)校 驗(yàn)用的監(jiān)督碼(既CRC碼)r位，并附在信息后邊，構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)共 (k+r) 位, 最后發(fā)送岀去。在接收端，則根據(jù)信息碼和 CRC碼之間所遵循的規(guī)則進(jìn)行檢驗(yàn)，以確定傳送中是否岀錯(cuò)。16位的CRC碼產(chǎn)生的規(guī)則是先將要發(fā)送的二進(jìn)制序列數(shù)左移16位(既乘以)后，再除以一個(gè)多項(xiàng)式，最后所得到的余數(shù)既是 CRC碼。假設(shè)數(shù)據(jù)傳輸過(guò)程中需要發(fā)送15位的二進(jìn)制信息g=1010011

2、10100001，這串二進(jìn)制碼可表示為代數(shù)多項(xiàng)式g(x) = xA14 + xA12 + xA9 + xA8 + xA7 + xA5 + 1，其中g(shù)中第k位的值，對(duì)應(yīng) g(x)中xAk的系數(shù)。將g(x)乘以xAm,既將g后加m個(gè)0,然后除以m階多項(xiàng)式h(x)，得到的(m-1)階余項(xiàng)r(x)對(duì)應(yīng)的二進(jìn)制碼r就是CRC編碼。h(x)可以自由選擇或者使用國(guó)際通行標(biāo)準(zhǔn)，一般按照h(x)的階數(shù)m將CRC算法稱為CRC-m比如CRC-32CRC-64 等。國(guó)際通行標(biāo)準(zhǔn)可以參看/wiki/Cyclic_redundancy_checkg(x)和h(x)的除運(yùn)算，可

3、以通過(guò) g和h做xor (異或)運(yùn)算。比如將 11001與10101做xor運(yùn)算：1；150：0：1；1；0；1；0；1;I0d1IoI0IIVIIII明白了 xor運(yùn)算法則后，舉一個(gè)例子使用CRC-8算法求101001110100001的效驗(yàn)碼。CRC-8標(biāo)準(zhǔn)的h(x) = xA8 + xA7 + xA6 + xA4 + xA2 + 1，既 h 是 9 位的二進(jìn)制串 111010101。go10100111010000100000000h1110101018101001101110000100000000h111010101g20111000100000100000000h111010101

4、g3000010001000100000000h111010101g401100010000000000h111010101g50010111010000000h111010101g601010000100000h111010101870100101110000b111010101g8011111011000h11101010100010001100經(jīng)過(guò)迭代運(yùn)算后，最終得到的r是10001100,這就是CRC效驗(yàn)碼。通過(guò)示例，可以發(fā)現(xiàn)一些規(guī)律，依據(jù)這些規(guī)律調(diào)整算法：1.每次迭代，根據(jù)gk的首位決定b，b是與gk進(jìn)行運(yùn)算的二進(jìn)制碼。若 gk的首位是1，則b=h；若gk的 首位是0，則b=0,或者

5、跳過(guò)此次迭代，上面的例子中就是碰到0后直接跳到后面的非零位。氐首位是1b 二 h11111011000111010101r00010001100甌首位是001111011000b 二 00011110110002.每次迭代，gk的首位將會(huì)被移岀，所以只需考慮第2位后計(jì)算即可。這樣就可以舍棄h的首位，將b取h的后 m位。比如 CRC-8的h是111010101，b只需是11010101。S10100111g:10100111010000100000000fS01001110b11010101S首位：1S10011011g;10100111010000100000000fs00110111b110

6、10101s首位：1S1110001010100111010000100000000ts11000100b11010101s首位：1s00010001g:10100111010000100000000fs00100010b0S首位：0S00100010g:10100111010000100000000fs01000100b0s首位：0藍(lán)色表示寄存器S的首位，是需要移岀的，b根據(jù)S的首位選擇0或者h(yuǎn)。黃色是需要移入寄存器的位。 S'是經(jīng)過(guò)位移后的So查表法同樣是上面的那個(gè)例子，將數(shù)據(jù)按每4位組成1個(gè)block，這樣g就被分成6個(gè)blockgBlB2B3B4B5B6010100111010

7、000100000000下面的表展示了 4次迭代計(jì)算步驟，灰色背景的位是保存在寄存器中的經(jīng)4次迭代，B1被移出寄存器。被移出的部分，不我們關(guān)心的，我們關(guān)心的是這 4次迭代對(duì)B2和B3產(chǎn) 生了什么影響。注意表中紅色的部分，先作如下定義：B23 = 00111010bl = 00000000b2 = 01010100b3 = 10101010b4 = 11010101b' = b1 xor b2 xor b3 xor b44次迭代對(duì)B2和B3來(lái)說(shuō),實(shí)際上就是讓它們與 b1,b2,b3,b4做了 xor計(jì)算，既：B23 xor b1 xor b2 xor b3 xor b4可以證明xor運(yùn)算

8、滿足交換律和結(jié)合律，于是：B23 xor b1 xor b2 xor b3 xor b4 = B23 xor (b1 xor b2 xor b3 xor b4) = B23 xor b'b1是由B1的第1位決定的，b2是由B1迭代1次后的第2位決定(既是由B1的第1和第2位決定)， 同理,b3和b4都是由B1決定。通過(guò)B1就可以計(jì)算出b'o另外，B1由4位組成，其一共2A4有種可能值。于是我們就可以想到一種更快捷的算法，事先將b'所有可能的值，16個(gè)值可以看成一個(gè)表；這樣就可以不必進(jìn)行那4次迭代，而是用B1查表得到b'值，將B1移出，B3移入，與b'計(jì)算

9、，然后是下一次迭代。SrSBlB2B2B3bg： B1|B2使用BB3 B4 B51查表得到B6S& SB2B3B3B4bg: B1|B2使用氏B3 B4 B5 B6 i查表得到6|可看到每次迭代，寄存器中的數(shù)據(jù)以4位為單位移入和移岀，關(guān)鍵是通過(guò)寄存器前4位查表獲得，這樣的算法可以大大提高運(yùn)算速度。上面的方法是半字節(jié)查表法，另外還有單字節(jié)和雙字節(jié)查表法，原理都是一樣的一一事先計(jì)算岀2A8或2X6 個(gè)b'的可能值，迭代中使用寄存器前8位或16位查表獲得b'。反向算法之前討論的算法可以稱為正向CRC算法，意思是將g左邊的位看作是高位，右邊的位看作低位。G的右邊加m個(gè)0,然后

10、迭代計(jì)算是從高位開(kāi)始，逐步將低位加入到寄存器中。在實(shí)際的數(shù)據(jù)傳送過(guò)程中，是一邊接收數(shù)據(jù)，一邊計(jì)算 CRC碼，正向算法將新接收的數(shù)據(jù)看作低位。逆向算法顧名思義就是將左邊的數(shù)據(jù)看作低位，右邊的數(shù)據(jù)看作高位。這樣的話需要在g的左邊加m個(gè)0,h也要逆向，例如正向 CRC-16算法h=0x4c11db8，逆向CRC-16算法h=0xedb88320。b的選擇0還是h，由 寄存器中右邊第1位決定，而不是左邊第1位。寄存器仍舊是向左位移，就是說(shuō)迭代變成從低位到高位。s00000000g:00000000101001110100001fs00000001b0S末位：0S00000001g=00000000101001110100001f s00000010b10101011S末位：1s10101001g=00000000101001110100001f s01010011lb11010101S末位：11、C語(yǔ)言實(shí)現(xiàn)1、crc-8crc8 c 語(yǔ)言源程序 uint8 xCal_crc(uint8 *ptr,