CRC校驗碼算法的研究與實現

王根義

（陜西職業技術學院 陜西 西安 710100）

在通信系統的數據傳輸過程中，由于信道中各種復雜因素的影響，往往使傳輸的信號受到干擾，造成誤碼的出現。接收方為了檢查所接收的數據是否有誤碼，可采用多種檢測方法。差錯控制編碼是目前數據傳輸過程中普遍采用的一種提高數據通信可靠性的方法，而CRC是一種在實際通信中應用很廣泛的差錯控制編碼，具有很強的檢錯能力。但由于國內對CRC技術應用的不夠深入和不夠廣泛，許多檢錯改錯工程死板地套用有限的模式，浪費了資源，本論文就是為了提高和推廣國內的CRC技術，讓相關人員能根據實際需要，靈活地采用CRC方法進行檢錯而撰寫的。

1 有關符號的約定

模2除法就是在除的過程中用模2減法來減。模2加或模2減就是異或，結果都相同。本論文用“⊕”表示模2加，用“^” 表示異或，用“mod”表示求模。

2 分析研究按模2mod的相關性能

1）設信息碼段為 h1h2h3h4h5h6H，生成多項式 g（x）的代碼為11021H，分析研究計算CRC碼的校驗碼段的過程。

設 （h1h2h3h4h5h6，0000H）按模 2mod（11021H）= （m3m2m 1m0H）。

如果先求出（h1h2，0000 H）按模 2mod （11021H）= （r3r2 r1r0H）

那么 [（h3h4h5h6，0000H）⊕（r3r2r1r0，0000 H）]按模 2 mod（11021H）= （m3m2m1m0H）。

如果先求出 [（h3h4，0000H）⊕（r3r2， 0000 H）]按模2mod（11021H）=（d3d2d1d0H）

那么[（h5h6，0000H）⊕（d3d2，0000 H）]按模 2mod （11021H）⊕（d1d0，00H） = （m3m2m1m0H）。

2）分析研究（h1H⊕h2H，0000H）按模 2mod（11021H）

設（h1H）=（a3a2a1a0B），（h2H）=（b3b2b1b0B），則

（h1H⊕h2H，0000H）按模 2mod （11021H）[1]

=（a3×219）B 按模 2mod （11021H）⊕

（a2×218）B 按模 2mod （11021H）⊕

（a1×217）B 按模 2mod （11021H）⊕

（a0×216）B 按模 2mod （11021H）⊕

（b3×219）B 按模 2mod （11021H）⊕

（b2×218）B 按模 2mod （11021H）⊕

（b1×217）B+（b0×216）B

可見， 如果 a3和 b3、a2和 b2、a1和 b1或 a0和 b0這 4對二進制數中，哪一對中的兩個二進制數相等，則這一對二進制數對余數的作用就抵消了。

3 求CRC碼的軟件設計

在本論文的內容2中得到的結論非常重要，由此可以研制出用C語言編程求CRC校驗碼段的各種方法，在下面列舉3種方法。

1）方法 1[2－4]

typedef unsigned char uchar；

typedef unsigned int uint；

code uchar crcbuff[]={0xe3，0xd2，0x0d，0x06，0x00，0x00，0x00，0x00}；

uint crc； //CRC碼

uint crc16l（uchar*ptr，uchar len）；

void main（void）

{

uchar*ptr；

crc=0； //CRC初值

ptr=crcbuff； //指向第一個 Byte數據

crc=crc16l（ptr，8）；

while（1）；

}

uint crc16l （uchar*ptr，uchar len） /*ptr為數據指針，len為數據長度（數據元素的個數，8個字節數）*/

{

uchar i；

while（len－－）

{

for（i=0x80； i； i＞＞=1）

{

if（（crc&0x8000） ^（*ptr&i）） {crc＜＜=1； crc^=0x1021；}

//生成多項式CRC－CCITT=X16+X12+X5+1對應的代碼為11021

else crc＜＜=1；

}

ptr++；

}

return（crc）；

}

執行結果 crc=0x5f1d；

如想驗證是否正確，可在程序中改 。

