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

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

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

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

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

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

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

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