CCITT CRC-16計算原理與實現(xiàn)

CRC的全稱為Cyclic Redundancy Check，中文名稱為循環(huán)冗余校驗。它是一類重要的線性分組碼，編碼和解碼方法簡單，檢錯和糾錯能力強，在通信領(lǐng)域廣泛地用于實現(xiàn)差錯控制。實際上，除 數(shù)據(jù)通信外，CRC在其它很多領(lǐng)域也是大有用武之地的。例如我們讀軟盤上的文件，以及解壓一個ZIP文件時，偶爾會碰到“Bad CRC”錯誤，由此它在數(shù)據(jù)存儲方面的應(yīng)用可略見一斑。

差錯控制理論是在代數(shù)理論基礎(chǔ)上建立起來的。這里我們著眼于介紹CRC的算法與實現(xiàn)，對原理只能捎帶說明一下。若需要進一步了解線性碼、分組碼、循環(huán)碼、糾錯編碼等方面的原理，可以閱讀有關(guān)資料。

利用CRC進行檢錯的過程可簡單描述為：在發(fā)送端根據(jù)要傳送的k位二進制碼序列，以一定的規(guī)則產(chǎn)生一個校驗用的r位監(jiān)督 碼(CRC碼)，附在原始信息后邊，構(gòu)成一個新的二進制碼序列數(shù)共k+r位，然后發(fā)送出去。在接收端，根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進行檢驗，以 確定傳送中是否出錯。這個規(guī)則，在差錯控制理論中稱為“生成多項式”。　

1 代數(shù)學(xué)的一般性算法

在代數(shù)編碼理論中，將一個碼組表示為一個多項式，碼組中各碼元當(dāng)作多項式的系數(shù)。例如 1100101 表示為
1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1，即 x6+x5+x2+1。

設(shè)編碼前的原始信息多項式為P(x)，P(x)的最高冪次加1等于k；生成多項式為G(x)，G(x)的最高冪次等于r；CRC多項式為R(x)；編碼后的帶CRC的信息多項式為T(x)。

發(fā)送方編碼方法：將P(x)乘以xr(即對應(yīng)的二進制碼序列左移r位)，再除以G(x)，所得余式即為R(x)。用公式表示為
T(x)=xrP(x)+R(x)

接收方解碼方法：將T(x)除以G(x)，如果余數(shù)為0，則說明傳輸中無錯誤發(fā)生，否則說明傳輸有誤。

舉例來說，設(shè)信息碼為1100，生成多項式為1011，即P(x)=x3+x2，G(x)=x3+x+1，計算CRC的過程為

xrP(x) x3(x3+x2) x6+x5 x
-------- = ---------- = -------- = (x3+x2+x) + --------
G(x) x3+x+1 x3+x+1 x3+x+1
即 R(x)=x。注意到G(x)最高冪次r=3，得出CRC為010。

如果用豎式除法，計算過程為

1110
-------
1011 /1100000 (1100左移3位)
1011
----
1110
1011
-----
1010
1011
-----
0010
0000
----
010
因此，T(x)=(x6+x5)+(x)=x6+x5+x, 即 1100000+010=1100010

如果傳輸無誤，

T(x) x6+x5+x
------ = --------- = x3+x2+x,
G(x) x3+x+1
無余式。回頭看一下上面的豎式除法，如果被除數(shù)是1100010，顯然在商第三個1時，就能除盡。

上述推算過程，有助于我們理解CRC的概念。但直接編程來實現(xiàn)上面的算法，不僅繁瑣，效率也不高。實際上在工程中不會直接這樣去計算和驗證CRC。

下表中列出了一些見于標準的CRC資料：

* 生成多項式的最高冪次項系數(shù)是固定的1，故在簡記式中，將最高的1統(tǒng)一去掉了，
如04C11DB7實際上是104C11DB7。

** 前稱CRC-CCITT。ITU的前身是CCITT。

2.CRC算法的實現(xiàn)
---------------
要用程序?qū)崿F(xiàn)CRC算法，考慮對第2節(jié)的長除法做一下變換，依然是M = 11100110，G = 1011，
其系數(shù)r為3。

11001100
------------------------
1011 )11100110000
1011.......
----.......
1010......
1011......
----......
1110...
1011...
------...
1010..
1011..
-------
100 ---校驗碼