找回密碼
 立即注冊

QQ登錄

只需一步,快速開始

搜索
查看: 3070|回復(fù): 0
打印 上一主題 下一主題
收起左側(cè)

CRC---循環(huán)冗余校驗(yàn)碼

[復(fù)制鏈接]
跳轉(zhuǎn)到指定樓層
樓主
ID:94349 發(fā)表于 2015-11-2 14:41 | 只看該作者 回帖獎(jiǎng)勵(lì) |倒序?yàn)g覽 |閱讀模式
CRC---循環(huán)冗余校驗(yàn)碼

CRC的基本原理

      基本原理:在K位信息碼后再拼接R位的校驗(yàn)碼,整個(gè)編碼長度為N位,因此,這種編碼又叫(N,K)碼。對于一個(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)碼的具體生成過程為:假設(shè)發(fā)送信息用信息多項(xiàng)式C(X)表示,將C(x)左移R位,則可表示成C(x)*2R,這樣C(x)的右邊就會空出R位,這就是校驗(yàn)碼的位置。通過C(x)*2R除以生成多項(xiàng)式G(x)得到的余數(shù)就是校驗(yàn)碼。



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

      在國際標(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碼通常用來傳送6-bit字符串。CRC-16及CRC-CCITT碼則用是來傳送8-bit字符,其中CRC-16為美國采用,而CRC-CCITT為歐洲國家所采用。CRC-32碼大都被采用在一種稱為Point-to-Point的同步傳輸中。下面以最常用的CRC-16為例來說明其生成過程。

      CRC-16碼由兩個(gè)字節(jié)構(gòu)成,在開始時(shí)CRC寄存器的每一位都預(yù)置為1,然后把CRC寄存器與8-bit的數(shù)據(jù)進(jìn)行異或,之后對CRC寄存器從高到低進(jìn)行移位,在最高位(MSB)的位置補(bǔ)零,而最低位(LSB,移位后已經(jīng)被移出CRC寄存器)如果為1,則把寄存器與預(yù)定義的多項(xiàng)式碼進(jìn)行異或,否則如果LSB為零,則無需進(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值。

    碼字長度為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ì)算過程

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

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

      3.CRC寄存器向右移一位,MSB補(bǔ)零,移出并檢查LSB。

      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)換成對應(yīng)的R+1位二進(jìn)制數(shù)。

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

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

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



CRC64   


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

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

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

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




分享到:  QQ好友和群QQ好友和群 QQ空間QQ空間 騰訊微博騰訊微博 騰訊朋友騰訊朋友
收藏收藏 分享淘帖 頂 踩
回復(fù)

使用道具 舉報(bào)

您需要登錄后才可以回帖 登錄 | 立即注冊

本版積分規(guī)則

小黑屋|51黑電子論壇 |51黑電子論壇6群 QQ 管理員QQ:125739409;技術(shù)交流QQ群281945664

Powered by 單片機(jī)教程網(wǎng)

快速回復(fù) 返回頂部 返回列表