CRC校驗(yàn)碼算法的研究與實(shí)現(xiàn)

王根義

（陜西職業(yè)技術(shù)學(xué)院 陜西 西安 710100）

在通信系統(tǒng)的數(shù)據(jù)傳輸過程中，由于信道中各種復(fù)雜因素的影響，往往使傳輸?shù)男盘柺艿礁蓴_，造成誤碼的出現(xiàn)。接收方為了檢查所接收的數(shù)據(jù)是否有誤碼，可采用多種檢測方法。差錯控制編碼是目前數(shù)據(jù)傳輸過程中普遍采用的一種提高數(shù)據(jù)通信可靠性的方法，而CRC是一種在實(shí)際通信中應(yīng)用很廣泛的差錯控制編碼，具有很強(qiáng)的檢錯能力。但由于國內(nèi)對CRC技術(shù)應(yīng)用的不夠深入和不夠廣泛，許多檢錯改錯工程死板地套用有限的模式，浪費(fèi)了資源，本論文就是為了提高和推廣國內(nèi)的CRC技術(shù)，讓相關(guān)人員能根據(jù)實(shí)際需要，靈活地采用CRC方法進(jìn)行檢錯而撰寫的。

1 有關(guān)符號的約定

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

2 分析研究按模2mod的相關(guān)性能

1）設(shè)信息碼段為 h1h2h3h4h5h6H，生成多項(xiàng)式 g（x）的代碼為11021H，分析研究計(jì)算CRC碼的校驗(yàn)碼段的過程。

設(shè) （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）

設(shè)（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對二進(jìn)制數(shù)中，哪一對中的兩個二進(jìn)制數(shù)相等，則這一對二進(jìn)制數(shù)對余數(shù)的作用就抵消了。

3 求CRC碼的軟件設(shè)計(jì)

在本論文的內(nèi)容2中得到的結(jié)論非常重要，由此可以研制出用C語言編程求CRC校驗(yàn)碼段的各種方法，在下面列舉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數(shù)據(jù)

crc=crc16l（ptr，8）；

while（1）；

}

uint crc16l （uchar*ptr，uchar len） /*ptr為數(shù)據(jù)指針，len為數(shù)據(jù)長度（數(shù)據(jù)元素的個數(shù)，8個字節(jié)數(shù)）*/

{

uchar i；

while（len－－）

{

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

{

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

//生成多項(xiàng)式CRC－CCITT=X16+X12+X5+1對應(yīng)的代碼為11021

else crc＜＜=1；

}

ptr++；

}

return（crc）；

}

執(zhí)行結(jié)果 crc=0x5f1d；

如想驗(yàn)證是否正確，可在程序中改 。

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

ptr=crcbuff_fan_result；

crc=crc16l（ptr，10）；

執(zhí)行結(jié)果 crc=0；符合 CRC校驗(yàn)的原理。

此程序的難點(diǎn)在于把移位前crc的Bit15與數(shù)據(jù)對應(yīng)的Bit（即*ptr&i）做XOR運(yùn)算，根據(jù)此結(jié)果來決定是否執(zhí)行crc^=0x1021；兩次異或運(yùn)算與原值相同。

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

下面給出半字節(jié)查表的處理程序。

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數(shù)據(jù)流

{

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

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

uint gx=0x8005，i=0；/*i為左移次數(shù)，gx為生成多項(xiàng)式*/

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數(shù)據(jù)流的子程序，在計(jì)算整個數(shù)據(jù)流的CRC校驗(yàn)碼時，只需將reg的初值置（為0x0000），和第一個8 bit的數(shù)據(jù)作為函數(shù)的兩個實(shí)參傳遞給上述函數(shù)求CRC值，之后，即可將上次求得的CRC值和本次將要處理的8 bit數(shù)據(jù)作為函數(shù)實(shí)參傳遞給上述函數(shù)的形參進(jìn)行處理即可，最終返回的reg值便是所想得到的整個數(shù)據(jù)流的CRC校驗(yàn)值。

上面提出的3種方法經(jīng)過上機(jī)實(shí)驗(yàn)均證明正確可行，各有其特點(diǎn)。

4 結(jié)束語

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

[1]苗長云.現(xiàn)代通信原理及應(yīng)用[M].北京:電子工業(yè)出版社，2005.

[2]陶亞雄.現(xiàn)代通信原理[M].北京:電子工業(yè)出版社，2003.

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

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

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

[6]朱榮華.一種CRC并行計(jì)算原理及實(shí)現(xiàn)方法[J].電子學(xué)報(bào)，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]黃月江.信息安全保密：現(xiàn)代與未來戰(zhàn)爭的信息衛(wèi)士[M].北京：國防工業(yè)出版社，2008.

[8]楊義先.現(xiàn)代密碼新理論[M].北京：科學(xué)出版社，2002.

[9]譚方勇.網(wǎng)絡(luò)安全技術(shù)實(shí)用教程 [M].重慶：重慶出版社，2000.