循环冗余校验

来自GSXAB的知识库
循环冗余校验
术语名称 循环冗余校验
英语名称 cyclic redundancy check
别名 CRC

循环冗余校验(cyclic redundancy check, CRC)是一种常见检错码，多应用于网络传输或文件存储的完整性校验。是一种基于多项式带余除法的算法。根据多项式选择的差异， CRC 这一分类下有多种不同校验码。

类似奇偶校验中添加额外的校验位使得总的按位异或和为 0 或 1 ，循环冗余校验要求向信息尾部添加指定的校验位，使得整体校验的每个校验段都在某一多项式下结果为 0 ，如果出现了循环的冗余则校验出存在错误，因此称为循环冗余校验。实践中，为加速硬件运算，这一过程中的多项式通常直接取 [math]\displaystyle{ \mathrm{GF}(2) }[/math] 上的多项式，以使得其中加减法全部被转化为按位异或运算。

由于奇偶校验中全体数据都是 1 位长度在多项式 [math]\displaystyle{ x+1 }[/math] 下的结果，奇偶校验可以看作 1 位的 CRC 。

原理

二进制信息与 GF(2) 上的多项式

二进制信息可以被看作 [math]\displaystyle{ \mathrm{GF}(2) }[/math] 上的多项式。将最左侧视为最高次项系数，最右侧视为常数项系数。

比如二进制数 [math]\displaystyle{ 10111001 }[/math] 可以看成多项式 [math]\displaystyle{ x^7 + x^5 + x^4 + x^3 + 1 }[/math] ，或者说 [math]\displaystyle{ 1x^7 + 0x^6 + 1x^5 + 1x^4 + 1x^3 + 0x^2 + 0x^1 + 1x^0 }[/math] ，因为这个多项式所有项写出并降幂排列的系数连起来就是这个二进制数。

构造多项式整除关系

类似奇偶校验中固定全部 1 的个数来使得全部异或和得到固定值，任意多项式 [math]\displaystyle{ P(x) }[/math] 与某固定的 [math]\displaystyle{ d }[/math] 次多项式 [math]\displaystyle{ G(x) }[/math] ，根据多项式带余除法的定义，必然存在唯一一对 [math]\displaystyle{ Q(x),R(x) }[/math] 使得 [math]\displaystyle{ M(x) \cdot x^d=Q(x)G(x)+R(x) }[/math] 且其中 [math]\displaystyle{ \deg R \lt \deg G }[/math] 。 因此，必然存在 [math]\displaystyle{ P(x) - R(x) = Q(x) G(x) }[/math] ，也就是 [math]\displaystyle{ G(x) \mid P(x) - R(x) }[/math] 。 考虑 [math]\displaystyle{ \mathrm{GF}(2) }[/math] 上加法和减法都是异或运算，这里也可以表达为 [math]\displaystyle{ G(x) \mid P(x) + R(x) }[/math] ，

因此，只要考虑 [math]\displaystyle{ P(x) }[/math] 再加上 [math]\displaystyle{ R(x) }[/math] 后仍然可以明确地取得原有数据，我们通常取 [math]\displaystyle{ P(x) = M(x) \cdot x^d }[/math] ，其中 [math]\displaystyle{ M(x) }[/math] 是原数据对应的多项式。这里称原数据本身为信息码，对应的多项式为报文多项式(message polynomial)，而对应地把 [math]\displaystyle{ G(x) }[/math] 称为生成多项式(generator polynomial)。也就是说这里在后方增加了必然不小于 [math]\displaystyle{ R(x) }[/math] 位数的 0 。

最终得到的信息是多项式 [math]\displaystyle{ D(x) = P(x)+R(x) = M(x)\cdot x^d + R(x) }[/math] 。

校验整除关系

此时，给定算法中有给定的 [math]\displaystyle{ G(x) }[/math] ，对取到的每一段数据 [math]\displaystyle{ D(x) = M(x) \cdot x^d + R(x) }[/math] ，我们都应该有 [math]\displaystyle{ G(x) \mid D(x) }[/math] 。如果整除关系不成立，证明 [math]\displaystyle{ D(x) }[/math] 中存在错误，且这个错误的多项式模 [math]\displaystyle{ G(x) }[/math] 下与新的余数同余。

位运算实现

