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

摘要：循環(huán)冗余碼校驗CRC是常用的重要校驗方法之一。AVR高速嵌入式單片機(jī)功能強(qiáng)大，在無線數(shù)據(jù)傳輸應(yīng)用方面具有很大優(yōu)勢。本文基于 Atmega128高速嵌入式單片機(jī)，實現(xiàn)32位CRC校驗碼的直接生成法和查表生成法;根據(jù)實驗結(jié)果，分析兩種方法的特點。 關(guān)鍵詞：Atmega128 CRC校驗碼 CRC生成表 數(shù)據(jù)段 引 言 　　隨著技術(shù)的不斷進(jìn)步，各種數(shù)據(jù)通信的應(yīng)用越來越廣泛。由于傳輸距離、現(xiàn)場狀況、干擾等諸多因素的影響，設(shè)備之間的通信數(shù)據(jù)常會發(fā)生一些無法預(yù)測的錯誤。為了降低錯誤所帶來的影響，一般在通信時采用數(shù)據(jù)校驗的辦法，而循環(huán)冗余碼校驗是常用的重要校驗方法之一。 　　AVR高速嵌入式單片機(jī)是8位RISC MCU，執(zhí)行大多數(shù)指令只需一個時鐘周期，速度快(8MHz AVR的運(yùn)行速度約等于200MHz 80C51的運(yùn)行速度)，32個通用寄存器直接與ALU相連，消除了運(yùn)算瓶頸;內(nèi)嵌可串行下載或自我編程的Flash和EPPROM，功能繁多，具有多種運(yùn)行模式。 　　本文采用Atmel公司的Atmega128高速嵌入式單片機(jī)，依照IEEE 1999年公布的802.11無線局域網(wǎng)協(xié)議標(biāo)準(zhǔn)，采用32位循環(huán)冗余校驗碼(Cyclic Redundancy Check)實現(xiàn)無線傳輸數(shù)據(jù)時的差錯校驗。 1 CRC循環(huán)冗余校驗碼原理 1.1 數(shù)據(jù)傳輸?shù)膸袷? 　　根據(jù)IEEE制定的802.11無線局域網(wǎng)絡(luò)協(xié)議，在數(shù)據(jù)傳輸時都應(yīng)按照幀傳輸。這里，我們采用了信息處理系統(tǒng)-數(shù)據(jù)通信-高級數(shù)據(jù)鏈路控制規(guī)程-幀結(jié)構(gòu)，它的每個幀由下列字段組成(傳輸順序自左至右)： 地 址控 制信 息 CRC校驗位地址——數(shù)據(jù)站地址字段; 控制——控制字段。 信息——信息字段; CRC校驗位——根據(jù)前面三個字段生成的CRC校驗位。 由地址、控制、信息三個字段組成的總的字段統(tǒng)稱為數(shù)據(jù)段。

1.2 CRC校驗碼的理論生成方法 　　CRC校驗采用多項式編碼方法，被處理的數(shù)據(jù)塊可以看作是一個n階的二進(jìn)制多項式。這里，假定待發(fā)送的二進(jìn)制數(shù)據(jù)段為g(x)，生成多項式為 m(x)，得到的CRC校驗碼為c(x)。 　　CRC校驗碼的編碼方法是用待發(fā)送的二進(jìn)制數(shù)據(jù)g(x)除以生成多項式m(x)，將最后的余數(shù)作為CRC校驗碼，實現(xiàn)步驟如下。 　　 ① 設(shè)待發(fā)送的數(shù)據(jù)塊是m位的二進(jìn)制多項式 g(x)，生成多項式為r階的m(x)。在數(shù)據(jù)塊的末尾添加r個0，數(shù)據(jù)塊的長度增加到m+r位，對應(yīng)的二進(jìn)制多項式為G(x) 。 　?、?用生成多項式m(x)去除G(x) ，求得余數(shù)為階數(shù)是r-1的二進(jìn)制多項式c(x)。此二進(jìn)制多項式 c(x)就是g(x)經(jīng)過生成多項式m(x)編碼的CRC校驗碼。

