ＣＲＣ－３２的算法研究與程序?qū)崿F(xiàn)

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

關(guān)鍵詞:差錯控制；循環(huán)冗余校驗（CRC）；檢錯碼

0 引言

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

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

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

1 CRC校驗原理

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

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

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

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

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

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

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

2 CRC校驗的檢錯性能

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

CRC碼具有良好的檢錯性能，因而在數(shù)據(jù)通信中得到廣泛應(yīng)用。

3 CRC-32的程序?qū)崿F(xiàn)

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

下面是生成CRC-32校驗碼的子程序。參數(shù)表可以先在PC機上算出來，也可在程序初始化時完成。下面是用于計算參數(shù)表的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};//事先計算出的參數(shù)表，共有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; //要移出的字節(jié)的值

oldcrc=crc_32_tab[t]; //根據(jù)移出的字節(jié)的值查表

c=DataBuf[charcnt];//新移進來的字節(jié)值

oldcrc32= (oldcrc32 << 8) | c; //將新移進來的字節(jié)值添在寄存器末字節(jié)中

oldcrc32=oldcrc32^oldcrc; //將寄存器與查出的值進行xor運算

charcnt++;}

crc32=oldcrc32;

return crc32;

}

4 結(jié)束語

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

參考文獻

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

[2] 李壽強，循環(huán)冗余校驗CRC的算法分析及其實現(xiàn)方法(J).成都電子機械高等?？茖W校學報，2003，12.

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

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

[5] 王忠，李延社，游智勝.CRC算法設(shè)計與程序?qū)崿F(xiàn)(J).電子測量技術(shù)，2007，12（30）