由于带余除法的实际操作等价于逐位计算部分商然后做减法，考虑到 [math]\displaystyle{ \mathrm{GF}(2) }[/math] 中多项式最高项系数必为 1 ，部分商的每项系数都只可能是 0 和 1 ，所以计算每位部分商的过程被直接简化为比较大小。因此被拆分为比较、乘以 [math]\displaystyle{ x }[/math] 和减法三个运算。

以上流程中仅需要四个不同运算：

  • 比较两个多项式大小。对应于比较两个二进制数大小。
  • 当被除数不够除时，将被除多项式乘以 [math]\displaystyle{ x }[/math] 再继续试商。对应于二进制数移位。
  • 将两个多项式相减。两个多项式系数对应相减，就是两个多项式系数对应异或，就是两个二进制数按位异或。
  • 多项式 [math]\displaystyle{ D(x) = M(x) \cdot x^d + R(x) }[/math] 和 [math]\displaystyle{ P(x) = M(x) \cdot x^d }[/math] 中已知左侧或右侧取得另一侧。就是二进制数按最后 [math]\displaystyle{ d }[/math] 位分割或合并。

因此全部算法仅需要以上三种二进制数运算。

变种

所有种类的 CRC 校验码均遵循类似以上的原理，但是具体位置可能存在以下调整：

  • 有时要求的不是 [math]\displaystyle{ G(x) \mid D(x) }[/math] ，而是某种 [math]\displaystyle{ D(x) \equiv R(x) \pmod{G(x)} }[/math] ，或者说 [math]\displaystyle{ G(x) \mid D(x) + R(x) }[/math] 。
  • 在数据的最高位前填充数据，以免数据开头的 0 导致 [math]\displaystyle{ M(x) }[/math] 或者 [math]\displaystyle{ D(x) }[/math] 最高位前存在大量不影响整除关系的 0 ，无法正确校验出这些 0 是否存在。
  • 二进制和多项式的对应关系不一定是从最高位到最低位。

生成校验码

在 d 位 CRC 中，我们使用一个 [math]\displaystyle{ d }[/math] 次多项式 [math]\displaystyle{ G(x) }[/math] ，若包括系数为 0 的项，可以写成一个 [math]\displaystyle{ d+1 }[/math] 位的二进制数 [math]\displaystyle{ g }[/math] 。

对信息码，或者说一个二进制数 [math]\displaystyle{ m }[/math] ，记其多项式为 [math]\displaystyle{ M(x) }[/math] 。首先我们向其后方添加 [math]\displaystyle{ d }[/math] 个 [math]\displaystyle{ 0 }[/math] ，也就得到了一个对应 [math]\displaystyle{ M(x) \cdot x^d }[/math] 的二进制数。

通过比较大小、移位和减法进行 [math]\displaystyle{ M(x) \cdot x^d }[/math] 对 [math]\displaystyle{ G(x) }[/math] 的带余除法，得到余数 [math]\displaystyle{ R(x) }[/math] ，对应一个不超过 [math]\displaystyle{ d }[/math] 位的二进制数 [math]\displaystyle{ r }[/math] 。

将二进制数前方补 0 补到 [math]\displaystyle{ d }[/math] 位连接到 [math]\displaystyle{ m }[/math] 后，即得到一个对应 [math]\displaystyle{ D(x) = M(x) \cdot x^d + R(x) }[/math] 的二进制数，这就是带有 CRC 校验码后的完整数据。

校验

对接受到的 [math]\displaystyle{ D(x) }[/math] （或 [math]\displaystyle{ M(x) }[/math] 与 [math]\displaystyle{ R(x) }[/math] 两段信息），通过比较大小、移位、减法确认是否有 [math]\displaystyle{ G(x) \mid D(x) }[/math] 。如果不成立，可以判定数据存在问题。

常见使用

上述描述中，使用 [math]\displaystyle{ d }[/math] 位二进制数、校验码长度， [math]\displaystyle{ (d+1) }[/math] 次多项式的 CRC 一般被命名为某个 CRC [math]\displaystyle{ d }[/math]-xxx 。最常用的 CRC 可以省略掉后缀。

  • CRC-1 ：多项式 [math]\displaystyle{ x+1 }[/math] 。即奇偶校验码。
  • CRC-8 ：多项式 [math]\displaystyle{ x^8 + x^7 + x^6 + x^4 + x^2 + 1 }[/math] 。
  • CRC-32 ：多项式 [math]\displaystyle{ 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 }[/math] 。


模板:检错码

检索自“https://knowledge.gsxab.top/index.php?title=循环冗余校验&oldid=3648”