循环冗余校验（CRC）算法入门引导

写给嵌入式程序员的循环冗余校验（CRC）算法入门引导前言CRC校验（循环冗余校验）是数据通讯中最常采用的校验方式。在嵌入式软件开发中，经常要用到CRC 算法对各种数据进行校验。因此，掌握基本的CRC算法应是嵌入式程序员的基本技能。可是，我认识的嵌入式程序员中能真正掌握CRC算法的人却很少，平常在项目中见到的CRC的代码多数都是那种效率非常低下的实现方式。
其实，在网上有一篇介绍CRC 算法的非常好的文章，作者是Ross Williams，题目叫：“A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS”。我常将这篇文章推荐给向我询问CRC算法的朋友，但不少朋友向我抱怨原文太长了，而且是英文的。希望我能写篇短点的文章，因此就有了本文。不过，我的水平比不了Ross Williams，我的文章肯定也没Ross Williams的写的好。因此，阅读英文没有障碍的朋友还是去读Ross Williams的原文吧。
本文的读者群设定为软件开发人员，尤其是从事嵌入式软件开发的程序员，而不是专业从事数学或通讯领域研究的学者（我也没有这个水平写的这么高深）。因此，本文的目标是介绍CRC算法的基本原理和实现方式，用到的数学尽量控制在高中生可以理解的深度。
另外，鉴于大多数嵌入式程序员都是半路出家转行过来的，不少人只会C语言。因此，文中的示例代码全部采用C语言来实现。作为一篇入门短文，文中给出的代码更注重于示范性，尽可能的保持易读性。因此，文中的代码并不追求最高效的实现，但对于一般的应用却也足够快速了。
从奇偶校验说起所谓通讯过程的校验是指在通讯数据后加上一些附加信息，通过这些附加信息来判断接收到的数据是否和发送出的数据相同。比如说RS232串行通讯可以设置奇偶校验位，所谓奇偶校验就是在发送的每一个字节后都加上一位，使得每个字节中1的个数为奇数个或偶数个。比如我们要发送的字节是0x1a，二进制表示为0001 1010。
采用奇校验，则在数据后补上个0，数据变为0001 1010 0，数据中1的个数为奇数个（3个）
采用奇校验，则在数据后补上个1，数据变为0001 1010 1，数据中1的个数为偶数个（4个）
接收方通过计算数据中1个数是否满足奇偶性来确定数据是否有错。
奇偶校验的缺点也很明显，首先，它对错误的检测概率大约只有50%。也就是只有一半的错误它能够检测出来。另外，每传输一个字节都要附加一位校验位，对传输效率的影响很大。因此，在高速数据通讯中很少采用奇偶校验。奇偶校验优点也很明显，它很简单，因此可以用硬件来实现，这样可以减少软件的负担。因此，奇偶校验也被广泛的应用着。
奇偶校验就先介绍到这来，之所以从奇偶校验说起，是因为这种校验方式最简单，而且后面将会知道奇偶校验其实就是CRC 校验的一种(CRC-1)。

累加和校验
另一种常见的校验方式是累加和校验。所谓累加和校验实现方式有很多种，最常用的一种是在一次通讯数据包的最后加入一个字节的校验数据。这个字节内容为前面数据包中全部数据的忽略进位的按字节累加和。比如下面的例子：
我们要传输的信息为： 6、23、4
加上校验和后的数据包：6、23、4、33
这里 33 为前三个字节的校验和。接收方收到全部数据后对前三个数据进行同样的累加计算，如果累加和与最后一个字节相同的话就认为传输的数据没有错误。
累加和校验由于实现起来非常简单，也被广泛的采用。但是这种校验方式的检错能力也比较一般，对于单字节的校验和大概有1/256 的概率将原本是错误的通讯数据误判为正确数据。之所以这里介绍这种校验，是因为CRC校验在传输数据的形式上与累加和校验是相同的，都可以表示为：通讯数据 校验字节（也可能是多个字节）
初识 CRC 算法CRC 算法的基本思想是将传输的数据当做一个位数很长的数。将这个数除以另一个数。得到的余数作为校验数据附加到原数据后面。还以上面例子中的数据为例：
6、23、4 可以看做一个2进制数： 0000011000010111 00000010
假如被除数选9，二进制表示为：1001
则除法运算可以表示为：

