CRC校驗(yàn)算法的設(shè)計(jì)與實(shí)現(xiàn)

崔彥坤 馬萌

摘要：介紹了循環(huán)冗余校驗(yàn)（CRC）算法的原理和循環(huán)冗余校驗(yàn)算法設(shè)計(jì)分析過程，給出了使用查表法詳細(xì)的算法設(shè)計(jì)。描述了VEE可視化語言中使用的重要模塊及使用VEE語言實(shí)現(xiàn)CRC校驗(yàn)算法的具體設(shè)計(jì)過程，并且給出了詳細(xì)的設(shè)計(jì)流程，該方法校驗(yàn)速度非?？欤岣吡擞?jì)算機(jī)網(wǎng)絡(luò)通信的速度和報(bào)文傳輸?shù)臏?zhǔn)確性，使用手動(dòng)算法舉例驗(yàn)證了該算法的準(zhǔn)確性。

關(guān)鍵詞：循環(huán)冗余；CRC校驗(yàn)；VEE可視化語言

中圖分類號(hào)：TP316文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1008-1739（2019）01-62-3

0引言

計(jì)算機(jī)串口通信中，為防止數(shù)據(jù)通信錯(cuò)誤，一般采用奇偶校驗(yàn)法和糾錯(cuò)校驗(yàn)法等方法進(jìn)行校驗(yàn)。但在一些通信安全要求嚴(yán)格的場合，上述2種方法均不能滿足要求，需要采用CRC校驗(yàn)原理進(jìn)行校驗(yàn)。CRC校驗(yàn)法是一種在數(shù)據(jù)通信和數(shù)據(jù)壓縮中廣泛使用的循環(huán)校驗(yàn)法，以低出錯(cuò)率保證數(shù)據(jù)的可靠無差錯(cuò)傳輸，因此，已被標(biāo)準(zhǔn)化納入TCP/IP和其他協(xié)議的校驗(yàn)中，并且遵循ISO/OSI標(biāo)準(zhǔn)工業(yè)現(xiàn)場總線通信（IEC61158）。

隨著通信領(lǐng)域的快速發(fā)展，數(shù)據(jù)傳輸?shù)目煽啃燥@得尤為重要，為了保證數(shù)據(jù)在傳送過程中的正確無誤，不僅需要高可靠的硬件電路，同時(shí)還需要查錯(cuò)檢查機(jī)制。CRC校驗(yàn)法是數(shù)據(jù)通信領(lǐng)域中最常用的一種查錯(cuò)校驗(yàn)法，其特征是信息字段和校驗(yàn)字段的長度可以任意選定，CRC校驗(yàn)法也具有數(shù)據(jù)傳輸檢錯(cuò)功能，對數(shù)據(jù)進(jìn)行多形式計(jì)算，并將得到的結(jié)果附在幀的后面，接收設(shè)備也執(zhí)行類似的算法，以保證數(shù)據(jù)傳輸?shù)恼_性和完整性[1]。

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

CRC校驗(yàn)原理實(shí)際上就是在一個(gè)P位二進(jìn)制數(shù)據(jù)序列之后附加一個(gè)r位二進(jìn)制檢驗(yàn)碼，從而構(gòu)成一個(gè)總長度為n=P+r位的二進(jìn)制序列，附加在數(shù)據(jù)序列之后的這個(gè)校驗(yàn)碼與數(shù)據(jù)序列的內(nèi)容之間存在著某種特定的關(guān)系[2]。如果因干擾原因，數(shù)據(jù)序列中的某一位或某些位發(fā)生錯(cuò)誤，這種特定的關(guān)系就會(huì)被破壞，因此，通過檢查這一關(guān)系，就可以實(shí)現(xiàn)對數(shù)據(jù)正確性的檢查。

CRC校驗(yàn)就是一種被廣泛采用的錯(cuò)誤檢驗(yàn)編碼，是計(jì)算機(jī)網(wǎng)絡(luò)通信中運(yùn)用最多的一種可靠性很高的檢錯(cuò)編碼方式，是由分組線性碼的分支而來，有較少的冗余位，漏檢率很低，從而可以有效地提高傳輸速度。其二元碼組編碼簡單且誤判概率很低，在通信系統(tǒng)中得到了廣泛應(yīng)用。循環(huán)冗余校驗(yàn)的算法實(shí)現(xiàn)包括硬件實(shí)現(xiàn)和軟件實(shí)現(xiàn)，硬件實(shí)現(xiàn)速度很慢，軟件實(shí)現(xiàn)方法就相對較快[3]，以太網(wǎng)就采用32位的循環(huán)冗余校驗(yàn)編碼方式。

2循環(huán)冗余校驗(yàn)算法

2.1 VEE可視化語言

