標(biāo)題: CRC---循環(huán)冗余校驗(yàn)碼 [打印本頁(yè)]
作者: 51黑er    時(shí)間: 2015-11-2 14:41
標(biāo)題: CRC---循環(huán)冗余校驗(yàn)碼
CRC---循環(huán)冗余校驗(yàn)碼

CRC的基本原理

    　　基本原理：在K位信息碼后再拼接R位的校驗(yàn)碼，整個(gè)編碼長(zhǎng)度為N位，因此，這種編碼又叫（N，K）碼。對(duì)于一個(gè)給定的（N，K）碼，可以證明存在一個(gè)最高次冪為N-K=R的多項(xiàng)式G(x)。根據(jù)G(x)可以生成K位信息的校驗(yàn)碼，而G(x)叫做這個(gè)CRC碼的生成多項(xiàng)式。

    　　校驗(yàn)碼的具體生成過(guò)程為：假設(shè)發(fā)送信息用信息多項(xiàng)式C(X)表示，將C(x)左移R位，則可表示成C(x)*2R，這樣C(x)的右邊就會(huì)空出R位，這就是校驗(yàn)碼的位置。通過(guò)C(x)*2R除以生成多項(xiàng)式G(x)得到的余數(shù)就是校驗(yàn)碼。



CRC的標(biāo)準(zhǔn)

    　　在國(guó)際標(biāo)準(zhǔn)中，根據(jù)生成多項(xiàng)式G(x)的不同，CRC又可分為以下幾種標(biāo)準(zhǔn)：

    　�、貱RC-12碼:   G(x)=X12+X11+X3+X2+X+1

    　�、贑RC-16碼:   G(x)=X16+X15+X2+1

    　�、跜RC-CCITT碼: G(x)=X16+X12+X5+1

    　�、蹸RC-32碼:   G(x)=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+X+1

    　　CRC-12碼通常用來(lái)傳送6-bit字符串。CRC-16及CRC-CCITT碼則用是來(lái)傳送8-bit字符，其中CRC-16為美國(guó)采用，而CRC-CCITT為歐洲國(guó)家所采用。CRC-32碼大都被采用在一種稱為Point-to-Point的同步傳輸中。下面以最常用的CRC-16為例來(lái)說(shuō)明其生成過(guò)程。

    　　CRC-16碼由兩個(gè)字節(jié)構(gòu)成，在開(kāi)始時(shí)CRC寄存器的每一位都預(yù)置為1，然后把CRC寄存器與8-bit的數(shù)據(jù)進(jìn)行異或，之后對(duì)CRC寄存器從高到低進(jìn)行移位，在最高位（MSB）的位置補(bǔ)零，而最低位（LSB，移位后已經(jīng)被移出CRC寄存器）如果為1，則把寄存器與預(yù)定義的多項(xiàng)式碼進(jìn)行異或，否則如果LSB為零，則無(wú)需進(jìn)行異或。重復(fù)上述的由高至低的移位8次，第一個(gè)8-bit數(shù)據(jù)處理完畢，用此時(shí)CRC寄存器的值與下一個(gè)8-bit數(shù)據(jù)異或并進(jìn)行如前一個(gè)數(shù)據(jù)似的8次移位。所有的字符處理完成后CRC寄存器內(nèi)的值即為最終的CRC值。

    碼字長(zhǎng)度為64bit的CRC編碼。常用的生成多項(xiàng)式有：

    ISO 3309規(guī)定的    x^64 + x^4 + x^3 + x + 1；
   
    ECMA規(guī)定的   x^64 + x^62 + x^57 + x^55 + x^54 + x^53 + x^52 + x^47 + x^46 + x^45 + x^40 + x^39 + x^38 + x^37 + x^35 + x^33 +x^32 + x^31 + x^29 + x^27 + x^24 + x^23 + x^22 + x^21 +x^19 + x^17 + x^13 + x^12 + x^10 + x^9 + x^7 + x^4 + x + 1


CRC的計(jì)算過(guò)程

    　　1．設(shè)置CRC寄存器，并給其賦值FFFF(hex)。

    　　2．將數(shù)據(jù)的第一個(gè)8-bit字符與16位CRC寄存器的低8位進(jìn)行異或，并把結(jié)果存入CRC寄存器。

    　　3．CRC寄存器向右移一位，MSB補(bǔ)零，移出并檢查L(zhǎng)SB。

    　　4．如果LSB為0，重復(fù)第三步；若LSB為1，CRC寄存器與多項(xiàng)式碼相異或。

    　　5．重復(fù)第3與第4步直到8次移位全部完成。此時(shí)一個(gè)8-bit數(shù)據(jù)處理完畢。

    　　6．重復(fù)第2至第5步直到所有數(shù)據(jù)全部處理完成。

    　　7．最終CRC寄存器的內(nèi)容即為CRC值。

