- 相關推薦
AVR單片機CRC校驗碼的查表與直接生成
摘要：循環冗余碼校驗CRC是常用的重要校驗方法之一。AVR高速嵌入式單片機功能強大，在無線數據傳輸應用方面具有很大優勢。本文基于Atmega128高速嵌入式單片機，實現32位CRC校驗碼的直接生成法和查表生成法；根據實驗結果，分析兩種方法的特點。關鍵詞：Atmega128CRC校驗碼CRC生成表數據段
引言
隨著技術的不斷進步，各種數據通信的應用越來越廣泛。由于傳輸距離、現場狀況、干擾等諸多因素的影響，設備之間的通信數據常會發生一些無法預測的錯誤。為了降低錯誤所帶來的影響，一般在通信時采用數據校驗的辦法，而循環冗余碼校驗是常用的重要校驗方法之一。
AVR高速嵌入式單片機是8位RISCMCU,執行大多數指令只需一個時鐘周期，速度快（8MHzAVR的運行速度約等于200MHz80C51的運行速度），32個通用寄存器直接與ALU相連，消除了運算瓶頸；內嵌可串行下載或自我編程的Flash和EPPROM,功能繁多，具有多種運行模式。
本文采用Atmel公司的Atmega128高速嵌入式單片機，依照IEEE1999年公布的802.11無線局域網協議標準，采用32位循環冗余校驗碼（CyclicRedundancyCheck）實現無線傳輸數據時的差錯校驗。
1CRC循環冗余校驗碼原理
1.1數據傳輸的幀格式
根據IEEE制定的802.11無線局域網絡協議，在數據傳輸時都應按照幀傳輸。這里，我們采用了信息處理系統-數據通信-高級數據鏈路控制規程-幀結構，它的每個幀由下列字段組成（傳輸順序自左至右）：
地址控制信息CRC校驗位
地址——數據站地址字段；
控制——控制字段。
信息——信息字段；
CRC校驗位——根據前面三個字段生成的CRC校驗位。
由地址、控制、信息三個字段組成的總的字段統稱為數據段。
1.2CRC校驗碼的理論生成方法
CRC校驗采用多項式編碼方法，被處理的數據塊可以看作是一個n階的二進制多項式。這里，假定待發送的二進制數據段為g（x），生成多項式為m（x），得到的CRC校驗碼為c（x）。
CRC校驗碼的編碼方法是用待發送的二進制數據g（x）除以生成多項式m（x），將最后的余數作為CRC校驗碼，實現步驟如下。
①設待發送的數據塊是m位的二進制多項式g（x），生成多項式為r階的m（x）。在數據塊的末尾添加r個0,數據塊的長度增加到m+r位，對應的二進制多項式為G（x）。
②用生成多項式m（x）去除G（x），求得余數為階數是r-1的二進制多項式c（x）。此二進制多項式c（x）就是g（x）經過生成多項式m（x）編碼的CRC校驗碼。
③用模2的方式減去c（x），得到的二進制多項式就是包含了CRC校驗碼的待發送字符串。
CRC校驗可以100%地檢測出所有奇數個隨機錯誤和長度小于等于r（r為m（x）的階數）的突發錯誤。所以，CRC的生成多項式的階數越高，誤判的概率就越小。CCITT建議：2048Kb/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用于重要數據傳輸十分合適，所以在通信、計算機等領域運用十分廣泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）內，都采用了CRC校驗碼進行差錯控制；以太網卡芯片、MPEG解碼芯片中，也采用CRC-32進行差錯控制。
m（x）生成多項式的系數為0或1,但是m（x）的首項系數為1,末項系數也必須為1.m（x）的次數越高，其檢錯能力越強。
2使用Atmega128生成32位CRC校驗碼
2.1直接計算法生成32位CRC校驗碼
直接計算法就是依據CRC校驗碼的產生原理來設計程序。其優點是模塊代碼少，修改靈活，可移植性好。這種算法簡單，容易實現，對任意長度生成多項式m（x）都適用。在發送的數據不長的情況下可以使用，但是如果發送的數據塊很長，這種方法就不太適合了。因為它1次只能處理1位數據，效率太低，運算量大。
計算法生成32位CRC校驗碼的流程如圖1所示。
用AVR單片機匯編語言實現CRC-32源程序見本刊網絡補充版
2.2查表法生成32位CRC校驗碼
和直接計算法相反，查表法生成32位CRC校驗碼的優點是運算量小，速度快；缺點是可移植性較差。這種算法首先要求得到32位CRC生成表，由于1個字節有8位，所以這個表總共有256項。但是，由于AVR高速嵌入式單片機中的寄存器是以1個字節為單位的，所以在編程實現中，這個CRC生成表總共有1024項，分別從0——1023;每4位對應1個32位CRC生成表的項，每一項都從高到低降冪排列。關于32位CRC生成表的程序詳見本刊網絡補充版
查表法生成32位CRC校驗碼的流程如圖2所示。
圖2所示的流程圖中，在通過異或運算得到CRC生成表的索引時，由于AVR高速嵌入式單片機中的寄存器是以1個字節為單元的，所以在編程實現中應根據所要求生成的CRC校驗碼的位數乘以相應的系數。例如：在數據傳輸時要求32位CRC校驗碼，應該把所得到的索引數乘以系數4,然后再從高到低依次取得32位CRC生成表單元中的內容。
使用查表法得到32位CRC校驗碼的源程序詳見本刊網絡補充版
3實驗結果
為了比較所述兩種32位CRC校驗碼生成方法的特點，分別選取不同字節數的數據段，對兩種方法在不同情況下的效果進行比較，如表1所列。
表1兩種算法實驗結果對比
計算法生成32位CRC校驗碼查表法生成32位CRC校驗碼數據段字節數程序耗時/μs周期數程序耗時/μs周期數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
以上所有實驗結果均是在AVRStudio4仿真軟件上選用Atmel公司的Atmega128高速嵌入式單片機為實驗設備平臺，在12MHz運行速度下模擬所得。
在調用32位CRC生成表程序以得到32位CRC生成表時，耗時3968.33μs,執行了47620個時鐘周期。從上述實驗結果可得出以下幾點結論。
①如果不考慮生成32位CRC生成表的時間，例如直接把32位CRC生成表燒入到Atmega128的可編程閃速存儲器Flash中，由表1可清楚地看出，查表法的運行速度比直接計算法要快得多。因此，在類似情況下，在進行數據傳輸要求生成32位CRC校驗碼時，應該選擇查表法。
②在某些應用中，如果對硬件存儲器空間要求很高，并且在一定程度上對時間沒有特別高的要求時，可以采用直接計算法，以避免查表法中CRC生成表對存儲器空間的占用。
③雖然實驗結果對32位CRC校驗碼的兩種算法進行了對比，但是所得到的結論也適用于8位、16位、24位CRC校驗碼。
結語
CRC循環冗余校驗碼是一種方便、有效、快速的校驗方法，被廣泛應用在許多實際工程中。文中所列的兩種算法——查表法和直接計算法，都可以得到CRC校驗碼；但是它們各有特點，在工程應用中應該根據實際需要選擇最適合的方法，以得到最優的效果。
【AVR單片機CRC校驗碼的查表與直接生成】相關文章：
AVR單片機GCC編程08-06
計算法簡單實現crc校驗08-06
CRC校驗實用程序庫08-06
制作調查表08-16
用C語言實現CRC校驗計算08-06
氣柜直接置換08-06
氣柜直接置換-08-06