數據傳輸過程中差錯不可避免，接收方在收到數據后，先對數據的準確性進行校驗，異常數據特殊處理。校驗的方式有很多，常見的有CRC循環冗余校驗。CRC算法檢錯能力強，效率高，是信息通信領域最為普遍的校驗方式。CRC校驗算法應用廣，且實現算法簡單，但其背后的涉及的糾錯碼的代數理論，不是一般人可以理解的。所以，在不理解循環校驗原理的基礎上，貿然分析算法流程是不明智的，根據源碼倒推實現流程，也不會明白為什么要這樣執行？一般關注CRC以應用為主，以及為什么都是CRC16算法，得出的結果卻不同。本文的意圖只是這個。

1、CRC定義
假設要發送996這個數字，將其除以7余數為2，發送時將996-2合并后發出，接收方按同樣運算判斷數據包是否正確。同樣的源數據，因為除數不同而余數不同。CRC算法也是因為類似原理。

CRC算法中參數解釋如下：
1、除法定為模2除法

2、除數定為多項式，如x^16+x12+x^5+1（0x1021） 2¹⁶⁺²12+2⁵⁺²0=65536+4096+32+1= 69665=0x11021 。依據不可描述的標準，多項式最高位和最低位必須為1，所以一般簡化為0x1021，忽略最高位，記為Poly。

3、因為多項式長度不同，一般分為CRC8、CRC16和CRC32，因為模2除法簡化為異或和移位操作，其初始值為Init。

4、還有三個參數

RefIn：待測數據的每個字節是否按位反轉，TRUE或FALSE。

RefOut：在計算后之后，異或輸出之前，整個數據是否按位反轉，TRUE或FALSE。

XorOut：計算結果與此參數異或后得到最終的CRC值。但是任何數與0異或還是它本身，所以該值為0時可以忽略。

5、因為多項式Poly，初始值等差異，CRC有不同的版本。理論上是多項式是可以隨意定義的，但是通用的標準多項式是經過數學推導的，盡可能的保證不同的數據求出的CRC值不相同。

6、參考https://crccalc.com/ 的定義，不同場景使用不同的多項式。


2、CRC算法與模板
通用版的CRC算法如下：
CRC8

//以CRC-8/ITU為參考 unsigned char CRC8(unsigned char *data, unsigned int len) {unsigned char i;unsigned char poly = 0x07;//與表中的Poly列對應unsigned char init = 0x00;//與表中的Init列對應unsigned char wChar = 0;while (len--){wChar = *(data++);//RefIn為TRUE時執行，FALSE時刪除//InvertUint8(&wChar,&wChar);init ^= wChar;for( i = 0;i < 8;i++){if(init & 0x80){init = (init << 1) ^ poly;}else{init = init << 1;}}}//RefOut為TRUE時執行，FALSE時刪除//InvertUint8(&init,&init);//與XorOut進行異或，若為0時執行或不執行沒有區別init=init^0x55;return (init);}

CRC16

//以CRC-16/X-25為參考 unsigned short CRC16(unsigned char *data, unsigned int len) {unsigned char i;unsigned short poly = 0x1021;//與表中的Poly列對應unsigned short init = 0xFFFF;//與表中的Init列對應unsigned char wChar = 0;while (len--){wChar = *(data++);//RefIn為TRUE時執行，FALSE時刪除InvertUint8(&wChar,&wChar);init ^= (wChar << 8);for( i = 0;i < 8;i++){if(init & 0x8000){init = (init << 1) ^ poly;}else{init = init << 1;}}}//RefOut為TRUE時執行，FALSE時刪除InvertUint16(&init,&init);//與XorOut進行異或，若為0時執行或不執行沒有區別init=init^0xFFFF;return (init); }

CRC8和CRC16，根據不同版本的參數差異，查表，將模板里的參數改為對應值，即可得出對應版本的CRC值。其中涉及到數據反轉的代碼如下：

void InvertUint8(unsigned char *DesBuf, unsigned char *SrcBuf) {int i;unsigned char temp = 0;for(i = 0; i < 8; i++){if(SrcBuf[0] & (1 << i)){temp |= 1 << (7 - i);}}*DesBuf = temp; }void InvertUint16(unsigned short *DesBuf, unsigned short *SrcBuf) {int i;unsigned short temp = 0;for(i = 0; i < 16; i++){if(SrcBuf[0] & (1 << i)){temp |= 1 << (15 - i);}}*DesBuf = temp; }

3、查表
針對上面的代碼，求解CRC移位異或運算的循環體，對時間要求較高的場景，可以提前計算生成數值表，以空間換時間。

//以CRC-8/ITU為例，生成數組查表 void creatTable(void) {unsigned char i,init;unsigned short j;for(j=0;j<=255;j++){if(j%16==0){printf("\r\n");}init=j;for( i = 0;i < 8;i++){if(init & 0x80){init = (init << 1) ^ 0x07;//以實際poly為準;}else{init = init << 1;}}printf("0x%02X,", init);} }

確定poly后，假設init為0-255，求出256個參數，轉為一維數組。如上，以CRC-8/ITU為例，生成數組如下：

原來的直接計算改為查表，如下：

//以CRC-8/ITU為參考 unsigned char CRC8(unsigned char *data, unsigned int len) {unsigned char i;unsigned char poly = 0x07;//與表中的Poly列對應unsigned char init = 0x00;//與表中的Init列對應unsigned char wChar = 0;while (len--){wChar = *(data++);//RefIn為TRUE時執行，FALSE時刪除//InvertUint8(&wChar,&wChar);init ^= wChar;/************************************************************/ #if 1init=crcTable[init];//查表，空間換時間 #elsefor( i = 0;i < 8;i++){if(init & 0x80){init = (init << 1) ^ poly;}else{init = init << 1;}} #endif /************************************************************/}//RefOut為TRUE時執行，FALSE時刪除//InvertUint8(&init,&init);//與XorOut進行異或，若為0時執行或不執行沒有區別init=init^0x55;return (init); }

對于CRC16也可以使用查表法。

總結

以上是生活随笔為你收集整理的【嵌入式算法】CRC校验算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。