循環(huán)冗余校驗在單片機無線通信中的應(yīng)用

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

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

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

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

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

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

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

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

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

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

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