CRC16算法原理

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

2、這串二進制碼可表示為代數(shù)多項式g(x)=xA14+xA12+xA9+xA8+xA7+xA5+1,其中g(shù)中第k位的值，對應g(x)中x”的系數(shù)。將g(x)乘以xAm,既將g后加m個0,然后除以m階多項式h(x),得到的(m-1)階余項r(x)對應的二進制碼r就是CRC碼。h(x)可以自由選擇或者使用國際通行標準，一般按照h(x)的階數(shù)m將CRCB法稱為CRC-m比如CRC-32、CRC-64等。國際通行標準可以參看/wiki/Cyclic_redundancy_checkg(x)和h(x)的除運算，可以通過g和h做xor(異或)運算。比如將11001與

3、10101做xor運算：p:110011;1:1101011;1!011100：1明白了xor運算法則后，舉一個例子使用CRC-8算法求101001110100001的效驗碼。CRC-8標準的h(x)=xA8+xA7+xA6+xA4+xA2+1，既h是9位的二進制串111010101。g010100111010000100000000h11101010101001101110000100000000h1110101010111000100000100000000h111010101000010001000100000000h11101010101100010000000000h11101010

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

5、100gfe01111011000b=00r011110110002.每次迭代，gk的首位將會被移出，所以只需考慮第2位后計算即可。這樣就可以舍棄h的首位，將b取h的后m位。比如CRC-8的h是111010101,b只需是11010101。ssb-Sis1010011101001110110101011001101100110111g：10100111010000100000000S首位：1g：10100111010000100000000b飛tsb飛sb-S*sb11010101111000101100010011010101000100010010001000010001001000100

6、0s首位:g=s首位:g:S首位:g=s首位:loioonioiooooiooooooooloioonioiooooioooooooooloioonioiooooiooooooooo藍色表示寄存器S的首位，是需要移出的，b根據(jù)S的首位選擇0或者h。黃色是需要移入寄存器的位。S,是經(jīng)過位移后的SogBlB2B3B4B5B6010100111010000100000000查表法同樣是上面的那個例子，將數(shù)據(jù)按每4位組成1個block,這樣g就被分成6個block。下面的表展示了4次迭代計算步驟，灰色背景的位是保存在寄存器中的經(jīng)4次迭代，B1被移出寄存器。被移出的部分，不我們關(guān)心的，我們關(guān)心的是這4次

7、迭代對B2和B3產(chǎn)生了什么影響。注意表中紅色的部分，先作如下定義：B23=00111010bl=00000000b2=01010100b3=10101010b4=11010101b=b1xorb2xorb3xorb44次迭代對B2和B3來說,實際上就是讓它們與b1,b2,b3,b4做了xor計算，既：B23xorb1xorb2xorb3xorb4可以證明xor運算滿足交換律和結(jié)合律，于是：B23xorb1xorb2xorb3xorb4=B23xor(b1xorb2xorb3xorb4)=B23xorbb1是由B1的第1位決定的，b2是由B1迭代1次后的第2位決定(既是由B1的第1和第2位決定)

8、，同理,b3和b4都是由B1決定。通過B1就可以計算出bo另外，B1由4位組成,其一共2A4有種可能值。于是我們就可以想到一種更快捷的算法，事先將b所有可能的值，16個值可以看成一個表；這樣就可以不必進行那4次迭代，而是用B1查表得到b值，將B1移出，B3移入，與b計算，然后是下一次迭代。SfSBlB2B2B3bg：B1|B2|使用BB3B4B51查表得到B6SSB2B3B3#bg:B1|B2|使用B：B3B4B5B6Ii查表得到6|一r1rT111rrr1*1可看到每次迭代，寄存器中的數(shù)據(jù)以4位為單位移入和移出，關(guān)鍵是通過寄存器前4位查表獲得,這樣的算法可以大大提高運算速度。上面的方法是半字

9、節(jié)查表法，另外還有單字節(jié)和雙字節(jié)查表法，原理都是一樣的一一事先計算出2人8或2人16個b的可能值，迭代中使用寄存器前8位或16位查表獲得bo反向算法之前討論的算法可以稱為正向CRCT法，意思是將g左邊的位看作是高位，右邊的位看作低位。G的右邊加m個0,然后迭代計算是從高位開始，逐步將低位加入到寄存器中。在實際的數(shù)據(jù)傳送過程中，是一邊接收數(shù)據(jù)，一邊計算CRM,正向算法將新接收的數(shù)據(jù)看作低位。逆向算法顧名思義就是將左邊的數(shù)據(jù)看作低位，右邊的數(shù)據(jù)看作高位。這樣的話需要在g的左邊加m個0,h也要逆向，例如正向CRC-16算法h=0x4c11db8,逆向CRC-16算法h=0xedb88320。b的選擇0還是h,由寄存器中右邊第1位決定，而不是左邊第1位。寄存器仍舊是向左位移，就是說迭代變成從低位到高位。00000000g=0000000010100111010000100000001S末位:0000000100000010g=0000000010100111010000110101011S末位:S10101001g:000000001010011101000010101