循環備援校驗 CRC的算法分析和程式實作
循環備援校驗 CRC的算法分析和程式實作
西南交通大學計算機與通信工程學院 劉東
摘要通信的目的是要把資訊及時可靠地傳送給對方，是以要求一個通信系統傳輸消息必須可靠與快速，在數字通信系統中可靠與快速往往是一對沖突。為了解決可靠性，通信系統都采用了差錯控制。本文詳細介紹了循環備援校驗CRC（Cyclic Redundancy Check）的差錯控制原理及其算法實作。
關鍵字通信 循環備援校驗 CRC-32 CRC-16 CRC-4
概述在數字通信系統中可靠與快速往往是一對沖突。若要求快速，則必然使得每個資料碼元所占地時間縮短、波形變窄、能量減少，進而在受到幹擾後産生錯誤地可能性增加，傳送資訊地可靠性下降。若是要求可靠，則使得傳送消息地速率變慢。是以，如何合理地解決可靠性也速度這一對沖突，是正确設計一個通信系統地關鍵問題之一。為保證傳輸過程的正确性，需要對通信過程進行差錯控制。差錯控制最常用的方法是自動請求重發方式（ARQ）、向前糾錯方式（FEC）和混合糾錯（HEC）。在傳輸過程誤碼率比較低時，用FEC方式比較理想。在傳輸過程誤碼率較高時，采用FEC容易出現“亂糾”現象。HEC方式則式ARQ和FEC的結合。在許多數字通信中，廣泛采用ARQ方式，此時的差錯控制隻需要檢錯功能。實作檢錯功能的差錯控制方法很多，傳統的有：奇偶校驗、校驗和檢測、重複碼校驗、恒比碼校驗、行列備援碼校驗等，這些方法都是增加資料的備援量，将校驗碼和資料一起發送到接受端。接受端對接受到的資料進行相同校驗，再将得到的校驗碼和接受到的校驗碼比較，如果二者一緻則認為傳輸正确。但這些方法都有各自的缺點，誤判的機率比較高。
循環備援校驗CRC（Cyclic Redundancy Check）是由分組線性碼的分支而來，其主要應用是二進制碼組。編碼簡單且誤判機率很低，在通信系統中得到了廣泛的應用。下面重點介紹了CRC校驗的原理及其 算法實作。
一、循環備援校驗碼（CRC ）CRC校驗采用多項式編碼方法。被處理的資料塊可以看作是一個n階的二進制多項式，由
。如一個8位二進制數10110101可以表示為： 。多項式乘除法運算過程與普通代數多項式的乘除法相同。多項式的加減法運算以2為模，加減時不進，錯位，和邏輯異或運算一緻。
采用CRC校驗時，發送方和接收方用同一個生成多項式g（x）,并且g（x）的首位和最後一位的系數必須為1。CRC的處理方法是：發送方以g（x）去除t（x），得到餘數作為CRC校驗碼。校驗時，以計算的校正結果是否為0為據，判斷資料幀是否出錯。
CRC校驗可以100％地檢測出所有奇數個随機錯誤和長度小于等于k（k為g（x）的階數）的突發錯誤。是以CRC的生成多項式的階數越高，那麼誤判的機率就越小。CCITT建議：2048 kbit/s的PCM基群裝置采用CRC-4方案，使用的CRC校驗碼生成多項式g（x）= 。采用16位CRC校驗，可以保證在 bit碼元中隻含有一位未被檢測出的錯誤 。在IBM的同步資料鍊路控制規程SDLC的幀校驗序列FCS中，使用CRC-16，其生成多項式g（x）= ；而在CCITT推薦的進階資料鍊路控制規程HDLC的幀校驗序列FCS中，使用CCITT-16，其生成多項式g（x）= 。CRC-32的生成多項式g（x）= 。CRC-32出錯的機率比CRC-16低 倍 。由于CRC-32的可靠性，把CRC-32用于重要資料傳輸十分合适，是以在通信、計算機等領域運用十分廣泛。在一些UART通信控制晶片（如MC6582、Intel8273和Z80-SIO）内，都采用了CRC校驗碼進行差錯控制；以太網卡晶片、MPEG解碼晶片中，也采用CRC-32進行差錯控制。
二、 CRC 校驗碼的算法分析CRC校驗碼的編碼方法是用待發送的二進制資料t（x）除以生成多項式g（x），将最後的餘數作為CRC校驗碼。其實作步驟如下：
（1） 設待發送的資料塊是m位的二進制多項式t（x），生成多項式為r階的g（x）。在資料塊的末尾添加r個0，資料塊的長度增加到m+r位，對應的二進制多項式為 。
（2） 用生成多項式g（x）去除 ，求得餘數為階數為r-1的二進制多項式y（x）。此二進制多項式y（x）就是t（x）經過生成多項式g（x）編碼的CRC校驗碼。
（3） 用 以模2的方式減去y（x），得到二進制多項式 。 就是包含了CRC校驗碼的待發送字元串。
從CRC的編碼規則可以看出，CRC編碼實際上是将代發送的m位二進制多項式t（x）轉換成了可以被g（x）除盡的m+r位二進制多項式 ，是以解碼時可以用接受到的資料去除g（x），如果餘數位零，則表示傳輸過程沒有錯誤；如果餘數不為零，則在傳輸過程中肯定存在錯誤。許多CRC的硬體解碼電路就是按這種方式進行檢錯的。同時 可以看做是由t（x）和CRC校驗碼的組合，是以解碼時将接收到的二進制資料去掉尾部的r位資料，得到的就是原始資料。
為了更清楚的了解CRC校驗碼的編碼過程，下面用一個簡單的例子來說明CRC校驗碼的編碼過程。由于CRC-32、CRC-16、CCITT和CRC-4的編碼過程基本一緻，隻有位數和生成多項式不一樣。為了叙述簡單，用一個CRC-4編碼的例子來說明CRC的編碼過程。
設待發送的資料t（x）為12位的二進制資料100100011100；CRC-4的生成多項式為g（x）= ，階數r為4，即10011。首先在t（x）的末尾添加4個0構成 ，資料塊就成了1001000111000000。然後用g（x）去除 ，不用管商是多少，隻需要求得餘數y（x）。下表為給出了除法過程。
| 除數次數 | 被除數/ g（x）/結果 | 餘數 |
| 1 001000111000000 | 100111000000 | |
| 1 0011 | ||
| 0 000100111000000 | ||
| 1 | 1 00111000000 | 1000000 |
| 1 0011 | ||
| 0 00001000000 | ||
| 2 | 1 000000 | 1100 |
| 1 0011 | ||
| 0 001100 |
從上面表中可以看出，CRC編碼實際上是一個循環移位的模2運算。對CRC-4，我們假設有一個5 bits的寄存器，通過反複的移位和進行CRC的除法，那麼最終該寄存器中的值去掉最高一位就是我們所要求的餘數。是以可以将上述步驟用下面的流程描述：
//reg是一個5 bits的寄存器
把reg中的值置0.
把原始的資料後添加r個0.
While (資料未處理完)
Begin
If (reg首位是1)
reg = reg XOR 0011.
把reg中的值左移一位，讀入一個新的資料并置于register的0 bit的位置。
End
reg的後四位就是我們所要求的餘數。
這種算法簡單，容易實作，對任意長度生成多項式的G（x）都适用。在發送的資料不長的情況下可以使用。但是如果發送的資料塊很長的話，這種方法就不太适合了。它一次隻能處理一位資料，效率太低。為了提高處理效率，可以一次處理4位、8位、16位、32位。由于處理器的結構基本上都支援8位資料的處理，是以一次處理8位比較合适。
為了對優化後的算法有一種直覺的了解，先将上面的算法換個角度了解一下。在上面例子中，可以将編碼過程看作如下過程：
由于最後隻需要餘數，是以我們隻看後四位。構造一個四位的寄存器reg，初值為0，資料依次移入reg0（reg的0位），同時reg3的資料移出reg。有上面的算法可以知道，隻有當移出的資料為1時，reg才和g（x）進行XOR運算；移出的資料為0時，reg不與g（x）進行XOR運算，相當與和0000進行XOR運算。就是說，reg和什麼樣的資料進行XOR移出的資料決定。由于隻有一個bit，是以有 種選擇。上述算法可以描述如下，
//reg是一個4 bits的寄存器
初始化t[]={0011,0000}
把reg中的值置0.
把原始的資料後添加r個0.
While (資料未處理完)
Begin
把reg中的值左移一位，讀入一個新的資料并置于register的0 bit的位置。
reg = reg XOR t[移出的位]
End
上面算法是以bit為機關進行處理的，可以将上述算法擴充到8位，即以Byte為機關進行處理，即CRC-32。構造一個四個Byte的寄存器reg，初值為0x00000000，資料依次移入reg0（reg的0位元組，以下類似），同時reg3的資料移出reg。用上面的算法類推可知，移出的資料位元組決定reg和什麼樣的資料進行XOR。由于有8個bit，是以有 種選擇。上述算法可以描述如下：
//reg是一個4 Byte的寄存器
初始化t[]＝{…}//共有 ＝256項
把reg中的值置0.
把原始的資料後添加r/8個0位元組.
While (資料未處理完)
Begin
把reg中的值左移一個位元組，讀入一個新的位元組并置于reg的第0個byte的位置。
reg = reg XOR t[移出的位元組]
End
算法的依據和多項式除法性質有關。如果一個m位的多項式t（x）除以一個r階的生成多項式g（x）， ，将每一位 （0=<k<m）提出來，在後面不足r個0後，單獨去除g（x），得到的餘式位 。則将 後得到的就是t（x）由生成多項式g（x）得到的餘式。對于CRC-32，可以将每個位元組在後面補上32個0後與生成多項式進行運算，得到餘式和此位元組唯一對應，這個餘式就是上面算法種t[]中的值，由于一個位元組有8位，是以t[]共有 ＝256項。多項式運算性質可以參見參考文獻[1]。這種算法每次處理一個位元組，通過查表法進行運算，大大提高了處理速度，故為大多數應用所采用。
三、 CRC-32 的程式實作。為了提高編碼效率，在實際運用中大多采用查表法來完成CRC-32校驗，下面是産生CRC-32校驗嗎的子程式。
unsigned long crc_32_tab[256]={
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,0x0edb8832,…, 0x5a05df1b, 0x2d02ef8d
};//事先計算出的參數表，共有256項，未全部列出。
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; //要移出的位元組的值
oldcrc=crc_32_tab[t]; //根據移出的位元組的值查表
c=DataBuf[charcnt]; //新移進來的位元組值
oldcrc32= (oldcrc32 << 8) | c; //将新移進來的位元組值添在寄存器末位元組中
oldcrc32=oldcrc32^oldcrc; //将寄存器與查出的值進行xor運算
charcnt++;
}
crc32=oldcrc32;
return crc32;
}
參數表可以先在PC機上算出來，也可在程式初始化時完成。下面是用于計算參數表的c語言子程式，在Visual C++ 6.0下編譯通過。
#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，類推
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個值
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);
}
}
結束語CRC校驗由于實作簡單，檢錯能力強，被廣泛使用在各種資料校驗應用中。占用系統資源少，用軟硬體均能實作，是進行資料傳輸差錯檢測地一種很好的手段。
參考文獻[1] 王新梅 肖國鎮. 糾錯碼－原理與方法.西安：西安電子科技大學出版社，2001
[2] 羅偉雄 韓力 原東昌 丁志傑 通信原理與電路. 北京：北京理工大學出版社，1999
[3] 王仲文 ARQ編碼通信.北京：機械工業出版社，1991
[4] Ross Williams, A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS. Document url: http://www.repairfaq.org/filipg/ ,1993