循环冗余校验

循环冗余校验（CRC, Cyclic Redundancy Check）

现今的计算机网络中广泛应用的差错检测技术基于循环冗余检测，CRC编码也称为多项式编码（polynomial code）。

CRC中的计算采用模2运算，即加法不进位、减法不借位，这意味着加法和减法是相同的，同时模2运算等价于异或XOR运算。

发送方与接收方

假设待发送的数据$D$的长度为$d$位，发送方和接收方首先需要协商一个长度为$r + 1$位的生成多项式$G$（generator）。

对于发送方，需要在数据$D$后附加一个长度为$r$位的R，即得到一个长度为$d + r$位的序列，并且这个序列用模2运算能够被$G$整除。

对于接收方，使用$G$去除接收到的$d + r$位。如果余数不为0，则说明出现了差错。

发送方需要构造的长度为$d + r$位的序列可以通过将数据$D$左移$r$位，并加上$R$得到。由于得到的$d + r$位序列能够被$G$整除，即为$G$的整数倍。

$R$为$D \cdot 2^r$除以$G$的余数：

计算示例

假设$D$ = 101110，$G$ = 1001，那么$r$ = 3，需要在$D$末尾补齐3个0进行除法。

计算得出余数$R$为011，因此发送方需要传输的数据为101110011。

为什么叫“多项式编码”

一个比特串可以看作一个系数只取0或1的多项式：最高位对应最高次幂。例如$D = 101110$对应$x^5 + x^3 + x^2 + x$，$G = 1001$对应$x^3 + 1$。“左移$r$位”就是乘以$x^r$，模2长除法就是多项式除法，只是系数的加减都按异或计算。

CRC能发现哪些差错

设发送的比特为$T$，传输中出错的位置构成差错模式$E$（出错的位为1），接收方收到的就是$T \oplus E$。由于$T$是$G$的倍数：

所以只有当$E$恰好是$G$的倍数时，差错才会漏检。由此可以得到CRC的几条重要性质：

以太网和802.11使用的CRC-32有$r = 32$位，随机差错漏检的概率约为$2^{-32}$，而且长度不超过32的突发差错全部能被发现。CRC的计算可以用移位寄存器和异或门在硬件中高速完成，这也是它被广泛使用的原因之一。