crc循環(huán)冗余碼

1、  CRC循環(huán)冗余碼原理 收藏 一。 在遠距離數(shù)據(jù)通信中，為確保高效而無差錯地傳送數(shù)據(jù)，必須對數(shù)據(jù)進行校驗即差錯控制。循環(huán)冗余校驗CRC(Cyclic   Redundancy   Check)是對一個傳送數(shù)據(jù)塊進行校驗，是一種高效的差錯控制方法。         1循環(huán)冗余校驗碼原理         CRC校驗采用多項式編碼方法，如一個8位二進制數(shù)(B7B6B5B4B3B2B1B0)可以用7階二進制碼多項式B7X7+B6X6+B5X5+B4X4+B3X3+B2X2+B1X1

2、+B0X0表示。     例如11000001可表示為     1X7+1X6+0X5+0X4+0X3+0X2+0X1+0X0     一般說，n位二進制數(shù)可用(n-1)階多項式表示。它把要發(fā)送的數(shù)據(jù)位串看成是系數(shù)只能為“1”或“0”的多項式。一個n位的數(shù)據(jù)塊可以看成是從Xn-1到X0的n項多項式的系數(shù)序列，位于數(shù)據(jù)塊左邊的最高位是Xn-1項的系數(shù)，次高位是Xn-2項的系數(shù)，依此類推，位于數(shù)據(jù)塊右邊的最低位是X0項的系數(shù)，這個多項式的階數(shù)為n-1。     多項式乘除法運算過程與普通代數(shù)多項式的乘除法相同。多項式的

3、加減法運算以2為模，加減時不進、錯位，如同邏輯異或運算。     采用CRC校驗時，發(fā)送方和接收方事先約定一個生成多項式G(X)，并且G(X)的最高項和最低項的系數(shù)必須為1。設(shè)m位數(shù)據(jù)塊的多項式為M(X)，生成多項式G(X)的階數(shù)必需比M(X)的階數(shù)低。CRC校驗碼的檢錯原理是：發(fā)送方先為數(shù)據(jù)塊生成CRC校驗碼，使這個CRC校驗碼的多項式能被G(X)除盡，實際發(fā)送此CRC校驗碼；接收方用收到的CRC校驗碼除以G(X)，如果能除盡，表明傳輸正確，否則，表示有傳輸錯誤，請求重發(fā)。     生成數(shù)據(jù)塊的CRC校驗碼的方法是：     (1)

4、   設(shè)G(X)為r階，在數(shù)據(jù)塊末尾添加r個0，使數(shù)據(jù)塊為m+r位，則相應(yīng)的多項式為XrM(X)；     (2)   以2為模，用對應(yīng)于G(X)的位串去除對應(yīng)于XrM(X)的位串，求得余數(shù)位串；     (3)   以2為模，從對應(yīng)于XrM(X)的位串中減去余數(shù)位串，結(jié)果就是為數(shù)據(jù)塊生成的帶足夠校驗信息的CRC校驗碼位串。     例如，設(shè)要發(fā)送的數(shù)據(jù)為1101011011，G(X)=X4+X+1，則首先在發(fā)送數(shù)據(jù)塊的末尾加4個0，得到11010110110000，然后用G(X)的位串10011去除，再

5、用11010110110000減去余數(shù)位串1110，得到的即為CRC位串11010110111110，將對應(yīng)多項式稱為T(X)，顯然，T(X)能被G(X)除盡。這樣，一旦接收到的CRC位串不能被同樣的G(X)的位串除盡，那么一定有傳輸錯誤。     當(dāng)使用CRC校驗碼進行差錯控制時，除了為G(X)的整數(shù)倍的差錯多項式不能被檢測外，其它差錯均能被查出。CRC校驗碼的差錯控制效果取決于G(X)的階數(shù)，階數(shù)越高，效果越好。目前，常用的有兩種生成多項式G(X)的方法，分別是：     CRC-16X16+X15+X2+1     CCITTX

6、16+X12+X5+1     CRC校驗碼實際上是一種線性碼，將任意CRC校驗碼循環(huán)移位后仍然是一個CRC校驗碼。由于它有良好的結(jié)構(gòu)，檢錯能力強，易于實現(xiàn)硬件編、譯碼，因此在數(shù)據(jù)通信系統(tǒng)中得到廣泛的應(yīng)用。 二。CRC的全稱為Cyclic Redundancy Check，中文名稱為循環(huán)冗余校驗。它是一類重要的線性分組碼，編碼和解碼方法簡單，檢錯和糾錯能力強，在通信領(lǐng)域廣泛地用于實現(xiàn)差錯控制。實際上，除數(shù)據(jù)通信外，CRC在其它很多領(lǐng)域也是大有用武之地的。例如我們讀軟盤上的文件，以及解壓一個ZIP文件時，偶爾會碰到“Bad CRC”錯誤，由此它在數(shù)據(jù)存儲方面的應(yīng)用可