　?、?用模2的方式減去c(x)，得到的二進(jìn)制多項式就是包含了CRC校驗碼的待發(fā)送字符串。 CRC校驗可以100%地檢測出所有奇數(shù)個隨機(jī)錯誤和長度小于等于r(r為m(x)的階數(shù))的突發(fā)錯誤。所以，CRC的生成多項式的階數(shù)越高，誤判的概率就越小。CCITT建議：2048 Kb/s的PCM基群設(shè)備采用CRC-4方案，使用的CRC校驗碼生成多項式m(x)=x4+x+1 。采用16位CRC校驗，可以保證在 1014bit碼元中只含有1位未被檢測出的錯誤 。在IBM的同步數(shù)據(jù)鏈路控制規(guī)程SDLC的幀校驗序列FCS中，使用CRC-16，其生成多項式m(x)=x16+x15+x2+1;而在CCITT推薦的高級數(shù)據(jù)鏈路控制規(guī)程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用于重要數(shù)據(jù)傳輸十分合適，所以在通信、計算機(jī)等領(lǐng)域運(yùn)用十分廣泛。在一些UART通信控制芯片(如MC6582、Intel8273和Z80-SIO)內(nèi)，都采用了CRC校驗碼進(jìn)行差錯控制;以太網(wǎng)卡芯片、MPEG解碼芯片中，也采用CRC- 32進(jìn)行差錯控制。 　　m(x) 生成多項式的系數(shù)為0或1，但是m(x) 的首項系數(shù)為1，末項系數(shù)也必須為1。m(x) 的次數(shù)越高，其檢錯能力越強(qiáng)。 2 使用Atmega128生成32位CRC校驗碼 2.1 直接計算法生成32位CRC校驗碼 　　直接計算法就是依據(jù)CRC校驗碼的產(chǎn)生原理來設(shè)計程序。其優(yōu)點是模塊代碼少，修改靈活，可移植性好。這種算法簡單，容易實現(xiàn)，對任意長度生成多項式 m(x) 都適用。在發(fā)送的數(shù)據(jù)不長的情況下可以使用，但是如果發(fā)送的數(shù)據(jù)塊很長，這種方法就不太適合了。因為它1次只能處理1位數(shù)據(jù)，效率太低，運(yùn)算量大。 　　計算法生成32位CRC校驗碼的流程如圖1所示。 　　用AVR單片機(jī)匯編語言實現(xiàn)CRC-32源程序見本刊網(wǎng)絡(luò)補(bǔ)充版(http://www.dpj.com.cn)。 2.2 查表法生成32位CRC校驗碼 　　和直接計算法相反，查表法生成32位CRC校驗碼的優(yōu)點是運(yùn)算量小，速度快;缺點是可移植性較差。這種算法首先要求得到32位CRC生成表，由于1個字節(jié)有8位，所以這個表總共有256項。但是，由于AVR高速嵌入式單片機(jī)中的寄存器是以1個字節(jié)為單位的，所以在編程實現(xiàn)中，這個CRC生成表總共有 1024項，分別從0"1023;每4位對應(yīng)1個32位CRC生成表的項，每一項都從高到低降冪排列。關(guān)于32位CRC生成表的程序詳見本刊網(wǎng)絡(luò)補(bǔ)充版(http://www.dpj.com.cn)。 　　查表法生成32位CRC校驗碼的流程如圖2所示。 　　圖2所示的流程圖中，在通過異或運(yùn)算得到CRC生成表的索引時，由于AVR高速嵌入式單片機(jī)中的寄存器是以1個字節(jié)為單元的，所以在編程實現(xiàn)中應(yīng)根據(jù)所要求生成的CRC校驗碼的位數(shù)乘以相應(yīng)的系數(shù)。例如：在數(shù)據(jù)傳輸時要求32位CRC校驗碼，應(yīng)該把所得到的索引數(shù)乘以系數(shù)4，然后再從高到低依次取得 32位CRC生成表單元中的內(nèi)容。 　　使用查表法得到32位CRC校驗碼的源程序詳見本刊網(wǎng)絡(luò)補(bǔ)充版(http://www.dpj.com.cn)。 3 實驗結(jié)果 　　為了比較所述兩種32位CRC校驗碼生成方法的特點，分別選取不同字節(jié)數(shù)的數(shù)據(jù)段，對兩種方法在不同情況下的效果進(jìn)行比較，如表1所列。 表1 兩種算法實驗結(jié)果對比 計算法生成32位CRC校驗碼查表法生成32位CRC校驗碼 數(shù)據(jù)段字節(jié)數(shù)程序耗時/μs 周期數(shù)程序耗時/μs 周期數(shù) 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 　　以上所有實驗結(jié)果均是在AVR Studio4仿真軟件上選用Atmel公司的Atmega128高速嵌入式單片機(jī)為實驗設(shè)備平臺，在12MHz運(yùn)行速度下模擬所得。 　　在調(diào)用32位CRC生成表程序以得到32位CRC生成表時，耗時3968.33μs，執(zhí)行了47620個時鐘周期。從上述實驗結(jié)果可得出以下幾點結(jié)論。 　?、? 如果不考慮生成32位CRC生成表的時間，例如直接把32位CRC生成表燒入到Atmega128的可編程閃速存儲器Flash中，由表1可清楚地看出，查表法的運(yùn)行速度比直接計算法要快得多。因此，在類似情況下，在進(jìn)行數(shù)據(jù)傳輸要求生成32位CRC校驗碼時，應(yīng)該選擇查表法。 　?、?在某些應(yīng)用中，如果對硬件存儲器空間要求很高，并且在一定程度上對時間沒有特別高的要求時，可以采用直接計算法，以避免查表法中CRC生成表對存儲器空間的占用。 　　③ 雖然實驗結(jié)果對32位CRC校驗碼的兩種算法進(jìn)行了對比，但是所得到的結(jié)論也適用于8位、16位、24位CRC校驗碼。 結(jié) 語 　　CRC循環(huán)冗余校驗碼是一種方便、有效、快速的校驗方法，被廣泛應(yīng)用在許多實際工程中。文中所列的兩種算法——查表法和直接計算法，都可以得到CRC 校驗碼;但是它們各有特點，在工程應(yīng)用中應(yīng)該根據(jù)實際需要選擇最適合的方法，以得到最優(yōu)的效果。