前言

最近的工作中，要实现对通信数据的 CRC 计算，所以花了两天的时间好好研究了一下，周末有时间整理了一下笔记。

一个完整的数据帧通常由以下部分构成：
CRC校验原理及其实现 - 图1
校验位（字）是为了保证数据在传输过程中的完整性，采用一种指定的算法对原始数据进行计算，得出的一个校验值。接收方接收到数据时，采用同样的校验算法对原始数据进行计算，如果计算结果和接收到的校验值一致，说明数据校验正确，这一帧数据可以使用，如果不一致，说明传输过程中出现了差错，这一帧数据丢弃，请求重发。

常用的校验算法有奇偶校验、校验和、CRC，还有 LRC、BCC 等不常用的校验算法。

以串口通讯中的奇校验为例，如果数据中 1 的个数为奇数，则奇校验位 0，否则为 1。

例如原始数据为：0001 0011，数据中 1 的个数（或各位相加）为 3，所以奇校验位为 0。这种校验方法很简单，但这种校验方法有很大的误码率。假设由于传输过程中的干扰，接收端接收到的数据是 0010 0011，通过奇校验运算，得到奇校验位的值为 0，虽然校验通过，但是数据已经发生了错误。
CRC校验原理及其实现 - 图2
校验和同理也会有类似的错误：
CRC校验原理及其实现 - 图3
一个好的校验校验方法，配合数字信号编码方式，如 (差分) 曼彻斯特编码，(不)归零码等对数据进行编码，可大大提高通信的健壮性和稳定性。例如以太网中使用的是 CRC-32 校验，曼彻斯特编码方式。本篇文章介绍 CRC 校验的原理和实现方法。

CRC 算法简介

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

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

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 位宽一致。

通常如果只给了一个多项式，其他的没有说明则：INIT=0x00，REFIN=false，REFOUT=false，XOROUT=0x00。

常用的 21 个标准 CRC 参数模型：
CRC校验原理及其实现 - 图4

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 模型各个参数的来源。至于每种参数模型的检错能力、重复率，需要专业的数学计算了，不在本文讨论的范畴内。

CRC 计算

好了，了解了 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
    • 模 2 除法求余数：

CRC校验原理及其实现 - 图5

  • 验证手算结果：

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

CRC 校验

上面通过笔算的方式，讲解了 CRC 计算的原理，下面来介绍一下如何进行校验。

按照上面 CRC 计算的结果，最终的数据帧：0011 0100 1101 1111 = 34DF，前 8 位 0011 0100 是原始数据，后 8 位 1101 1111 是 CRC 结果。

接收端的校验有两种方式：

  • 一种是和 CRC 计算一样，在本地把接收到的数据和 CRC 分离，然后在本地对数据进行 CRC 运算，得到的 CRC 值和接收到的 CRC 进行比较，如果一致，说明数据接收正确，如果不一致，说明数据有错误。

  • 另一种方法是把整个数据帧进行 CRC 运算，因为是数据帧相当于把原始数据左移 8 位，然后加上余数，如果直接对整个数据帧进行 CRC 运算（除以多项式），那么余数应该为 0，如果不为 0 说明数据出错。

  • image.png

而且，不同位出错，余数也不同，可以证明，余数与出错位数的对应关系只与 CRC 参数模型有关，而与原始数据无关。

CRC 计算的 C 语言实现

无论是用 C 还是其他语言，实现方法网上很多，这里我找了一个基于 C 语言的 CRC 计算库，里面包含了常用的 21 个 CRC 参数模型计算函数，可以直接使用，只有crcLib.c和crcLib.h两个文件。

GitHub 地址：https://github.com/whik/crc-lib-c
个人RCR算法库：crc_collection.ccrc_collection.hmain.c
使用方法非常简单：

  1.  * main.c
  2.  *
  3.  *  Created on: May 15, 2021
  4.  *      Author: mate
  5.  */
  7. #include <stdio.h>
  8. #include "crc_collection.h"
  10. #define DATALEN   3
  12. int main( )
  13. {
  14.     unsigned char data_buf[DATALEN] = {0x11, 0x55, 0xED};
  16.     printf("CRC_8_STD = 0x%02X\n", crc8_cal(data_buf, DATALEN, CRC_8_STD) );
  17.     printf("CRC_8_ITU = 0x%02X\n", crc8_cal(data_buf, DATALEN, CRC_8_ITU) );
  18.     printf("CRC_8_MAXIM = 0x%02X\n", crc8_cal(data_buf, DATALEN, CRC_8_MAXIM) );
  20.     printf("CRC_16_XMODE = 0x%04X\n", crc16_cal(data_buf, DATALEN,  CRC_16_XMODE));
  21.     printf("CRC_16_CCITT = 0x%04X\n", crc16_cal(data_buf, DATALEN,  CRC_16_CCITT));
  22.     printf("CRC_16_USB = 0x%04X\n", crc16_cal(data_buf, DATALEN,  CRC_16_USB));
  23.     printf("CRC_16_IBM = 0x%04X\n", crc16_cal(data_buf, DATALEN,  CRC_16_IBM));
  24.     printf("CRC_16_MAXIM = 0x%04X\n", crc16_cal(data_buf, DATALEN,  CRC_16_MAXIM));
  25.     printf("CRC_16_MODBUS = 0x%04X\n", crc16_cal(data_buf, DATALEN,  CRC_16_MODBUS));
  27.     printf("CRC_32_STD = 0x%08X\n", crc32_cal(data_buf, DATALEN,  CRC_32_STD));
  28.     printf("CRC_32_MPEG_2 = 0x%08X\n", crc32_cal(data_buf, DATALEN,  CRC_32_MPEG_2));
  30.     int file_CRC32 = 0;
  31.     Crc32_ComputeFile("crc_collection.c", (uint32_t *)&file_CRC32, CRC_32_STD);
  32.     printf("CRC_32_File = 0x%08X\n", file_CRC32);
  34.     return 0;
  35. }

计算结果：
image.png

CRC 计算工具

下面这几款工具都可以自定义 CRC 算法模型，而且都有标准 CRC 模型可供选择。如果自己用 C 语言或者 Verilog 实现校验算法时，非常适合作为标准答案进行验证。

  • 在线计算：www.ip33.com/crc.html
  • 离线计算工具：CRC_Calc v0.1.exe 或者 GCRC.exe

格西 CRC 计算器
CRC校验原理及其实现 - 图9

下载连接：http://www.geshe.com/home/products/GToolbox/bin/GCRC.exe

总结

CRC 校验并不能 100% 的检查出数据的错误，非常低的概率会出现 CRC 校验正确但数据中有错误位的情况。这和 CRC 的位数，多项式的选择等等有很大的关系，所以在实际使用中尽量选择标准 CRC 参数模型，这些多项式参数都是经过理论计算得出的，可以提高 CRC 的检错能力。CRC 校验可以检错，也可以纠正单一比特的错误，你知道纠错的原理吗？

参考资料