1、15循環(huán)冗余校驗在單片機無線通信中的應用循環(huán)冗余校驗在單片機無線通信中的應用AnApplicationofCyclicRedundancyCodeCheckAlgithminWirelessCommunicationbetweenMCUs（華南理工大學）趙希權曾志新李勇ZhaoXiquanZengZhixinLiYong摘要摘要：本文介紹了循環(huán)冗余碼（CRC碼）校驗的原理和計算方法，分析兩種查表冗余校驗快速算法，提出新型分段查表法，良好

2、地解決以單片機為核心的濕度測控系統無線數據傳輸差錯控制的實時性和小存儲量的要求。關鍵詞關鍵詞：循環(huán)冗余碼校驗；快速算法；單片機中圖分類號：TN311.53文獻標識碼：BAbstract：ThepaperpresentstheprincipleofCRCchecktheanalysisoftwodifferentkindsofrapidalgithmofCRCbasedontablechecking，aswellastheresearch

3、inganewalgithmwithsectiondividing.ThealgithmmeetsnotonlytherequirementofrealtimesmallsizeofmemybutalsotheneedoferrcontrolofwirelesscommunicationinMUCbasedhuitymeasuringcontrollingsystem.Keywds:CRCrapidalgithmMUC概述概述在無線通訊

4、過程中，數據以電磁波形式進行傳輸。由于傳輸空間中的電磁噪聲干擾，通信中發(fā)出數據與接收數據時常不一致，產生差錯。為保證通信系統的可靠性，首先要采用一種差錯檢測技術檢測數據傳輸過程中的錯誤，然后加以糾正或重新讀取信息。循環(huán)碼冗余（CRC，cyclicredundancycode）校驗技術是一種十分有效的錯誤檢測技術，能檢驗一位錯、雙位錯、所有的奇數錯、所有長度小于或等于所用的生成多項式長度的錯誤。如采用16次方生成多項式的CRC校驗，對17

5、位以上的驗錯率高達99.997％。在通信系統、控制系統中得到廣泛運用。本文討論的查表以及分段查表實現CRC快速算法，具有高實時性，又能適應單片機嵌入式系統存儲量小的特點。1循環(huán)冗余碼校驗原理循環(huán)冗余碼校驗原理CRC碼是一種典型二元分組碼，通常用多項式來表示。先選定一個r1次生成多項式G(x)。若有一個k位數據碼元序列B=(bk1bk2.……b1b0)對應（k1）次多項式B(x)＝bk1xk1bk2xk2……b1x1b0。將數據B向左移動

6、了r位，變?yōu)椋╧＋r）次的新數列B’=(bk1bk2.……b1b000…00)，低r位全為0，相應多項式為xrB(x)。用生成多項式G（x）去除xrB(x)，求得最高次數為r次的余式R（x），即CRC碼多項式，設其對應序列R＝（cr1cr2…c1c0）。編碼時將r位檢驗碼與k＋r位數據碼B’進行異或運算，得待校驗信息碼Br=(bk1bk2.……b1b0cr1cr2，…c1c0)，此信息碼定可以被G（x）整除。接收時，再用G（x）除以接收

7、到的信息碼。若能整除，則表明數據傳輸無誤；否則數據出錯。例如有一串8位二進制數據（00010101）需要發(fā)送，選7次生成多項式G(x)=x6x3x1，相應碼字（1001010）。進行模2除法求余運算：101111001010）0001010100000035的余數高8位字節(jié)模2加（異或），得到一個新多項式，再對此多項式求余，得新余式R＇(x)。最后將R＇(x)與Rkl(x)x8進行模2加（異或運算）得到Mk1(x)的余式。這是一個遞推算

8、法，數據從第一個字節(jié)開始，依照此遞推算法可以計算出任意字節(jié)長數據的CRC碼。每次推算只涉及到一次對一個字節(jié)數據的求余運算，我們事先把一個字節(jié)的所有可能的余數（28＝256個）制成表，運算過程中只需查表即可，不需要進行費時的模2除法求余運算。每個余數用兩個字節(jié)表示，共占512個字節(jié)。因為查表運算的速度快，節(jié)省CRC碼求解的時間，大大提高了系統的實時性，這種算法也稱為基于查表的CRC快速算法。但是，按照上面算法，若要傳輸5個字節(jié)的數據（m4

9、m3m2m1m0），求解CRC碼時實際上是對7個字節(jié)數據（m4m3m2m1m0OO）求余（O表示個各碼元都是0的一個字節(jié)）。對于同樣的k個字節(jié)數據求CRC碼可以用另一種方法求，(4))()()()()()()()()(8xGxRxRxxQxGxRxQxGxMklkhkkkk?????數據為k＋1個字節(jié)時有，(5))()()()()(81xGxMxxMxGxMikk???將（4）式帶入（5）式中，得：)()()()()()(8168xGx

10、MxxRxGxxRxxQiklkhk???(6))()()()()()(8xGxRxGxRxQxxQk????最終所得CRC碼是R＇（x）與R＂(x)模2加的結果，＝。式(6)中的Rkh（x）x16表示一個三字節(jié)的數據，最高位字節(jié))(xR)()(8xMxxRikl?為R＂（x），是原數據M（x）的CRC碼高8位字節(jié)其余的兩位低字節(jié)都為0；其余式為R＇(x)。從數據尾部新加入的一個字節(jié)和上一次求出的CRC碼R（x）的低8位字節(jié)進行模2加法

11、運算得到R＂(x)。可知每當有一個字節(jié)的數據從后面加上來，只需要進行一次模2除法運算Rkh（x）x16G(x)。如上述，事先把（RkhOO）所有余數制成表格，同樣可以實現快速查表。若待傳輸的數據是5個字節(jié)，則只進行5次查表運算即可，與前一種查表運算相比節(jié)省了兩次查表運算的時間，計算效率提高約30％。對短字節(jié)數據傳輸而言，此查表CRC快速算法對計算效率的改善十分明顯。3分段查表分段查表CRC碼快速算法碼快速算法設有一個字節(jié)2進制數據，其對