可以看到，最后的余数为1。如果我们将这个余数作为校验和的话，传输的数据则是：6、23、4、1
CRC 算法和这个过程有点类似，不过采用的不是上面例子中的通常的这种除法。在CRC算法中，将二进制数据流作为多项式的系数，然后进行的是多项式的乘除法。还是举个例子吧。
比如说我们有两个二进制数，分别为：1101 和1011。
1101 与如下的多项式相联系：1x3+1x2+0x1+1x0=x3+x2+x0
1011与如下的多项式相联系：1x3+0x2+1x1+1x0=x3+x1+x0
两个多项式的乘法：(x3+x2+x0)(x3+x1+x0)=x6+x5+x4+x3+x3+x3+x2+x1+x0
得到结果后，合并同类项时采用模2运算。也就是说乘除法采用正常的多项式乘除法，而加减法都采用模2运算。所谓模2运算就是结果除以2后取余数。比如3 mod 2 = 1。因此，上面最终得到的多项式为：x6+x5+x4+x3+x2+x1+x0，对应的二进制数:111111
加减法采用模2运算后其实就成了一种运算了，就是我们通常所说的异或运算：

0+0=0 0+1=1 1+0=1 1+1=0

0-0=0 1-0=1 0-1=1 1-1=0

上面说了半天多项式，其实就算是不引入多项式乘除法的概念也可以说明这些运算的特殊之处。只不过几乎所有讲解 CRC 算法的文献中都会提到多项式，因此这里也简单的写了一点基本的概念。不过总用这种多项式表示也很罗嗦，下面的讲解中将尽量采用更简洁的写法。
除法运算与上面给出的乘法概念类似，还是遇到加减的地方都用异或运算来代替。下面是一个例子：
要传输的数据为：1101011011
除数设为：10011
在计算前先将原始数据后面填上4个0：11010110110000，之所以要补0，后面再做解释。

从这个例子可以看出，采用了模2的加减法后，不需要考虑借位的问题，所以除法变简单了。最后得到的余数就是CRC 校验字。为了进行CRC运算，也就是这种特殊的除法运算，必须要指定个被除数，在CRC算法中，这个被除数有一个专有名称叫做“生成多项式”。生成多项式的选取是个很有难度的问题，如果选的不好，那么检出错误的概率就会低很多。好在这个问题已经被专家们研究了很长一段时间了，对于我们这些使用者来说，只要把现成的成果拿来用就行了。
最常用的几种生成多项式如下：
CRC8=X8+X5+X4+X0
CRC-CCITT=X16+X12+X5+X0
CRC16=X16+X15+X2+X0
CRC12=X12+X11+X3+X2+X0
CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+X0
有一点要特别注意，文献中提到的生成多项式经常会说到多项式的位宽（Width，简记为W），这个位宽不是多项式对应的二进制数的位数，而是位数减1。比如CRC8中用到的位宽为8的生成多项式，其实对应得二进制数有九位：100110001。另外一点，多项式表示和二进制表示都很繁琐，交流起来不方便，因此，文献中多用16进制简写法来表示，因为生成多项式的最高位肯定为1，最高位的位置由位宽可知，故在简记式中，将最高的1统一去掉了，如CRC32的生成多项式简记为04C11DB7实际上表示的是104C11DB7。当然，这样简记除了方便外，在编程计算时也有它的用处。
对于上面的例子，位宽为4（W=4），按照CRC算法的要求，计算前要在原始数据后填上W个0，也就是4个0。
位宽W=1的生成多项式(CRC1)有两种，分别是X1和X1+X0，读者可以自己证明10 对应的就是奇偶校验中的奇校验，而11对应则是偶校验。因此，写到这里我们知道了奇偶校验其实就是CRC校验的一种特例，这也是我要以奇偶校验作为开篇介绍的原因了。
CRC算法的编程实现说了这么多总算到了核心部分了。从前面的介绍我们知道CRC校验核心就是实现无借位的除法运算。下面还是通过一个例子来说明如何实现CRC校验。
假设我们的生成多项式为：100110001（简记为0x31），也就是CRC-8
则计算步骤如下：
（1）      将CRC寄存器（8-bits，比生成多项式少1bit）赋初值0
（2）      在待传输信息流后面加入8个0
（3）      While (数据未处理完)
（4）      Begin
（5）          If (CRC寄存器首位是1)
（6）              reg = reg XOR 0x31
（7）          CRC寄存器左移一位，读入一个新的数据于CRC寄存器的0 bit的位置。
（8）      End
（9）      CRC寄存器就是我们所要求的余数。

