CRC 循环校验详解

2022-11-20 language c/cpp

Cyclic Redundancy Check, CRC 循环冗余校验，通常用于网络、文件等校验，校验码的长度固定，而且从检错的正确率与速度成本之间比较好的平衡，使其称为当前最常见的数据校验方式。

模二运算

这是针对计算机的算法，其与算术运算相似，支持加减乘除四则运算，不过无进位和借位 (Carry Less)，而 CRC 采用的是模二除法，实际计算结果与异或 XOR 相同。

手动计算

假设数据为 0xC2 = b11000010，对应被除数为 0x1D5 = b 111010101，那么计算如下。

1100001000000000  --> 通过0补齐长度
111010101.......
--------
001010001.......
  111010101.....
  --------
  010010001.....
   111010101.... --> A
   ---------
   011110111....
    111010101...
    --------
    000111011...
       111010101 --> B
       ---------
       000001101 --> 0x0D

计算时只需要对齐首位非零即可，可能只需要移动一位，如 A 所示；也可能会移动多个位，如 B 所示。计算结果实际上只关注余数，而除数则不关注。

将上述的校验值添加到消息的末尾，接受方以同样的方式计算。

1100001000001101  --> 数据保存传输时将结果保存
111010101.......
--------
001010001.......
  111010101.....
  --------
  010010001.....
   111010101....
   ---------
   011110111....
    111010101...
    --------
    000111010...
       111010101
       ---------
       000000000 --> 0x00

如果计算结果为 0 则表示数据传输正常。

也就是说，将实际数据作为除数，根据校验算法确定被除数，余数就作为校验值，不过需要注意，CRC 校验并不是单纯的模二除法，初始值会向左移位，同时不要求最后除尽，只要对齐至最后一位即可，如果长度不满足则前面补零。

多项式表达

计算 CRC 需要先确定参数模型，通常有如下的几个：

  • NAME 参数模型名称，通常会表示位数以及部分注解，例如 CRC-8、CRC-8-ATM 等。
  • WIDTH 宽度，即生成的 CRC 数据位宽，如上的 CRC-8 生成的 CRC 就是 8 位。
  • POLY(Polynomial) 十六进制多项式，一般省略最高位 1，如 x8+x7+x6+x4+x2+1，二进制对应 1 1101 0101，省略最高位转换为十六进制为 0xD5。
  • INIT 初始值，和 WIDTH 位宽一致。
  • REFIN (Input Reflected) 计算前原始数据是否翻转，例如原始数据 0x34 = 00110100 翻转后为 00101100 = 0x2c 。
  • REFOUT (Result Reflected) 运算完成之后，得到的 CRC 值是否进行翻转，注意这里是对整个结果进行翻转。
  • XOROUT 计算结果与此参数进行异或运算后得到最终的 CRC 值。

参考