在編寫(xiě)數(shù)據(jù)傳輸程序時(shí)，數(shù)據(jù)容錯(cuò)是一個(gè)非常重要的問(wèn)題。循環(huán)冗余位校驗(yàn)（CycliclRedundncyCheck英文簡(jiǎn)稱CRC）是目前運(yùn)用非常廣泛的一種數(shù)據(jù)容錯(cuò)方法，在數(shù)據(jù)傳輸，數(shù)據(jù)壓縮等領(lǐng)域運(yùn)用極其廣泛。CRC的實(shí)現(xiàn)分為硬件和軟件兩種方法，其中軟件實(shí)現(xiàn)的關(guān)鍵在于計(jì)算速度。如果單純模擬硬件實(shí)現(xiàn)方法，則計(jì)算速度較慢。筆者在編制一個(gè)數(shù)據(jù)通訊軟件中，運(yùn)用了一種新穎的查表法計(jì)算CRC，速度很快，效果極佳。

首先介紹其原理，如果每次參與CRC計(jì)算的信息為一個(gè)字節(jié)，該信息字節(jié)加到16位的累加器中去時(shí)，只有累加器的高8位或低8位與信息字節(jié)相互作用（異或），相互作用（異或）的結(jié)果記為組合值，那么累加器中的新值等于組合值加上（按模2異或）累加器中未改變的那一半即為新的CRC值。

組合值只有256種可能，因此可利用硬件模擬算法先算好它們的CRC值預(yù)先填入一張表中，該表的每一單元對(duì)應(yīng)相對(duì)值的CRC。這樣就可以通過(guò)查表法來(lái)計(jì)算CRC值，以便大大提高CRC運(yùn)算的速度。下面給出用Ｃ語(yǔ)言編制的計(jì)算程序。

首先將CRC生成多項(xiàng)式及CRC值表定義為一個(gè)頭文件CRC.H：

#defineCRC_CCITT0x1021//CCITT多項(xiàng)式

#defineREV_CCITT0x8408//反轉(zhuǎn)CCITT多項(xiàng)式

#defineCRC160x8005//CRC16多項(xiàng)式

#defineREV_CRC160x

001//反轉(zhuǎn)CRC16多項(xiàng)式

unsignedshortcrc_tble[256];　//CRC值表

注：16位CCITT多項(xiàng)式（X16+X12+X5+1）和16位CRC16多項(xiàng)式（X16+X15+X2+1）為兩種最常用的CRC多項(xiàng)式。反轉(zhuǎn)多項(xiàng)式是指在數(shù)據(jù)通訊時(shí)，信息字節(jié)先傳送或接收低位字節(jié)，如重新排位影響CRC計(jì)算速度，故設(shè)反轉(zhuǎn)多項(xiàng)式。

造表和查表法CRC計(jì)算函數(shù)。

#include"crc.h"

voidmk_crctble(unsignedshortgenpoly)

unsignedshortcrc_tble[256];

unsignedshort

ccnum=0;

unsignedshorti,j,k;

for(i=0,k=0;i256;i++,k++)

　　　i=8;

for(j=8;j>0;j--)

　　　　　　　if((i^ccnum)0x8000)

ccnum=(

ccnum=1)^genpoly;

　　　　　　　else

ccnum=1;

　　　i=1;　　　

crc_tble[k]=

ccnum;　　　

voidcrc_upd

te(unsignedshortd

t

,unsignedshort

ccnum)

ccnum=(

ccnum=8)^crc_tble[(

ccnum>>8)^d

t];　

注：genpoly為CRC多項(xiàng)式，

ccnum為累加器值（即為新的CRC值），d

t

為參與CRC計(jì)算的信息。



參考文獻(xiàn)：

【1】顧慰文，《糾錯(cuò)碼及其在計(jì)算機(jī)系統(tǒng)中的應(yīng)用》，人民郵電出版社，1980。

【2】J.P.Roth,W.G.Bouricius:Progrmmedlgorithmstocomputetests

todetectndnddistinguishbetweenfiluresinlogiccircuits,IEEETrns.

Electron.Comput.,EC- 16,No.5,pp.567-580(1977)

【3】JoeCmpell:CProgrmmer'sGuidetoSerilCommuniction.(1988)