循环冗余校验CRC

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

CRC目的在于保证数据的完整性，其方法是在发送数据的后面再增加多余的若干位数据，接收方使用同样的CRC计算方法，检查接收到的数据CRC是否为0。

  • 结果为0：数据是完整的，接收方可以处理这个数据。
  • 结果不为0：数据不完整，接收方一般丢弃或者要求重发数据。

:::warning CRC的核心算法就是如何通过一堆“发送数据”来计算“多余的若干数据”。 :::

CRC采用的策略是用除法求余数（CRC算法的本质）。不同于十进制的除法运算，CRC用的是二进制的触发运算。二进制除法运算属于模2运算，模2运算的特点是没有进位。

CRC的细节

CRC计算还涉及初始值、结果异或值、输入数据反转、输出数据反转。

  • 初始值是给CRC计算一个初始值，可以是0或其他值；
  • 结果异或值是把计算结果再异或某一个值，目的是防止全0数据的CRC一直为0。
  • 输入数据反转是指输入数据以字节为单位按逆序处理；
  • 输出数据反转是指CRC计算结果整体按位逆序处理。（这样做的一个合理解释是右移运算比左移运算更容易计算，效率高，与大小端无关）

CRC二进制除法过程

  1. 如果输入数据反转为True，对输入数据按字节进行反转作为被除数；否则直接将输入数据作为被除数。
  2. 被除数补0，CRC码为几位就补几个0，CRC-4补4个0，CRC-5补5个0， CRC-8补8个0， CRC-16补16个0。
  3. 如果初始值不为0，第一步计算需要先把被除数与初始值两者做模2加法运算（异或）。
  4. 进行二进制除法运算，求得余数，得到结果。
  5. 如果结果异或值不为0，那么最后的结果需要同结果异或值做异或运算。
  6. 如果输出数据反转为True，那么最终的结果还需要按位进行反转。

CRC表

CRC表是对CRC优化的一种方式。由于CRC的计算过程中需要不停地循环做异或操作，占用CPU较多。因此，在算法上有一种空间换时间的做法。即：提前把0x00 - 0xFF共256个数据的CRC码计算保存好，那么在计算的过程中就可以节省CPU，这个提前计算好的表叫CRC表（CRC表仅与多项式有关）。

:::warning 为什么CRC表仅与多项式有关？
输入初始值、输入数据反转、输出数据反转、结果异或值都是与输入输出数据相关的。因此CRC表（通用的CRC表）仅与多项式有关。 :::

参考文献

  1. https://www.bilibili.com/read/cv12483775