CCITT CRC-16計(jì)算原理及應(yīng)用

　CRC的全稱為Cyclic Redundancy Check，中文名稱為循環(huán)冗余校驗(yàn)。它是一類重要的線性分組碼，編碼和解碼方法簡單，檢錯和糾錯能力強(qiáng)，在通信領(lǐng)域廣泛地用于實(shí)現(xiàn)差錯控制。實(shí)際上，除 數(shù)據(jù)通信外，CRC在其它很多領(lǐng)域也是大有用武之地的。例如我們讀軟盤上的文件，以及解壓一個ZIP文件時(shí)，偶爾會碰到“Bad CRC”錯誤，由此它在數(shù)據(jù)存儲方面的應(yīng)用可略見一斑。
　　差錯控制理論是在代數(shù)理論基礎(chǔ)上建立起來的。這里我們著眼于介紹CRC的算法與實(shí)現(xiàn)，對原理只能捎帶說明一下。若需要進(jìn)一步了解線性碼、分組碼、循環(huán)碼、糾錯編碼等方面的原理，可以閱讀有關(guān)資料。
　　利用CRC進(jìn)行檢錯的過程可簡單描述為：在發(fā)送端根據(jù)要傳送的k位二進(jìn)制碼序列，以一定的規(guī)則產(chǎn)生一個校驗(yàn)用的r位監(jiān)督 碼（CRC碼），附在原始信息后邊，構(gòu)成一個新的二進(jìn)制碼序列數(shù)共k+r位，然后發(fā)送出去。在接收端，根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進(jìn)行檢驗(yàn)，以 確定傳送中是否出錯。這個規(guī)則，在差錯控制理論中稱為“生成多項(xiàng)式”。
　　1 代數(shù)學(xué)的一般性算法
　　在代數(shù)編碼理論中，將一個碼組表示為一個多項(xiàng)式，碼組中各碼元當(dāng)作多項(xiàng)式的系數(shù)。例如 1100101 表示為
　　1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1，即 x6+x5+x2+1。
　　設(shè)編碼前的原始信息多項(xiàng)式為P（x），P（x）的最高冪次加1等于k；生成多項(xiàng)式為G（x），G（x）的最高冪次等于r；CRC多項(xiàng)式為R（x）；編碼后的帶CRC的信息多項(xiàng)式為T（x）。
　　發(fā)送方編碼方法：將P（x）乘以xr（即對應(yīng)的二進(jìn)制碼序列左移r位），再除以G（x），所得余式即為R（x）。用公式表示為
　　T（x）=xrP（x）+R（x）
　　接收方解碼方法：將T（x）除以G（x），如果余數(shù)為0，則說明傳輸中無錯誤發(fā)生，否則說明傳輸有誤。
　　舉例來說，設(shè)信息碼為1100，生成多項(xiàng)式為1011，即P（x）=x3+x2，G（x）=x3+x+1，計(jì)算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。
　　如果用豎式除法，計(jì)算過程為
　　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時(shí)，就能除盡。
　　上述推算過程，有助于我們理解CRC的概念。但直接編程來實(shí)現(xiàn)上面的算法，不僅繁瑣，效率也不高。實(shí)際上在工程中不會直接這樣去計(jì)算和驗(yàn)證CRC。
　　下表中列出了一些見于標(biāo)準(zhǔn)的CRC資料：
　　名稱生成多項(xiàng)式簡記式*應(yīng)用舉例
　　CRC-4x4+x+1ITU G.704
　　CRC-12x12+x11+x3+x+1
　　CRC-16x16+x12+x2+11005IBM SDLC
　　CRC-ITU**x16+x12+x5+11021ISO HDLC， ITU X.25， V.34/V.41/V.42， PPP-FCS
　　CRC-32x32+x26+x23+.。.+x2+x+104C11DB7ZIP， RAR， IEEE 802 LAN/FDDI， IEEE 1394， PPP-FCS
　　CRC-32cx32+x28+x27+.。.+x8+x6+11EDC6F41SCTP
　　* 生成多項(xiàng)式的最高冪次項(xiàng)系數(shù)是固定的1，故在簡記式中，將最高的1統(tǒng)一去掉了，
　　如04C11DB7實(shí)際上是104C11DB7。
　　** 前稱CRC-CCITT。ITU的前身是CCITT。
　　2.CRC算法的實(shí)現(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 《---校驗(yàn)碼
?