《2022年CRC算法原理及C语言实现 2.pdf》由会员分享，可在线阅读，更多相关《2022年CRC算法原理及C语言实现 2.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、CRC 算法原理及 C 语言实现（介绍了3 种方法）摘 要 本文从理论上推导出CRC 算法实现原理，给出三种分别适应不同计算机或微控制器硬件环境的C 语言程序。读者更能根据本算法原理，用不同的语言编写出独特风格更加实用的 CRC 计算程序。关键词 CRC 算法 C 语言1 引言循环冗余码CRC 检验技术广泛应用于测控及通信领域。CRC 计算可以靠专用的硬件来实现，但是对于低成本的微控制器系统，在没有硬件支持下实现CRC 检验，关键的问题就是如何通过软件来完成CRC 计算，也就是CRC 算法的问题。这里将提供三种算法，它们稍有不同，一种适用于程序空间十分苛刻但CRC 计算速度要求不高的微控制器系
2、统，另一种适用于程序空间较大且CRC 计算速度要求较高的计算机或微控制器系统，最后一种是适用于程序空间不太大，且CRC 计算速度又不可以太慢的微控制器系统。2 CRC 简介CRC 校验的基本思想是利用线性编码理论，在发送端根据要传送的k 位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC 码）r 位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位，最后发送出去。在接收端，则根据信息码和CRC 码之间所遵循的规则进行检验，以确定传送中是否出错。16 位的 CRC 码产生的规则是先将要发送的二进制序列数左移16 位（既乘以）后，再除以一个多项式，最后所得到的余数既是CRC 码，
3、如式（2-1）式所示，其中B(X)表示 n 位的二进制序列数，G(X)为多项式，Q(X)为整数，R(X)是余数（既CRC 码）。（2-1）R(X)=B(X)*16%G(X)求 CRC 码所采用模2 加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。生成CRC 码的多项式如下，其中CRC-16 和 CRC-CCITT 产生 16位的 CRC 码，而 CRC-32 则产生的是32 位的 CRC 码。本文不讨论32 位的 CRC 算法，有兴趣的朋友可以根据本文的思路自己去推导计算方法。CR
4、C-16：（美国二进制同步系统中采用）CRC-CCITT：（由欧洲CCITT 推荐）CRC-32：接收方将接收到的二进制序列数（包括信息码和CRC 码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误，关于其原理这里不再多述。用软件计算CRC码时，接收方可以将接收到的信息码求CRC 码，比较结果和接收到的CRC 码是否相同。3 按位计算CRC 对于一个二进制序列数可以表示为式(3-1):(3-1)求此二进制序列数的CRC 码时，先乘以后（既左移16 位），再除以多项式G(X)，所得的余数既是所要求的CRC 码。如式(3-2)所示：(3-2)可以设：(3-3)其中为整数，为 1
5、6 位二进制余数。将式(3-3)代入式(3-2)得：名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -(3-4)再设：(3-5)其中为整数，为 16 位二进制余数，将式(3-5)代入式(3-4)，如上类推，最后得到：(3-6)根据 CRC 的定义，很显然，十六位二进制数既是我们要求的CRC 码。式(3-5)是编程计算CRC 的关键，它说明计算本位后的CRC 码等于上一位CRC 码乘以 2 后除以多项式，所得的余数再加上本位值除以多项式所得的余数。由此不难理解下面求CRC码的 C 语言程序。*ptr 指向发送缓冲区的首字节，len 是要发送的总字节数，0 x1021 与多项
6、式有关。unsigned int cal_crc(unsigned char*ptr,unsigned char len)unsigned char i;unsigned int crc=0;while(len-!=0)for(i=0 x80;i!=0;i/=2)if(crc&0 x8000)!=0)crc*=2;crc=0 x1021;/*余式 CRC 乘以 2 再求 CRC */else crc*=2;if(*ptr&i)!=0)crc=0 x1021;/*再加上本位的CRC*/ptr+;return(crc);按位计算CRC 虽然代码简单，所占用的内存比较少，但其最大的缺点就是一位一位地
7、计算会占用很多的处理器处理时间，尤其在高速通讯的场合，这个缺点更是不可容忍。因此下面再介绍一种按字节查表快速计算CRC 的方法。4 按字节计算CRC 不难理解，对于一个二进制序列数可以按字节表示为式(4-1)，其中为一个字节(共 8 位)。(4-1)求此二进制序列数的CRC 码时，先乘以后（既左移16 位），再除以多项式G(X)，所得的余数既是所要求的CRC 码。如式(4-2)所示：（4-2）可以设：(4-3)其中为整数，为 16 位二进制余数。将式(4-3)代入式(4-2)得：（4-4）因为：（4-5）其中是 的高八位，是 的低八位。将式（4-5）代入式（4-4），经整理后得：（4-6）再设
8、：(4-7)其中为整数，为 16 位二进制余数。将式(4-7)代入式(4-6)，如上类推，最后得：(4-8)很显然，十六位二进制数既是我们要求的CRC 码。式(4-7)是编写按字节计算CRC 程序的关键，它说明计算本字节后的CRC 码等于上一字节余名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -式 CRC 码的低 8 位左移 8 位后，再加上上一字节CRC 右移 8 位（也既取高8 位）和本字节之和后所求得的CRC 码，如果我们把8 位二进制序列数的CRC 全部计算出来，放如一个表里，采用查表法，可以大大提高计算速度。由此不难理解下面按字节求CRC 码的 C 语言程序。
9、*ptr 指向发送缓冲区的首字节，len 是要发送的总字节数，CRC 余式表是按0 x11021 多项式求出的。unsigned int cal_crc(unsigned char*ptr,unsigned char len)unsigned int crc;unsigned char da;unsigned int crc_ta256=/*CRC余式表*/0 x0000,0 x1021,0 x2042,0 x3063,0 x4084,0 x50a5,0 x60c6,0 x70e7,0 x8108,0 x9129,0 xa14a,0 xb16b,0 xc18c,0 xd1ad,0 xe1ce,
10、0 xf1ef,0 x 1231,0 x0210,0 x3273,0 x2252,0 x52b5,0 x4294,0 x72f7,0 x62d6,0 x9339,0 x8318,0 xb37b,0 xa35a,0 xd3bd,0 xc39c,0 xf3ff,0 xe3de,0 x2462,0 x3443,0 x0420,0 x1401,0 x64e6,0 x74c7,0 x44a4,0 x5485,0 xa56a,0 xb54b,0 x8528,0 x9509,0 xe5ee,0 xf5cf,0 xc5ac,0 xd58d,0 x3653,0 x2672,0 x1611,0 x0630,0 x
11、76d7,0 x66f6,0 x5695,0 x46b4,0 xb75b,0 xa77a,0 x9719,0 x8738,0 xf7df,0 xe7fe,0 xd79d,0 xc7bc,0 x48c4,0 x58e5,0 x6886,0 x78a7,0 x0840,0 x1861,0 x2802,0 x3823,0 xc9cc,0 xd9ed,0 xe98e,0 xf9af,0 x8948,0 x9969,0 xa90a,0 xb92b,0 x5af5,0 x4ad4,0 x7ab7,0 x6a96,0 x1a71,0 x0a50,0 x3a33,0 x2a12,0 xdbfd,0 xcbdc
12、,0 xfbbf,0 xeb9e,0 x9b79,0 x8b58,0 xbb3b,0 xab1a,0 x6ca6,0 x7c87,0 x4ce4,0 x5cc5,0 x2c22,0 x3c03,0 x0c60,0 x1c41,0 xedae,0 xfd8f,0 xcdec,0 xddcd,0 xad2a,0 xbd0b,0 x8d68,0 x9d49,0 x7e97,0 x6eb6,0 x5ed5,0 x4ef4,0 x3e13,0 x2e32,0 x1e51,0 x0e70,0 xff9f,0 xefbe,0 xdfdd,0 xcffc,0 xbf1b,0 xaf3a,0 x9f59,0 x
13、8f78,0 x9188,0 x81a9,0 xb1ca,0 xa1eb,0 xd10c,0 xc12d,0 xf14e,0 xe16f,0 x1080,0 x00a1,0 x30c2,0 x20e3,0 x5004,0 x4025,0 x7046,0 x6067,0 x83b9,0 x9398,0 xa3fb,0 xb3da,0 xc33d,0 xd31c,0 xe37f,0 xf35e,0 x02b1,0 x1290,0 x22f3,0 x32d2,0 x4235,0 x5214,0 x6277,0 x7256,0 xb5ea,0 xa5cb,0 x95a8,0 x8589,0 xf56e
14、,0 xe54f,0 xd52c,0 xc50d,0 x34e2,0 x24c3,0 x14a0,0 x0481,0 x7466,0 x6447,0 x5424,0 x4405,0 xa7db,0 xb7fa,0 x8799,0 x97b8,0 xe75f,0 xf77e,0 xc71d,0 xd73c,0 x26d3,0 x36f2,0 x0691,0 x16b0,0 x6657,0 x7676,0 x4615,0 x5634,0 xd94c,0 xc96d,0 xf90e,0 xe92f,0 x99c8,0 x89e9,0 xb98a,0 xa9ab,0 x5844,0 x4865,0 x
15、7806,0 x6827,0 x18c0,0 x08e1,0 x3882,0 x28a3,0 xcb7d,0 xdb5c,0 xeb3f,0 xfb1e,0 x8bf9,0 x9bd8,0 xabbb,0 xbb9a,0 x4a75,0 x5a54,0 x6a37,0 x7a16,0 x0af1,0 x1ad0,0 x2ab3,0 x3a92,0 xfd2e,0 xed0f,0 xdd6c,0 xcd4d,0 xbdaa,0 xad8b,0 x9de8,0 x8dc9,0 x7c26,0 x6c07,0 x5c64,0 x4c45,0 x3ca2,0 x2c83,0 x1ce0,0 x0cc1
16、,0 xef1f,0 xff3e,0 xcf5d,0 xdf7c,0 xaf9b,0 xbfba,0 x8fd9,0 x9ff8,0 x6e17,0 x7e36,0 x4e55,0 x5e74,0 x2e93,0 x3eb2,0 x0ed1,0 x1ef0 ;crc=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 5 页 -while(len-!=0)da=(uchar)(crc/256);/*以 8 位二进制数的形式暂存CRC 的高 8 位*/crc=8;/*左移 8 位，相当于CRC 的低 8 位乘以 */crc=crc_tada*ptr;/*高 8 位和当前字节相加后再
17、查表求CRC，再加上以前的CRC*/ptr+;return(crc);很显然，按字节求CRC 时，由于采用了查表法，大大提高了计算速度。但对于广泛运用的8 位微处理器，代码空间有限，对于要求256 个 CRC 余式表（共512 字节的内存）已经显得捉襟见肘了，但 CRC 的计算速度又不可以太慢，因此再介绍下面一种按半字节求CRC 的算法。5 按半字节计算CRC 同样道理，对于一个二进制序列数可以按字节表示为式(5-1)，其中为半个字节(共 4 位)。(5-1)求此二进制序列数的CRC 码时，先乘以后（既左移16 位），再除以多项式G(X)，所得的余数既是所要求的CRC 码。如式(4-2)所示：
18、（5-2）可以设：(5-3)其中为整数，为 16 位二进制余数。将式(5-3)代入式(5-2)得：（5-4）因为：（5-5）其中是 的高 4 位，是 的低 12 位。将式（5-5）代入式（5-4），经整理后得：（5-6）再设：(5-7)其中为整数，为 16 位二进制余数。将式(5-7)代入式(5-6)，如上类推，最后得：(5-8)很显然，十六位二进制数既是我们要求的CRC 码。式(5-7)是编写按字节计算CRC 程序的关键，它说明计算本字节后的CRC 码等于上一字节CRC 码的低 12 位左移 4 位后，再加上上一字节余式CRC 右移 4 位（也既取高4 位）和本字节之和后所求得的CRC 码，
19、如果我们把4 位二进制序列数的CRC 全部计算出来，放在一个表里，采用查表法，每个字节算两次（半字节算一次），可以在速度和内存空间取得均衡。由此不难理解下面按半字节求CRC 码的 C 语言程序。*ptr 指向发送缓冲区的首字节，len是要发送的总字节数，CRC 余式表是按0 x11021 多项式求出的。unsigned cal_crc(unsigned char*ptr,unsigned char len)unsigned int crc;unsigned char da;unsigned int crc_ta16=/*CRC余式表*/0 x0000,0 x1021,0 x2042,0 x30
20、63,0 x4084,0 x50a5,0 x60c6,0 x70e7,0 x8108,0 x9129,0 xa14a,0 xb16b,0 xc18c,0 xd1ad,0 xe1ce,0 xf1ef,crc=0;名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 5 页 -while(len-!=0)da=(uchar)(crc/256)/16;/*暂存 CRC 的高四位*/crc=4;/*CRC右移 4 位，相当于取CRC 的低 12 位*/crc=crc_tada(*ptr/16);/*CRC的高 4 位和本字节的前半字节相加后查表计算CRC，然后加上上一次CRC 的余数*/da=
21、(uchar)(crc/256)/16;/*暂存 CRC 的高 4 位*/crc=4;/*CRC右移 4 位，相当于 CRC 的低 12 位 */crc=crc_tada(*ptr&0 x0f);/*CRC的高 4 位和本字节的后半字节相加后查表计算CRC，然后再加上上一次CRC 的余数*/ptr+;return(crc);5 结束语以上介绍的三种求CRC 的程序，按位求法速度较慢，但占用最小的内存空间；按字节查表求 CRC 的方法速度较快，但占用较大的内存；按半字节查表求CRC 的方法是前两者的均衡，即不会占用太多的内存，同时速度又不至于太慢，比较适合 8 位小内存的单片机的应用场合。以上所给的C 程序可以根据各微处理器编译器的特点作相应的改变，比如把 CRC 余式表放到程序存储区内等。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 5 页 -