实际上，真正的CRC 计算通常与上面描述的还有些出入。这是因为这种最基本的CRC除法有个很明显的缺陷，就是数据流的开头添加一些0并不影响最后校验字的结果。这个问题很让人恼火啊，因此真正应用的CRC 算法基本都在原始的CRC算法的基础上做了些小的改动。
所谓的改动，也就是增加了两个概念，第一个是“余数初始值”，第二个是“结果异或值”。
所谓的“余数初始值”就是在计算CRC值的开始，给CRC寄存器一个初始值。“结果异或值”是在其余计算完成后将CRC寄存器的值在与这个值进行一下异或操作作为最后的校验值。
常见的三种CRC 标准用到个各个参数如下表。

	CCITT	CRC16	CRC32
校验和位宽W	16	16	32
生成多项式	x16+x12+x5+1	x16+x15+x2+1	x32+x26+x23+x22+x16+ x12+x11+x10+x8+x7+x5+ x4+x2+x1+1
除数（多项式）	0x1021	0x8005	0x04C11DB7
余数初始值	0xFFFF	0x0000	0xFFFFFFFF
结果异或值	0x0000	0x0000	0xFFFFFFFF

加入这些变形后，常见的算法描述形式就成了这个样子了：
（1）      设置CRC寄存器，并给其赋值为“余数初始值”。
（2）      将数据的第一个8-bit字符与CRC寄存器进行异或，并把结果存入CRC寄存器。
（3）      CRC寄存器向右移一位，MSB补零，移出并检查LSB。
（4）      如果LSB为0，重复第三步；若LSB为1，CRC寄存器与0x31相异或。
（5）      重复第3与第4步直到8次移位全部完成。此时一个8-bit数据处理完毕。
（6）      重复第2至第5步直到所有数据全部处理完成。
（7）      最终CRC寄存器的内容与“结果异或值”进行或非操作后即为CRC值。

示例性的C代码如下所示，因为效率很低，项目中如对计算时间有要求应该避免采用这样的代码。不过这个代码已经比网上常见的计算代码要好了，因为这个代码有一个crc的参数，可以将上次计算的crc结果传入函数中作为这次计算的初始值，这对大数据块的CRC计算是很有用的，不需要一次将所有数据读入内存，而是读一部分算一次，全读完后就计算完了。这对内存受限系统还是很有用的。

1.     #define POLY        0x1021  
   
2.     /**
   
3.      * Calculating CRC-16 in 'C'
   
4.      * @para addr, start of data
   
5.      * @para num, length of data
   
6.      * @para crc, incoming CRC
   
7.      */  
   
8.     uint16_t crc16(unsigned char *addr, int num, uint16_t crc)  
   
