從技術(shù)層面解析CRC循環(huán)冗余算法原理

Cyclic Redundancy Check循環(huán)冗余檢驗(yàn)，是基于數(shù)據(jù)計(jì)算一組效驗(yàn)碼，用于核對(duì)CRC循環(huán)冗余算法數(shù)據(jù)傳輸過(guò)程中是否被更改或傳輸錯(cuò)誤。

算法原理

假設(shè)數(shù)據(jù)傳輸過(guò)程中需要發(fā)送15位的二進(jìn)制信息g=101001110100001，這串二進(jìn)制碼可表示為代數(shù)多項(xiàng)式g(x) = x^14 + x^12 + x^9 + x^8 + x^7 + x^5 + 1，其中g(shù)中第k位的值，對(duì)應(yīng)g(x)中x^k的系數(shù)。將g(x)乘以x^m，既將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算法稱(chēng)為CRC-m，比如CRC-32、CRC-64等。

g(x)和h(x)的除運(yùn)算，可以通過(guò)g和h做xor（異或）運(yùn)算。

比如將11001與10101做xor運(yùn)算：

明白了xor運(yùn)算法則后，舉一個(gè)例子使用CRC-8算法求101001110100001的效驗(yàn)碼。CRC-8標(biāo)準(zhǔn)的h(x) = x^8 + x^7 + x^6 + x^4 + x^2 + 1，既h是9位的二進(jìn)制串111010101。

經(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，或者跳過(guò)此次迭代，上面的例子中就是碰到0后直接跳到后面的非零位。
2. 每次迭代，gk的首位將會(huì)被移出，所以只需考慮第2位后計(jì)算即可。這樣就可以舍棄h的首位，將b取h的后m位。比如CRC-8的h是111010101，b只需是11010101。
3. 每次迭代，受到影響的是gk的前m位，所以構(gòu)建一個(gè)m位的寄存器S，此寄存器儲(chǔ)存gk的前m位。每次迭代計(jì)算前先將S的首位拋棄，將寄存器左移一位，同時(shí)將g的后一位加入寄存器。若使用此種方法，計(jì)算步驟如下：

※藍(lán)色表示寄存器S的首位，是需要移出的，b根據(jù)S的首位選擇0或者h(yuǎn)。黃色是需要移入寄存器的位。S'是經(jīng)過(guò)位移后的S。

查表法

同樣是上面的那個(gè)例子，將數(shù)據(jù)按每4位組成1個(gè)block，這樣g就被分成6個(gè)block。

下面的表展示了4次迭代計(jì)算步驟，灰色背景的位是保存在寄存器中的。

經(jīng)4次迭代，B1被移出寄存器。被移出的部分，不我們關(guān)心的，我們關(guān)心的是這4次迭代對(duì)B2和B3產(chǎn)生了什么影響。注意表中紅色的部分，先作如下定義：

B23 = 00111010

b1 = 00000000

b2 = 01010100

b3 = 10101010

b4 = 11010101

b' = b1 xor b2 xor b3 xor b4

4次迭代對(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)算滿(mǎn)足交換律和結(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'。另外，B1由4位組成，其一共2^4有種可能值。于是我們就可以想到一種更快捷的算法，事先將b'所有可能的值，16個(gè)值可以看成一個(gè)表；這樣就可以不必進(jìn)行那4次迭代，而是用B1查表得到b'值，將B1移出，B3移入，與b'計(jì)算，然后是下一次迭代。

可看到每次迭代，寄存器中的數(shù)據(jù)以4位為單位移入和移出，關(guān)鍵是通過(guò)寄存器前4位查表獲得

，這樣的算法可以大大提高運(yùn)算速度。

上面的方法是半字節(jié)查表法，另外還有單字節(jié)和雙字節(jié)查表法，原理都是一樣的——事先計(jì)算出2^8或2^16個(gè)b'的可能值，迭代中使用寄存器前8位或16位查表獲得b'。

CRC循環(huán)冗余反向算法

之前討論的算法可以稱(chēng)為正向CRC算法，意思是將g左邊的位看作是高位，右邊的位看作低位。G的右邊加m個(gè)0，然后迭代計(jì)算是從高位開(kāi)始，逐步將低位加入到寄存器中。在實(shí)際的數(shù)據(jù)傳送過(guò)程中，是一邊接收數(shù)據(jù)，一邊計(jì)算CRC碼，正向算法將新接收的數(shù)據(jù)看作低位。

CRC循環(huán)冗余逆向算法顧名思義就是將左邊的數(shù)據(jù)看作低位，右邊的數(shù)據(jù)看作高位。這樣的話需要在g的左邊加m個(gè)0，h也要逆向，例如正向CRC-16算法h=0x4c11db8，逆向CRC-16算法h=0xedb88320。b的選擇0還是h，由寄存器中右邊第1位決定，而不是左邊第1位。寄存器仍舊是向左位移，就是說(shuō)迭代變成從低位到高位。

審核編輯：湯梓紅