一、循環(huán)冗余校驗(yàn)碼（CRC） 
CRC校驗(yàn)采用多項(xiàng)式編碼方法。被處理的數(shù)據(jù)塊可以看作是一個(gè)n階的二進(jìn)制多項(xiàng)式，由 。如一個(gè)8位二進(jìn)制數(shù)10110101可以表示為： 。多項(xiàng)式乘除法運(yùn)算過(guò)程與普通代數(shù)多項(xiàng)式的乘除法相同。多項(xiàng)式的加減法運(yùn)算以2為模，加減時(shí)不進(jìn)，錯(cuò)位，和邏輯異或運(yùn)算一致。 
采用CRC校驗(yàn)時(shí)，發(fā)送方和接收方用同一個(gè)生成多項(xiàng)式g（x）,并且g（x）的首位和最后一位的系數(shù)必須為1。CRC的處理方法是：發(fā)送方以g（x）去除t（x），得到余數(shù)作為CRC校驗(yàn)碼。校驗(yàn)時(shí)，以計(jì)算的校正結(jié)果是否為0為據(jù)，判斷數(shù)據(jù)幀是否出錯(cuò)。 
CRC校驗(yàn)可以100％地檢測(cè)出所有奇數(shù)個(gè)隨機(jī)錯(cuò)誤和長(zhǎng)度小于等于k（k為g（x）的階數(shù)）的突發(fā)錯(cuò)誤。所以CRC的生成多項(xiàng)式的階數(shù)越高，那么誤判的概率就越小。CCITT建議：2048 kbit/s的PCM基群設(shè)備采用CRC-4方案，使用的CRC校驗(yàn)碼生成多項(xiàng)式g（x）= 。采用16位CRC校驗(yàn)，可以保證在  bit碼元中只含有一位未被檢測(cè)出的錯(cuò)誤 。在IBM的同步數(shù)據(jù)鏈路控制規(guī)程SDLC的幀校驗(yàn)序列FCS中，使用CRC-16，其生成多項(xiàng)式g（x）= ；而在CCITT推薦的高級(jí)數(shù)據(jù)鏈路控制規(guī)程HDLC的幀校驗(yàn)序列FCS中，使用CCITT-16，其生成多項(xiàng)式g（x）= 。CRC-32的生成多項(xiàng)式g（x）= 。CRC-32出錯(cuò)的概率比CRC-16低 倍 。由于CRC-32的可靠性，把CRC-32用于重要數(shù)據(jù)傳輸十分合適，所以在通信、計(jì)算機(jī)等領(lǐng)域運(yùn)用十分廣泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）內(nèi)，都采用了CRC校驗(yàn)碼進(jìn)行差錯(cuò)控制；以太網(wǎng)卡芯片、MPEG解碼芯片中，也采用CRC-32進(jìn)行差錯(cuò)控制。 
二、CRC校驗(yàn)碼的算法分析 
CRC校驗(yàn)碼的編碼方法是用待發(fā)送的二進(jìn)制數(shù)據(jù)t（x）除以生成多項(xiàng)式g（x），將最后的余數(shù)作為CRC校驗(yàn)碼。其實(shí)現(xiàn)步驟如下： 
設(shè)待發(fā)送的數(shù)據(jù)塊是m位的二進(jìn)制多項(xiàng)式t（x），生成多項(xiàng)式為r階的g（x）。在數(shù)據(jù)塊的末尾添加r個(gè)0，數(shù)據(jù)塊的長(zhǎng)度增加到m+r位，對(duì)應(yīng)的二進(jìn)制多項(xiàng)式為 。 
用生成多項(xiàng)式g（x）去除 ，求得余數(shù)為階數(shù)為r-1的二進(jìn)制多項(xiàng)式y(tǒng)（x）。此二進(jìn)制多項(xiàng)式y(tǒng)（x）就是t（x）經(jīng)過(guò)生成多項(xiàng)式g（x）編碼的CRC校驗(yàn)碼。 
用 以模2的方式減去y（x），得到二進(jìn)制多項(xiàng)式 。 就是包含了CRC校驗(yàn)碼的待發(fā)送字符串。 
從CRC的編碼規(guī)則可以看出，CRC編碼實(shí)際上是將代發(fā)送的m位二進(jìn)制多項(xiàng)式t（x）轉(zhuǎn)換成了可以被g（x）除盡的m+r位二進(jìn)制多項(xiàng)式 ，所以解碼時(shí)可以用接受到的數(shù)據(jù)去除g（x），如果余數(shù)位零，則表示傳輸過(guò)程沒(méi)有錯(cuò)誤；如果余數(shù)不為零，則在傳輸過(guò)程中肯定存在錯(cuò)誤。許多CRC的硬件解碼電路就是按這種方式進(jìn)行檢錯(cuò)的。同時(shí) 可以看做是由t（x）和CRC校驗(yàn)碼的組合，所以解碼時(shí)將接收到的二進(jìn)制數(shù)據(jù)去掉尾部的r位數(shù)據(jù)，得到的就是原始數(shù)據(jù)。 
為了更清楚的了解CRC校驗(yàn)碼的編碼過(guò)程，下面用一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明CRC校驗(yàn)碼的編碼過(guò)程。由于CRC-32、CRC-16、CCITT和CRC-4的編碼過(guò)程基本一致，只有位數(shù)和生成多項(xiàng)式不一樣。為了敘述簡(jiǎn)單，用一個(gè)CRC-4編碼的例子來(lái)說(shuō)明CRC的編碼過(guò)程。 
設(shè)待發(fā)送的數(shù)據(jù)t（x）為12位的二進(jìn)制數(shù)據(jù)100100011100；CRC-4的生成多項(xiàng)式為g（x）= ，階數(shù)r為4，即10011。首先在t（x）的末尾添加4個(gè)0構(gòu)成 ，數(shù)據(jù)塊就成了1001000111000000。然后用g（x）去除 ，不用管商是多少，只需要求得余數(shù)y（x）。下表為給出了除法過(guò)程。 
除數(shù)次數(shù) 被除數(shù)/ g（x）/結(jié)果    余數(shù) 
0  1 001000111000000 100111000000 
1 0011 
0 000100111000000 
1  1 00111000000  1000000 
1 0011  
0 00001000000 
2  1 000000 1100 
1 0011 
0 001100 