CRC碼的生成步驟

    　　1、將x的最高冪次為R的生成多項(xiàng)式G(x)轉(zhuǎn)換成對(duì)應(yīng)的R+1位二進(jìn)制數(shù)。

    　　2、將信息碼左移R位，相當(dāng)與對(duì)應(yīng)的信息多項(xiàng)式C(x)*2R。

    　　3、用生成多項(xiàng)式（二進(jìn)制數(shù)）對(duì)信息碼做模2除，得到R位的余數(shù)。

    　　4、將余數(shù)拼到信息碼左移后空出的位置，得到完整的CRC碼。



CRC64   


  3. #include <STDIO.H>   
  4. #include <MATH.H>   
  5.   
  6. // POLY   
  7. //注意：因最高位一定為“1”，故略去

  9. #define cnCRC_64_H  0x42F0E1EB   
  10. #define cnCRC_64_L  0xA9EA3693   
  11. //CRC-64-ECMA-182 x64 + x62 + x57 + x55 + x54 + x53 + x52 + x47 + x46 + x45 +   
  12. //x40 + x39 + x38 + x37 + x35 + x33 + x32 + x31 + x29 + x27 + x24 + x23 + x22   
  13. //+ x21 + x19 + x17 + x13 + x12 + x10 + x9 + x7 + x4 + x + 1   
  14. //(as described in ECMA-182 p.63)  or 0xC96C5795D7870F42 (0x92D8AF2BAF0E1E85)   
  15.   
  16. unsigned long TableCRCHigh[256];     // CRC ±í for 64   
  17. unsigned long TableCRCLow[256];     // CRC ±í for 64   
  18.   
  19. void BuildTable64();    //建立CRC表  
  20. unsigned long* CRC_64( unsigned char * aData, unsigned long aSize );        //生成CRC  
  21. //unsigned char test[11] = {0x01,0x02,0x03,0xf8,0x05,0x60,0x9e,0xce,0x1e,0xcb,0xf3};  

  23. unsigned char test[5] = {'A','B','C','D','E'};  

  25. void main()  
  26. {  
  27.     unsigned int i;  
  28.   
  29.     unsigned long* crc64;       //CRC的結(jié)果   
  30.    
  31.     BuildTable64();     //creat table   
  32.   
  33.     for (i=0;i<256;i++)  
  34.     {  
  35.         printf("%x,%x\n", TableCRCHigh[i],TableCRCLow[i]);  
  36.     }  
  37.   
  38.     crc64 = CRC_64(test,11);        //creat CRC  value   
  39.   
  40.         printf("The CRC is:%x,%x\n", *crc64,*(crc64+1));  
  41. }  
  42.   
  43. // 構(gòu)造64位CRC表   
  44. void BuildTable64()   
  45. {   
  46.     unsigned long i, j;   
  47.     unsigned long nData[2];   
  48.     unsigned long nAccum[2];   
  49.   
  50.     nData[0] = 0;  
  51.     nData[1] = 0;  
  52.   
  53.     for ( i = 0; i < 256; i++ )   
  54.     {   
  55.         nAccum[0] = 0;  
  56.         nAccum[1] = 0;  
  57.         nData[1] = i;  
  58.   
  59.         nData[0] = nData[1]<<24;  
  60.         nData[1]  = 0;  
  61.   
  62.         for ( j = 0; j < 8; j++ )   
  63.         {   
  64.             if ( (nData[0]^nAccum[0]) & 0x80000000 )   
  65.             {  
  66.                 nAccum[0] = ((nAccum[0]<<1) | ((nAccum[1]&0x80000000)>>31)) ^ cnCRC_64_H;  
  67.                 nAccum[1] = (nAccum[1]<<1) ^ cnCRC_64_L;  
  68.             }  
  69.             else   
  70.             {  
  71.                 nAccum[0] = (nAccum[0] << 1 ) | ((nAccum[1]&0x80000000)>>31);  
  72.                 nAccum[1] = nAccum[1] << 1;  
  73.             }  
  74.             nData[0] = (nData[0] << 1 ) | ((nData[1]&0x80000000)>>31);  
  75.             nData[1] = nData[1] << 1;      
  76.         }   
  77.   
  78.         TableCRCHigh[i] = nAccum[0];   
  79.         TableCRCLow[i]  = nAccum[1];   
  80.     }   
  81. }   
  82.   
  83. // 計(jì)算64位CRC值   
  84. unsigned long* CRC_64( unsigned char* aData, unsigned long aSize )   
  85. {   
  86.     unsigned long i;   
  87.     unsigned long nAccum[2];   
  88.     unsigned long temp;  
  89.     unsigned long index;  
  90.   
  91.     nAccum[0] = 0;  
  92.     nAccum[1] = 0;  
  93.   
  94.     for ( i = 0; i < aSize; i++ )   
  95.     {  
  96.         temp = nAccum[0];  
  97.         index = (temp >> 24) ^ *aData++;  
  98.   
  99.         nAccum[0] = ((nAccum[0] << 8 ) | ((nAccum[1]&0xff000000)>>24)) ^ TableCRCHigh[index];  
  100.         nAccum[1] = (nAccum[1] << 8) ^ TableCRCLow[index];  
  101.     }  
  102.   
  103.     return nAccum;   
  104. }
復(fù)制代碼








歡迎光臨 (http://www.torrancerestoration.com/bbs/) Powered by Discuz! X3.1