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

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

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

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

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

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

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

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

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

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

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

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