1  引言
       循环冗余码CRC 检验技术广泛应用于测控及通信领域。CRC 计算可以靠专用的硬件来实现，但是对于低成本的微控制器系统，在没有硬件支持下实现CRC 检验，关键的问题就是如何通过软件来完成CRC 计算，也就是CRC 算法的问题。
    这里将提供三种算法，它们稍有不同，一种适用于程序空间十分苛刻但CRC 计算速度要求不高的微控制器系统，另一种适用于程序空间较大且CRC 计算速度要求较高的计算机或微控制器系统，最后一种是适用于程序空间不太大，且CRC 计算速度又不可以太慢的微控制器系统。

2  CRC 简介
       CRC 校验的基本思想是利用线性编码理论，在发送端根据要传送的k 位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC 码）r 位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。
       16 位的CRC 码产生的规则是先将要发送的二进制序列数左移16 位（既乘以16 2 ）后，再除以一个多项式，最后所得到的余数既是CRC 码，如式（2-1）式所示，其中B(X)表示n 位的二进制序列数，G(X)为多项式，Q(X)为整数，R(X)是余数（既CRC 码）。
       $(B(X) * 2^16)/(G(X)) = Q(X) + (R(X))/(G(X))$
       求CRC码采用：模2 加减运算法则。既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价。乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。生成CRC码的多项式如下，其中CRC-16 和CRC-CCITT产生16 位的CRC码，而CRC-32 则产生的是32 位的CRC码。本文不讨论32 位的CRC算法，有兴趣的朋友可以根据本文的思路自己去推导计算方法。
       CRC-16：（美国二进制同步系统中采用）$G(X) = X^16 + X^15 + X^2 + 1$
       CRC-CCITT：（由欧洲CCITT 推荐）      $G(X) = X^16 + X^12 + X^5 + 1$
       CRC-32：$G(X) = X^32 + X^26 + X^23 + X^22 + X^16 + X^12 + X^11 + X^10 + X^8 +X^7 + X^5 + X^4 +X^2 + X^1 + 1$
       接收方将接收到的二进制序列数（包括信息码和CRC 码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误，关于其原理这里不再多述。用软件计算CRC 码时，接收方可以将接收到的信息码求CRC 码，比较结果和接收到的CRC 码是否相同。

3  按位计算CRC
       对于一个二进制序列数可以表示为式(3-1):
       $B(X) = B_n*2^n + B_(n-1)*2^(n-1)+ ... + B_1*2^1 + B_0*2^0$                            (3-1)
求此二进制序列数的CRC 码时，先乘以$2^16$后（既左移16 位），再除以多项式G(X)，所得的余数既是所要求的CRC 码。如式(3-2)所示：
       $(B(X)*2^16)/(G(X)) = (B_n*2^16)/(G(X))*2^n + (B_(n-1)*2^16)/(G(X))*2^(n-1) + ... + (B_1*2^16)/(G(X))*2^1 + (B_0*2^16)/(G(X))*2^0$                                                     (3-2)
可以设, $(B_n*2^16)/(G(X)) = Q_n(X) + (R_n(X)/G(X))$                              (3-3)
将式(3-3)代入式(3-2)得，
       $(B(X)*2^16)/(G(X)) = \{Q_n(X) + (R_n(X)/G(X))\}*2^n + (B_(n-1)*2^16)/(G(X))*2^(n-1) + ... + (B_1*2^16)/(G(X))*2^1 + (B_0*2^16)/(G(X))*2^0 = Q_n(X)*2^n + \{(R_n(X)*2)/G(X) + (B_(n-1)*2^16)/(G(X))\}*2^(n-1) + ... + (B_1*2^16)/(G(X))*2^1 + (B_0*2^16)/(G(X))*2^0$  (3-4)
再设，$(R_n(X)*2)/G(X) + (B_(n-1)*2^16)/(G(X)) = Q_(n-1)(X) + (R_(n-1)(X)/G(X))   (3-5)
将式(3-5)代入式(3-4)，如此类推，最后得到：
       $(B(X)*2^16)/(G(X)) = Q_n(X)*2^n + Q_(n-1)(X)*2^(n-1) + ... + Q(X)*2 + Q_0(X) + (R_0(X)/G(X))     (3-6)
根据CRC定义，显然，$R_0(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);
}