CRC校驗(yàn)編程和硬件快速校驗(yàn)探討

引 言
循環(huán)冗余校驗(yàn)(Cyclic Remdancy 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)算過程也不相同。初接觸者往往難以領(lǐng)晤，省略CRC校驗(yàn)使通信的可靠性降低。而不少C語言程序，運(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ù)，將其作為表格，編程寫到程序存儲(chǔ)器中查詢而避免在線運(yùn)算，已是非常通用的做法。鑒于此，有些廠商在說明書中就直接給出了這個(gè)列表。但如果是CRC一16校驗(yàn)，存儲(chǔ)表格要占512字節(jié)(CRC一32則需要1 KB)，對(duì)于有限的單片機(jī)ROM資源來說所占比例不小，往往只因?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則傳輸無誤，為其他值則對(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ù)值，依此類推，直到所有通信數(shù)據(jù)都同中間余數(shù)異或，再模除完為止。如此得到最終的r位余數(shù)，作為全組數(shù)據(jù)校驗(yàn)的CRC碼附在該組數(shù)據(jù)之后發(fā)送。接收方以同樣的過程，算得收到數(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è)備來說，其最終余數(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)算，但這樣一來后面多位是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。
如上處理后，按理說被模除數(shù)和余數(shù)也應(yīng)該反序。但這樣的話r位的余數(shù)在同下一個(gè)k位數(shù)據(jù)模加時(shí)不但k位數(shù)據(jù)應(yīng)反序，而且必須左端(最高位)對(duì)齊進(jìn)行異或，處理起來不但麻煩也容易出錯(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ù)來求取CRC校驗(yàn)碼。但由于所有二進(jìn)制數(shù)的反序值都是唯一對(duì)應(yīng)的，所以并不影響生成CRC碼的唯一確定性，只是接收方需要按照同樣的反序規(guī)則處理.