|
引言 循環(huán)冗余校驗（Cyclic Redundancy Check，CRC）是最為常用的計算機和儀表數(shù)據(jù)通信的校驗方法。CRC碼是一種線性分組碼，編碼簡單但具有很強的檢錯糾錯能力。除了各種嵌入式儀表、變頻器等設備，還有一些數(shù)字型傳感器的輸出數(shù)據(jù)也提供CRC碼，如數(shù)字溫度傳感器DS18B20、集成溫濕度采集芯片SHT11等。但是，各廠商所提供的CRC校驗多項式（用于同通信碼模除）互有差別，且有CRC8和CRC16之分。另外，規(guī)定模除余數(shù)初始值所有的位有全清0或全置1之分（其CRC硬件生成電路不同），故其模除求余的運算過程也不相同。初接觸者往往難以領晤，省略CRC校驗使通信的可靠性降低。而不少C語言程序，運算時需要使用較多的RAM單元，較難在80C51、PIC16等低檔單片機上運行。 因此，對于嵌入式系統(tǒng)中的CRC校驗，事先根據(jù)特定的校驗多項式，算出1字節(jié)數(shù)據(jù)范圍所對應的256個余數(shù)，將其作為表格，編程寫到程序存儲器中查詢而避免在線運算，已是非常通用的做法。鑒于此，有些廠商在說明書中就直接給出了這個列表。但如果是CRC16校驗，存儲表格要占512字節(jié)（CRC32則需要1 KB），對于有限的單片機ROM資源來說所占比例不小，往往只因為多裝了此表，就不得不升級單片機的型號。 本文分析和解釋了實際CRC校驗碼的生成特點，據(jù)此給出節(jié)省RAM和ROM且運算快速的通用CRC校驗編程思想和程序結構，并探討了用少量硬件實現(xiàn)快速、可靠CRC校驗的方法。 1 CRC原理和實際校驗碼的反序生成特點機臺 一個k位二進制數(shù)據(jù)在傳送時，按一定規(guī)律附加一些冗余位而增大其碼距，就能檢錯和糾錯。標準CRC碼是將原數(shù)據(jù)左移r位，再用r+1位的特別約定多項式 (polynomial function) 模除之，獲得最多為r（8、16、32）位的余數(shù)，跟隨原數(shù)據(jù)之后生成k+r位的編碼發(fā)送。接收方再用相同的約定多項式，模除收到的數(shù)據(jù)，余數(shù)為0則傳輸無誤，為其他值則對應各個位的出錯。. 但是對于實際應用，為加快通信速度，r位的余數(shù)并不是每次都傳輸，而是采用累計模加（異 或）的方法，不斷地與下一個k位數(shù)據(jù)異或運算，組成新的中間余數(shù)（仍為r位，因一般選擇r≥k），再被約定多項式模除得到新的余數(shù)值，依此類推，直到所有通信數(shù)據(jù)都同中間余數(shù)異或，再模除完為止。如此得到最終的r位余數(shù)，作為全組數(shù)據(jù)校驗的CRC碼附在該組數(shù)據(jù)之后發(fā)送。接收方以同樣的過程，算得收到數(shù)組的最終余數(shù)，再同最后收到的CRC碼對比（或將CRC碼也作為數(shù)據(jù)，看最后余數(shù)是否為0）。當然這樣只能查出該組數(shù)據(jù)的傳輸是否有錯，而不能糾錯。 首數(shù)據(jù)的余數(shù)是唯一的，再異或進后續(xù)的任何一個特定數(shù)據(jù)之后，結果依然唯一。所以只要選擇r有足夠的位數(shù)，就能保證多個數(shù)據(jù)中一旦有個別位傳輸錯誤，其最終的CRC余數(shù)與傳.輸正確的余數(shù)相等的可能性極低，因此能查出傳輸錯誤。 對于元器件和不少的設備來說，其最終余數(shù)，即組校驗的CRC碼，是靠硬件快速生成的。為了使硬件電路簡化，也為了接收方易于校驗編程，往往采用變形生成的CRC碼和與其對應的校驗處理方式。 對于模除余數(shù)的初始值，ISO/IEC 13239標準規(guī)定各位（8、16、32）均置1，而DS18B20器件和一些控制儀表的通信CRC碼卻是清0。在軟件編程時要根據(jù)不同器件賦予不同的初始值。 特別約定多項式g(x)都是r+1位的，如ISO/IEC 13239標準的CRC8，g(x)=x8+x2+x+1。其最高位恒為1，將其隱含則可簡化模除運算，但這樣一來后面多位是0，較難在多字節(jié)（如 16位需2字節(jié)）CRC校驗中定位計算和存儲。因此，大多數(shù)CRC碼生成和校驗的處理都采用將約定多項式反序的方法，即將最低位1放到最高位并丟棄最高次冪系數(shù)1，從而將運算和存儲都降為r位。 對于CRC8，g(x)=x8+x2+x+1，去高位反序后的模除.數(shù)為 11100000（0E0H），r＝8。. 對于CRC16，g(x)=x16+x15+x2+1，去高位反序后的模除數(shù)為 0A001H，r＝16。 對于CRCCCITT，g(x)=x16+x12+x5+1，同樣處理后的模除數(shù)為8408H，但也常用正序值1021H。. 對于 CRC32，g(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1，處理后的模除數(shù)為0EDB88320H，r＝32。 如上處理后，按理說被模除數(shù)和余數(shù)也應該反序。但這樣的.話r位的余數(shù)在同下一個k 位數(shù)據(jù)模加時不但k位數(shù)據(jù)應反序，而且必須左端（最高位）對齊進行異或，處理起來不但麻煩也容易出錯。因此，實際CRC碼的生成和校驗一般仍是將余數(shù)，即被（模）除數(shù)，按正序排列，新數(shù)據(jù)也仍是右對齊異或進余數(shù)中。但是將被模除數(shù)原先的左移r位右添0改成了右移r位左添（r個）0。這相當于k+r位被模除數(shù)中僅r位被反序（放左端），而前面k位（現(xiàn)放.于右端）依然正序。可以看出，按反序原則，實際上每一次都是異或進通信數(shù)據(jù)的反序值，如 11001000B（0C8H）變?yōu)?0010011(13H)，再異或進被模除數(shù)來求取CRC校驗碼。但由于所有二進制數(shù)的反序值都是唯一對應的，所以并不影響生成CRC碼的唯一確定性，只是接收方需要按照同樣的反序規(guī)則處理。 2 嵌入式系統(tǒng)CRC校驗的編程 如上所述，k+r位的被模除數(shù)采用右移的方法不斷地同反序的約定多項式對位模除，也就遵從了從高位向低位不斷減余的除法規(guī)則。但由于不必求模除的商，因此只要將被模除數(shù)不斷地右移位，與去掉最高位的反序約定多項式模減，求得余數(shù)即可。 但如果被模除數(shù)最低位右端的移出位是0，則無論從左端添進多少個0，也不夠模除約定多項式（其隱含的最高位是1）。在此情況下該位的商是0，余數(shù)不變，不應再同約定多項式對位模減，而要繼續(xù)左添0右移位，直到當前余數(shù)（被模除數(shù)）右移出的位值為1才夠模除（商1），才可將余數(shù)再對位模減一次多項式。由此看出，將約定多項式去掉最高位，可以使模減（異或）的計算位數(shù)r減少（一般r都正好是1字節(jié)位數(shù)的整數(shù)倍）。 由于被模除數(shù)是k+r位的，因此.總共需要右移k位，即左添進k個0，才能模除到最低位結束。得到的余數(shù)最多是r位（約定多項式為r＋1位），再將它異或入一個新數(shù)據(jù)，作為新的被模除數(shù)。 每異或進一個數(shù)據(jù)，求新一輪CRC碼，都只進行k（字節(jié)數(shù)據(jù)k＝8）次的右移和一般都少于k次的模減（異或）運算，而且模減的中間差值無需保留（后值覆蓋前值）。因此CRC碼生成的運算過程，就是右移位、判斷移出位為1則同多項式模減（C語言不能對移出位檢測，需將余數(shù)備份后同0x01相 “與”）、差值回存后再右移的k次循環(huán)過程，如圖1所示。之后，再異或進下一個數(shù)據(jù)（該步與查表法一致）。編程得當?shù)脑掃\算量很小。. 
筆者用51匯編語言編寫CRC8校驗程序，算得1字節(jié)數(shù)據(jù)的CRC碼，只需64～80個機器周期，只多用1字節(jié)RAM單元（CRC16校驗多用2字節(jié)，時間加倍）來存儲余數(shù)，即下一次的被模除數(shù)（不斷覆蓋上一次已無用的）。因此，完全可以直接運算，而不必存儲大量的數(shù)據(jù)表格。C語言編程，要考慮語句代碼的優(yōu)化以及只定義使用int和char型局部變量，以免耗時和占用R.AM單元太多。 接收方對于最后收到的r位CRC校驗碼，.不需要再納入模除而使最終余數(shù)為0，只需同信息數(shù)據(jù)的模除余數(shù)比較，相等則確定通信正確。這樣可以減少模除循環(huán)次數(shù)，節(jié)省時間。 3 硬件CRC校驗的探討 器件或設備的說明書中，常給出其硬件CRC碼的生成電路。以總線數(shù)字溫度傳感器DS18B20為例，其8位CRC碼生成電路如圖2所示。. 對應該硬件電路，等效的模除多項式為：
該模除多項式反序后，再隱含最高位，其多項式的值為8CH。 8位移位寄存器的初始值清0（00H），通信數(shù)組數(shù)據(jù)的每個字節(jié)低位在前，按位依次輸入，當數(shù)據(jù)全部輸入完成后，移位寄存器各個位的存儲（輸出）值就是所需的CRC校驗碼。 在實際應用中發(fā)現(xiàn)，Autonics等品牌的控制儀表，其通信CRC校驗碼與DS18B20的完全相同。
對應于圖2的硬件生成電路，可用1片8D觸發(fā)器（如74HC373）和1片4封裝異或門（如74HC136）連接而成，如圖3所示。
對于CRC賦初值00H（74HC373清0）的操作，可先讀出D0～D7的隨機值，然后將讀出的數(shù)據(jù)再串行輸入即可。因為相同的數(shù)據(jù)相異或總是為0，再除以任何多項式仍為0。 若MCU剩余足夠的I/O口，可將CRC碼的D0～D7位并行讀入。否則，還需加一片74HC165，將D0～D7轉換成串行數(shù)據(jù)讀入。 以少量的硬件實現(xiàn)快速CRC，能節(jié)省單片機的運算時間和存儲資源。用于發(fā)送端，能夠快速獲得CRC校驗碼，在系統(tǒng)其他任務很重時，能增強實時性。而用于接收端，除了上述優(yōu)點之外，還能顯著增強系統(tǒng)接收和確認信息的可靠性，適用于一些遠程控制的執(zhí)行裝置（如變頻驅動器、閥門定位控制器、重要的監(jiān)測報警裝置等）。這些裝置對于接收到的數(shù)據(jù)或命令信息，一旦因誤校驗而不能正確地判斷執(zhí)行，其后果都是比較嚴重的。因此，要提高嵌入式系統(tǒng)的可靠性和實時性，硬件 CRC校驗是一種選擇。 結語 本文在分析了常用CRC碼的反序生成原理的基礎上，給出了其編程運算的統(tǒng)一步驟，并提出了由硬件快速生成CRC碼或對接.收數(shù)據(jù)進行CRC校驗的電路和方法，可為嵌入式系統(tǒng)的可靠性和實時性設計提供參考。 參考文獻 1. 王新梅 肖國鎮(zhèn) 糾錯碼--原理與方法 2001 2. 羅偉雄 韓力 原東昌 通信原理與電路 1999 3. 李安福 符合ISO/IEC標準的快速CRC運算 [期刊論文] -單片機與嵌入式系統(tǒng)應用2008(10) 4. Williams Ross A Painless Guide to CRC Error Detection Algorithms 2008 作者： 大連理工大學 鄒久朋 林瑤瑤 周建 下載PDF文檔： 
CRC校驗編程和硬件快速校驗探討.pdf
(318.02 KB)
|
