概述

循环冗余校验（Cyclic redundancy check，通称“CRC”）是一种根据网络数据数据包或计算机文件等数据产生简短固定位数校验码的一种散列函數，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者存储之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。

原理

CRC校验（循环冗余校验）是数据通讯中最常采用的校验方式。在嵌入式软件开发中，经常要用到CRC 算法对各种数据进行校验。

奇偶校验

奇偶校验是CRC 校验的一种(CRC-1)。RS232串行通讯可以设置奇偶校验位，所谓奇偶校验就是在发送的每一个字节后都加上一位，使得每个字节中1的个数为奇数个或偶数个。比如我们要发送的字节是0x1a，二进制表示为0001 1010。

  • 采用奇校验，则在数据后补上个0，数据变为0001 1010 0，数据中1的个数为奇数个（3个）
  • 采用偶校验，则在数据后补上个1，数据变为0001 1010 1，数据中1的个数为偶数个（4个）

接收方通过计算数据中1个数是否满足奇偶性来确定数据是否有错。

奇偶校验的缺点也很明显，首先，它对错误的检测概率大约只有50%。也就是只有一半的错误它能够检测出来。另外，每传输一个字节都要附加一位校验位，对传输效率的影响很大。因此，在高速数据通讯中很少采用奇偶校验。奇偶校验优点也很明显，它很简单，因此可以用硬件来实现，这样可以减少软件的负担。因此，奇偶校验也被广泛的应用着。

累加和校验

另一种常见的校验方式是累加和校验。所谓累加和校验实现方式有很多种，最常用的一种是在一次通讯数据包的最后加入一个字节的校验数据。这个字节内容为前面数据包中全部数据的忽略进位的按字节累加和。比如下面的例子：

我们要传输的信息为： 6、23、4
加上校验和后的数据包：6、23、4、33

这里 33 为前三个字节的校验和。接收方收到全部数据后对前三个数据进行同样的累加计算，如果累加和与最后一个字节相同的话就认为传输的数据没有错误。

加和校验由于实现起来非常简单，也被广泛的采用。但是这种校验方式的检错能力也比较一般，对于单字节的校验和大概有1/256 的概率将原本是错误的通讯数据误判为正确数据。之所以这里介绍这种校验，是因为CRC校验在传输数据的形式上与累加和校验是相同的，都可以表示为：通讯数据 校验字节（也可能是多个字节）。

CRC算法

CRC 算法的基本思想是将传输的数据当做一个位数很长的数。将这个数除以另一个数。得到的余数作为校验数据附加到原数据后面。CRC算法中，将二进制数据流作为多项式的系数，然后进行的是多项式的乘除法。

下面是一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
要传输的数据为：1101011011
除数设为：10011

在计算前先将原始数据后面填上4个0：11010110110000
          1100001010
      ——————————————
10011)11010110110000
      10011
      ——————————————
       10011
       10011
      ——————————————
            10110
            10011
      ——————————————
              10100
              10011
      ——————————————
                1110

从这个例子可以看出，采用了模2的加减法(异或运算符)后，不需要考虑借位的问题，所以除法变简单了。最后得到的余数就是CRC 校验字。为了进行CRC运算，也就是这种特殊的除法运算，必须要指定个被除数，在CRC算法中，这个被除数有一个专有名称叫做“生成多项式”。生成多项式的选取是个很有难度的问题，如果选的不好，那么检出错误的概率就会低很多。

最常用的几种生成多项式如下：

  • CRC8 = X^8 + X^5 + X^4 + X^0 = 1 0011 0001 (0x31)
  • CRC12 = X^12 + X^11 + X^3 + X^2 + X^0 = 1 1000 0000 1101 (0x080D)
  • CRC-CCITT = X^16 + X^12 + X^5 + X^0 = 1 0001 0000 0010 0001 (0x1021)
  • CRC16 = X^16 + X^15 + X^2 + X^0 = 1 1000 0000 0000 0101 (0x8005)
  • CRC32 = 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 + X^0 = 1 0000 0100 1100 0001 0001 1101 1011 0111 (0x04C11DB7)

生成多项式经常会说到多项式的位宽（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算法

假设生成多项式(被除数)为：100110001（简记为0x31），也就是CRC-8，
原始CRC计算步骤如下：

  • 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

