首页 | 新闻 | 新品 | 文库 | 方案 | 视频 | 下载 | 商城 | 开发板 | 数据中心 | 座谈新版 | 培训 | 工具 | 博客 | 论坛 | 百科 | GEC | 活动 | 主题月 | 电子展
返回列表 回复 发帖

CRC 算法原理及C 语言实现

CRC 算法原理及C 语言实现

1 引言
    循环冗余码CRC 检验技术广泛应用于测控及通信领域。CRC 计算可以靠专用的硬件来实现,但是对于低成本的微控制器系统,在没有硬件支持下实现CRC 检验,关键的问题就是如何通过软件来完成CRC 计算,也就是CRC 算法的问题。
    这里将提供三种算法,它们稍有不同,一种适用于程序空间十分苛刻但CRC 计算速度要求不高的微控制器系统,另一种适用于程序空间较大且CRC 计算速度要求较高的计算机或微控制器系统,最后一种是适用于程序空间不太大,且CRC 计算速度又不可以太慢的微控制器系统。
2 CRC 简介
    CRC 校验的基本思想是利用线性编码理论,在发送端根据要传送的k 位二进制码序列,以一定的规则产生一个校验用的监督码(既CRC 码)r 位,并附在信息后边,构成一个新的二进制码序列数共(k r)位,最后发送出去。在接收端,则根据信息码和CRC码之间所遵循的规则进行检验,以确定传送中是否出错。
    16 位的CRC 码产生的规则是先将要发送的二进制序列数左移16 位(既乘以216 )后,再除以一个多项式,最后所得到的余数既是CRC 码,如式(2-1)式所示,其中B(X)表示n 位的二进制序列数,G(X)为多项式,Q(X)为整数,R(X)是余数(既CRC 码)。

    求CRC码所采用模2 加减运算法则,既是不带进位和借位的按位加减,这种加减运算实际上就是逻辑上的异或运算,加法和减法等价,乘法和除法运算与普通代数式的乘除法运算是一样,符合同样的规律。生成CRC码的多项式如下,其中CRC-16 和CRC-CCITT产生16 位的CRC码,而CRC-32 则产生的是32 位的CRC码。本文不讨论32 位的CRC算法,有兴趣的朋友可以根据本文的思路自己去推导计算方法。

CRC-16:(美国二进制同步系统中采用) G(X ) = X16   X15   X 2  1
CRC-CCITT:(由欧洲CCITT 推荐) G(X ) = X16   X12   X 5  1
CRC-32: G(X ) = X 32   X 26   X 23   X 22   X16   X12   X11   X10   X 8  X 7   X 5   X 4   X 2   X1  1

    接收方将接收到的二进制序列数(包括信息码和CRC 码)除以多项式,如果余数为0,则说明传输中无错误发生,否则说明传输有误,关于其原理这里不再多述。用软件计算CRC 码时,接收方可以将接收到的信息码求CRC 码,比较结果和接收到的CRC 码是否相同。
3 按位计算CRC
    对于一个二进制序列数可以表示为式(3-1):

    求此二进制序列数的CRC 码时,先乘以216 后(既左移16 位),再除以多项式G(X),所得的余数既是所要求的CRC 码。如式(3-2)所示:

其中Qn  (X ) 为整数, Rn (X )  为16 位二进制余数。将式(3-3)代入式(3-2)得:

其中  Qn-1( X )  为整数,Rn-1( X ) 为16 位二进制余数,将式(3-5)代入式(3-4),如上类推,最后得到:

    根据CRC 的定义,很显然,十六位二进制数 R0( X )  既是我们要求的CRC 码。式(3-5)是编程计算CRC 的关键,它说明计算本位后的CRC 码等于上一位CRC 码乘以2 后除以多项式,所得的余数再加上本位值除以多项式所得的余数。由此不难理解下面求CRC 码的C 语言程序。*ptr 指向发送缓冲区的首字节,len 是要发送的总字节数,0x1021 与多项式有关。

unsigned int cal_crc(unsigned char *ptr, unsigned char len) {
unsigned char i;
unsigned int crc=0;
while(len--!=0) {
for(i=0x80; i!=0; i/=2) {
if((crc&0x8000)!=0) {crc*=2; crc^=0x1021;} /* 余式CRC 乘以2 再求CRC */
else crc*=2;
if((*ptr&i)!=0) crc^=0x1021; /* 再加上本位的CRC */
}
ptr  ;
}
return(crc);
}

    按位计算CRC 虽然代码简单,所占用的内存比较少,但其最大的缺点就是一位一位地计算会占用很多的处理器处理时间,尤其在高速通讯的场合,这个缺点更是不可容忍。因此下面再介绍一种按字节查表快速计算CRC 的方法。
4 按字节计算CRC
    不难理解,对于一个二进制序列数可以按字节表示为式(4-1),其中B n (X ) 为一个字节(共8 位)。

    求此二进制序列数的CRC 码时,先乘以216 后(既左移16 位),再除以多项式G(X),所得的余数既是所要求的CRC 码。如式(4-2)所示:

其中Qn(X )为整数, Rn(X )为16 位二进制余数。将式(4-3)代入式(4-2)得:

其中  RnH8(X)是Rn(X )的高八位,RnL8(X) 是Rn(X )  的低八位。将式(4-5)代入式(4-4),经整理后得:

其中Qn-1(X)为整数,Rn-1(X)为16 位二进制余数。将式(4-7)代入式(4-6),如上类推,最后得:

很显然,十六位二进制数R0(X)既是我们要求的CRC 码。
继承事业,薪火相传
返回列表