Atmega128單片機CRC校驗碼的查表與直接生成

引 言

　　隨著(zhù)技術(shù)的不斷進(jìn)步，各種數據通信的應用越來(lái)越廣泛。由于傳輸距離、現場(chǎng)狀況、干擾等諸多因素的影響，設備之間的通信數據常會(huì )發(fā)生一些無(wú)法預測的錯誤。為了降低錯誤所帶來(lái)的影響，一般在通信時(shí)采用數據校驗的辦法，而循環(huán)冗余碼校驗是常用的重要校驗方法之一。

　　AVR高速嵌入式單片機是8位RISC MCU，執行大多數指令只需一個(gè)時(shí)鐘周期，速度快（8MHz AVR的運行速度約等于200MHz 80C51的運行速度），32個(gè)通用寄存器直接與ALU相連，消除了運算瓶頸；內嵌可串行下載或自我編程的Flash和EPPROM，功能繁多，具有多種運行模式。

　　本文采用Atmel公司的Atmega128高速嵌入式單片機，依照IEEE 1999年公布的802.11無(wú)線(xiàn)局域網(wǎng)協(xié)議標準，采用32位循環(huán)冗余校驗碼（Cyclic Redundancy Check）實(shí)現無(wú)線(xiàn)傳輸數據時(shí)的差錯校驗。

1 CRC循環(huán)冗余校驗碼原理

1.1 數據傳輸的幀格式

　　根據IEEE制定的802.11無(wú)線(xiàn)局域網(wǎng)絡(luò )協(xié)議，在數據傳輸時(shí)都應按照幀傳輸。這里，我們采用了信息處理系統－數據通信－高級數據鏈路控制規程－幀結構，它的每個(gè)幀由下列字段組成（傳輸順序自左至右）：

地址——數據站地址字段；

控制——控制字段。

信息——信息字段；

CRC校驗位——根據前面三個(gè)字段生成的CRC校驗位。

由地址、控制、信息三個(gè)字段組成的總的字段統稱(chēng)為數據段。

1.2 CRC校驗碼的理論生成方法

　　CRC校驗采用多項式編碼方法，被處理的數據塊可以看作是一個(gè)n階的二進(jìn)制多項式。這里，假定待發(fā)送的二進(jìn)制數據段為g(x)，生成多項式為 m(x)，得到的CRC校驗碼為c(x)。

　　CRC校驗碼的編碼方法是用待發(fā)送的二進(jìn)制數據g(x)除以生成多項式m(x)，將最后的余數作為CRC校驗碼，實(shí)現步驟如下。

　　 ① 設待發(fā)送的數據塊是m位的二進(jìn)制多項式 g(x)，生成多項式為r階的m(x)。在數據塊的末尾添加r個(gè)0，數據塊的長(cháng)度增加到m+r位，對應的二進(jìn)制多項式為G(x) 。

　?、?用生成多項式m(x)去除G(x) ，求得余數為階數是r-1的二進(jìn)制多項式c(x)。此二進(jìn)制多項式 c(x)就是g(x)經(jīng)過(guò)生成多項式m(x)編碼的CRC校驗碼。

　?、?用模2的方式減去c(x)，得到的二進(jìn)制多項式就是包含了CRC校驗碼的待發(fā)送字符串。

CRC校驗可以100%地檢測出所有奇數個(gè)隨機錯誤和長(cháng)度小于等于r（r為m(x)的階數）的突發(fā)錯誤。所以，CRC的生成多項式的階數越高，誤判的概率就越小。CCITT建議：2048 Kb/s的PCM基群設備采用CRC-4方案，使用的CRC校驗碼生成多項式m(x)=x4+x+1 。采用16位CRC校驗，可以保證在 1014bit碼元中只含有1位未被檢測出的錯誤 。在IBM的同步數據鏈路控制規程SDLC的幀校驗序列FCS中，使用CRC-16，其生成多項式m(x)=x16+x15+x2+1；而在CCITT推薦的高級數據鏈路控制規程HDLC的幀校驗序列FCS中，使用CCITT-16，其生成多項式m(x)= x16+x15+x5+1。CRC-32的生成多項式m(x)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1。CRC-32出錯的概率為CRC-16的10-5。由于CRC-32的可靠性，把CRC-32用于重要數據傳輸十分合適，所以在通信、計算機等領(lǐng)域運用十分廣泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）內，都采用了CRC校驗碼進(jìn)行差錯控制；以太網(wǎng)卡芯片、MPEG解碼芯片中，也采用CRC-32進(jìn)行差錯控制。

