《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 模擬設(shè)計 > 設(shè)計應(yīng)用 > CRC校驗編程和硬件快速校驗探討
CRC校驗編程和硬件快速校驗探討
大連理工大學(xué) 鄒久朋 林瑤瑤 周建
摘要: 本文分析和解釋了實際CRC校驗碼的生成特點,據(jù)此給出節(jié)省RAM和ROM且運算快速的通用CRC校驗編程思想和程序結(jié)構(gòu),,并探討了用少量硬件實現(xiàn)快速、可靠CRC校驗的方法,。
關(guān)鍵詞: 接口IC 快速 編程 CRC 硬件
Abstract:
Key words :

引 言
    循環(huán)冗余校驗(Cyclic Re&mdancy Check,CRC)是最為常用的計算機和儀表數(shù)據(jù)通信的校驗方法,。CRC碼是一種線性分組碼,,編碼簡單但具有很強的檢錯糾錯能力。除了各種嵌入式儀表,、變頻器等設(shè)備,,還有一些數(shù)字型傳感器的輸出數(shù)據(jù)也提供CRC碼,如數(shù)字溫度傳感器DSl8820,、集成溫濕度采集芯片SHTll等,。但是,各廠商所提供的CRC校驗多項式(用于同通信碼模除)互有差別,,且有CRC一8和CRC一16之分,。另外,規(guī)定模除余數(shù)初始值所有的位有全清0或全置1之分(其CRC硬件生成電路不同),,故其模除求余的運算過程也不相同,。初接觸者往往難以領(lǐng)晤,省略CRC校驗使通信的可靠性降低,。而不少C語言程序,,運算時需要使用較多的RAM單元,較難在80C51,、PIC16等低檔單片機上運行,。
    因此,對于嵌入式系統(tǒng)中的CRC校驗,,事先根據(jù)特定的校驗多項式,算出1字節(jié)數(shù)據(jù)范圍所對應(yīng)的256個余數(shù),,將其作為表格,,編程寫到程序存儲器中查詢而避免在線運算,已是非常通用的做法,。鑒于此,,有些廠商在說明書中就直接給出了這個列表。但如果是CRC一16校驗,存儲表格要占512字節(jié)(CRC一32則需要1 KB),,對于有限的單片機ROM資源來說所占比例不小,,往往只因為多裝了此表,就不得不升級單片機的型號,。
    本文分析和解釋了實際CRC校驗碼的生成特點,,據(jù)此給出節(jié)省RAM和ROM且運算快速的通用CRC校驗編程思想和程序結(jié)構(gòu),并探討了用少量硬件實現(xiàn)快速,、可靠CRC校驗的方法,。


