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)鍵詞：Atmega128 CRC校驗(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位RISC MCU，執(zhí)行大多數(shù)指令只需一個(gè)時(shí)鐘周期，速度快（8MHz AVR的運(yùn)行速度約等于200MHz 80C51的運(yùn)行速度），32個(gè)通用寄存器直接與ALU相連，消除了運(yùn)算瓶頸；內(nèi)嵌可串行下載或自我編程的Flash和EPPROM，功能繁多，具有多種運(yùn)行模式。

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

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

    1.1 數(shù)據(jù)傳輸?shù)膸袷?/P>

　　根據(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.2 CRC校驗(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)步驟如下。

　　 ① 設(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)過生成多項(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建議：2048 Kb/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源程序見本刊網(wǎng)絡(luò)補(bǔ)充版（http://www.dpj.com.cn）。

    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生成表的程序詳見本刊網(wǎng)絡(luò)補(bǔ)充版（http://www.dpj.com.cn）。

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

　　圖2所示的流程圖中，在通過異或運(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)碼的源程序詳見本刊網(wǎng)絡(luò)補(bǔ)充版（http://www.dpj.com.cn）。

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ù)
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í)驗(yàn)結(jié)果均是在AVR Studio4仿真軟件上選用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í)間沒有特別高的要求時(shí)，可以采用直接計(jì)算法，以避免查表法中CRC生成表對(duì)存儲(chǔ)器空間的占用。

　?、?雖然實(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)的效果。