CRC算法原理及C語言實現(xiàn)(介紹了3種方法)

1、CRC算法原理及C語言實現(xiàn)（介紹了3種方法）CRC算法原理及C語言實現(xiàn)-51 丿 | 發(fā) 網(wǎng)- ()摘 耍 本文從理論上推導(dǎo)出CRC算法實現(xiàn)原理，給出三種分別適應(yīng)不同計算機或微控制器 駛件壞境的C語言程序。讀者更能根據(jù)本算法原理，用不同的語言編寫出獨特風(fēng)格更加實用 的CRC計算程序。關(guān)犍詞 CRC 算法 C語言1引言循環(huán)兀余碼CRC檢驗技術(shù)廣泛應(yīng)用J測控及通信領(lǐng)域。CRCil算可以靠專用的硬件來 實現(xiàn)，但足対J：低成本的微控制器系統(tǒng)，在沒仃fig件支持卜一實現(xiàn)CRC檢驗，關(guān)鍵的問題就是 如何通過軟件來完成CRC計算，也就是CRC算法的問題。這里將提供匚種算法,它們稍有不同,種適用F程序空間卜分

2、苛刻但CRC計算速度要 求不筒的微控制器系統(tǒng)，另-種適用空間較人ECRCH算速度要求較高的計算機或微 控制器系統(tǒng)，最后-種是適用J：程序空間不太人，且CRC計算速度又不可以太慢的微控制器 系統(tǒng)。2 CRC簡介CRC校驗的膚本思想足利用線性編碼理論，在發(fā)送端根據(jù)要傳送的k位二進制碼序列，以- 定的規(guī)則產(chǎn)生一個校驗用的監(jiān)骨碼（既CRC碼）位,并附在信息后邊，構(gòu)成一個新的二進 制碼序列數(shù)共（k+r）位，最后發(fā)送出去。在接收端，則根據(jù)信息碼和CRC碼Z間所遵循的規(guī) 則進行檢驗，以確定傳送中是否出錯。16位的CRC碼產(chǎn)生的規(guī)則是先將耍發(fā)送的二進制序列數(shù)左移16位（既乘以）后，再除以 個多項式，最后所得到

3、的余數(shù)既是CRC碼，如式（21）式所示，直中E（X）表示n位的一.進制 序列數(shù)，G（X）為多項式，Q（X）為幣數(shù)，R（X）是余數(shù)（既CRC碼）.（2-1）求CRC碼所采用模2加減運算法則，既足不帶進位和借位的按位加減，這種加減運篦實際上 就是邏輯上的界或運算，加法和減法等價，乘法和除法運算與普通代數(shù)式的乘除法運算是一 樣，符合同樣的規(guī)律。生成CRC碼的多項式如卜，其中CRC-16和CRC-CCITT產(chǎn)生16位的CRC 碼，l（ljCRC-32則產(chǎn)生的是32位的CRC碼。本文不討論32位的CRC算法，仃興趣的朋友町以 根據(jù)本文的思路自己去推導(dǎo)計算方法。CRC-16：（美國二進制同步系統(tǒng)P采用）C

4、RC-CCITT：（由歐洲CCITT推薦）CRC-32：接收方將接收到的二進制序列數(shù)（包括信息碼和CROPS）除以多項式，如果余數(shù)為0則說 明傳輸屮無錯謀發(fā)生，否則說明傳輸勺謀，關(guān)其原理這里不再女述。用軟件計算CRC碼時, 接收方町以將接收到的信息碼求CRC碼，比較結(jié)果和接收到的CRC碼是否相同。3按位計算CRC對一個二進制序列數(shù)可以衣示為式（3-1）:(3-1)求此二進制序列數(shù)的CRC碼時，先乘以后(既左移16位)，再除以多項式G(X),所得的余 數(shù)既是所耍求的CRC碼。如式(32)所示：(3-2)可以設(shè)：(3-3)其中為整數(shù)，為16位二進制余數(shù)。將式(3-3)代入式(3-2)得：(3-4)

5、再設(shè)：(3-5)其屮為整數(shù)，為16位二進制余數(shù)，將式(35)代入式(3/),如上類推，瑕后得到：(3-6)根據(jù)CRC的定義，很顯然，十六位二進制數(shù)既是我們要求的CRC碼。式(3-5)是編程汁算CRC的關(guān)鍵，它說明計算本位厲的CRC碼等J： I一位CRC碼乘以2后除以 多項式，所得的余數(shù)再加上本位值除以多項式所徇的余數(shù)。宙此不難理解卜面求CRC碼的C 語言程序。*pu指向發(fā)送緩沖區(qū)的首字節(jié)，la是要發(fā)送的總字節(jié)數(shù)，0x1021與多項式冇關(guān)。 unsigned int cal_cic(unsigned char *ptr. unsigned char len) unsigned cliai 1；u

