**把数据看作一个二进制多项式,用一个约定好的生成多项式对它进行“模 2 除法”,然后将余数附加到数据后面作为校验码。**接收方收到数据后用相同的生成多项式再除一次,如果余数为 0,说明数据没有错误。
生成多项式:G
- 有 r+1 比特,最高项是 r 次
假设有:
- 数据:
D
(例如:11010011101100) - 生成多项式(即除数):
G
(例如:1011) ➜ 通常约定为某个固定的 k+1 位二进制数,对应多项式的系数
步骤如下
- 扩展数据:
在数据
D
末尾补上k
个 0(k 为 G 的位数 - 1),得到D0
- 模 2 除法:
用
D0
除以G
,得到余数R
注意这里的除法是 模 2 除法,也就是不进位、只用异或操作 - 生成 CRC 校验码:
把余数
R
附加到原始数据D
后面,形成发送的数据帧 - 接收方校验:
收到数据帧后,用同样的
G
再除一遍,检查余数是否为 0
CRC 可以检测的错误类型包括:
- ✅ 单比特错误(1 个比特反转)
- ✅ 双比特错误(2 个位翻转,间距合适)
- ✅ 奇数个比特错误(只要生成多项式包含
(x+1)
因子) - ✅ 突发错误(burst error):指多个连续位出错
CRC 可以保证检测出长度 ≤ 生成多项式长度(k+1)的所有突发错误
通常使用的 CRC-32、CRC-16 等多项式设计良好,可以检测:
- 所有单比特错误
- 所有两位错误
- 所有小范围突发错误(长度 ≤ 32 或 16)
- 大概率地检测长突发错误(虽然不能保证)