**把数据看作一个二进制多项式,用一个约定好的生成多项式对它进行“模 2 除法”,然后将余数附加到数据后面作为校验码。**接收方收到数据后用相同的生成多项式再除一次,如果余数为 0,说明数据没有错误。

生成多项式:G

  • 有 r+1 比特,最高项是 r 次

假设有:

  • 数据:D(例如:11010011101100)
  • 生成多项式(即除数):G(例如:1011) ➜ 通常约定为某个固定的 k+1 位二进制数,对应多项式的系数

步骤如下

  1. 扩展数据: 在数据 D 末尾补上 k 个 0(k 为 G 的位数 - 1),得到 D0
  2. 模 2 除法:D0 除以 G,得到余数 R 注意这里的除法是 模 2 除法,也就是不进位、只用异或操作
  3. 生成 CRC 校验码: 把余数 R 附加到原始数据 D 后面,形成发送的数据帧
  4. 接收方校验: 收到数据帧后,用同样的 G 再除一遍,检查余数是否为 0

CRC 可以检测的错误类型包括:

  1. 单比特错误(1 个比特反转)
  2. 双比特错误(2 个位翻转,间距合适)
  3. 奇数个比特错误(只要生成多项式包含 (x+1) 因子)
  4. 突发错误(burst error):指多个连续位出错

CRC 可以保证检测出长度 ≤ 生成多项式长度(k+1)的所有突发错误

通常使用的 CRC-32、CRC-16 等多项式设计良好,可以检测:

  • 所有单比特错误
  • 所有两位错误
  • 所有小范围突发错误(长度 ≤ 32 或 16)
  • 大概率地检测长突发错误(虽然不能保证)