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

時間：2004-12-05 13:41:00

關鍵字： AVR單片機 CRC校驗碼單片機C BSP

手機看文章

掃描二維碼
隨時隨地手機看文章

[導讀]循環(huán)冗余碼校驗CRC是常用的重要校驗方法之一。

摘要：循環(huán)冗余碼校驗CRC是常用的重要校驗方法之一。AVR高速嵌入式單片機功能強大，在無線數(shù)據(jù)傳輸應用方面具有很大優(yōu)勢。本文基于Atmega128高速嵌入式單片機，實現(xiàn)32位CRC校驗碼的直接生成法和查表生成法；根據(jù)實驗結果，分析兩種方法的特點。

關鍵詞：Atmega128 CRC校驗碼 CRC生成表數(shù)據(jù)段

引言

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

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

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

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

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

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

地址

控制

信息

CRC校驗位

地址——數(shù)據(jù)站地址字段；

控制——控制字段。

信息——信息字段；

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

由地址、控制、信息三個字段組成的總的字段統(tǒng)稱為數(shù)據(jù)段。

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

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

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

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

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

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

CRC校驗可以100%地檢測出所有奇數(shù)個隨機錯誤和長度小于等于r（r為m(x)的階數(shù)）的突發(fā)錯誤。所以，CRC的生成多項式的階數(shù)越高，誤判的概率就越小。CCITT建議：2048 Kb/s的PCM基群設備采用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ù)傳輸十分合適，所以在通信、計算機等領域運用十分廣泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）內(nèi)，都采用了CRC校驗碼進行差錯控制；以太網(wǎng)卡芯片、MPEG解碼芯片中，也采用CRC-32進行差錯控制。

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

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

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

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

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

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

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

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

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

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

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

3 實驗結果

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

表1 兩種算法實驗結果對比

	計算法生成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