不同的語言對算法的實(shí)現(xiàn)過程都是一樣的，現(xiàn)在的編程語言種類繁多，由于通信設(shè)備對設(shè)備的控制及儀器之間處理要求比較嚴(yán)格，因此在數(shù)據(jù)校驗(yàn)方面要求更為嚴(yán)格。VEE是一種主要用于儀器控制和測量處理的可視化編程語言，它集成儀器設(shè)備控制、高級(jí)數(shù)據(jù)采集及處理、數(shù)據(jù)分析顯示等眾多先進(jìn)技術(shù)，可運(yùn)行于Windows，SUN，Unix等多種平臺(tái)的測試軟件開發(fā)環(huán)境，其強(qiáng)大的使用圖形顯示以及便捷的程序設(shè)計(jì)能力，為過程控制及測試、測量自動(dòng)化提供了很好的解決方案。它還適用于產(chǎn)品的跟蹤測試，包括從產(chǎn)品設(shè)計(jì)、生產(chǎn)及品質(zhì)控制等一系列的產(chǎn)品指導(dǎo)過程，其基本單元是一系列的功能控件，所有功能控件是在VEE下選取和創(chuàng)建的，連線完成一次程序[4]，使用VEE自動(dòng)測試語言設(shè)計(jì)測試平臺(tái)在測試領(lǐng)域已經(jīng)很普遍，本文主要使用VEE可視化語言實(shí)現(xiàn)CRC校驗(yàn)算法的設(shè)計(jì)過程。

2.2具體算法過程

使用VEE語言設(shè)計(jì)CRC校驗(yàn)過程中，先將字符串轉(zhuǎn)為以字節(jié)為單位的數(shù)組，分別輸出每個(gè)字節(jié)進(jìn)行逐一循環(huán)校驗(yàn)，最終CRC校驗(yàn)碼為“源CRC校驗(yàn)碼”（初始為0，可視為0000，0000，0000，0000）的高8位左移后與本字節(jié)異或（異或結(jié)果設(shè)為）。查表取第位的值（這個(gè)值是16位的）與“源CRC校驗(yàn)碼”異或后得出的16位是“CRC校驗(yàn)碼”，將剛得出的“CRC校驗(yàn)碼”賦值給“源CRC校驗(yàn)碼”，繼續(xù)進(jìn)行下一個(gè)字節(jié)的校驗(yàn)，直到最后一個(gè)字節(jié)校驗(yàn)完成后得出“CRC校驗(yàn)碼”，即為這段字符串的“最終CRC校驗(yàn)碼”，并在該數(shù)據(jù)段的末尾加上該校驗(yàn)碼，這樣就構(gòu)成了一個(gè)完成的數(shù)據(jù)包，以12ab為例介紹CRC檢驗(yàn)具體實(shí)現(xiàn)過程[5]，主要設(shè)計(jì)流程如圖1所示。

①使用VEE語言實(shí)現(xiàn)字符串轉(zhuǎn)數(shù)組，先確定字符串長度，再算出字節(jié)數(shù)。分別將字符按順序2個(gè)一組取出，并將取出的字節(jié)轉(zhuǎn)換成一維數(shù)組，然后輸出。主要使用到的模塊有strLen（str），該模塊為取字符串長度，然后通過除2和循環(huán)單獨(dú)取字節(jié)，strFromLen （str，from，len）中str代表要轉(zhuǎn)換的字符串，from代表要開始截取的字符，len代表截取字符的總長度，其次還是用到collector收集器，使用這3個(gè)模塊和基本的計(jì)算循環(huán)便可實(shí)現(xiàn)字符串轉(zhuǎn)數(shù)組。

②進(jìn)制轉(zhuǎn)換在CRC校驗(yàn)中使用最多，主要包括十進(jìn)制轉(zhuǎn)二進(jìn)制、十進(jìn)制轉(zhuǎn)十六進(jìn)制、二進(jìn)制轉(zhuǎn)十進(jìn)制，十六進(jìn)制轉(zhuǎn)十進(jìn)制、十六進(jìn)制轉(zhuǎn)二進(jìn)制等，以十進(jìn)制轉(zhuǎn)十六進(jìn)制為例，主要思想就是除16，整個(gè)十進(jìn)制數(shù)循除以16的0次方、1次方、2次方和3次方，除后所得余數(shù)和除數(shù)（取整）分別記錄在相應(yīng)的位置，余數(shù)10～15分別對應(yīng)字母a～f，以1234為例，1234/162取整為4，余數(shù)為210，210/161取整13，余數(shù)為2，則十進(jìn)制1234對應(yīng)的十六進(jìn)制數(shù)為ox04d2。

③手動(dòng)計(jì)算異或即轉(zhuǎn)換成二進(jìn)制后，0和1同則0，異則1，VEE可視化語言里的bitXor（x，y）實(shí)現(xiàn)了計(jì)算異或功能，直接輸入需要的異或值，便可直接輸出結(jié)果。

