- 相關(guān)推薦
AVR單片機(jī)CRC校驗(yàn)碼的查表與直接生成
摘要：循環(huán)冗余碼校驗(yàn)CRC是常用的重要校驗(yàn)方法之一。AVR高速嵌入式單片機(jī)功能強(qiáng)大，在無(wú)線數(shù)據(jù)傳輸應(yīng)用方面具有很大優(yōu)勢(shì)。本文基于Atmega128高速嵌入式單片機(jī)，實(shí)現(xiàn)32位CRC校驗(yàn)碼的直接生成法和查表生成法；根據(jù)實(shí)驗(yàn)結(jié)果，分析兩種方法的特點(diǎn)。關(guān)鍵詞：Atmega128CRC校驗(yàn)碼CRC生成表數(shù)據(jù)段
引言
隨著技術(shù)的不斷進(jìn)步，各種數(shù)據(jù)通信的應(yīng)用越來(lái)越廣泛。由于傳輸距離、現(xiàn)場(chǎng)狀況、干擾等諸多因素的影響，設(shè)備之間的通信數(shù)據(jù)常會(huì)發(fā)生一些無(wú)法預(yù)測(cè)的錯(cuò)誤。為了降低錯(cuò)誤所帶來(lái)的影響，一般在通信時(shí)采用數(shù)據(jù)校驗(yàn)的辦法，而循環(huán)冗余碼校驗(yàn)是常用的重要校驗(yàn)方法之一。
AVR高速嵌入式單片機(jī)是8位RISCMCU,執(zhí)行大多數(shù)指令只需一個(gè)時(shí)鐘周期，速度快（8MHzAVR的運(yùn)行速度約等于200MHz80C51的運(yùn)行速度），32個(gè)通用寄存器直接與ALU相連，消除了運(yùn)算瓶頸；內(nèi)嵌可串行下載或自我編程的Flash和EPPROM,功能繁多，具有多種運(yùn)行模式。
本文采用Atmel公司的Atmega128高速嵌入式單片機(jī)，依照IEEE1999年公布的802.11無(wú)線局域網(wǎng)協(xié)議標(biāo)準(zhǔn)，采用32位循環(huán)冗余校驗(yàn)碼（CyclicRedundancyCheck）實(shí)現(xiàn)無(wú)線傳輸數(shù)據(jù)時(shí)的差錯(cuò)校驗(yàn)。
1CRC循環(huán)冗余校驗(yàn)碼原理
1.1數(shù)據(jù)傳輸?shù)膸袷?br />
根據(jù)IEEE制定的802.11無(wú)線局域網(wǎng)絡(luò)協(xié)議，在數(shù)據(jù)傳輸時(shí)都應(yīng)按照幀傳輸。這里，我們采用了信息處理系統(tǒng)-數(shù)據(jù)通信-高級(jí)數(shù)據(jù)鏈路控制規(guī)程-幀結(jié)構(gòu)，它的每個(gè)幀由下列字段組成（傳輸順序自左至右）：
地址控制信息CRC校驗(yàn)位
地址——數(shù)據(jù)站地址字段；
控制——控制字段。
信息——信息字段；
CRC校驗(yàn)位——根據(jù)前面三個(gè)字段生成的CRC校驗(yàn)位。
由地址、控制、信息三個(gè)字段組成的總的字段統(tǒng)稱為數(shù)據(jù)段。
1.2CRC校驗(yàn)碼的理論生成方法
CRC校驗(yàn)采用多項(xiàng)式編碼方法，被處理的數(shù)據(jù)塊可以看作是一個(gè)n階的二進(jìn)制多項(xiàng)式。這里，假定待發(fā)送的二進(jìn)制數(shù)據(jù)段為g（x），生成多項(xiàng)式為m（x），得到的CRC校驗(yàn)碼為c（x）。
CRC校驗(yàn)碼的編碼方法是用待發(fā)送的二進(jìn)制數(shù)據(jù)g（x）除以生成多項(xiàng)式m（x），將最后的余數(shù)作為CRC校驗(yàn)碼，實(shí)現(xiàn)步驟如下。
�、僭O(shè)待發(fā)送的數(shù)據(jù)塊是m位的二進(jìn)制多項(xiàng)式g（x），生成多項(xiàng)式為r階的m（x）。在數(shù)據(jù)塊的末尾添加r個(gè)0,數(shù)據(jù)塊的長(zhǎng)度增加到m+r位，對(duì)應(yīng)的二進(jìn)制多項(xiàng)式為G（x）。
�、谟蒙啥囗�(xiàng)式m（x）去除G（x），求得余數(shù)為階數(shù)是r-1的二進(jìn)制多項(xiàng)式c（x）。此二進(jìn)制多項(xiàng)式c（x）就是g（x）經(jīng)過(guò)生成多項(xiàng)式m（x）編碼的CRC校驗(yàn)碼。
③用模2的方式減去c（x），得到的二進(jìn)制多項(xiàng)式就是包含了CRC校驗(yàn)碼的待發(fā)送字符串。
CRC校驗(yàn)可以100%地檢測(cè)出所有奇數(shù)個(gè)隨機(jī)錯(cuò)誤和長(zhǎng)度小于等于r（r為m（x）的階數(shù)）的突發(fā)錯(cuò)誤。所以，CRC的生成多項(xiàng)式的階數(shù)越高，誤判的概率就越小。CCITT建議：2048Kb/s的PCM基群設(shè)備采用CRC-4方案，使用的CRC校驗(yàn)碼生成多項(xiàng)式m（x）=x4+x+1.采用16位CRC校驗(yàn)，可以保證在1014bit碼元中只含有1位未被檢測(cè)出的錯(cuò)誤。在IBM的同步數(shù)據(jù)鏈路控制規(guī)程SDLC的幀校驗(yàn)序列FCS中，使用CRC-16,其生成多項(xiàng)式m（x）=x16+x15+x2+1;而在CCITT推薦的高級(jí)數(shù)據(jù)鏈路控制規(guī)程HDLC的幀校驗(yàn)序列FCS中，使用CCITT-16,其生成多項(xiàng)式m（x）=x16+x15+x5+1.CRC-32的生成多項(xiàng)式m（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1.CRC-32出錯(cuò)的概率為CRC-16的10-5.由于CRC-32的可靠性，把CRC-32用于重要數(shù)據(jù)傳輸十分合適，所以在通信、計(jì)算機(jī)等領(lǐng)域運(yùn)用十分廣泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）內(nèi)，都采用了CRC校驗(yàn)碼進(jìn)行差錯(cuò)控制；以太網(wǎng)卡芯片、MPEG解碼芯片中，也采用CRC-32進(jìn)行差錯(cuò)控制。
m（x）生成多項(xiàng)式的系數(shù)為0或1,但是m（x）的首項(xiàng)系數(shù)為1,末項(xiàng)系數(shù)也必須為1.m（x）的次數(shù)越高，其檢錯(cuò)能力越強(qiáng)。
2使用Atmega128生成32位CRC校驗(yàn)碼
2.1直接計(jì)算法生成32位CRC校驗(yàn)碼
直接計(jì)算法就是依據(jù)CRC校驗(yàn)碼的產(chǎn)生原理來(lái)設(shè)計(jì)程序。其優(yōu)點(diǎn)是模塊代碼少，修改靈活，可移植性好。這種算法簡(jiǎn)單，容易實(shí)現(xiàn)，對(duì)任意長(zhǎng)度生成多項(xiàng)式m（x）都適用。在發(fā)送的數(shù)據(jù)不長(zhǎng)的情況下可以使用，但是如果發(fā)送的數(shù)據(jù)塊很長(zhǎng)，這種方法就不太適合了。因?yàn)樗?次只能處理1位數(shù)據(jù)，效率太低，運(yùn)算量大。
計(jì)算法生成32位CRC校驗(yàn)碼的流程如圖1所示。
用AVR單片機(jī)匯編語(yǔ)言實(shí)現(xiàn)CRC-32源程序見(jiàn)本刊網(wǎng)絡(luò)補(bǔ)充版
2.2查表法生成32位CRC校驗(yàn)碼
和直接計(jì)算法相反，查表法生成32位CRC校驗(yàn)碼的優(yōu)點(diǎn)是運(yùn)算量小，速度快；缺點(diǎn)是可移植性較差。這種算法首先要求得到32位CRC生成表，由于1個(gè)字節(jié)有8位，所以這個(gè)表總共有256項(xiàng)。但是，由于AVR高速嵌入式單片機(jī)中的寄存器是以1個(gè)字節(jié)為單位的，所以在編程實(shí)現(xiàn)中，這個(gè)CRC生成表總共有1024項(xiàng)，分別從0——1023;每4位對(duì)應(yīng)1個(gè)32位CRC生成表的項(xiàng)，每一項(xiàng)都從高到低降冪排列。關(guān)于32位CRC生成表的程序詳見(jiàn)本刊網(wǎng)絡(luò)補(bǔ)充版
查表法生成32位CRC校驗(yàn)碼的流程如圖2所示。
圖2所示的流程圖中，在通過(guò)異或運(yùn)算得到CRC生成表的索引時(shí)，由于AVR高速嵌入式單片機(jī)中的寄存器是以1個(gè)字節(jié)為單元的，所以在編程實(shí)現(xiàn)中應(yīng)根據(jù)所要求生成的CRC校驗(yàn)碼的位數(shù)乘以相應(yīng)的系數(shù)。例如：在數(shù)據(jù)傳輸時(shí)要求32位CRC校驗(yàn)碼，應(yīng)該把所得到的索引數(shù)乘以系數(shù)4,然后再?gòu)母叩降鸵来稳〉?2位CRC生成表單元中的內(nèi)容。
使用查表法得到32位CRC校驗(yàn)碼的源程序詳見(jiàn)本刊網(wǎng)絡(luò)補(bǔ)充版
3實(shí)驗(yàn)結(jié)果
為了比較所述兩種32位CRC校驗(yàn)碼生成方法的特點(diǎn)，分別選取不同字節(jié)數(shù)的數(shù)據(jù)段，對(duì)兩種方法在不同情況下的效果進(jìn)行比較，如表1所列。
表1兩種算法實(shí)驗(yàn)結(jié)果對(duì)比
計(jì)算法生成32位CRC校驗(yàn)碼查表法生成32位CRC校驗(yàn)碼數(shù)據(jù)段字節(jié)數(shù)程序耗時(shí)/μs周期數(shù)程序耗時(shí)/μs周期數(shù)3193.67232429.333524222.50267034.8341810319.58383548.5858320517.92621576.0891340886.2510635131.081573801582.92189995241.0828931502957.0835485433.5852032003891.2546695571.0868532204267.9251215626.0875132394645.1755742678.3381402404659.5855915681.0881732504872.9258475708.588503
以上所有實(shí)驗(yàn)結(jié)果均是在AVRStudio4仿真軟件上選用Atmel公司的Atmega128高速嵌入式單片機(jī)為實(shí)驗(yàn)設(shè)備平臺(tái)，在12MHz運(yùn)行速度下模擬所得。
在調(diào)用32位CRC生成表程序以得到32位CRC生成表時(shí)，耗時(shí)3968.33μs,執(zhí)行了47620個(gè)時(shí)鐘周期。從上述實(shí)驗(yàn)結(jié)果可得出以下幾點(diǎn)結(jié)論。
�、偃绻豢紤]生成32位CRC生成表的時(shí)間，例如直接把32位CRC生成表燒入到Atmega128的可編程閃速存儲(chǔ)器Flash中，由表1可清楚地看出，查表法的運(yùn)行速度比直接計(jì)算法要快得多。因此，在類似情況下，在進(jìn)行數(shù)據(jù)傳輸要求生成32位CRC校驗(yàn)碼時(shí)，應(yīng)該選擇查表法。
�、谠谀承⿷�(yīng)用中，如果對(duì)硬件存儲(chǔ)器空間要求很高，并且在一定程度上對(duì)時(shí)間沒(méi)有特別高的要求時(shí)，可以采用直接計(jì)算法，以避免查表法中CRC生成表對(duì)存儲(chǔ)器空間的占用。
�、垭m然實(shí)驗(yàn)結(jié)果對(duì)32位CRC校驗(yàn)碼的兩種算法進(jìn)行了對(duì)比，但是所得到的結(jié)論也適用于8位、16位、24位CRC校驗(yàn)碼。
結(jié)語(yǔ)
CRC循環(huán)冗余校驗(yàn)碼是一種方便、有效、快速的校驗(yàn)方法，被廣泛應(yīng)用在許多實(shí)際工程中。文中所列的兩種算法——查表法和直接計(jì)算法，都可以得到CRC校驗(yàn)碼；但是它們各有特點(diǎn)，在工程應(yīng)用中應(yīng)該根據(jù)實(shí)際需要選擇最適合的方法，以得到最優(yōu)的效果。
【AVR單片機(jī)CRC校驗(yàn)碼的查表與直接生成】相關(guān)文章：
AVR單片機(jī)GCC編程08-06
AVR單片機(jī)的RC5和RC6算法比較與改進(jìn)08-06
一種基于AVR單片機(jī)的工頻干擾濾除快速算法08-06
計(jì)算法簡(jiǎn)單實(shí)現(xiàn)crc校驗(yàn)08-06
制作調(diào)查表08-16
用C語(yǔ)言實(shí)現(xiàn)CRC校驗(yàn)計(jì)算08-06
氣柜直接置換08-06
氣柜直接置換-08-06