通用型CRC校驗算法

1、CRC校驗簡單原理
CRC校驗方法是在通訊領域應用極廣的一類數據校驗方法，常用的包括CRC8、CRC16、CRC32（數字為生成多項式Gx-1），在嵌入式領域應用較多（DS18B20溫度傳感器正負溫度精度校驗（CRC查表法）），其校驗手段極為有效，但是其本生并不具有糾錯能力。假設有目前有效數據Kx（信息碼）有K位，生成多項式為Gx，經過有限次取模運算（等同于XOR，不借位的模2運算），求得冗余碼（FCS序列）有N位，則最終傳輸數據為Tx=Kx+N，而接收方在收到數據后用Tx%Gx（有限次XOR）是否為0判斷數據傳輸的正確性。
具體CRC校驗原理，還可以參看其他博客或者百度了解學習。
2、算法
經過上述的簡單說明，應該知道可以引入Kx、Gx、Tx、Rx，采用最高位對其（Gx補償）直接計算法，對數據比特串較短、時間要求不高的可以采用，使用必須要滿足以下要求：
*

① Gx補償位數滿足：Gx*2^(sizeof（Kx）-sizeof（Gx）)。 ② 運算次數滿足：sizeof（Kx）-sizeof（Gx）。 ③ CRC進行XOR運算滿足：CRC & (2^(sizeof(Kx)-1)。 ④ Rx還原滿足：CRC/（2^(sizeof(Kx)-sizeof(Gx)+1）。

其中sizeof表示取得元素在二進制下位長。
3、應用效果
(1)測試數據：
①Kx=110011,Gx=11001,Rx=1001
②Kx=101001,Gx=1101,Rx=001

/**** vision：v1.0.0 Author：LHC Gx:生成碼（生成多項式） KX：信息碼（要發送的數據部分） TX：真實發送的數據（Kx+Rx） Rx：CRC循環冗余檢驗碼（FCS序列） 目前Bug：單crc序列的首位或者多位為00時，將不會顯示，需要按添加位數人工補0 Data_Test:Kx=110011,Gx=11001,Rx=1001；Kx=101001,Gx=1101,Rx=001 Ways:直接計算法（位數直接與Kx對其），在簡單應用領域滿足要求，不適用極限時間要求 ****/#include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h>typedef unsigned int uint_32; #define BDH_SYSTEM 2 //用于表示輸出數據進制 uint_32 gx,kx,tx,rx; char gx_c[32],kx_c[32],rx_c[32],tx_c[32]; //最大數據串長度 char flag='y';uint_32 Binnary_Change_Decimal(char p[]) //把二進制數據串轉換為10進制 {int length =0,i=0;uint_32 sum=0;length =strlen(p);for(i=0;i<length;i++) //此處length不包含‘/0’{if(p[i]=='1') //帶權法算出10進制值sum =sum+(uint_32)pow(2,length-1-i); //pow函數用于計算y^x,x、y及返回值都是double型}//printf("%d\n",sizeof(sum));return sum; }void Input_Binary() //輸入為2進制比特串 {printf("please Kx with (binary) system:\n");gets(kx_c);kx =Binnary_Change_Decimal(kx_c);tx =kx; //首次把TX值賦值為KX，方便后面擴展printf("please Gx with (binary) system:\n");gets(gx_c);gx =Binnary_Change_Decimal(gx_c); }/*void Input_Decimal() //輸入為10進制模式 {printf("please Kx with (decimal) system:\n");scannf("%d",&kx);printf("please Gx with (decimal) system:\n");scannf("%d",&gx); }*/uint_32 CRC_Value(uint_32 *Kx,uint_32 Gx) //通用CRC核心函數 {uint_32 crc=0; //暫存每次XOR運算后的數據char kx_c_t[32]; //用于求出10進制轉2進制后的數據而設定的臨時變量int length_1 =0,length_2=0,i;char Gx_Binary[32];itoa(Gx,Gx_Binary,BDH_SYSTEM); //將int型數據轉換成數據串，2表示二進制length_1=strlen(Gx_Binary);*Kx =(*Kx)*(uint_32)pow(2,length_1-1); //還原出被除數 itoa(*Kx,kx_c_t,BDH_SYSTEM);length_2 =strlen(kx_c_t);crc =*Kx; //還原后的除數為首次運算的crcGx =Gx*(uint_32)pow(2,(length_2-length_1)); //湊出GX的長度和KX一樣長for(i=0;i<(length_2-length_1)+1;i++) //運算次數9-4+1、10-5+1{//if(crc&0x100) //只要滿足被除數KX的最高位與除數相與后不為0即可參加XOR運算，512、256if(crc&((uint_32)pow(2,length_2-1))) //2^0=1,次數起始為0{crc ^=Gx;printf("CRC1:%d\n",crc); //crc運算步驟crc <<=1;}else //最高位不為1移位{crc <<=1;printf("CRC2:%d\n",crc);}}//printf("pow:%d\n",(uint_32)pow(2,length_1));return crc/(uint_32)pow(2,(length_2-length_1)+1); //去除運算結束后多余的RX位數//此處必須注意運算結束后CRC都會被<<1，所以還原的CRC應在原基礎上>>1 }void main() {while(flag=='y'){fflush(stdin); //清空緩沖區Input_Binary();rx =CRC_Value(&kx,gx);itoa(kx,kx_c,BDH_SYSTEM); //把真實的KX算出itoa(rx,rx_c,BDH_SYSTEM);itoa(tx,tx_c,BDH_SYSTEM);strcat(tx_c,rx_c); //此處Tx為字符串的簡單拼接printf("\noutput (Kx):%s\n",kx_c); //輸出為2進制printf("output (GX):%s\n",gx_c);printf("output (Tx):%s\n",tx_c);printf("output (RX):%s\n",rx_c);tx =Binnary_Change_Decimal(tx_c);if(tx%gx==0) //檢測數據是否出錯printf("\nRX=%d,data is true!\n",(tx%gx));elseprintf("data have errors! please cheak!\n");printf("Have a want to continue?(y/n)\n");scanf("%s",&flag);} }

(2)運行效果

圖3.1 測試1

圖3.2 測試2

4、說明
首先，為什么我要大費周章的開發這樣一個程序呢？原因其實很簡單，網絡上關于CRC校驗的原代碼的確是很多，原理更是不計其數，但是有三點需要注意，其一，CRC校驗是有很多標準（CRC—16/IBM、CRC-8等）的，而這些標準的區別就在于采用的生成多項式不同，比如說CRC-8的Gx為：X^8+X2+X+1(100000101,注意最高位和最低位為1)，這就會造成你的直接引用卻無法得到預期的結果，在者CRC校驗本身并不難，而難的是如何用計算機實現，因為你要考慮很多因素，最多的就是數據邊界問題（char類型數據在Keil 5中容納數據為255），這個自己體會了；其二，當你去不斷參考別人的經驗代碼的時候，你會發現這樣一句話“CRC為嵌入式開發人員的法寶之一，但僅有少數人能掌握其核心算法！”，真的有這么難嗎，前輩的答案顯然是正確的，當你瀏覽很多個碼齡超過4年以上的前輩的代碼后你會發現，難于理解，因為數學思維極強，最后結果就會是直接不想看甚至放棄了，但是我編寫的則不同，簡單，易于理解，起源于謝希仁計網，通用型極高；其三，純屬個人愛好，還有就是特別討厭直接引用別人代碼，而不知所云（可能是個人強迫癥），以及編寫過后對收獲成果的一種成就感促使我這么做。
還有一點需要說明的是，從圖3.2可以看出，最后的Tx是錯誤的，原因是C98編譯器只統計數據的有效位，原Rx=001，有效數據為1，所以00被丟棄了，造成Kx%Gx出錯，這個是我故意留于檢測用，改正僅需加入2個0即可。
最后，我的成功是站在巨人的肩膀上的，我姑且這么說吧，模型參考了一位前輩的，但是前輩的核心思想有問題，其核心是自己總結的，這篇博客將會是我在CSDN的“LHC_黎明之光”博客號首篇原創文章，前路漫漫，望我們一同成長學習吧！如果發現錯誤的話，歡迎給我留言哦。

總結

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

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