CRC寄存器就是我们所要求的余数。
实际C代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
unsigned char crc8_gen(unsigned char *data,unsigned char length){
    int j;
    unsigned char crc_reg = 0;
    while(length--){
        crc_reg ^= *data++;
        for(j=0;j<8;j++){
            if(crc_reg & 0x80){
                crc_reg = (crc_reg << 1) ^ 0x31;
            }else{
                crc_reg = crc_reg << 1;
            }
        }
    }
    return crc_reg;
}

实际上，真正的CRC 计算通常与上面描述的还有些出入。这是因为这种最基本的CRC除法有个很明显的缺陷，就是数据流的开头添加一些0并不影响最后校验字的结果。因此真正应用的CRC 算法基本都在原始的CRC算法的基础上做了些小的改动。所谓的改动，也就是增加了两个概念，第一个是“余数初始值”，第二个是“结果异或值”。

所谓的“余数初始值”就是在计算CRC值的开始，给CRC寄存器一个初始值。“结果异或值”是在其余计算完成后将CRC寄存器的值在与这个值进行一下异或操作作为最后的校验值。

实际CRC算法

实际CRC计算步骤如下：

  • 1.设置CRC寄存器，并给其赋值为“余数初始值”。
  • 2.将数据的第一个8-bit字符与CRC寄存器进行异或，并把结果存入CRC寄存器。
  • 3.CRC寄存器向左移一位，LSB补零，移出并检查MSB。
  • 4.如果MSB为0，重复第三步；若MSB为1，CRC寄存器与0x31相异或。
  • 5.重复第3与第4步直到8次移位全部完成。此时一个8-bit数据处理完毕。
  • 6.重复第2至第5步直到所有数据全部处理完成。
  • 7.最终CRC寄存器的内容与“结果异或值”进行异或操作后即为CRC值。

实际使用中除了寄存器初始值、结果异或值外还有字节颠倒的标记RefIn和RefOut：
所谓颠倒意思是字节数左右取反，例如11010010，字节颠倒后变为01001011。

RefIn：这是个BOOL值，表示字符串是否进行了字节颠倒。某些硬件传输时使用LSB模式，即先传输低位的bit，这样使用MSB模式收到的字节就是颠倒的。假如A传输的是1000 0000，但是底层硬件传输时按照0000 0001的顺序传给B，B的传输模式是MSB，即认为接收的第一个bit是高位bit。那么本来应该是0x80，但是B却认为它接收的是0x01。

对于这种情况，在做crc之前把每一个字节颠倒过来就好了。但是这么做将浪费大量时间和工作量，于是出现了颠倒crc算法，即除了源串字节不进行颠倒以外，初始值、poly、进寄存器方向、最后的crc结果都进行颠倒。这样与费时费事的颠倒每个字节计算的结果完全一致。

RefOut：颠倒输出结果。

常见CRC参数模型如下：

CRC算法名称 宽度 多项式 初始值 结果异或值 输入值反转 输出值反转
CRC-4/ITU 4 03 00 00 true true
CRC-5/EPC 5 09 09 00 false false
CRC-5/ITU 5 15 00 00 true true
CRC-5/USB 5 05 1F 1F true true
CRC-6/ITU 6 03 00 00 true true
CRC-7/MMC 7 09 00 00 false false
CRC-8 8 07 00 00 false false
CRC-8/ITU 8 07 00 55 false false
CRC-8/ROHC 8 07 FF 00 true true
CRC-8/MAXIM 8 31 00 00 true true
CRC-16/IBM 16 8005 0000 0000 true true
CRC-16/MAXIM 16 8005 0000 FFFF true true
CRC-16/USB 16 8005 FFFF FFFF true true
CRC-16/MODBUS 16 8005 FFFF 0000 true true
CRC-16/CCITT 16 1021 0000 0000 true true
CRC-16/CCITT-FALSE 16 1021 FFFF 0000 false false
CRC-16/x^5 16 1021 FFFF FFFF true true
CRC-16/XMODEM 16 1021 0000 0000 false false
CRC-16/DNP 16 3D65 0000 FFFF true true
CRC-32 32 04C11DB7 FFFFFFFF FFFFFFFF true true
CRC-32/MPEG-2 32 04C11DB7 FFFFFFFF 00000000 false false

实现CRC算法主要有逐位计算和查表两种，逐位计算效率比查表低很多。具体算法实现将在后续章节给出。