　　m(x) 生成多項式的系數為0或1，但是m(x) 的首項系數為1，末項系數也必須為1。m(x) 的次數越高，其檢錯能力越強。

2 使用Atmega128生成32位CRC校驗碼

2.1 直接計算法生成32位CRC校驗碼

　　直接計算法就是依據CRC校驗碼的產(chǎn)生原理來(lái)設計程序。其優(yōu)點(diǎn)是模塊代碼少，修改靈活，可移植性好。這種算法簡(jiǎn)單，容易實(shí)現，對任意長(cháng)度生成多項式m(x) 都適用。在發(fā)送的數據不長(cháng)的情況下可以使用，但是如果發(fā)送的數據塊很長(cháng)，這種方法就不太適合了。因為它1次只能處理1位數據，效率太低，運算量大。

　　計算法生成32位CRC校驗碼的流程如圖1所示。

　　用AVR單片機匯編語(yǔ)言實(shí)現CRC-32源程序見(jiàn)本刊網(wǎng)絡(luò )補充版（http://www.dpj.com.cn）。

2.2 查表法生成32位CRC校驗碼

　　和直接計算法相反，查表法生成32位CRC校驗碼的優(yōu)點(diǎn)是運算量小，速度快；缺點(diǎn)是可移植性較差。這種算法首先要求得到32位CRC生成表，由于1個(gè)字節有8位，所以這個(gè)表總共有256項。但是，由于A(yíng)VR高速嵌入式單片機中的寄存器是以1個(gè)字節為單位的，所以在編程實(shí)現中，這個(gè)CRC生成表總共有1024項，分別從0~1023；每4位對應1個(gè)32位CRC生成表的項，每一項都從高到低降冪排列。關(guān)于32位CRC生成表的程序詳見(jiàn)本刊網(wǎng)絡(luò )補充版（http://www.dpj.com.cn）。

　　查表法生成32位CRC校驗碼的流程如圖2所示。

　　圖2所示的流程圖中，在通過(guò)異或運算得到CRC生成表的索引時(shí)，由于A(yíng)VR高速嵌入式單片機中的寄存器是以1個(gè)字節為單元的，所以在編程實(shí)現中應根據所要求生成的CRC校驗碼的位數乘以相應的系數。例如：在數據傳輸時(shí)要求32位CRC校驗碼，應該把所得到的索引數乘以系數4，然后再從高到低依次取得32位CRC生成表單元中的內容。

　　使用查表法得到32位CRC校驗碼的源程序詳見(jiàn)本刊網(wǎng)絡(luò )補充版（http://www.dpj.com.cn）。

3 實(shí)驗結果

　　為了比較所述兩種32位CRC校驗碼生成方法的特點(diǎn)，分別選取不同字節數的數據段，對兩種方法在不同情況下的效果進(jìn)行比較，如表1所列。

表1 兩種算法實(shí)驗結果對比

　　以上所有實(shí)驗結果均是在A(yíng)VR Studio4仿真軟件上選用Atmel公司的Atmega128高速嵌入式單片機為實(shí)驗設備平臺，在12MHz運行速度下模擬所得。

　　在調用32位CRC生成表程序以得到32位CRC生成表時(shí)，耗時(shí)3968.33μs，執行了47620個(gè)時(shí)鐘周期。從上述實(shí)驗結果可得出以下幾點(diǎn)結論。

　?、?如果不考慮生成32位CRC生成表的時(shí)間，例如直接把32位CRC生成表燒入到Atmega128的可編程閃速存儲器Flash中，由表1可清楚地看出，查表法的運行速度比直接計算法要快得多。因此，在類(lèi)似情況下，在進(jìn)行數據傳輸要求生成32位CRC校驗碼時(shí)，應該選擇查表法。

　?、?在某些應用中，如果對硬件存儲器空間要求很高，并且在一定程度上對時(shí)間沒(méi)有特別高的要求時(shí)，可以采用直接計算法，以避免查表法中CRC生成表對存儲器空間的占用。

　?、?雖然實(shí)驗結果對32位CRC校驗碼的兩種算法進(jìn)行了對比，但是所得到的結論也適用于8位、16位、24位CRC校驗碼。

結 語(yǔ)

　　CRC循環(huán)冗余校驗碼是一種方便、有效、快速的校驗方法，被廣泛應用在許多實(shí)際工程中。文中所列的兩種算法——查表法和直接計算法，都可以得到CRC校驗碼；但是它們各有特點(diǎn)，在工程應用中應該根據實(shí)際需要選擇最適合的方法，以得到最優(yōu)的效果。