6、nsigned mt crc-0;while(len-!=0) fbr(i=0x80; i!=0; i/=2) if(crc&0x8000)»=0) crc*=2; crcA=0xl021;/余式CRC乘以2再求CRC /else crc*-2;if(*ptr&i)?=0) 0xx1021;/* 再加上本位的CRC /ptr 卄；renim(crc);按位計算CRC雖然代碼簡單，所占用的內(nèi)存比較少，但具垠人的缺點就是位一位地計算 會占用很多的處理器處理時間，尤其在高速通訊的場介，這個缺點更是不可容忍。因此卜両 再介紹一種按字節(jié)資表快速計算CRC的方法。4按字節(jié)計算CR

7、C不難理解，對一個二進制序列數(shù)可以按字節(jié)衣示為式(4-1),其屮為一個字節(jié)(共8位)。(4-1)求此二進制序列數(shù)的CRC碼時，先乘以后(既左移16位)，再除以多項式G(X),所得的余 數(shù)既是所耍求的CRC碼。如式(4-2)所示：(4-2)可以設(shè)：(4-3)其中為整數(shù)，為16位二進制余數(shù)。將式(4-3)代入式(4-2)得：(4-4)因為：(4-5)其屮是的高八位，是的低八位。將式(4-5)代入式(4-4),經(jīng)整理后得：(4-6)再設(shè)：(4-7)其中為整數(shù)，為16位二進制余數(shù)。將式(47)代入式(46),如上類推，最后得：(4-8)很顯然，十六位二進制數(shù)既是我們耍求的CRC碼。式(4-7)是編寫按

8、字卩計算CRC程序的關(guān)鍵，它說明計算本字卩后的CRC碼等J：上一字卩余式 CRC碼的低8位左移8位后，再加上上一字節(jié)CRC右移3位(也既取高8位)和本字節(jié)之和后所 求得的CRC碼，如果我們把8位二進制序列數(shù)的CRC全部計算出來，放如一個表里，采用査 衣仏，町以人人提舟計算速度。由此不難理解卜面按字節(jié)求CRC碼的C語言榨序。怕指向 發(fā)送緩沖區(qū)的苗寧節(jié)，1"是耍發(fā)送的總了節(jié)數(shù)，CRC余式衣是按0x11021多項式求出的。 unsigned int cal_cic(uiisigned char *pti; unsigned chai len) unsigned int crc;unsign

9、ed char da;unsigned int crc_ta256-/ CRC余式表 */0x0000. 0x1021, 0x2042, 0x3063. 0x4084. Ox5Oa5,0x60c6, 0x70亡7,0x810& 0x9129, Oxa 14a. 0xbl6b, Oxcl8c, Oxdlad. Oxelce, Oxflef.Ox 1231, 0x0210. 0x3273. 0x2252, Ox52b5, 0x4294. Ox72f7, 0x62d6,0x9339、0x8318, 0xb37b, Oxa35a. Oxd3bd, Oxc39c, OxfBff. Oxe3de,

10、0x2462, 0x3443, 0x0420. 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485,0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, Oxf5cf. Oxc5ac, Oxd58d,0x3653. 0x2672, 0x1611, 0x0630, Ox76d7, 0x66f6. 0x5695、0x46b4,Oxb75b. 0xa77a, 0x9719, 0x8738. Oxf7df 0xe7fe, 0xd79d, 0xc7bc,0x48c4, 0x58e5, 0x6886, 0x78aL 0x0840, 0x1861, 0x2

11、802, 0x3823、0xc9cc, 0xd9ed, 0xe98e. Oxfaf, 0x894& 0x9969、0xa90a, 0xb92b,Ox5af5, 0x4ad4, Ox7ab7, 0x6a96, 0xla71, 0x0a50, 0x3a33, 0x2al2,Oxdbfd, Oxcbdc, Oxfbbf. 0xeb9e 0x9b79、Ox8b5& Oxbb3b, Oxab la,0x6ca6, 0x7c87, 0x4ce4. Ox5cc5, 0x2c22, Ox3cO3. 0x0c60, 0xlc4LOxedae, OxfdSf. Oxcdec, Oxddcd, Ox

12、ad2a. OxbdOb、Ox8d6& 0x9d49,0x7e97, 0x6eb6, 0x5ed5. 0x4ef4, 0x3el3, 0x2e32, 0xle51, 0x0e70.0xff9f Oxefbe, Oxdfdd, Oxcffc, Oxbflb, Oxaf3a. 0x9f59. 0x8f7&0x9188, 0x8la9, Oxblca, Oxa 1 eb, OxdlOc, 0xcl2d, Oxfl4e, 0xel6f,0x1080, OxOOal, 0x30c2. 0x20亡3. 0x5004, 0x4025, 0x7046. 0x6067,0x83b9, 0x939