9.     {  
   
10.         int i;  
    
11.         for (; num > 0; num--)              /* Step through bytes in memory */  
    
12.         {  
    
13.             crc = crc ^ (*addr++ << 8);     /* Fetch byte from memory, XOR into CRC top byte*/  
    
14.             for (i = 0; i < 8; i++)             /* Prepare to rotate 8 bits */  
    
15.             {  
    
16.                 if (crc & 0x8000)            /* b15 is set... */  
    
17.                     crc = (crc << 1) ^ POLY;    /* rotate and XOR with polynomic */  
    
18.                 else                          /* b15 is clear... */  
    
19.                     crc <<= 1;                  /* just rotate */  
    
20.             }                             /* Loop for 8 bits */  
    
21.             crc &= 0xFFFF;                  /* Ensure CRC remains 16-bit value */  
    
22.         }                               /* Loop until num=0 */  
    
23.         return(crc);                    /* Return updated CRC */  
    
24.     }  

复制代码

上面的代码是我从http://mdfs.net/Info/Comp/Comms/CRC16.htm找到的，不过原始代码有错误，我做了些小的修改。

下面对这个函数给出个例子片段代码：

1.     unsigned char data1[] = {'1', '2', '3', '4', '5', '6', '7', '8', '9'};  
   
2.     unsigned char data2[] = {'5', '6', '7', '8', '9'};  
   
3.     unsigned short c1, c2;  
   
4.     c1 = crc16(data1, 9, 0xffff);  
   
5.     c2 = crc16(data1, 4, 0xffff);  
   
6.     c2 = crc16(data2, 5, c2);  
   
7.     printf("%04x", c1);  
   
8.     printf("%04x", c2);  

复制代码

读者可以验算，c1、c2 的结果都为 29b1。上面代码中crc 的初始值之所以为0xffff，是因为CCITT标准要求的除数初始值就是0xffff。

上面的算法对数据流逐位进行计算，效率很低。实际上仔细分析CRC计算的数学性质后我们可以多位多位计算，最常用的是一种按字节查表的快速算法。该算法基于这样一个事实：计算本字节后的CRC码，等于上一字节余式CRC码的低8位左移8位，加上上一字节CRC右移 8位和本字节之和后所求得的CRC码。如果我们把8位二进制序列数的CRC(共256个)全部计算出来，放在一个表里，编码时只要从表中查找对应的值进行处理即可。

按照这个方法，可以有如下的代码（这个代码也不是我写的，是我在Micbael Barr的书“Programming Embedded Systems in C and C++” 中找到的，同样，我做了点小小的改动。）：

1.     /*
   
2.     crc.h
   
3.     */  
   
4.       
   
5.     #ifndef CRC_H_INCLUDED  
   
6.     #define CRC_H_INCLUDED  
   
7.       
   
8.     /*
   
9.     * The CRC parameters. Currently configured for CCITT.
   
10.     * Simply modify these to switch to another CRC Standard.
    
11.     */  
    
12.     /*
    
13.     #define POLYNOMIAL          0x8005
    
14.     #define INITIAL_REMAINDER   0x0000
    
15.     #define FINAL_XOR_VALUE     0x0000
    
16.     */  
    
17.     #define POLYNOMIAL          0x1021  
    
18.     #define INITIAL_REMAINDER   0xFFFF  
    
19.     #define FINAL_XOR_VALUE     0x0000  
    
20.       
    
21.     /*
    
22.     #define POLYNOMIAL          0x1021
    
23.     #define POLYNOMIAL          0xA001
    
24.     #define INITIAL_REMAINDER   0xFFFF
    
25.     #define FINAL_XOR_VALUE     0x0000
    
26.     */  
    
27.       
    
28.     /*
    
29.     * The width of the CRC calculation and result.
    
30.     * Modify the typedef for an 8 or 32-bit CRC standard.
    
31.     */  
    
32.     typedef unsigned short width_t;  
    
33.     #define WIDTH (8 * sizeof(width_t))  
    
