转载：https://zhuanlan.zhihu.com/p/256487370
参考：C语言CRC
视频：https://www.bilibili.com/video/av63987698/

1.1 CRC算法简介

1.1.1 为什么需要CRC校验

一个完整的数据帧通常由以下部分构成：帧头+数据+校验位+帧尾
校验位是为了保证数据在传输过程中的完整性，采用一种指定的算法对原始数据进行计算，得出的一个校验值。接收方接收到数据时，采用同样的校验算法对原始数据进行计算，如果计算结果和接收到的校验值一致，说明数据校验正确，这一帧数据可以使用，如果不一致，说明传输过程中出现了差错，这一帧数据丢弃，请求重新发送。
常用的校验算法有奇偶校验、校验和、CRC，还有LRC、BCC等不常用的校验算法。
以串口通讯中的奇校验为例，如果数据中1的个数为奇数，则奇校验位0，否则为1。

例如原始数据为：0001 0011，数据中1的个数（或各位相加）为3，所以奇校验位为0。3个1，因此补0个1就是奇数。因此校验位为0。
这种校验方法很简单，但这种校验方法有很大的误码率。假设由于传输过程中的干扰，接收端接收到的数据是0010 0011，通过奇校验运算，得到奇校验位的值为0，虽然校验通过，但是数据已经发生了错误。
image.png
校验和同理也会有类似的错误：

image.png
一个好的校验校验方法，配合数字信号编码方式，如(差分)曼彻斯特编码（网络通信），(不)归零码等对数据进行编码，可大大提高通信的健壮性和稳定性。例如以太网中使用的是CRC-32校验，曼彻斯特编码方式，MODBUS协议使用的是CRC16的校验。

1.3 CRC校验

循环冗余校验（Cyclic Redundancy Check， CRC）是一种根据网络数据包或计算机文件等数据产生简短固定位数校验码的一种信道编码技术，主要用来检测或校验数据传输或者保存后可能出现的错误。它是利用除法及余数的原理来作错误侦测的。

CRC校验计算速度快，检错能力强，易于用编码器等硬件电路实现。从检错的正确率与速度、成本等方面，都比奇偶校验等校验方式具有优势。因而，CRC 成为计算机信息通信领域最为普遍的校验方式。常见应用有以太网/USB通信，压缩解压，视频编码，图像存储，磁盘读写等。

1.3.1 CRC参数模型

同样的CRC多项式，调用不同的CRC计算函数，得到的结果却不一样，而且和手算的结果也不一样，这就涉及到CRC的参数模型了。计算一个正确的CRC值，需要知道CRC的参数模型。

一个完整的CRC参数模型应该包含以下信息：WIDTH，POLY，INIT，REFIN，REFOUT，XOROUT。

  • NAME：参数模型名称。
  • WIDTH：宽度，即生成的CRC数据位宽，如CRC-8，生成的CRC为8位
  • POLY：十六进制多项式，省略最高位1，如 x8 + x2 + x + 1，二进制为1 0000 0111，省略最高位1，转换为十六进制为0x07。
  • INIT：CRC初始值，和WIDTH位宽一致。
  • REFIN：true或false，在进行计算之前，原始数据是否翻转，如原始数据：0x34 = 0011 0100，如果REFIN为true，进行翻转之后为0010 1100 = 0x2c
  • REFOUT：true或false，运算完成之后，得到的CRC值是否进行翻转，如计算得到的CRC值：0x97 = 1001 0111，如果REFOUT为true，进行翻转之后为11101001 = 0xE9。
  • XOROUT：计算结果与此参数进行异或运算后得到最终的CRC值，和WIDTH位宽一致。

常用的21个标准CRC参数模型：
image.png
CRC校验在电子通信领域非常常用，可以说有通信存在的地方，就有CRC校验：

  • 美信(MAXIM)的芯片DS2401/DS18B20，都是使用的CRC-8/MAXIM模型
  • SD卡或MMC使用的是CRC-7/MMC模型
  • Modbus通信使用的是CRC-16/MODBUS参数模型
  • USB协议中使用的CRC-5/USB和CRC-16/USB模型
  • STM32自带的硬件CRC计算模块使用的是CRC-32模型

至于多项式的选择，初始值和异或值的选择，输入输出是否翻转，这就涉及到一定的编码和数学知识了。感兴趣的朋友，可以了解一下每个CRC模型各个参数的来源。至于每种参数模型的检错能力、重复率，需要专业的数学计算了，不在本文讨论的范畴内。

1.3.2 CRC实现