7、略見一斑。差錯控制理論是在代數(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)作

8、多項式的系數(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ā)生，否則

9、說明傳輸有誤。舉例來說，設(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, 即

10、1100000+010=1100010如果傳輸無誤， T(x) x6+x5+x - = - = x3+x2+x, G(x) x3+x+1無余式?；仡^看一下上面的豎式除法，如果被除數(shù)是1100010，顯然在商第三個1時，就能除盡。  三。CRC校驗    crc算法已經(jīng)有成熟和比較經(jīng)典的現(xiàn)成代碼可供我們利用。CRC計算可以靠專用的硬件來實現(xiàn),但是對于低成本的微控制器系統(tǒng),在沒有硬件支持下實現(xiàn)CRC檢驗,關(guān)鍵的問題就是如何通過軟件來完成CRC計算,也就是CRC算法的問題。CRC校驗的基本思想是利用線性編碼理論,在發(fā)送端根據(jù)要傳送的k位二進制碼序列,

11、以一定的規(guī)則產(chǎn)生一個校驗用的監(jiān)督碼（既CRC碼）r位,并附在信息后邊,構(gòu)成一個新的二進制碼序列數(shù)共(k+r)位,最后發(fā)送出去。在接收端,則根據(jù)信息碼和CRC碼之間所遵循的規(guī)則進行檢驗,以確定傳送中是否出錯。1.生成多項式。16位的CRC碼產(chǎn)生的規(guī)則是先將要發(fā)送的二進制序列數(shù)左移16位（既乘以 ）后,再除以一個多項式,最后所得到的余數(shù)既是CRC碼。任意一個由二進制位串組成的代碼都可以和一個系數(shù)僅為0和1取值的多項式一一對應(yīng)。例如：代碼1010111對應(yīng)的多項式為x6+x4+x2+x+1，而多項式為x5+x3+x2+x+1對應(yīng)的代碼101111。標(biāo)準(zhǔn)CRC生成多項式如下表：  

12、 名稱        生成多項式              簡記式*   標(biāo)準(zhǔn)引用    CRC-4       x4+x+1              

13、60;   3         ITU G.704    CRC-8       x8+x5+x4+1              0x31            

14、0;          CRC-8       x8+x2+x1+1              0x07                   

15、;    CRC-8       x8+x6+x4+x3+x2+x1       0x5E    CRC-12      x12+x11+x3+x+1          80F   CRC-16      x16+x15+x2+1

16、            8005      IBM SDLC   CRC16-CCITT x16+x12+x5+1            1021      ISO HDLC, ITU X.25, V.34/V.41/V.42, PPP-FCS  &

17、#160; CRC-32      x32+x26+x23+.+x2+x+1 04C11DB7 ZIP, RAR, IEEE 802 LAN/FDDI, IEEE 1394, PPP-FCS    CRC-32c     x32+x28+x27+.+x8+x6+1 1EDC6F41 SCTP /葉子：這里不知道問什么省略了，有些迷惑哦。要是生成多項式要是都省了，那還怎么校驗？我猜想可能是中間的全為一吧。       

18、                          生成多項式的最高位固定的1，故在簡記式中忽略最高位1了，如0x1021實際是0x11021。I、基本算法（人工筆算）：   以CRC16-CCITT為例進行說明，CRC校驗碼為16位，生成多項式17位。假如數(shù)據(jù)流為4字節(jié)：BYTE3、BYTE2、BYTE1、BYTE0；數(shù)據(jù)流左

19、移16位，相當(dāng)于擴大256×256倍，再除以生成多項式0x11021，做不借位的除法運算（相當(dāng)于按位異或），所得的余數(shù)就是CRC校驗碼。發(fā)送時的數(shù)據(jù)流為6字節(jié)：BYTE3、BYTE2、BYTE1、BYTE0、CRC1、CRC0；II、計算機算法1（比特型算法）：1)將擴大后的數(shù)據(jù)流（6字節(jié)）高16位（BYTE3、BYTE2）放入一個長度為16的寄存器；2)如果寄存器的首位為1，將寄存器左移1位(寄存器的最低位從下一個字節(jié)獲得)，再與生成多項式的簡記式異或；    否則僅將寄存器左移1位(寄存器的最低位從下一個字節(jié)獲得)；3)重復(fù)第2步，直到數(shù)據(jù)流（6字節(jié)

