基于WSN的CRC算法的改进与实现.pdf

《基于WSN的CRC算法的改进与实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、[摘[关键又称为(n，k)码。其编码格式如下：{if((crcI&0xS000)!=O)nn一1r+1rr-1{crcl=2；crc1=Ox1021；}／／余式CRC乘以2再求CRCll：：：IIl数据位校验位else1．1编码规则_l1{crc1=2；}设有k个数据位，需要添加r个校验位，n=k+r，其编码规if((ptr&i)!=0)crc1-~x1021；∥再加上本位CRC则如下：}用w(x)=wW⋯W表示k个数据位，把w(x)左移r位，p仃++；}即相当于W(x)x2，给校验位空出r位来；retum(crc1)；}

2、给定一个r阶的多项式E(x)，可以求出一个校验位表达式从上述代码可知，直接基于问题的描述和所涉及的概念F(x)。E(x)称为该循环码的生成多项式。即如下表达式：出发，利用按位计算CRC，虽然代码简单(也可采用模拟硬件电路按位操作加以实现)，所占用的内存比较少，但其最大的-Q(X)+器缺点就是一位一位地计算会占用很多的处理器处理时间，尤根据上面公式可知，用W(x)去除生成多项式G(x)，商为其在高速通讯的场合，这个缺点更是不可容忍，因而实现对它H(x)，余数则为R(x)。据此可得：的改进具有理论和实际的意义。W(x)=H(x

3、)G(x)+R(x)在CRC编码过程中，四则运算采用模2运算，即不考虑2．CRC算法改进借位和进位。所以有：2．1快速算法基本思想[3]w(x)+R(x)=H(x)G(x)CRC常用的生成多项式如CRC．16、CRC．CCITT和M(X)+R(x)即为所求11位CRC码，它应是生成多项式CRC．32，由它们产生的校验码字节数均为整数个字节。而单片G(x)的倍式，即可以被G(x)整除。机的操作是以字节形式进行的，所以，算法应以字节为单位进校验数据时用数据的n位CRC编码去除G(x)，若余数为行运算。显然，单片机的数据序列、校

4、验序列都是字节序列。实0则说明数据正确，否则根据余数的值即可查出差错位。际上，这种算法所要解决的问题就是如何对多字节序列进行1．2生成多项式特点除法取余式运算的问题，从而达到时空的权衡。生成多项式应满足以下条件：2．2多字节序列运算规律(1)任何一位发生错误，w(x)×2+R(x)即CRC码除以设一个由i个字节构成的字节序列Wi=【W。W：⋯⋯W。W．】，G(x)的余数不能为0；取其前i-1个字节构成一个新的序列w。产[W。W⋯⋯w。．2W。】，(2)余数继续作模2除，应使余数循环；则两个序列之间的关系可以用多项式表示为W

5、(x)_x．．(x)(3)若要能纠正一位错，则不同的码位错不能有相同的余+m(x)。数，且当给定生成多项式后，余数与出错位之间的对应关系应其中，mi(x)表示m。的二进制多项式形式，xSWi．，(x)表示将保持不变，与编码无关。w。左移一个字节。1．3原算法实现闭对于序列w．，来说，／木以CRC．CCITT为例，按位计算CRC算法实现，不使用作者简介：李冠楠，男，黑龙江牡丹江人，硕士，讲师。主要研究方向：计算机网络技术，计算机语言学。一65—经验交流bc】刊Fx)+其中令二字节序列余数Rl=[hl]而对于序列W．来说，可得

6、E(x)=E(=xSf~x)1_x)E(x)因此，对x．．(x)+w．(x)取余式运算就等价于对W(x)的取余式运算，即[aOOl奎垒壅查一∞【∞。oo】●_Re[e[]-_·__-_-·--．·一-．--．__．_--··-·_一．●其中，xsR．．(x)+w(x)表示一个由R．．和m，共同组成的_二图1三字节序列【abc】计算流程字节序列[h．．1．．w．】，故对它取余式运算就等于对M序列的取余按字节计算CRC算法实现，利Hj0x00至0xFF余表式运算，其结果就是M序列的余式RF[h，l，]。故以此类推便可唪／得到最

7、终结果。uintCal2．3变字节序列的计算—crc()为了时空的权衡我们在此引入了查表的思想，对j『三字{crclptr；节序列如果事先计算出一字节即0x00至0xFF之间的所有的crc1<<=8：余式并汇制成表，这样就减少了时间开销且只需占用512个pt+；字节牢间。crc1=crcI+ptr；设三字节序列T[abc]、Ta00=[aO0]和二字节序列Tbc=pt什+；一。[b。c。]．。．用．．多．项．．式。表。。示_。为'．．Tla．出．(．x)一～=T(x)+T(x)。while(1en一!=O、．．．。对f序列

8、。。T．．．来说，fda=(uchar)(crc1>>8)；提取余式岛字节存入da／crc1<<=8；crcl=Crctable[da]；—而对于序列T来说，町得crclptr；三x)+ptr++；}remm(crc1)；}其中，R和T都是2_2字节序列，此Raoo(x)+T(x)仍然按半字节计算CRC