CRC校驗(yàn)原理與程序設(shè)計(jì)――(RS485總線系統(tǒng)應(yīng)用之1

1.CRC校驗(yàn)原理

1.1 CRC的基本概念：

CRC是英文Cyclical Redundancy Check的縮寫，翻譯成中文通常稱作循環(huán)冗余校驗(yàn)或簡稱為CRC校驗(yàn)。它是數(shù)據(jù)傳輸領(lǐng)域中最常用的一種差錯校驗(yàn)方法，其特點(diǎn)是傳輸數(shù)據(jù)和CRC校驗(yàn)值的長度可以任意選定。在當(dāng)今手機(jī)、計(jì)算機(jī)和數(shù)碼產(chǎn)品普及的信息數(shù)字化時代，CRC校驗(yàn)無處不在。CRC分為多種標(biāo)準(zhǔn)，例如：CRC -12碼通常用來傳送6-bit字符串。CRC-16及CRC-CCITT碼則用是來傳送8-bit字符，其中CRC-16多為美國采用，而CRC- CCITT多為歐洲國家所采用。而CRC-32碼大都被應(yīng)用在Point-to-Point的同步傳輸中。更多的CRC校驗(yàn)標(biāo)準(zhǔn)類型參見附表：CRC校驗(yàn)標(biāo)準(zhǔn)類型。

1.2 CRC校驗(yàn)的基本原理：

在代數(shù)編碼理論中，一個數(shù)值可以表示為一個多項(xiàng)式。例如：一個十進(jìn)制數(shù)值2892，可以用多項(xiàng)式表示為2x3 + 8x2 + 9x + 2(x=10)。同理，一個二進(jìn)制數(shù)值1010101對應(yīng)的多項(xiàng)式為x6 + x4 + x2 + 1(x=2)。

生成CRC碼的基本原理是：設(shè)被校驗(yàn)的數(shù)據(jù)為K位，校驗(yàn)碼為R位，碼字長度為N(=K+R)，則對于CRC碼集中的任一碼字，存在且僅存在一個R次多項(xiàng)式g(x)，使得

V(x)=A(x)g(x)=xRm(x) + r(x);

其中: m(x)為被校驗(yàn)數(shù)據(jù)的K-1次多項(xiàng)式

r(x)為校驗(yàn)碼的R-1次多項(xiàng)式

g(x)稱為生成多項(xiàng)式：g(x)=g0 + g1x1 + g2x2 + ... + g(R-1)x(R-1) + gRxR

發(fā)送方通過指定的g(x)計(jì)算出CRC校驗(yàn)碼，接收方則通過該g(x)來驗(yàn)證收到的CRC校驗(yàn)碼。綜上所述，一個完整的CRC校驗(yàn)過程是：

發(fā)送方：根據(jù)要傳送的K位原始數(shù)據(jù)(二進(jìn)制碼序列)，以標(biāo)準(zhǔn)指定的多項(xiàng)式計(jì)算出一個R位校驗(yàn)碼(CRC碼)，附在原始數(shù)據(jù)后邊，構(gòu)成一個新的二進(jìn)制碼序列共K + R位，然后發(fā)送出去。

接收方：將接收到的數(shù)據(jù)除以與發(fā)送方相同的多項(xiàng)式值，如果能夠除盡，則正確，否則證明出錯。還有另外一種處理，就是接收方用發(fā)送方相同的方法計(jì)算出接收到數(shù)據(jù)的CRC校驗(yàn)值，再與發(fā)送方發(fā)來的校驗(yàn)值比較，相同則正確，否則證明出錯。

2. CRC校驗(yàn)碼的計(jì)算步驟：

例如：有一個要發(fā)送的7位二進(jìn)制數(shù)1011001;對應(yīng)的m(x)=x6 + x4 + x3 + 1。設(shè)CRC校驗(yàn)碼取4位并設(shè)g(x)=x4 + x + 1，則該多項(xiàng)式對應(yīng)的值是10011。根據(jù)CRC規(guī)則，為保證被除數(shù)夠除，首先需將要發(fā)送的數(shù)擴(kuò)大2R 即24倍(左移4位)，得到 10110010000，對應(yīng)的xRm(x)=x10 + x8 + x7 + x4 。

CRC校驗(yàn)碼的生成本質(zhì)其實(shí)就是采用模2除法取余數(shù)，該除法的簡捷計(jì)算就是將除數(shù)和被除數(shù)按位做異或(相同為0，不同為1。0^0=0; 0^1=1; 1^0=1; 1^1=0)運(yùn)算。需要注意的是，進(jìn)行異或運(yùn)算時除數(shù)必須和被除數(shù)最高有效位對齊。下面是將10110010000除以11001手工計(jì)算的演示，得到余數(shù)為1010，該值即是數(shù)據(jù)1011001的CRC校驗(yàn)值。

10110010000 將1011001左移4位

10011 多項(xiàng)式值與被除數(shù)最高有效位對齊

=00101010000 第1次異或結(jié)果

10011 多項(xiàng)式值與被除數(shù)最高有效位對齊

=00001100000 第2次異或結(jié)果

10011 多項(xiàng)式值與被除數(shù)最高有效位對齊

=00000101100 第3次異或結(jié)果

10011 多項(xiàng)式值與被除數(shù)最高有效位對齊

=00000001010 第4次異或結(jié)果

為了簡便計(jì)算機(jī)程序求解CRC，在實(shí)際應(yīng)用中通常把多項(xiàng)式值的最高位舍掉，并且將參加計(jì)算的數(shù)據(jù)高低位顛倒后再計(jì)算。前面的演算數(shù)據(jù)顛倒后的運(yùn)算情況如下：

00001001101

11001

00001010100

11001

00000110000

11001

00110100000

11001

01010000000

提請注意：只有真正讀懂以上手工演算的步驟和規(guī)律，才能理解下節(jié)內(nèi)容。

3. CRC校驗(yàn)的程序設(shè)計(jì)

下面以最常用的CRC-16-IBM校驗(yàn)標(biāo)準(zhǔn)為例來說明CRC校驗(yàn)碼的生成過程。 因?yàn)镃RC-16碼由兩個字節(jié)構(gòu)成，所以首先要準(zhǔn)備一個16位的CRC寄存器，并將每一位都置1。具體的計(jì)算步驟為：