④計(jì)算循環(huán)冗余校驗(yàn)碼表，外循環(huán)從0～255，每次循環(huán)把要計(jì)算字節(jié)送入余數(shù)單元（4 byte）最低位字節(jié)中，然后左移8位。內(nèi)循環(huán)次數(shù)為8，每次循環(huán)先將余數(shù)單元中數(shù)據(jù)左移一位，最低位補(bǔ)0。2次循環(huán)結(jié)束之后就可以算出整個(gè)循環(huán)冗余校驗(yàn)碼表，即把0～255的CRC碼計(jì)算出來，存儲(chǔ)至表格里，然后再根據(jù)字節(jié)查詢對應(yīng)CRC碼。

3試驗(yàn)仿真

CRC校驗(yàn)是通信設(shè)備常用的一種校驗(yàn)法，VEE可視化語言是安捷倫公司推出的一款專門控制儀器儀表及設(shè)備的語言，使用VEE語言控制設(shè)備進(jìn)行通信就需要使用到CRC校驗(yàn)來驗(yàn)證數(shù)據(jù)傳輸?shù)恼_性，因此使用VEE設(shè)計(jì)實(shí)現(xiàn)CRC校驗(yàn)是控制通信設(shè)備進(jìn)行設(shè)備遠(yuǎn)程測試的重要環(huán)節(jié)。

CRC校驗(yàn)有計(jì)算和查表2種方法，計(jì)算法（以CRC16為例）為校驗(yàn)數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)后左移16位，然后開始與17位二進(jìn)制（1000 1000 0001 0000 1）異或，直到把右邊最后一位異或完成為止，所得結(jié)果轉(zhuǎn)換為16進(jìn)制，即為該校驗(yàn)數(shù)的校驗(yàn)碼，以計(jì)算法來驗(yàn)證12ab的校驗(yàn)過程，具體過程為：

根據(jù)手動(dòng)校驗(yàn)12ab來驗(yàn)證該程序的準(zhǔn)確性，最終結(jié)果與程序一致。2個(gè)字節(jié)的計(jì)算相對比較簡單，可是在現(xiàn)實(shí)設(shè)備使用中字節(jié)相當(dāng)長，如果使用手動(dòng)計(jì)算特別耗費(fèi)人力和時(shí)間，經(jīng)過多方驗(yàn)證，該程序與手動(dòng)計(jì)算完全一致。

4結(jié)束語

本質(zhì)上循環(huán)冗余校驗(yàn)計(jì)算的就是移位和異或，所以一次處理移動(dòng)幾位都沒有關(guān)系，只要做相應(yīng)的處理就好了。循環(huán)冗余校驗(yàn)實(shí)現(xiàn)簡單、檢錯(cuò)能力強(qiáng)，提高了通信速度，占用系統(tǒng)資源少，用軟硬件均能實(shí)現(xiàn)，一定程度上解決了傳輸速率和校驗(yàn)時(shí)間的矛盾，是計(jì)算機(jī)網(wǎng)絡(luò)通信中對數(shù)據(jù)包進(jìn)行檢錯(cuò)很好的手段[6]。CRC是一種常用的檢錯(cuò)校驗(yàn)法，它不具備自動(dòng)糾錯(cuò)，只要經(jīng)過嚴(yán)格的校驗(yàn)，并使用足夠多的排查，那么出現(xiàn)檢測不到的差錯(cuò)概率就會(huì)很小，使用CRC差錯(cuò)檢測技術(shù)只能做到無差錯(cuò)傳輸，并不可保證完全可靠傳輸。

參考文獻(xiàn)

[1]許偉，王曉燕. CRC算法在計(jì)算機(jī)網(wǎng)絡(luò)通信中的應(yīng)用[J].數(shù)字技術(shù)與應(yīng)用，2014（2）：119.

[2]秦紅磊，路輝，朗榮玲.自動(dòng)測試系統(tǒng)———硬件及軟件技術(shù)[M].北京：高等教育出版社，2007.

[3]陶傳會(huì).淺議CRC算法在計(jì)算機(jī)網(wǎng)絡(luò)通信中應(yīng)用[J].信息與電腦（理論版），2011（5）：136.

[4]聽雨軒工作室.AgilentVEE虛擬儀器工程設(shè)計(jì)與開發(fā)[M].北京：國防工業(yè)出版社，2004.

[5]邱林海.多媒體通信中CRC碼及其快速算法設(shè)計(jì)[J].小型微型機(jī)算機(jī)系統(tǒng)，1998（11）：18-20.

[6]劉星華.循環(huán)冗余校驗(yàn)校驗(yàn)在單片機(jī)系統(tǒng)中的軟件快速實(shí)現(xiàn)[J].福建工程學(xué)院學(xué)報(bào)，2007，5（1）：76-78.