CRC算法原理及C語言實(shí)現(xiàn)

1、CRC 算法原理及C 語言實(shí)現(xiàn)摘要本文從理論上推導(dǎo)出CRC 算法實(shí)現(xiàn)原理,給出三種分別適應(yīng)不同計(jì)算機(jī)或微控制器硬件環(huán)境的C 語言程序。讀者更能根據(jù)本算法原理,用不同的語言編寫出獨(dú)特風(fēng)格更加實(shí)用的CRC 計(jì)算程序。關(guān)鍵詞CRC算法C 語言1 引言循環(huán)冗余碼CRC 檢驗(yàn)技術(shù)廣泛應(yīng)用于測控及通信領(lǐng)域。CRC 計(jì)算可以靠專用的硬件來實(shí)現(xiàn),但是對(duì)于低成本的微控制器系統(tǒng),在沒有硬件支持下實(shí)現(xiàn)CRC 檢驗(yàn),關(guān)鍵的問題就是如何通過軟件來完成CRC 計(jì)算,也就是CRC 算法的問題。這里將提供三種算法,它們稍有不同,一種適用于程序空間十分苛刻但CRC 計(jì)算速度要求不高的微控制器系統(tǒng),另一種適用于程序空間較大且CR

2、C 計(jì)算速度要求較高的計(jì)算機(jī)或微控制器系統(tǒng),最后一種是適用于程序空間不太大,且CRC 計(jì)算速度又不可以太慢的微控制器系統(tǒng)。2 CRC 簡介CRC 校驗(yàn)的基本思想是利用線性編碼理論,在發(fā)送端根據(jù)要傳送的k 位二進(jìn)制碼序列,以一定的規(guī)則產(chǎn)生一個(gè)校驗(yàn)用的監(jiān)督碼(既CRC 碼r 位,并附在信息后邊,構(gòu)成一個(gè)新的二進(jìn)制碼序列數(shù)共(k+r位,最后發(fā)送出去。在接收端,則根據(jù)信息碼和CRC 碼之間所遵循的規(guī)則進(jìn)行檢驗(yàn),以確定傳送中是否出錯(cuò)。16位的CRC 碼產(chǎn)生的規(guī)則是先將要發(fā)送的二進(jìn)制序列數(shù)左移16位(既乘以162后,再除以一個(gè)多項(xiàng)式,最后所得到的余數(shù)既是CRC 碼,如式(2-1式所示,其中B(X表示n 位

3、的二進(jìn)制序列數(shù),G(X為多項(xiàng)式,Q(X為整數(shù),R(X是余數(shù)(既CRC 碼。(2(16X G X R X Q X G X B +=(2-1求CRC碼所采用模2加減運(yùn)算法則,既是不帶進(jìn)位和借位的按位加減,這種加減運(yùn)算實(shí)際上就是邏輯上的異或運(yùn)算,加法和減法等價(jià),乘法和除法運(yùn)算與普通代數(shù)式的乘除法運(yùn)算是一樣,符合同樣的規(guī)律。生成CRC碼的多項(xiàng)式如下,其中CRC-16和CRC-CCITT 產(chǎn)生16位的CRC碼,而CRC-32則產(chǎn)生的是32位的CRC碼。本文不討論32位的CRC算法,有興趣的朋友可以根據(jù)本文的思路自己去推導(dǎo)計(jì)算方法。接收方將接收到的二進(jìn)制序列數(shù)(包括信息碼和CRC 碼除以多項(xiàng)式,如果余數(shù)為

4、0,則說明傳輸中無錯(cuò)誤發(fā)生,否則說明傳輸有誤,關(guān)于其原理這里不再多述。用軟件計(jì)算CRC 碼時(shí),接收方可以將接收到的信息碼求CRC 碼,比較結(jié)果和接收到的CRC 碼是否相同。3 按位計(jì)算CRC 對(duì)于一個(gè)二進(jìn)制序列數(shù)可以表示為式(3-1:0111222(B B B B X B n n n n +=(3-1求此二進(jìn)制序列數(shù)的CRC 碼時(shí),先乘以162后(既左移16位,再除以多項(xiàng)式G(X,所得的余數(shù)既是所要求的CRC 碼。如式(3-2所示:(22(22(22(2(2(16016111611616X G B X G B X G B X G B X G X B n n n n +=(3-2 可以設(shè):(21

5、6X G X R X Q X G B nn n +=(3-3其中(X Q n 為整數(shù),(X R n 為16位二進(jìn)制余數(shù)。將式(3-3代入式(3-2得:(22(22(22(2(160161116116X G B X G B X G B X G X R X Q X G X B n n n n n += (22(22(2(2(2(1601611161X G B X G B X G B X G X R X Q n n n nn +=(3-4 再設(shè): (2(2(11161X G X R X Q X G B X G X R n n n n +=+ (3-5 其中(1X Q n 為整數(shù),(1X R n 為1

6、6位二進(jìn)制余數(shù),將式(3-5代入式(3-4,如上類推,最后得到:(2(2(2(2(00221116X G X R X Q X Q X Q X Q X G X B n n n n n n +=(3-6 根據(jù)CRC 的定義,很顯然,十六位二進(jìn)制數(shù)(0X R 既是我們要求的CRC 碼。式(3-5是編程計(jì)算CRC 的關(guān)鍵,它說明計(jì)算本位后的CRC 碼等于上一位CRC 碼乘以2后除CRC 碼的C 語言程序。*ptr 指向發(fā)送緩沖區(qū)的首字節(jié),len 是要發(fā)送的總字節(jié)數(shù),0x1021與多項(xiàng)式有關(guān)。unsigned int cal_crc(unsigned char *ptr, unsigned char l

7、en unsigned char i;unsigned int crc=0;while(len-!=0 for(i=0x80; i!=0; i/=2 if(crc&0x8000!=0 crc*=2; crc=0x1021; /* 余式CRC 乘以2再求CRC */else crc*=2;if(*ptr&i!=0 crc=0x1021; /* 再加上本位的CRC */ptr+;return(crc;按位計(jì)算CRC 雖然代碼簡單,所占用的內(nèi)存比較少,但其最大的缺點(diǎn)就是一位一位地計(jì)算會(huì)占用很多的處理器處理時(shí)間,尤其在高速通訊的場合,這個(gè)缺點(diǎn)更是不可容忍。因此下面再介紹一種按字節(jié)查表快

8、速計(jì)算CRC 的方法。4 按字節(jié)計(jì)算CRC 不難理解,對(duì)于一個(gè)二進(jìn)制序列數(shù)可以按字節(jié)表示為式(4-1,其中(X B n 為一個(gè)字節(jié)(共8位。(2(2(2(0811(818X B X B X B X B X B n n n n +=(4-1求此二進(jìn)制序列數(shù)的CRC 碼時(shí),先乘以162后(既左移16位,再除以多項(xiàng)式G(X,所得的余數(shù)既是所要求的CRC 碼。如式(4-2所示:(2(2(2(2(2(2(1601(816181616X G X B X G X B X G X B X G X B n n n n +=(4-2可以設(shè):(2(16X G X R X Q X G X B nn n +=(4-3其

9、中(X Q n 為整數(shù),(X R n 為16位二進(jìn)制余數(shù)。將式(4-3代入式(4-2得:(2(2(2(2(2(1601(8161816X G X B X G X B X G X R X Q X G X B n n n n n +=(22(2(2(2(1601(816188X G B X G X B X G X R X Q n n n n n +=(4-4因?yàn)? 888882(2(2(+=X R X R X R nL nH n881682(2(+=X R X R nL nH (4-5 其中(8X R nH 是(X R n 的高八位,(8X R nL 是(X R n 的低八位。將式(4-5代入式(

10、4-4,經(jīng)整理后得:(22(2(2(2(2(1601(8161888816X G B X G X B X R X G X R X Q X G X B n n nH nL n n +=(4-6再設(shè): (2(2(11161888X G X R X Q X G X B X B X G X R n n n nH nL +=+ (4-7其中(1X Q n 為整數(shù),(1X R n 為16位二進(jìn)制余數(shù)。將式(4-7代入式(4-6,如上類推,最后得:(2(2(2(001(81816X G X R X Q X Q X Q X G X B n n n n +=(4-8 很顯然,十六位二進(jìn)制數(shù)(0X R 既是我們要

11、求的CRC 碼。式(4-7是編寫按字節(jié)計(jì)算CRC程序的關(guān)鍵,它說明計(jì)算本字節(jié)后的CRC碼等于上一字節(jié)余式CRC碼的低8位左移8位后,再加上上一字節(jié)CRC右移8位(也既取高8位和本字節(jié)之和后所求得的CRC碼,如果我們把8位二進(jìn)制序列數(shù)的CRC全部計(jì)算出來,放如一個(gè)表里,采用查表法,可以大大提高計(jì)算速度。由此不難理解下面按字節(jié)求CRC碼的C語言程序。*ptr指向發(fā)送緩沖區(qū)的首字節(jié),len是要發(fā)送的總字節(jié)數(shù),CRC余式表是按0x11021多項(xiàng)式求出的。unsigned int cal_crc(unsigned char *ptr, unsigned char len unsigned int crc

12、; unsigned char da;unsigned int crc_ta256= /* CRC余式表 */0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7,0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef,0x 1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6,0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff,

13、 0xe3de,0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d,0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4,0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc,0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840,

14、0x1861, 0x2802, 0x3823,0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b,0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12,0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a,0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41,0xedae, 0xfd8f, 0xcdec, 0

15、xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49,0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70,0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78,0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f,0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067,0x83b9, 0x

16、9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e,0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256,0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d,0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0x

17、d73c,0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634,0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab,0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3,0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a,0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1

18、ad0, 0x2ab3, 0x3a92,0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9,0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1,0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8,0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0;crc=0;da=(uchar (crc/256; /*

19、 以8位二進(jìn)制數(shù)的形式暫存CRC的高8位 */crc<<=8; /* 左移8位,相當(dāng)于CRC的低8位乘以82 */ crc=crc_tada*ptr; /* 高8位和當(dāng)前字節(jié)相加后再查表求CRC ,再加上以前的CRC */ ptr+;return(crc;很顯然,按字節(jié)求CRC 時(shí),由于采用了查表法,大大提高了計(jì)算速度。但對(duì)于廣泛運(yùn)用的8位微處理器,代碼空間有限,對(duì)于要求256個(gè)CRC 余式表(共512字節(jié)的內(nèi)存已經(jīng)顯得捉襟見肘了,但CRC 的計(jì)算速度又不可以太慢,因此再介紹下面一種按半字節(jié)求CRC 的算法。 5 按半字節(jié)計(jì)算CRC 同樣道理,對(duì)于一個(gè)二進(jìn)制序列數(shù)可以按字節(jié)表示為式

20、(5-1,其中(X B n 為半個(gè)字節(jié)(共4位。(2(2(2(0411(414X B X B X B X B X B n n n n +=(5-1求此二進(jìn)制序列數(shù)的CRC 碼時(shí),先乘以162后(既左移16位,再除以多項(xiàng)式G(X,所得的余數(shù)既是所要求的CRC 碼。如式(4-2所示:(2(2(2(2(2(2(1601(416141616X G X B X G X B X G X B X G X B n n n n +=(5-2可以設(shè):(2(16X G X R X Q X G X B nn n +=(5-3其中(X Q n 為整數(shù),(X R n 為16位二進(jìn)制余數(shù)。將式(5-3代入式(5-2得:(2

21、(2(2(2(2(1601(4161416X G X B X G X B X G X R X Q X G X B n n n n n +=(22(2(2(2(1601(416144X G B X G X B X G X R X Q n n n n n +=(5-4因?yàn)? 41212442(2(2(+=X R X R X R nL nH n4121642(2(+=X R X R nL nH (5-5其中(4X R nH 是(X R n 的高4位,(12X R nL 是(X R n 的低12位。將式(5-5代入式(5-4,經(jīng)整理后得:(22(2(2(2(2(1601(41614412416X G

22、B X G X B X R X G X R X Q X G X B n n nH nL n n +=(5-6再設(shè): (2(2(111614412X G X R X Q X G X B X B X G X R n n n nH nL +=+ (5-7其中(1X Q n 為整數(shù),(1X R n 為16位二進(jìn)制余數(shù)。將式(5-7代入式(5-6,如上類推,最后得:R (X B ( X 216 (5-8 = Qn ( X 2 4 n + Qn 1 ( X 2 4 ( n 1 + + Q0 ( X + 0 G( X G( X 很顯然,十六位二進(jìn)制數(shù) R0 ( X 既是我們要求的 CRC 碼. 式(5-7是

23、編寫按字節(jié)計(jì)算 CRC 程序的關(guān)鍵, 它說明計(jì)算本字節(jié)后的 CRC 碼等于上一字節(jié) CRC 碼的低 12 位左移 4 位后,再加上上一字節(jié)余式 CRC 右移 4 位(也既取高 4 位和本字節(jié)之和后所 求得的 CRC 碼, 如果我們把 4 位二進(jìn)制序列數(shù)的 CRC 全部計(jì)算出來, 放在一個(gè)表里, 采用查表法, 每個(gè)字節(jié)算兩次(半字節(jié)算一次 ,可以在速度和內(nèi)存空間取得均衡.由此不難理解下面按半字節(jié) 求 CRC 碼的 C 語言程序.*ptr 指向發(fā)送緩沖區(qū)的首字節(jié),len 是要發(fā)送的總字節(jié)數(shù),CRC 余式表是 按 0x11021 多項(xiàng)式求出的. unsigned cal_crc(unsigned char *ptr, unsig