CRC校驗編程和硬件快速校驗探討

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

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