大漠落日

最近因為需要做一個上傳客戶端，所以又溫習了一下CRC校驗。

一、什么是CRC校驗
     循環(huán)校驗碼（Jyclic Redundancy Check,簡稱CRC碼): 是數據通信領域中最常用的一種差錯校驗碼，其特征是信息字段和校驗字段的長度可以任意選定。

二、CRC校驗計算
      CRC碼是由兩部分組成，前部分是信息碼，就是需要校驗的信息，后部分是校驗碼，如果CRC碼共長n個bit，信息碼長k個bit，它的編碼規(guī)則是：
      1、首先將原信息碼(kbit)左移r位(k+r=n),對應多項式為m(x)。
      2、運用一個生成R次多項式g(x)（也可看成二進制數）用模2除上面的式子，得到的余數就是校驗碼，r=R。
      非常簡單，要說明的：模2除就是在除的過程中用模2加，模2加實際上就是我們熟悉的異或運算，就是加法不考慮進位，公式是：    
      0+0=1+1=0,1+0=0+1=1，即‘異’則真，‘非異’則假。
      由此得到定理：a+b+b=a 也就是‘模2減’和‘模2加’直值表完全相同。 
      有了加減法就可以用來定義模2除法，于是就可以用生成多項式g(x)生成CRC校驗碼。
      例如：代碼1010111對應的多項式為x⁶+x⁴+x²+x+1，而多項式為x⁵+x³+x²+x+1對應的代碼101111。
      現在計算 信息碼1011001（多項式為x⁶+x⁴+x³+1），生成多項式g(x)=x⁴+x³+1（信息碼為11001）的CRC，計算過程如下
      step1:   1011001左移4位得到10110010000
      steo2:   采用多項式除法:  得余數為: 1010     (即校驗字段為：1010）
      CRC碼即為1011001,1010 (逗號前為信息碼，后為校驗碼)

三、編程實現
     

uint cal_crc(uchar *ptr, uchar len) { 
    uint crc; 
    uchar i; 
    crc=0; 
    while (len--!=0) { 
        for (i=0x80; i!=0; i/=2) { 
            if ((crc&0x8000)!=0){
                crc*=2; crc^=0x1021;
            } else crc*=2; 
            if ((*ptr&i)!=0)
                crc^=0x1021; 
        } 
    ptr++; 
    } 
    return(crc); 
} 

      

 四，實際應用
      發(fā)送方：發(fā)出的傳輸字段為:  1 0 1 1 0 0 1 1 0 10
                      信息字段       校驗字段
      接收方：使用相同的生成碼進行校驗:接收到的字段/生成碼（二進制除法）
                     如果能夠除盡，則正確

注：參考了網上很多資料
CRC校驗源碼分析
CRC算法分析和程序實現（pdf下載）《—— 重點推薦