CCITT CRC-16計算原理與實現

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

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

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

1 代數學的一般性算法

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

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

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

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

舉例來說，設信息碼為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
無余式。回頭看一下上面的豎式除法，如果被除數是1100010，顯然在商第三個1時，就能除盡。

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

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

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

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

2.CRC算法的實現
---------------
要用程序實現CRC算法，考慮對第2節的長除法做一下變換，依然是M = 11100110，G = 1011，
其系數r為3。

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