1 CRC原理和實際校驗碼的反序生成特點
    一個k位二進制數(shù)據(jù)在傳送時,按一定規(guī)律附加一些冗余位而增大其碼距,,就能檢錯和糾錯,。標準CRC碼是將原數(shù)據(jù)左移r位,再用r+1位的特別約定多項式(poly—nomial funetion)模除之,,獲得最多為r(8,、16、32)位的余數(shù),,跟隨原數(shù)據(jù)之后生成k+r位的編碼發(fā)送,。接收方再用相同的約定多項式,模除收到的數(shù)據(jù),,余數(shù)為O則傳輸無誤,,為其他值則對應(yīng)各個位的出錯。
    但是對于實際應(yīng)用,,為加快通信速度,,r位的余數(shù)并不是每次都傳輸,而是采用累計模加(異或)的方法,,不斷地與下一個k位數(shù)據(jù)異或運算,,組成新的中間余數(shù)(仍為r位,因一般選擇r≥k),,再被約定多項式模除得到新的余數(shù)值,,依此類推,直到所有通信數(shù)據(jù)都同中間余數(shù)異或,,再模除完為止,。如此得到最終的r位余數(shù),作為全組數(shù)據(jù)校驗的CRC碼附在該組數(shù)據(jù)之后發(fā)送,。接收方以同樣的過程,,算得收到數(shù)組的最終余數(shù),再同最后收到的CRC碼對比(或?qū)RC碼也作為數(shù)據(jù),,看最后余數(shù)是否為O),。當然這樣只能查出該組數(shù)據(jù)的傳輸是否有錯,,而不能糾錯。
    首數(shù)據(jù)的余數(shù)是唯一的,,再異或進后續(xù)的任何一個特定數(shù)據(jù)之后,,結(jié)果依然唯一。所以只要選擇r有足夠的位數(shù),,就能保證多個數(shù)據(jù)中一旦有個別位傳輸錯誤,,其最終的CRC余數(shù)與傳輸正確的余數(shù)相等的可能性極低,因此能查出傳輸錯誤,。
    對于元器件和不少的設(shè)備來說,,其最終余數(shù),即組校驗的CRC碼,,是靠硬件快速生成的,。為了使硬件電路簡化,也為了接收方易于校驗編程,,往往采用變形生成的CRC碼和與其對應(yīng)的校驗處理方式,。
    對于模除余數(shù)的初始值,ISO/IEC 13239標準規(guī)定各位(8,、16,、32)均置1,而DSl8820器件和一些控制儀表的通信CRC碼卻是清0,。在軟件編程時要根據(jù)不同器件賦予不同的初始值,。
    特別約定多項式g(x)都是r+1位的,如ISO/IEC13239標準的CRC一8,,g(x)=x8+x2+x+1,。其最高位恒為1,將其隱含則可簡化模除運算,,但這樣一來后面多位是O,,較難在多字節(jié)(如16位需2字節(jié))CRC校驗中定位計算和存儲。因此,,大多數(shù)CRC碼生成和校驗的處理都采用將約定多項式反序的方法,,即將最低位1放到最高位并丟棄最高次冪系數(shù)1,從而將運算和存儲都降為r位,。
    對于CRC一8,,g(x)=x8+x2+x+1,去高位反序后的模除數(shù)為11100000(OEOH),,r=8,。
    對于CRC一16,g(x)=x16+x15+x2+1,,去高位反序后的模除數(shù)為OA001H,r=16。
    對于CRC一CCITT,,g(x)=x16+x12+x5+1,,同樣處理后的模除數(shù)為8408H,但也常用正序值1021H,。
    對于CRC一32,,g(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1,處理后的模除數(shù)為0EDB88320H,,r=32,。
    如上處理后,按理說被模除數(shù)和余數(shù)也應(yīng)該反序,。但這樣的話r位的余數(shù)在同下一個k位數(shù)據(jù)模加時不但k位數(shù)據(jù)應(yīng)反序,,而且必須左端(最高位)對齊進行異或,處理起來不但麻煩也容易出錯,。因此,,實際CRC碼的生成和校驗一般仍是將余數(shù),即被(模)除數(shù),,按正序排列,,新數(shù)據(jù)也仍是右對齊異或進余數(shù)中。但是將被模除數(shù)原先的左移r位右添0改成了右移r位左添(r個)O,。這相當于k+r位被模除數(shù)中僅r位被反序(放左端),,而前面k位(現(xiàn)放于右端)依然正序??梢钥闯?,按反序原則,實際上每一次都是異或進通信數(shù)據(jù)的反序值,,如11001000B(0C8H)變?yōu)?00100ll(13H),,再異或進被模除數(shù)來求取CRC校驗碼。但由于所有二進制數(shù)的反序值都是唯一對應(yīng)的,,所以并不影響生成CRC碼的唯一確定性,,只是接收方需要按照同樣的反序規(guī)則處理.

