循環(huán)冗余檢驗(yàn)(CRC)算法原理

1、循環(huán)冗余檢驗(yàn)(CRC)算法原理Cyclic Redundancy Check循環(huán)冗余檢驗(yàn)，是基于數(shù)據(jù)計(jì)算一組效驗(yàn)碼，用于核對(duì)數(shù)據(jù)傳 輸過(guò)程中是否被更改或傳輸錯(cuò)誤。算法原理假設(shè)數(shù)據(jù)傳輸過(guò)程中需要發(fā)送15位的二進(jìn)制信息g=101001110100001，這串二進(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)，一

2、般按照h(x)的階數(shù)m將CRC算法稱為CRC-m比如CRC-32 CRC-64等。國(guó)際通行標(biāo)準(zhǔn)可以參看/wiki/Cyclic_red undan cy_checkg(x)和h(x)的除運(yùn)算，可以通過(guò) g和h做xor (異或)運(yùn)算。比如將11001與10101做xor運(yùn)算：1：1!0：0：1=;d 0; 1 i 0; 1 ;jo：iiiioioil!IjIIl!明白了 xor運(yùn)算法則后，舉一個(gè)例子使用 CRC-8算法求101001110100001的效驗(yàn)碼。CRC-8 標(biāo)準(zhǔn)的 h(x) = xA8 + xA7 + xA6 + xA4 + 於2 + 1

3、，既 h 是 9 位的二進(jìn)制串 111010101。0 h10100111010000160000000111010101gl01001101110000100000000h11101010120111000100000160000000h111010101000010001000100000000h11101010101100010000000000h111010101gseoioinoioooooooh111010101g601010060100000h11101010170100101110000h1110101018011111011000h111010101rOOClOOOllOO經(jīng)

4、過(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，或者跳過(guò)此次迭代，上面的例子中就是碰到0后直接跳到后面的非零位。甌首位是1Sk b = h11111011000111010101r00010001100甌首位是08k01111011000b = 00r011110110002每次迭代，gk的首位將會(huì)被移出，所以只需考慮第2位后計(jì)算即可。這樣就可以舍棄h的首位，將b取h的后m位。比如CRC-8的h是111

5、010101, b只需是11010101Sk+1111011000b11010101r00100011003.每次迭代，受到影響的是 gk的前m位，所以構(gòu)建一個(gè) m位的寄存器S,此寄存器儲(chǔ) 存gk的前m位。每次迭代計(jì)算前先將 S的首位拋棄，將寄存器左移一位，同時(shí)將 g的 后一位加入寄存器。若使用此種方法，計(jì)算步驟如下：S1010011110100111010000100000000JI s01001110b11010101S首位：1s10011011g:10100111010000100000000s00110111b11010101s首位:1S11100010g=10100111010000

6、100000000S11000100b11010101S首位；1S00010001g-10100111010000100000000t s00100010b0S首位：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è)blockBlB2B3B4B5B6010100111010000100000000gF面的表展示了 4次迭代計(jì)算步驟，灰色背景的位是保存在

7、寄存器中的。B3ss b Ssb0101 i 00110101 | 0011000 I 00000101 i 0011goi i 0011111sF s bmo I ono mo 丨 ono110011001110111001000100S i謝S jjb !I 11010101經(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

8、 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)算滿足交換律和結(jié)合律，于是：B23 xor b1 xor b2 xor b3 xor b4 = B23 xor (b1 xor b2 xor b3 xor b4) = B23xor bb1是由B1的第1位決定的，b2是由B1迭代1次后的第2位決定(既是由B1的第1和 第2位決定)，同理,b3和b4都是由B1決定。通過(guò)B1就可以計(jì)算出b。另外，B1由 4位組成，其一共2A4有種可能值。于是我們就可以想到一種更快捷的算法，事

9、先將b所有可能的值，16個(gè)值可以看成一個(gè)表；這樣就可以不必進(jìn)行那4次迭代，而是用B1查表得到b值，將B1移出，B3移入，與b計(jì)算，然后是下一次迭代。S If 1S 1BlB2B2B3bg: Bl B2 B3 B4|B5 B6使用Bl查表得到BS * 1S 1:B2B3B3B4bg: Bl B2 B3 B4 B5 B6使用E2查表得到6可看到每次迭代，寄存器中的數(shù)據(jù)以4位為單位移入和移出，關(guān)鍵是通過(guò)寄存器前4位查表獲得，這樣的算法可以大大提高運(yùn)算速度。上面的方法是半字節(jié)查表法，另外還有單字節(jié)和雙字節(jié)查表法，原理都是一樣的 事先計(jì)算出2A8或2A16個(gè)b的可能值，迭代中使用寄存器前 8位或16位查

10、表獲得b。反向算法之前討論的算法可以稱為正向CRC算法，意思是將g左邊的位看作是高位，右邊的位看作低位。G的右邊加m個(gè)0,然后迭代計(jì)算是從高位開始， 逐步將低位加入到寄存器中。 在實(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ō)迭代變成從低位到高位。S ()000000000