20、）全部移入寄存器；4)寄存器中的值則為CRC校驗碼CRC1、CRC0。III、計算機算法2（字節(jié)型算法）：256n表示256的n次方    把按字節(jié)排列的數(shù)據(jù)流表示成數(shù)學(xué)多項式，設(shè)數(shù)據(jù)流為BYTEnBYTEn1BYTEn2、BYTE1BYTE0，表示成數(shù)學(xué)表達式為BYTEn×256n+BYTEn-1×256(n-1)+.+BYTE1*256+BYTE0，在這里+表示為異或運算。設(shè)生成多項式為G17（17bit），CRC碼為CRC16。    則，CRC16(BYTEn×256n+BYTEn-1×

21、256(n-1)+.+BYTE1×256+BYTE0)×2562/G17，即數(shù)據(jù)流左移16位，再除以生成多項式G17。    先變換BYTEn-1、BYTEn-1擴大后的形式，    CRC16BYTEn×256n×2562/G17+BYTEn-1×256(n-1)×2562/G17+.+BYTE1×256×2562/G17+BYTE0×2562/G17        

22、; (Zn+Yn/G17)×256n+BYTEn-1×256(n-1)×2562/G17+.+BYTE1×256×2562/G17+BYTE0×2562/G17         Zn×256n+Yn×256/G17+BYTEn-1×2562/G17×256(n-1)+.+BYTE1×256×2562/G17+BYTE0×2562/G17    &#

23、160;    Zn×256n+(YH8n×256+YHLn)×256/G17+BYTEn-1×2562/G17×256(n-1)+.+BYTE1×256×2562/G17+BYTE0×2562/G17         Zn×256n+YHLn×256/G17+(YH8n+BYTEn-1)×2562/G17×256(n-1)+.+BYTE1×256×

24、;2562/G17+BYTE0×2562/G17    這樣就推導(dǎo)出，BYTEn-1字節(jié)的CRC校驗碼為YHLn×256/G17+(YH8n+BYTEn-1)×2562/G17，即上一字節(jié)CRC校驗碼Yn的高8位（YH8n）與本字節(jié)BYTEn-1異或，該結(jié)果單獨計算CRC校驗碼（即單字節(jié)的16位CRC校驗碼，對單字節(jié)可建立表格，預(yù)先生成對應(yīng)的16位CRC校驗碼），所得的CRC校驗碼與上一字節(jié)CRC校驗碼Yn的低8位（YL8n）乘以256（即左移8位）異或。然后依次逐個字節(jié)求出CRC，直到BYTE0。   

25、 字節(jié)型算法的一般描述為：本字節(jié)的CRC碼，等于上一字節(jié)CRC碼的低8位左移8位，與上一字節(jié)CRC右移8位同本字節(jié)異或后所得的CRC碼異或。        字節(jié)型算法如下：    1)CRC寄存器組初始化為全"0"(0x0000)。（注意：CRC寄存器組初始化全為1時，最后CRC應(yīng)取反。）    2)CRC寄存器組向左移8位,并保存到CRC寄存器組。    3)原CRC寄存器組高8位（右移8位）與數(shù)據(jù)字節(jié)進行異或運算，得出一個

26、指向值表的索引。    4)索引所指的表值與CRC寄存器組做異或運算。    5)數(shù)據(jù)指針加1，如果數(shù)據(jù)沒有全部處理完，則重復(fù)步驟2)。    6)得出CRC。unsigned short GetCrc_16(unsigned char * pData, int nLength)/函數(shù)功能：計算數(shù)據(jù)流* pData的16位CRC校驗碼，數(shù)據(jù)流長度為nLength    unsigned short cRc_16 = 0x0000;    / 初始

27、化        while(nLength>0)            cRc_16 = (cRc_16 << 8) cRctable_16(cRc_16>>8) *pData) & 0xff; /cRctable_16表由函數(shù)mK_cRctable生成        nLength-;   

28、60;    pData+;            return cRc_16;    void mK_cRctable(unsigned short gEnpoly)/函數(shù)功能：生成0255對應(yīng)的16CRC校驗碼，其實就是計算機算法1（比特型算法）/gEnpoly為生成多項式/注意，低位先傳送時，生成多項式應(yīng)反轉(zhuǎn)(低位與高位互換)。如CRC16-CCITT為0x1021，反轉(zhuǎn)后為0x8408 unsigned short cRc_16=0;un

29、signed short i,j,k;for(i=0,k=0;i<256;i+,k+)      cRc_16 = i<<8;      for(j=8;j>0;j-)      if(cRc_16&0x8000)                 /反轉(zhuǎn)時cRc_16&0x0001             cRc_16=(cRc_16<<=1)gEnpoly; /反轉(zhuǎn)時cRc_16=(cRc_16>>=1