2 嵌入式系統(tǒng)CRC校驗的編程
    如上所述,k+r位的被模除數(shù)采用右移的方法不斷地同反序的約定多項式對位模除,,也就遵從了從高位向低位不斷減余的除法規(guī)則,。但由于不必求模除的商,因此只要將被模除數(shù)不斷地右移位,,與去掉最高位的反序約定多項式模減,,求得余數(shù)即可。
    但如果被模除數(shù)最低位右端的移出位是O,,則無論從左端添進多少個O,,也不夠模除約定多項式(其隱含的最高位是1),。在此情況下該位的商是O,余數(shù)不變,,不應(yīng)再同約定多項式對位模減,,而要繼續(xù)左添O右移位,直到當前余數(shù)(被模除數(shù))右移出的位值為1才夠模除(商1),,才可將余數(shù)再對位模減一次多項式,。由此看出,將約定多項式去掉最高位,,可以使模減(異或)的計算位數(shù)r減少(一般r都正好是1字節(jié)位數(shù)的整數(shù)倍),。
    由于被模除數(shù)是k+r位的,因此總共需要右移k位,,即左添進尼個O,,才能模除到最低位結(jié)束。得到的余數(shù)最多是r位(約定多項式為r+1位),,再將它異或人一個新數(shù)據(jù),,作為新的被模除數(shù)。
    每異或進一個數(shù)據(jù),,求新一輪CRC碼,,都只進行走(字節(jié)數(shù)據(jù)是一8)次的右移和一般都少于是次的模減(異或)運算,而且模減的中間差值無需保留(后值覆蓋前值),。因此CRC碼生成的運算過程,,就是右移位、判斷移出位為1則同多項式模減(C語言不能對移出位檢測,,需將余數(shù)備份后同0xol相“與”),、差值回存后再右移的是次循環(huán)過程,如圖1所示,。之后,,再異或進下一個數(shù)據(jù)(該步與查表法一致)。編程得當?shù)脑掃\算量很小,。
    筆者用51匯編語言編寫(2R(:一8校驗程序,,算得1字節(jié)數(shù)據(jù)的CRC碼,只需64~80個機器周期,,只多用1字節(jié)RAM單元(CR(:一16校驗多用2字節(jié),,時間加倍)來存儲余數(shù),即下一次的被模除數(shù)(不斷覆蓋上一次已無用的),。因此,,完全可以直接運算,而不必存儲大量的數(shù)據(jù)表格,。C語言編程,,要考慮語句代碼的優(yōu)化以及只定義使用int和char型局部變量,,以免耗時和占用RAM單元太多。

 

 接收方對于最后收到的r位CRC校驗碼,,不需要再納入模除而使最終余數(shù)為O,,只需同信息數(shù)據(jù)的模除余數(shù)比較,,相等則確定通信正確,。這樣可以減少模除循環(huán)次數(shù),節(jié)省時間,。


3 硬件CRC校驗的探討
    器件或設(shè)備的說明書中,,常給出其硬件CRC碼的生成電路。以總線數(shù)字溫度傳感器DS18820為例,,其8位CRC碼生成電路如圖2所示,。

對應(yīng)該硬件電路,等效的模除多項式為:
    g(x)=x2+x5+x4+1
    該模除多項式反序后,,再隱含最高位,,其多項式的值為8CH。
    8位移位寄存器的初始值清O(00H),,通信數(shù)組數(shù)據(jù)的每個字節(jié)低位在前,,按位依次輸入,當數(shù)據(jù)全部輸入完成后,,移位寄存器各個位的存儲(輸出)值就是所需的CRC校驗碼,。
    在實際應(yīng)用中發(fā)現(xiàn),Autonics等品牌的控制儀表,,其通信CRC校驗碼與DSl8820的完全相同,。
    對應(yīng)于圖2的硬件生成電路,可用1片8D觸發(fā)器(如74HC373)和1片4封裝異或門(如74HCl36)連接而成,,如圖3所示,。

對于CRC賦初值OOH(74HC373清O)的操作,可先讀出DO~D7的隨機值,,然后將讀出的數(shù)據(jù)再串行輸入即可,。因為相同的數(shù)據(jù)相異或總是為O,再除以任何多項式仍為O,。
    若MCU剩余足夠的I/O口,,可將CRC碼的DO~D7位并行讀入。否則,,還需加一片74HCl65,,將D0~D7轉(zhuǎn)換成串行數(shù)據(jù)讀入。
    以少量的硬件實現(xiàn)快速CRC,,能節(jié)省單片機的運算時間和存儲資源,。用于發(fā)送端,,能夠快速獲得CRC校驗碼,在系統(tǒng)其他任務(wù)很重時,,能增強實時性,。而用于接收端,除了上述優(yōu)點之外,,還能顯著增強系統(tǒng)接收和確認信息的可靠性,,適用于一些遠程控制的執(zhí)行裝置(如變頻驅(qū)動器、閥門定位控制器,、重要的監(jiān)測報警裝置等),。這些裝置對于接收到的數(shù)據(jù)或命令信息,一旦因誤校驗而不能正確地判斷執(zhí)行,,其后果都是比較嚴重的,。因此,要提高嵌入式系統(tǒng)的可靠性和實時性,,硬件CRC校驗是一種選擇,。


結(jié) 語
    本文在分析了常用CRC碼的反序生成原理的基礎(chǔ)上,給出了其編程運算的統(tǒng)一步驟,,并提出了由硬件快速生成CRC碼或?qū)邮諗?shù)據(jù)進行CRC校驗的電路和方法,,可為嵌入式系統(tǒng)的可靠性和實時性設(shè)計提供參考.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載,。