




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 法律原理考試題及答案
- 法律文書寫作試題及答案
- 邏輯推理能力的系統(tǒng)訓(xùn)練試題及答案
- 法律面試題框架及答案
- 法律課試題及答案
- 計(jì)算機(jī)一級(jí)Msoffice新考點(diǎn)試題及答案
- 2025年計(jì)算機(jī)二級(jí)Python考試內(nèi)容梳理及試題及答案
- 2025年建筑工程合同管理與房地產(chǎn)開發(fā)合同研究
- 突破自我的文學(xué)概論試題及答案
- 醫(yī)保政策課件
- 舜宇校招面試題目及答案
- 2025年紡羊絨紗項(xiàng)目可行性研究報(bào)告
- 中國重癥患者腸外營養(yǎng)治療臨床實(shí)踐專家共識(shí)(2024)解讀
- 【MOOC答案】《大學(xué)籃球(四)》(華中科技大學(xué))章節(jié)作業(yè)期末慕課答案
- 2025年FRM金融風(fēng)險(xiǎn)管理師考試專業(yè)試卷(真題)預(yù)測與解析
- 2026屆新高考地理精準(zhǔn)復(fù)習(xí):海氣相互作用
- 吉林省長春市2025屆高三質(zhì)量監(jiān)測(四)英語試卷+答案
- 圖像分割與目標(biāo)檢測結(jié)合的醫(yī)學(xué)影像分析框架-洞察闡釋
- 2024年新疆澤普縣事業(yè)單位公開招聘村務(wù)工作者筆試題帶答案
- 《網(wǎng)絡(luò)素養(yǎng)教育》課件
- 2025年大數(shù)據(jù)分析師職業(yè)技能測試卷:數(shù)據(jù)采集與處理流程試題解析
評(píng)論
0/150
提交評(píng)論