34.     #define TOPBIT (1 << (WIDTH - 1))  
    
35.       
    
36.     /**
    
37.      * Initialize the CRC lookup table.
    
38.      * This table is used by crcCompute() to make CRC computation faster.
    
39.      */  
    
40.     void crcInit(void);  
    
41.       
    
42.     /**
    
43.      * Compute the CRC checksum of a binary message block.
    
44.      * @para message, 用来计算的数据
    
45.      * @para nBytes, 数据的长度
    
46.      * @note This function expects that crcInit() has been called
    
47.      *       first to initialize the CRC lookup table.
    
48.      */  
    
49.     width_t crcCompute(unsigned char * message, unsigned int nBytes);  
    
50.       
    
51.     #endif // CRC_H_INCLUDED  

复制代码

1.     /*
   
2.      *crc.c
   
3.      */  
   
4.       
   
5.     #include "crc.h"  
   
6.     /*
   
7.     * An array containing the pre-computed intermediate result for each
   
8.     * possible byte of input. This is used to speed up the computation.
   
9.     */  
   
10.     static width_t crcTable[256];  
    
11.       
    
12.     /**
    
13.      * Initialize the CRC lookup table.
    
14.      * This table is used by crcCompute() to make CRC computation faster.
    
15.      */  
    
16.     void crcInit(void)  
    
17.     {  
    
18.         width_t remainder;  
    
19.         width_t dividend;  
    
20.         int bit;  
    
21.         /* Perform binary long division, a bit at a time. */  
    
22.         for(dividend = 0; dividend < 256; dividend++)  
    
23.         {  
    
24.             /* Initialize the remainder.  */  
    
25.             remainder = dividend << (WIDTH - 8);  
    
26.             /* Shift and XOR with the polynomial.   */  
    
27.             for(bit = 0; bit < 8; bit++)  
    
28.             {  
    
29.                 /* Try to divide the current data bit.  */  
    
30.                 if(remainder & TOPBIT)  
    
31.                 {  
    
32.                     remainder = (remainder << 1) ^ POLYNOMIAL;  
    
33.                 }  
    
34.                 else  
    
35.                 {  
    
36.                     remainder = remainder << 1;  
    
37.                 }  
    
38.             }  
    
39.             /* Save the result in the table. */  
    
40.             crcTable[dividend] = remainder;  
    
41.         }  
    
42.     } /* crcInit() */  
    
43.       
    
44.     /**
    
45.      * Compute the CRC checksum of a binary message block.
    
46.      * @para message, 用来计算的数据
    
47.      * @para nBytes, 数据的长度
    
48.      * @note This function expects that crcInit() has been called
    
49.      *       first to initialize the CRC lookup table.
    
50.      */  
    
51.     width_t crcCompute(unsigned char * message, unsigned int nBytes)  
    
52.     {  
    
53.         unsigned int offset;  
    
54.         unsigned char byte;  
    
55.         width_t remainder = INITIAL_REMAINDER;  
    
56.         /* Divide the message by the polynomial, a byte at a time. */  
    
57.         for( offset = 0; offset < nBytes; offset++)  
    
58.         {  
    
59.             byte = (remainder >> (WIDTH - 8)) ^ message[offset];  
    
60.             remainder = crcTable[byte] ^ (remainder << 8);  
    
61.         }  
    
62.         /* The final remainder is the CRC result. */  
    
63.         return (remainder ^ FINAL_XOR_VALUE);  
    
64.     } /* crcCompute() */  

复制代码

上面代码中crcInit() 函数用来计算crcTable，因此在调用 crcCompute 前必须先调用 crcInit()。不过，对于嵌入式系统，RAM是很紧张的，最好将 crcTable 提前算好，作为常量数据存到程序存储区而不占用RAM空间。CRC 计算实际上还有很多内容可以介绍，不过对于一般的程序员来说，知道这些也就差不多了。余下的部分以后有时间了我再写篇文章来介绍吧。