13、& Oxa3fb. Oxb3da, Oxc33d, Oxd31c, 0xe37f, Oxf35e,0x02bl, 0x1290, 0x22f3. 0x32d2. 0x4235, 0x5214, 0x6277, 0x7256,Oxb5ea, Oxa5cb, 0x95a& 0x8589, Oxf56e. 0xe54f. Oxd52c, 0xc50d,0x34e2, 0x24c3, 0x140. 0x0481, 0x7466, 0x6447, 0x5424. 0x4405,0xa7db, Oxb7fa, 0x8799. 0x97b& Oxc75f, Oxf77e, 0xc71

14、d, Oxd73c,0x26d3, 0x362 0x0691. 0xl6b0. 0x6657, 0x7676. 0x4615, 0x5634,0xd94c、0xc96d, OxfPOe, 0xe92f, 0x99c& 0x89e9, 0xb98a, 0xa9ab,0x5844, 0x4865, 0x7806. 0x6827. 0xl8c0, OxOSel, 0x3882, 0x28a35Oxcb7d, Oxdb5c, Oxeb3f, Oxfble, 0x8bf9, 0x9bd& Oxabbb, 0xbb9a,0x4a75, 0x5a54, 0x6a37. 0x7al6, OxO

15、af 1, OxladO, 0x2ab3, 0x3a92,Oxfd2e, OxedOf、0xdd6c, 0xcd4d, Oxbdaa. Oxad8b. Ox9de8, 0x8dc9.0x7c26, 0x6c07, 0x5c64. 0x4c45. 0x3ca2, 0x2c83, OxlceO, OxOccl,Oxeflf, OxffJe, Oxcf5d, 0xdf7c, 0xaf9b, Oxbfba. 0x8fd9, Ox9ff8.0x6el7. 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2. OxOedL Oxi eft) ;crc=O;wlule(len!=0

16、) da-(ucliar) (crc/256);/以8位二進制數(shù)的形式暫存CRC的鬲8位/crc«=8;嚴左移8位，相當(dāng)J CRC的低8位乘以/crcrc-tatdaptr; /*高8位和當(dāng)詢字節(jié)相加后再査表求CRC ,再加上以前的CRC/ptT卄；retuni(crc);很顯然，按字節(jié)求CRC時，由J：采用了査表法，人人提高了計算速度。但対J：廣泛運用的8 位微處理器，代碼空間仃限，對J：耍求256個CRC余式表(共512字節(jié)的內(nèi)存)己經(jīng)顯得捉襟 見肘了，但CRC的計算速度乂不町以人慢，因此再介紹卜面一種按半字節(jié)求CRC的算法。5按半字節(jié)計算CRC同樣道理，對J：一個一.進制序列數(shù)

17、可以按字節(jié)表示為式(51),直中為半個字節(jié)(共4位)。(5-1)求此二進制序列數(shù)的CRC碼時，先乘以后(既左移16位)，再除以多項式G(X),所得的余 數(shù)既是所耍求的CRC碼。如式(42)所示：(5-2)可以設(shè)：(5-3)其屮為整數(shù)，為16位二進制余數(shù)。將式(5-3)代入式(5-2)得：(5-4)因為：(5-5)其屮是的高4位，是的低12位。將式(5-5)代入式(5-4),經(jīng)整理后得：(5-6)再設(shè)：(5-7)其屮為整數(shù)，為16位二進制余數(shù)。將式(5-7)代入式(5-6),如上類推，址后得：(5-8)很顯然，十六位二進制數(shù)既是我們要求的CRC碼。式(57)是編寫按字節(jié)計算CRC程序的關(guān)鍵，它說

18、明計算本字節(jié)后的CRC碼等上一字節(jié)CRC 碼的低12位左移4位后，再加上上一字節(jié)余式CRC右移4位(也既取高4位)和本字節(jié)Z和后 所求得的CRC碼，如果我們把4位二進制序列數(shù)的CRC全部計算出來，放在一個表里，采用 査表:丿、，每個字節(jié)算兩次(半字節(jié)算一次)，可以在速度和內(nèi)存空間取得均衡。由此不難理 解卜面按半字節(jié)求CRC碼的C語言程序。ptrlS向發(fā)送緩沖區(qū)的甘字節(jié)，len是耍發(fā)送的總字 節(jié)數(shù)，CRC余式表是按0x11021多項式求出的。unsigned cal_crc(unsigned chai *ptr, unsigned chai len) unsigned int crc;unsigned chai da;unsigned mt crc_ta16=/* CRC余式表 */0x0000,0xl021,0x2042,0x