① 設(shè)置CRC寄存器，并給其賦值FFFFH。

② 將被校驗(yàn)數(shù)據(jù)的第一個字節(jié)(8Bit)與CRC寄存器的低8位進(jìn)行異或，結(jié)果存CRC寄存器。

③ CRC寄存器的值向右移一位，最高位(MSB)補(bǔ)零，檢查移出的最低位(LSB)是否為1。

④ 如果LSB為0，重復(fù)第三步;若LSB為1，CRC寄存器與CRC16多項(xiàng)式值A(chǔ)001H相異或。

⑤ 重復(fù)第③與第④步，直到該字節(jié)的8次移位全部完成。

⑥ 如果被校驗(yàn)數(shù)據(jù)有多個字節(jié)，則重復(fù)第②至第⑤步直到所有數(shù)據(jù)全部處理完。

⑦ 最終CRC寄存器的內(nèi)容即為CRC值。

3.1 用查表法求CRC函數(shù)的程序

查表法省去了將被校驗(yàn)數(shù)據(jù)移位并與多項(xiàng)式異或計(jì)算的步驟，因此比計(jì)算法更快捷，但程序編碼量偏大。

3.1.1 用VC編寫的程序

unsigned short CRC16(puchMsg, usDataLen)

unsigned char * puchMsg ;

unsigned short usDataLen ;

{

unsigned char uchCRCHi = 0xFF ;

unsigned char uchCRCLo = 0xFF ;

unsigned uIndex ;

while (usDataLen--)

{

uIndex = uchCRCLo ^ * puchMsg++ ;

uchCRCLo = uchCRCHi ^ auchCRCLo [uIndex] ;

uchCRCHi = auchCRCHi [uIndex] ;

}

return (uchCRCLo 8 | uchCRCHi) ;

}

static char auchCRCHi[] = {

0x00, 0xC0, 0xC1, 0x01, 0xC3, 0x03, 0x02, 0xC2, 0xC6, 0x06,

0x07, 0xC7, 0x05, 0xC5, 0xC4, 0x04, 0xCC, 0x0C, 0x0D, 0xCD,

0x0F, 0xCF, 0xCE, 0x0E, 0x0A, 0xCA, 0xCB, 0x0B, 0xC9, 0x09,

0x08, 0xC8, 0xD8, 0x18, 0x19, 0xD9, 0x1B, 0xDB, 0xDA, 0x1A,

0x1E, 0xDE, 0xDF, 0x1F, 0xDD, 0x1D, 0x1C, 0xDC, 0x14, 0xD4,

0xD5, 0x15, 0xD7, 0x17, 0x16, 0xD6, 0xD2, 0x12, 0x13, 0xD3,

0x11, 0xD1, 0xD0, 0x10, 0xF0, 0x30, 0x31, 0xF1, 0x33, 0xF3,

0xF2, 0x32, 0x36, 0xF6, 0xF7, 0x37, 0xF5, 0x35, 0x34, 0xF4,

0x3C, 0xFC, 0xFD, 0x3D, 0xFF, 0x3F, 0x3E, 0xFE, 0xFA, 0x3A,

0x3B, 0xFB, 0x39, 0xF9, 0xF8, 0x38, 0x28, 0xE8, 0xE9, 0x29,