從上面表中可以看出，CRC編碼實(shí)際上是一個(gè)循環(huán)移位的模2運(yùn)算。對(duì)CRC-4，我們假設(shè)有一個(gè)5 bits的寄存器，通過(guò)反復(fù)的移位和進(jìn)行CRC的除法，那么最終該寄存器中的值去掉最高一位就是我們所要求的余數(shù)。所以可以將上述步驟用下面的流程描述： 
//reg是一個(gè)5 bits的寄存器 
把reg中的值置0. 
把原始的數(shù)據(jù)后添加r個(gè)0. 
While (數(shù)據(jù)未處理完) 
Begin 
If (reg首位是1) 
reg = reg XOR 0011. 
把reg中的值左移一位，讀入一個(gè)新的數(shù)據(jù)并置于register的0 bit的位置。 
End 
reg的后四位就是我們所要求的余數(shù)。 
這種算法簡(jiǎn)單，容易實(shí)現(xiàn)，對(duì)任意長(zhǎng)度生成多項(xiàng)式的G（x）都適用。在發(fā)送的數(shù)據(jù)不長(zhǎng)的情況下可以使用。但是如果發(fā)送的數(shù)據(jù)塊很長(zhǎng)的話，這種方法就不太適合了。它一次只能處理一位數(shù)據(jù)，效率太低。為了提高處理效率，可以一次處理4位、8位、16位、32位。由于處理器的結(jié)構(gòu)基本上都支持8位數(shù)據(jù)的處理，所以一次處理8位比較合適。 
為了對(duì)優(yōu)化后的算法有一種直觀的了解，先將上面的算法換個(gè)角度理解一下。在上面例子中，可以將編碼過(guò)程看作如下過(guò)程： 
由于最后只需要余數(shù)，所以我們只看后四位。構(gòu)造一個(gè)四位的寄存器reg，初值為0，數(shù)據(jù)依次移入reg0（reg的0位），同時(shí)reg3的數(shù)據(jù)移出reg。有上面的算法可以知道，只有當(dāng)移出的數(shù)據(jù)為1時(shí)，reg才和g（x）進(jìn)行XOR運(yùn)算；移出的數(shù)據(jù)為0時(shí)，reg不與g（x）進(jìn)行XOR運(yùn)算，相當(dāng)與和0000進(jìn)行XOR運(yùn)算。就是說(shuō)，reg和什么樣的數(shù)據(jù)進(jìn)行XOR移出的數(shù)據(jù)決定。由于只有一個(gè)bit，所以有 種選擇。上述算法可以描述如下， 
//reg是一個(gè)4 bits的寄存器 
初始化t[]={0011,0000} 
把reg中的值置0. 
把原始的數(shù)據(jù)后添加r個(gè)0. 
While (數(shù)據(jù)未處理完) 
Begin 
把reg中的值左移一位，讀入一個(gè)新的數(shù)據(jù)并置于register的0 bit的位置。 
reg = reg XOR t[移出的位] 
End 
上面算法是以bit為單位進(jìn)行處理的，可以將上述算法擴(kuò)展到8位，即以Byte為單位進(jìn)行處理，即CRC-32。構(gòu)造一個(gè)四個(gè)Byte的寄存器reg，初值為0x00000000，數(shù)據(jù)依次移入reg0（reg的0字節(jié)，以下類(lèi)似），同時(shí)reg3的數(shù)據(jù)移出reg。用上面的算法類(lèi)推可知，移出的數(shù)據(jù)字節(jié)決定reg和什么樣的數(shù)據(jù)進(jìn)行XOR。由于有8個(gè)bit，所以有 種選擇。上述算法可以描述如下： 
//reg是一個(gè)4 Byte的寄存器 
初始化t[]＝{…}//共有 ＝256項(xiàng) 
把reg中的值置0. 
把原始的數(shù)據(jù)后添加r/8個(gè)0字節(jié). 
While (數(shù)據(jù)未處理完) 
Begin 
把reg中的值左移一個(gè)字節(jié)，讀入一個(gè)新的字節(jié)并置于reg的第0個(gè)byte的位置。 
reg = reg XOR t[移出的字節(jié)] 
End 
算法的依據(jù)和多項(xiàng)式除法性質(zhì)有關(guān)。如果一個(gè)m位的多項(xiàng)式t（x）除以一個(gè)r階的生成多項(xiàng)式g（x）， ，將每一位 （0= <k <m）提出來(lái)，在后面不足r個(gè)0后，單獨(dú)去除g（x），得到的余式位 。則將 后得到的就是t（x）由生成多項(xiàng)式g（x）得到的余式。對(duì)于CRC-32，可以將每個(gè)字節(jié)在后面補(bǔ)上32個(gè)0后與生成多項(xiàng)式進(jìn)行運(yùn)算，得到余式和此字節(jié)唯一對(duì)應(yīng)，這個(gè)余式就是上面算法種t[]中的值，由于一個(gè)字節(jié)有8位，所以t[]共有 ＝256項(xiàng)。多項(xiàng)式運(yùn)算性質(zhì)可以參見(jiàn)參考文獻(xiàn)[1]。這種算法每次處理一個(gè)字節(jié)，通過(guò)查表法進(jìn)行運(yùn)算，大大提高了處理速度，故為大多數(shù)應(yīng)用所采用。 
三、CRC-32的程序?qū)崿F(xiàn)。 
為了提高編碼效率，在實(shí)際運(yùn)用中大多采用查表法來(lái)完成CRC-32校驗(yàn)，下面是產(chǎn)生CRC-32校驗(yàn)嗎的子程序。 
unsigned long  crc_32_tab[256]={ 
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,0x0edb8832,…, 0x5a05df1b, 0x2d02ef8d 
};//事先計(jì)算出的參數(shù)表，共有256項(xiàng)，未全部列出。 