下面手算一个CRC值，来了解CRC计算的原理。
问：原始数据：0x34，使用CRC-8/MAXIN参数模型，求CRC值？
答：根据CRC参数模型表，得到CRC-8/MAXIN的参数如下：

  1. POLY =         0x31 = 0011 0001(最高位1已经省略)
  2. INIT =         0x00
  3. XOROUT =     0x00
  4. REFIN =     TRUE
  5. REFOUT =     TRUE

有了上面的参数，这样计算条件才算完整，下面来实际计算：

  1. 0.原始数据 = 0x34 = 0011 0100，多项式 = 0x31 = 1 0011 0001
  2. 1.INIT = 00，原始数据高8位和初始值进行异或运算保持不变。
  3. 2.REFIN为TRUE，需要先对原始数据进行翻转：0011 0100 > 0010 1100
  4. 3.原始数据左移8位，即后面补8个0：0010 1100 0000 0000
  5. 4.把处理之后的数据和多项式进行模2除法，求得余数：
  6. 原始数据：0010 1100 0000 0000 = 10 1100 0000 0000
  7. 多项式：1 0011 0001
  8. 模2除法取余数低8位：1111 1011
  9. 5.与XOROUT进行异或，1111 1011 xor 0000 0000 = 1111 1011 
  10. 6.因为REFOUT为TRUE，对结果进行翻转得到最终的CRC-8值：1101 1111 = 0xDF
  11. 7.数据+CRC：0011 0100 1101 1111 = 34DF，相当于原始数据左移8位+余数。

模2除法求余数：
image.png
验证手算结果：
image.png
可以看出是一致的，当你手算的结果和工具计算结果不一致时，可以看看INIT，XOROUT，REFINT，REFOUT这些参数是否一致，有1个参数不对，计算出的CRC结果都不一样。

1.4 CRC计算的程序实现

为什么modbusCRC使用A005而不是8005
这也就是说为什么视频中式正向的，而这里是反向的。

0x8005=1000 0000 0000 0101B
0xA001=1010 0000 0000 0001B
对比两个二进制高低位正好是完全相反的，CRC校验分为正向校验与反向校验。正向校验高位在左，反向校验低位在左，比如正向CRC校验的数据为0xAF5D=1010 1111 0101 1101B与0x8005异或时应该是0xAF5D^0x8005，而要使用0xA001与数据进行校验也应该使0xAF5D高低位换顺序为0xBAF5=1011 1010 1111 0101B。正向校验使用左移位，反向校验使用右移位，其实原理是一样的，得看校验的数据高低位顺序。

CRC-16-MODBUS实现

相关参数：

  1. /******************************************************************************
  2.  * Name:    CRC-16/MODBUS       x16+x15+x2+1
  3.  * Poly:    0x8005
  4.  * Init:    0xFFFF
  5.  * Refin:   True
  6.  * Refout:  True
  7.  * Xorout:  0x0000
  8.  * Note:
  9.  *****************************************************************************/

实现步骤如下：
image.png

  1. //这个计算方法就和上面视频中的一样，不过那个是正的，这个是反的。 从左到右
  2. uint16_t crc16_modbus(uint8_t *data, uint16_t length)
  3. {
  4.     uint8_t i;
  5.     uint16_t crc = 0xffff;        // Initial value
  6.     while(length--)
  7.     {
  8.         crc ^= *data++;            // crc ^= *data; data++;
  9.         for (i = 0; i < 8; ++i)
  10.         {
  11.             if (crc & 1)
  12.                 crc = (crc >> 1) ^ 0xA001;        // 0xA001 = reverse 0x8005
  13.             else
  14.                 crc = (crc >> 1);
  15.         }
  16.     }
  17.     return crc;
  18. }
  21. unsigned int modbusCRC16(const vector<unsigned char> &data)
  22. {
  23.     unsigned short CRC = 0xffff;//（1）CRC寄存器初值0xffff
  25.     int dataSize = data.size();
  26.     for (int i = 0; i < dataSize; i++)//（5）重复步骤2~4
  27.     {
  28.         //1.每个数都要与CRC进行异或
  29.         CRC = CRC^data[i];//(2)数据与CRC异或
  30.         for (int j = 0; j < 8; j++)//（4）重复8次步骤3
  31.         {
  32.             //(3)检测低位是否为1。方法：与1相与，低位为1则结果为1，低位为0则结果为0
  33.             if (CRC & 1)//如果低位为1，则先右移一位，再与A001H相异或
  34.             {
  35.                 CRC >>= 1;
  36.                 CRC ^= 0xA001;
  37.             }
  38.             else//低位为0，则右移一位
  39.                 CRC >>= 1;
  40.         }
  41.     }
  42.     return CRC;
  43. }

实现函数：
https://github.com/whik/crc-lib-c
image.png