循环冗余校验在单片机无线通信中的应用

1/5循环冗余校验在单片机无线通信中的应用AnApplicationofCyclicRedundancyCodeCheckAlgorithminWirelessCommunicationbetweenMCUs（华南理工大学）赵希权曾志新李勇Zhao,XiquanZeng,ZhixinLi,Yong摘要：本文介绍了循环冗余码（CRC码）校验的原理和计算方法，分析两种查表冗余校验快速算法，提出新型分段查表法，良好地解决以单片机为核心的湿度测控系统无线数据传输差错控制的实时性和小存储量的要求。关键词：循环冗余码校验；快速算法；单片机中图分类号：TN311.53文献标识码：BAbstract：ThepaperpresentstheprincipleofCRCcheckandtheanalysisoftwodifferentkindsofrapidalgorithmofCRCbasedontable-checking，aswellastheresearchinganewalgorithmwithsection-dividing.Thealgorithmmeetsnotonlytherequirementofrealtimeandsmallsizeofmemory,butalsotheneedoferrorcontrolofwirelesscommunicationinMUCbasedhumiditymeasuringandcontrollingsystem.Keywords:CRC;rapidalgorithm;MUC概述在无线通讯过程中，数据以电磁波形式进行传输。由于传输空间中的电磁噪声干扰，通信中发出数据与接收数据时常不一致，产生差错。为保证通信系统的可靠性，首先要采用一种差错检测技术检测数据传输过程中的错误，然后加以纠正或重新读取信息。循环码冗余（CRC，cyclicredundancycode）校验技术是一种十分有效的错误检测技术，能检验一位错、双位错、所有的奇数错、所有长度小于或等于所用的生成多项式长度的错误。如采用16次方生成多项式的CRC校验，对17位以上的验错率高达99.997％。在通信系统、控制系统中得到广泛运用。本文讨论的查表以及分段查表实现CRC快速算法，具有高实时性，又能适应单片机嵌入式系统存储量小的特点。1循环冗余码校验原理CRC码是一种典型二元分组码，通常用多项式来表示。先选定一个r+1次生成多项式G(x)。若有一个k位数据码元序列B=(bk-1,bk-2.,……,b1,b0),对应（k-1）次多项式B(x)＝bk-1xk-1+bk-2xk-2+……+b1x1+b0。将数据B向左移动了r位，变为（k＋r）次的新数列B’=(bk-1,bk-2.,……,b1,b0,0,0,…,0,0)，低r位全为0，相应多项式为xrB(x)。用生成多项式G（x）去除xrB(x)，求得最高次数为r次的余式R（x），即CRC码多项式，设其对应序列R＝（cr-1,cr-2,…,c1,c0）。编码时将r位检验码与k＋r位数据码B’进行异或运算，得待校验信息码Br=(bk-1,bk-2.,……,b1,b0,cr-1,cr-2，…,c1,c0)，此信息码定可以被G（x）整除。接收时，再用G（x）除以接收到的信息码。若能整除，则表明数据传输无误；否则数据出错。例如有一串8位二进制数据（00010101）需要发送，选7次生成多项式G(x)=x6+x3+x+1，相应码字（1001010）。进行模2除法求余运算：101111001010）000101010000002/5100101000111100010010100110010010010101011101001010010110…6位余数得6位码余数（010110）。那么发送信息码为（00010101000000）⊕（010110）＝（00010101010110）共14位(⊕表示与或运算)，前8位是数据码，后6位是校验码。若接收到的信息码可以被生成多项式（1001010）整除，则说明数据传输无差错，接受到的就是发送的数据（00010101010110）；如果信息码中有任意码元出错，则余数不为零，差错被检验出来。本文所涉及的是单片机嵌入式系统无线通信，传输数据以8bit为单元，可以采用国际标准中CRC-16或CRC-CCITT编码方式。这里以CRC－CCITT码：G（x）=x16＋x12＋x5＋1为例。2CRC码的两种查表生成算法设有k个字节的2进制数据序列mk-1、mk－2、mk-3、...、m1、m0，m表示一个字节，用多项式Mk（x）代表，根据CRC的校验原理有：)()()()()()()()()(816xGxRxRxxQxGxRxQxGxxMklkhkkk（1）式中：Q（x）是Mk(x)/G(x)商；Rk(x)为余数，Rkh（x）和Rnl(x)分别是CRC码的高字节和低字节。那么从最低位新增一个字节Mi(x)，数据增加到k+1个字节,表示为多项式Mk＋1（x）＝Mk（x）8x+Mi(x)。对此式求余：)()()()()(16168161xGxxMxxxMxGxxMikk(2)将（1）式带入（2）式中得：)()()())()(()(8168xGxxRxGxxMxRxxQklikhk)()()()(')(')(88xGxxRxGxRxQxXQklk（3）式（3）中Q＇(x)是16))()((xxMxRikh/G（x）的商，R＇(x)表示所得的双字节余式。8)()('xxRxRkl表示最终得到的余数，即Mk+1（x）的CRC-CCITT校验码。从演算过程中可知Mk+1(x)的CRC校验码的求解算法，每当有一个字节数据从原数据后面加上来，进行一次求余计算。首先是新增加字节Mi（x）与原来数据多项式Mk（x）的余数高8位字节模2加（异或），得到一个新多项式，再对此多项式求余，得新余式R＇(x)。3/5最后将R＇(x)与Rkl(x)x8进行模2加（异或运算）得到Mk+1(x)的余式。这是一个递推算法，数据从第一个字节开始，依照此递推算法可以计算出任意字节长数据的CRC码。每次推算只涉及到一次对一个字节数据的求余运算，我们事先把一个字节的所有可能的余数（28＝256个）制成表，运算过程中只需查表即可，不需要进行费时的模2除法求余运算。每个余数用两个字节表示，共占512个字节。因为查表运算的速度快，节省CRC码求解的时间，大大提高了系统的实时性，这种算法也称为基于查表的CRC快速算法。但是，按照上面算法，若要传输5个字节的数据（m4m3m2m1m0），求解CRC码时实际上是对7个字节数据（m4m3m2m1m0OO）求余（O表示个各码元都是0的一个字节）。对于同样的k个字节数据求CRC码可以用另一种方法求，)()()()()()()()()(8xGxRxRxxQxGxRxQxGxMklkhkkkk(4)数据为k＋1个字节时有，)()()()()(81xGxMxxMxGxMikk(5)将（4）式带入（5）式中，得：)()()()()()(8168xGxMxxRxGxxRxxQiklkhk)()('')()(')(')(8xGxRxGxRxQxxQk(6)最终所得CRC码是R＇（x）与R＂(x)模2加的结果，)(''xR＝)()(8xMxxRikl。式(6)中的Rkh（x）x16表示一个三字节的数据，最高位字节为R＂（x），是原数据M（x）的CRC码高8位字节,其余的两位低字节都为0；其余式为R＇(x)。从数据尾部新加入的一个字节和上一次求出的CRC码R（x）的低8位字节进行模2加法运算得到R＂(x)。可知每当有一个字节的数据从后面加上来，只需要进行一次模2除法运算Rkh（x）x16/G(x)。如上述，事先把（RkhOO）所有余数制成表格，同样可以实现快速查表。若待传输的数据是5个字节，则只进行5次查表运算即可，与前一种查表运算相比节省了两次查表运算的时间，计算效率提高约30％。对短字节数据传输而言，此查表CRC快速算法对计算效率的改善十分明显。3分段查表CRC码快速算法设有一个字节2进制数据，其对应多项式为M（x）＝Mh(x)＋Ml(x),Mh(x)和Ml(x)分别是低4位、高4位都是零的8位2进制数所对应的多项式，数据码构成形式分别为（h3,h2,h1,h0,0000）和（0000h3,h2,h1,h0），则求解其CRC校验码的算法为：161616)()()()()()(xxGxMxxGxMxGxxMlh（7）由式（6）可知，对一个字节的求余运算可以转换成对两个多项式Mh（x）和Ml（x）求余运算，然后将两个余数异或，即可得到整个字节的CRC码。因为Mh（x）和Ml（x）中仅4/5含4位信息位，所以只有16（24）种CRC码,将这两种CRC码分别制成表，则只需要32x2＝64个字节的存储单元。比查表法多了一次查表运算和一次与或运算，所以此算法耗时相对较多，但占用存储空间缩小了7/8，对于单片机这样存储空间十分有限的嵌入式系统很有利。Mh（x）CRC码表如表1示：表1以CRC－CCITT生成的Mh（x）余数表M00102030405060708090a0b0c0d0e0f0000012312462365348c45af56ca67e97918883b9b5eaa7dbd94ccb7dfd2eef1dMl（x）CRC码表如表2示：表1以CRC－CCITT生成的Ml（x）余数表M000102030405060708090a0b0c0d0e0f00001021204230634084505a560c670e781089129a14ab16bc18cd1ade1cee1ef4结束语本文研究的系统是由一个主控系统与几个下位机构成，无线通讯协议比较简单，数据包基本格式如图1示。其中，SOH包头通常包含源地址和目的地址等控制信息；数据是传输的有用信息，且数据长度固定不变；校验码是通过CRC算法计算出来CRC码，整个数据包比较短。采取节省时间的第二种查表算法与分段查表算法相结合，以使通信达到最佳实时性和最小空间占用率的最佳编程效果。SOH数据校验码图1.数据包格式C51作为一种结构化的程序设计语言具有易测试、易开发、可读性好等特点，克服了汇编语言固有的一些缺点。在笔者参与开发设计的无线湿度测控系统中，采用C51实现的分段查表CRC快算法在通信中作用突出，大大提高了通信可靠性，并且占用存储空间小，实时性高。参考文献：[1]张海林,葛思擎,施仁.一种新型冗余码校验算法的研究[J].西安：西安交通大学学报.2003,37(10)：1056-1058[2]梁合庆,吕京建,博洋.从C到嵌入式C编程语言[M].北京：北京航空航天大学出版社,2002.4.[3]沈保锁，候春萍，现代通信技术[M].北京：国防工业出版社，2002.8.作者简介：赵希权,男,1975年11月,硕士研究生,研究方向：现代加工与质量控制。联系电话：[phone]或13168335570Email：[e-mail]on:Zhao,Xiquan,male,borninNov.1975,postgraduatemajoringinmodernmanufacturingandqualitycontrolTel：020-38673353Mobil：13168335570Email：[e-mail]（510640广州华南理工大学机械工程学院）赵希权曾志新李勇（CollegeofMechanicalEngineeringSouthChinaUniversityofTechnologyGuangzhou510640）Zhao,XiquanZen,ZhixinLi,Yong5/5基金项目：广东省技术创新项目（E8305013）；广东省工业攻关项目（B10803）。