crc算法原理及c语言实现new

《crc算法原理及c语言实现new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、CRC算法原理及C语言实现摘要本文从理论上推导出CRC算法实现原理，给出三种分别适应不同计算机或微控制器硬件环境的C语言程序。读者更能根据本算法原理，用不同的语言编写出独特风格更加实用的CRC计算程序。关键词CRC算法C语言1引言循环冗余码CRC检验技术广泛应用于测控及通信领域。CRC计算可以靠专用的硬件来实现，但是对于低成本的微控制器系统，在没有硬件支持下实现CRC检验，关键的问题就是如何通过软件来完成CRC计算，也就是CRC算法的问题。这里将提供三种算法，它们稍有不同，一种适用于程序空间十分苛刻但CRC计算速度要求不高的微控制器系统，另一种适用于程序空间较大且CRC计算速度要求较

2、高的计算机或微控制器系统，最后一种是适用于程序空间不太大，且CRC计算速度又不可以太慢的微控制器系统。2CRC简介CRC校验的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。1616位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以2）后，再除以一个多项式，最后所得到的余数既是CRC码，如式（2-1）式所示，其中B(X)表示n位的二进制序列数，G(

3、X)为多项式，Q(X)为整数，R(X)是余数（既CRC码）。16B(X)×2R(X)=Q(X)+（2-1）G(X)G(X)求CRC码所采用模2加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。生成CRC码的多项式如下，其中CRC-16和CRC-CCITT产生16位的CRC码，而CRC-32则产生的是32位的CRC码。本文不讨论32位的CRC算法，有兴趣的朋友可以根据本文的思路自己去推导计算方法。16152CRC-16：（美国二进制同步系统中采用）G(X)=X+X+X+116

4、125CRC-CCITT：（由欧洲CCITT推荐）G(X)=X+X+X+132262322161211108CRC-32：G(X)=X+X+X+X+X+X+X+X+X75421+X+X+X+X+X+1接收方将接收到的二进制序列数（包括信息码和CRC码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误，关于其原理这里不再多述。用软件计算CRC码时，接收方可以将接收到的信息码求CRC码，比较结果和接收到的CRC码是否相同。3按位计算CRC对于一个二进制序列数可以表示为式(3-1):nn-1B(X)=B×2+B×2+×××+B×2+B(3-1)nn-11016求此二进制序

5、列数的CRC码时，先乘以2后（既左移16位），再除以多项式G(X)，所得的余数既是所要求的CRC码。如式(3-2)所示：1616161616B(X)×2Bn×2nBn-1×2n-1B1×2B0×2=×2+×2+×××+×2+(3-2)G(X)G(X)G(X)G(X)G(X)16B×2R(X)nn可以设：=Q(X)+(3-3)nG(X)G(X)其中Q(X)为整数，R(X)为16位二进制余数。将式(3-3)代入式(3-2)得：nn16161616B(X)×2Rn(X)nBn-1×2n-1B1×2B0×2={Q(X)+}×2+×2+×××+×2+nG(X)G(X)G(X)G(X)G(X)1

6、61616nRn(X)×2Bn-1×2n-1B1×2B0×2=Q(X)×2+{+}×2+×××+×2+(3-4)nG(X)G(X)G(X)G(X)16R(X)×2B×2R(X)nn-1n-1再设：+=Q(X)+(3-5)n-1G(X)G(X)G(X)其中Q(X)为整数，R(X)为16位二进制余数，将式(3-5)代入式(3-4)，如上类推，最后得n-1n-1到：16B(X)×2nn-1n-2R0(X)=Q(X)×2+Q(X)×2+Q(X)×2+×××+Q(X)+(3-6)nn-1n-20G(X)G(X)根据CRC的定义，很显然，十六位二进制数R(X)既是我们要求的CRC码。0式(3-5

7、)是编程计算CRC的关键，它说明计算本位后的CRC码等于上一位CRC码乘以2后除以多项式，所得的余数再加上本位值除以多项式所得的余数。由此不难理解下面求CRC码的C语言程序。*ptr指向发送缓冲区的首字节，len是要发送的总字节数，0x1021与多项式有关。unsignedintcal_crc(unsignedchar*ptr,unsignedcharlen){unsignedchari;unsignedintcrc=0;while(len--!=0){f