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

摘要：循環(huán)冗余碼校驗CRC是常用的重要校驗方法之一。AVR高速嵌入式單片機功能強大，在無(wú)線(xiàn)數據傳輸應用方面具有很大優(yōu)勢。本文基于 Atmega128高速嵌入式單片機，實(shí)現32位CRC校驗碼的直接生成法和查表生成法;根據實(shí)驗結果，分析兩種方法的特點(diǎn)。 關(guān)鍵詞：Atmega128 CRC校驗碼 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校驗位地址——數據站地址字段; 控制——控制字段。 信息——信息字段; 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項，分別從01023;每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í)驗結果對比 計算法生成32位CRC校驗碼查表法生成32位CRC校驗碼 數據段字節數程序耗時(shí)/μs 周期數程序耗時(shí)/μs 周期數 3 193.67 2324 29.33 352 4 222.50 2670 34.83 418 10 319.58 3835 48.58 583 20 517.92 6215 76.08 913 40 886.25 10635 131.08 1573 80 1582.92 189995 241.08 2893 150 2957.08 35485 433.58 5203 200 3891.25 46695 571.08 6853 220 4267.92 51215 626.08 7513 239 4645.17 55742 678.33 8140 240 4659.58 55915 681.08 8173 250 4872.92 58475 708.58 8503 　　以上所有實(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)的效果。