unsigned long GenerateCRC32(char xdata * DataBuf,unsigned long  len) 
{ 
unsigned long oldcrc32; 
unsigned long crc32; 
unsigned long oldcrc; 
unsigned  int charcnt; 
        char c,t; 
oldcrc32 = 0x00000000; //初值為0 
    charcnt=0; 
while (len--) { 
                t= (oldcrc32 >> 24) & 0xFF;  //要移出的字節(jié)的值 
oldcrc=crc_32_tab[t];        //根據(jù)移出的字節(jié)的值查表 
                c=DataBuf[charcnt];          //新移進(jìn)來(lái)的字節(jié)值 
                oldcrc32= (oldcrc32 < < 8) | c;  //將新移進(jìn)來(lái)的字節(jié)值添在寄存器末字節(jié)中 
                oldcrc32=oldcrc32^oldcrc;    //將寄存器與查出的值進(jìn)行xor運(yùn)算 
                charcnt++; 
} 
        crc32=oldcrc32; 
        return crc32; 
} 
參數(shù)表可以先在PC機(jī)上算出來(lái)，也可在程序初始化時(shí)完成。下面是用于計(jì)算參數(shù)表的c語(yǔ)言子程序，在Visual C++ 6.0下編譯通過(guò)。 
#include <stdio.h> 
unsigned long int crc32_table[256]; 
unsigned long int ulPolynomial = 0x04c11db7; 
unsigned long int Reflect(unsigned long int ref, char ch) 
{ unsigned long int value(0); 
// 交換bit0和bit7，bit1和bit6，類(lèi)推 
for(int i = 1; i < (ch + 1); i++) 
{ if(ref & 1) 
value |= 1 < < (ch - i); 
    ref >>= 1; } 
return value; 
} 
init_crc32_table() 
{ unsigned long int crc,temp; 
// 256個(gè)值 
for(int i = 0; i <= 0xFF; i++) 
{  temp=Reflect(i, 8); 
crc32_table[i]= temp < < 24; 
for (int j = 0; j < 8; j++){ 
    unsigned long int t1,t2; 
unsigned long int flag=crc32_table[i]&0x80000000; 
t1=(crc32_table[i] < < 1); 
if(flag==0) 
  t2=0; 
else 
  t2=ulPolynomial; 
crc32_table[i] =t1^t2 ; } 
crc=crc32_table[i]; 
crc32_table[i] = Reflect(crc32_table[i], 32); 
} 
} 
結(jié)束語(yǔ) 
    CRC校驗(yàn)由于實(shí)現(xiàn)簡(jiǎn)單，檢錯(cuò)能力強(qiáng)，被廣泛使用在各種數(shù)據(jù)校驗(yàn)應(yīng)用中。占用系統(tǒng)資源少，
用軟硬件均能實(shí)現(xiàn)，是進(jìn)行數(shù)據(jù)傳輸差錯(cuò)檢測(cè)地一種很好的手段。