计算机网络：CRC

Cyclic Redundancy Check

在 n 位的数据后添上 k 位的冗余数据构成一帧发送。用于 error detection。

例子：

• 假设 A 要传给 B 的数据为 M = 10100110
• 那么在 M 末尾添上 k = 3 个 0 得到 M’ = 10100110000
• 另外我们有人为规定的 C = 1101 (degree k = 3)
• 然后将 M’ 除以 C 可得余数 R = 011 (k bit remainder)
• A 把 R 加到 M 的末尾也就是 M’ + R = 10100110011 发送至 B
• B 接收到数据后将其除以 C = 1101 得到的余数如果为零则校验成功

注意，所用的除法为“模二除法”，不借位，而是异或。

如上面的例子中的除法，应该是这样：

All single-bit errors can be detected as long as C(x)’s x^k and x⁰ terms have non-zero coefficients.

Any odd number of errors can be detected as long as C(x) contains the factor (x + 1).

Any burst error (i.e., sequence of consecutive error bits) for which the length of the burst is less than or equal to k bits can be detected.

Most burst errors of larger than k bits can also be detected.

除了上面例子里用的 CRC-4，还有 CRC-8、CRC-10、CRC-12、CRC-16 以及 ethernet 使用的 CRC-32。