ＣＲＣ－３２的算法研究與程序實現

摘要:循環冗余校臉CRC(Cyclic Redundancy Check)是一種編碼簡單，且高效、可靠的差錯控制方法，廣泛應用于工業測控及數據通信領城。首先分析了CRC的校驗原理、冗余位的產生方法、性能分析。然后以CRC-32為例，給出了軟件實現算法的C語言代碼。

關鍵詞:差錯控制；循環冗余校驗（CRC）；檢錯碼

0 引言

檢錯（和糾錯）技術的基本思想都是利用發送端發送的所有消息比特產生一個或多個用于檢錯（和糾錯）的特殊比特（如圖1所示）。

實現檢錯功能的差錯控制方法很多，傳統的有：奇偶校驗、校驗和檢測、重復碼校驗、恒比碼校驗、行列冗余碼校驗等，這些方法都是增加數據的冗余量，將校驗碼和數據一起發送到接受端。接受端對接受到的數據進行相同校驗，再將得到的校驗碼和接受到的校驗碼比較，如果二者一致則認為傳輸正確。

循環冗余校驗CRC（Cyclic Redundancy Check）是由分組線性碼的分支而來，其主要應用是二元碼組。編碼簡單且誤判概率很低，在通信系統中得到了廣泛的應用。

1 CRC校驗原理

CRC校驗主要是利用線性編碼理論，其基本原理如下:

在發送端，根據要傳送的k位二進制碼信息序列，以一定的規則產生一個校驗用的r位監督碼(即CRC碼)，并附在信息序列后邊，構成一個新的（k+r）位二進制碼序列，發送出去；在接收端，根據信息碼和CRC碼之間所遵循的規則進行校驗，以確定傳送中是否出錯。

校驗碼R是通過對數據序列D進行二進制除法取余運算得到的，它被一個稱為生成多項式的（r+1）位二進制序列G=[grgr-1…g1g0]來除，用多項式表示為

其中xrD(x)表示將數據序列D左移r位(即在D的末尾再增加r個位)， Q(x)代表這一除法所得的商，R(x)就是所需的余式.這一運算關系還可以用下式來表示：

其中，Re[]表示對括號內的式子進行取余運算。

校驗碼的編碼計算如上所述，而校驗過程則是對M序列直接進行除法取余運算，即

所得到的余式Ｒ（x）若為0表示數據正確，否則認為發生錯誤。

2 CRC校驗的檢錯性能

CRC校驗碼的檢錯能力與其生成多項式G(X)密切相關。G(X)的次數越高，其檢錯能力越強。若CRC校驗的生成多項式G(X)的最高次冪為r，則該CRC校驗碼的檢錯性能如下:(1)可檢出所有奇數個錯誤；(2)可檢出所有2bit個錯誤；(3)可檢出所有長度<=r個bit的突發錯誤；(4)對于長度二r+1個比特的突發錯誤，其漏檢率僅為:1/2r-1；(5)對于長度>r+1個比特的突發錯誤，其漏檢率僅為:1/2r；

CRC碼具有良好的檢錯性能，因而在數據通信中得到廣泛應用。

3 CRC-32的程序實現

編寫CRC校驗程序有2種辦法：一種為計算法，計算法就是依據CRC校驗碼的產生原理來設計程序。其優點是模塊代碼少，修改靈活，可移植性好;其缺點為計算量大。另一種為查表法，查表法的優缺點與計算法的正好相反，可以大大降低CPU的運算時間。這種方法應用比較廣泛。

下面是生成CRC-32校驗碼的子程序。參數表可以先在PC機上算出來，也可在程序初始化時完成。下面是用于計算參數表的c語言子程序，在Visual C++ 6.0下編譯通過。

#include

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;

}

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 longlen)

{unsigned long oldcrc32;

unsigned long crc32;

unsigned long oldcrc;

unsignedint 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;

}

4 結束語

本文給出的CRC-32檢驗碼的C語言源程序，已經在PC機上驗證通過，并且應用與基于CMX7143芯片的數傳電臺中，具有良好的可移植性。

參考文獻

[1]尹長川，郝建軍，羅濤等譯.數字通信基礎(M). 北京:機械工業出版社，2005原書第二版.

[2] 李壽強，循環冗余校驗CRC的算法分析及其實現方法(J).成都電子機械高等專科學校學報，2003，12.

[3]王新梅，肖國鎮編著.糾錯碼原理與方法.西安:西安電子科技大學出版社，2001

[4] 張海林，葛思擘，施仁.一種新型循環冗余碼校驗算法的研究(J)。西安交通大學學報，2003，10(37).

[5] 王忠，李延社，游智勝.CRC算法設計與程序實現(J).電子測量技術，2007，12（30）