《2022年CRC算法原理及C语言实现 .pdf》由会员分享，可在线阅读，更多相关《2022年CRC算法原理及C语言实现 .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 算法，有兴趣的朋友可以根据本文的思路自
4、己去推导计算方法。CRC-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-
5、2) 可以设： (3-3) 其中 为整数，为 16 位二进制余数。将式(3-3)代入式 (3-2)得：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - (3-4) 再设： (3-5) 其中 为整数，为 16 位二进制余数，将式(3-5)代入式 (3-4)，如上类推，最后得到： (3-6) 根据 CRC 的定义，很显然，十六位二进制数既是我们要求的CRC 码。式(3-5) 是编程计算CRC 的关键，它说明计算本位后的CRC 码等于上
6、一位CRC 码乘以 2 后除以多项式，所得的余数再加上本位值除以多项式所得的余数。由此不难理解下面求CRC码的 C 语言程序。 *ptr 指向发送缓冲区的首字节，len 是要发送的总字节数，0 x1021 与多项式有关。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 乘以
7、 2 再求 CRC */ else crc*=2; if(*ptr&i)!=0) crc=0 x1021; /* 再加上本位的CRC */ ptr+; return(crc); 按位计算CRC 虽然代码简单， 所占用的内存比较少，但其最大的缺点就是一位一位地计算会占用很多的处理器处理时间，尤其在高速通讯的场合，这个缺点更是不可容忍。因此下面再介绍一种按字节查表快速计算CRC 的方法。4 按字节计算CRC 不难理解，对于一个二进制序列数可以按字节表示为式(4-1)，其中为一个字节 (共 8 位)。 (4-1) 求此二进制序列数的CRC 码时，先乘以后（既左移16 位） ，再除以多项式G(X) ，
8、所得的余数既是所要求的CRC 码。如式 (4-2)所示：（4-2）可以设： (4-3) 其中 为整数，为 16 位二进制余数。将式(4-3)代入式 (4-2)得：（4-4）因为：（4-5）其中 是 的高八位，是 的低八位。将式（4-5）代入式（ 4-4） ，经整理后得：（4-6）再设： (4-7) 其中 为整数，为 16 位二进制余数。将式(4-7)代入式 (4-6)，如上类推，最后得： (4-8) 很显然，十六位二进制数既是我们要求的CRC 码。式(4-7) 是编写按字节计算CRC 程序的关键， 它说明计算本字节后的CRC 码等于上一字节余名师资料总结 - - -精品资料欢迎下载 - - -
9、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 式 CRC 码的低 8 位左移 8 位后，再加上上一字节CRC 右移 8 位（也既取高8 位）和本字节之和后所求得的CRC 码，如果我们把8 位二进制序列数的CRC 全部计算出来， 放如一个表里，采用查表法，可以大大提高计算速度。由此不难理解下面按字节求CRC 码的 C 语言程序。 *ptr 指向发送缓冲区的首字节，len 是要发送的总字节数，CRC 余式表是按0 x11021 多项式求出的。unsigned int cal_crc
10、(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, 0 xf1ef, 0 x 1231, 0 x0210, 0 x3273, 0 x2252, 0 x52b5
11、, 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 x76d7, 0 x66f6, 0
12、 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 x2
13、a12, 0 xdbfd, 0 xcbdc, 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
14、, 0 xefbe, 0 xdfdd, 0 xcffc, 0 xbf1b, 0 xaf3a, 0 x9f59, 0 x8f78, 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
15、 x22f3, 0 x32d2, 0 x4235, 0 x5214, 0 x6277, 0 x7256, 0 xb5ea, 0 xa5cb, 0 x95a8, 0 x8589, 0 xf56e, 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 x1
16、6b0, 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 x7806, 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
17、, 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, 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
18、 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 位和当前字节相加后再查表求CRC ，再加上以前的CRC */ ptr+; r
19、eturn(crc); 很显然，按字节求CRC 时，由于采用了查表法，大大提高了计算速度。但对于广泛运用的8 位微处理器，代码空间有限，对于要求256 个 CRC 余式表（共512 字节的内存）已经显得捉襟见肘了， 但 CRC 的计算速度又不可以太慢，因此再介绍下面一种按半字节求CRC 的算法。5 按半字节计算CRC 同样道理，对于一个二进制序列数可以按字节表示为式(5-1)，其中为半个字节 (共 4 位)。 (5-1) 求此二进制序列数的CRC 码时，先乘以后（既左移16 位） ，再除以多项式G(X) ，所得的余数既是所要求的CRC 码。如式 (4-2)所示：（5-2）可以设： (5-3)
20、其中 为整数，为 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 码，如
21、果我们把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 x2
22、042,0 x3063,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 位
23、，相当于取CRC 的低 12 位*/ crc=crc_tada(*ptr/16); /* CRC的高 4 位和本字节的前半字节相加后查表计算CRC，然后加上上一次CRC 的余数*/ da=(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 页 - - - - - - - - -