code uchar crcbuff_fan_result[]={0xe3，0xd2，0x0d，0x06，0x00，0x00，0x00，0x00，0x1d，0x5f}；

ptr=crcbuff_fan_result；

crc=crc16l（ptr，10）；

執行結果 crc=0；符合 CRC校驗的原理。

此程序的難點在于把移位前crc的Bit15與數據對應的Bit（即*ptr&i）做XOR運算，根據此結果來決定是否執行crc^=0x1021；兩次異或運算與原值相同。

2）方法 2:查表法[5－7]

下面給出半字節查表的處理程序。

typedef unsigned char uchar；

typedef unsigned int uint；

code uint crc_ba[16]={

0x0000， 0x1021， 0x2042， 0x3063， 0x4084， 0x50a5，0x60c6， 0x70e7， 0x8108， 0x9129， 0xa14a， 0xb16b， 0xc18c，0xd1ad， 0xe1ce， 0xf1ef，

}；

uint bancrc（uchar*ptr，uchar len）

{

uchar da； uint temp；

while（len－－!=0）

{temp=crc；

temp＞＞=12；

da=（uchar）temp； //

crc ＜＜=4；

crc^=crc_ba[da^（*ptr/16）]；

da= （（uchar）（crc/256）/16）；

crc ＜＜=4；

crc^=crc_ba[da^（*ptr&0fh）]；

ptr++；

}

return（crc）；

}

3）方法 3[3，8－9]

typedef unsigned char uchar；

typedef unsigned int uint；

uint reg；

uint crcdsp（uint reg， uchar data）

//reg為上次求得的CRC值，data為將要處理的8 bit數據流

{

uint msb；//保存reg將移出的最高1 bit信息。

uint data1；//保存 data的信息，但 data1為 16 bit。

uint gx=0x8005，i=0；/*i為左移次數，gx為生成多項式*/

data1= （uint）data；

data1 ＜＜=8；

reg=reg^data；

do

{

msb=reg&0x8000；

reg=reg＜＜ 1；

if（msb==0x8000）

{

reg=reg^gx；

}

i++；

}

while（i＜ 8）；

return （reg）；

}

以上為處理每一個8 bit數據流的子程序，在計算整個數據流的CRC校驗碼時，只需將reg的初值置（為0x0000），和第一個8 bit的數據作為函數的兩個實參傳遞給上述函數求CRC值，之后，即可將上次求得的CRC值和本次將要處理的8 bit數據作為函數實參傳遞給上述函數的形參進行處理即可，最終返回的reg值便是所想得到的整個數據流的CRC校驗值。

上面提出的3種方法經過上機實驗均證明正確可行，各有其特點。

4 結束語

本文創新點：找出了系數為1 bit二進制數的多項式按2模mod運算的新規律，根據按2模mod運算的這些性質，提出了計算任意長度CRC校驗碼的多種算法，并給出了具體實現這些算法的源程序。文中提出的CRC校驗碼的多種算法，可根據計算機的特點，靈活地應用在不同的工程當中。實踐證明，該算法正確可靠，可以降低差錯效驗的成本，提高差錯效驗的效率。

[1]苗長云.現代通信原理及應用[M].北京:電子工業出版社，2005.

[2]陶亞雄.現代通信原理[M].北京:電子工業出版社，2003.

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

[4]Cunningham D G，PH.D，Lane W G，et al.千兆以太網[M].北京：清華大學出版社，2000.

[5]黃軍.用Dephi編寫串口通信程序[M].北京：人民郵電出版社，2001.

[6]朱榮華.一種CRC并行計算原理及實現方法[J].電子學報，1999，27（4）:143-145.ZHU Rong-hua.The principle and realization of a parallel computing method [J].Chinese Journal of Electronics，1999，27（4）:143-145.

[7]黃月江.信息安全保密：現代與未來戰爭的信息衛士[M].北京：國防工業出版社，2008.

[8]楊義先.現代密碼新理論[M].北京：科學出版社，2002.

[9]譚方勇.網絡安全技術實用教程 [M].重慶：重慶出版社，2000.