CRC 算法核心：多项式、异或与校验位计算
咱们做网络通信的，天天跟比特流打交道。数据在线上跑，难免会串扰、丢位。CRC 就是用来揪出这些错误的。说白了，它就是个除法 – 但不是什么普通的除法，而是用“多项式”做的除法。
多项式 – CRC 的“DNA”
你可能会问：好好一个除法，怎么扯上多项式了？
其实很简单。发送方把数据看成一个大整数，双方约定好一个“除数”（也就是生成多项式）。发送方做除法后，把余数附在数据后面发过去。接收方收到后用同样的除数再做一次除法，如果余数为零，数据大概率没问题。
这个“除数”长啥样？举个例子：CRC-8 的一个常用多项式是 x⁸ + x² + x + 1。在计算机眼里，它就是一串比特位。怎么映射的？
- x⁸ 代表第 8 位是 1
- x² 代表第 2 位是 1
- x¹ 代表第 1 位是 1
- x⁰ 代表第 0 位是 1
核心转换规则：多项式指数对应比特位置，有这一项就填 1，没有就填 0。
所以 x⁸ + x² + x + 1 转换为二进制就是：1 0000 0111（从 x⁸ 到 x⁰，共 9 位）。
我个人习惯把多项式看成“战斗模式”。不同的多项式擅长抓不同类型的错误。比如 CRC-32 在以太网里用得最多，因为它对突发错误的检测能力很强。
异或运算 – CRC 的“基石”
CRC 里面没有进位，没有借位。你只需要一个操作：异或（XOR）。
异或的规则很简单：相同为 0，不同为 1。
| 输入 A | 输入 B | 输出 (A XOR B) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
为什么只能用异或？因为多项式除法本质上就是模 2 除法。加法不进位，减法不借位，异或正好满足这个要求。
你看硬件实现的时候，就是一排异或门。我在项目里见过有人看不懂 LFSR（线性反馈移位寄存器），其实它就是个异或门的组合，一层层往回反馈而已。
校验位计算 – 动手算一遍
光说理论太虚了。我们来算一个实际的例子。
假设：
- 原始数据： 1101 (二进制)
- 生成多项式： 1011 (对应 x³ + x + 1)
- CRC 宽度： 3 位（因为多项式最高次是 x³）
步骤分解
- 数据补零： 在原始数据后面补上 CRC 宽度个 0。这里补 3 个 0 →
1101 000。 - 开始除法： 用补零后的数据对多项式
1011做模 2 除法（只用异或）。 - 找到余数： 做完整除法后，余数就是 CRC 校验值。
我们手动模拟一下过程：
_______________
1011 ) 1 1 0 1 0 0 0
1 0 1 1 ← 第一次对齐，异或
------
0 1 1 0 0 0 ← 落下一位
1 0 1 1 ← 第二次对齐，异或
-----
0 1 1 1 0 ← 落下一位
1 0 1 1 ← 第三次对齐，异或
-----
0 1 0 1 ← 余数只有 3 位？
不，最高位是 x²，所以补成 3 位：101余数位数不够怎么办？ 左侧补 0。上面余数 101 位于 x² 位，本身已经是 3 位，不需要补。
如果余数是 01，则要补成 001。
所以，发送方发出去的数据是：1101 101（原始数据 + 余数）。
接收方收到后，会用 1101 101 去除以 1011。如果余数还是 0，数据就是干净的。
常见 CRC 多项式一览
不同的协议用不同的多项式。我整理了一个表，你可以对照看看：
| 名称 | 多项式 | 二进制表示 | 常见应用 |
|---|---|---|---|
| CRC-8 | x⁸ + x² + x + 1 | 1 0000 0111 | 1-Wire 总线 |
| CRC-16-IBM | x¹⁶ + x¹⁵ + x² + 1 | 1 1000 0000 0000 0101 | Modbus |
| CRC-32 | x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1 | 1000 0010 0110 0000 1000 1110 1101 1011 | Ethernet, ZIP |
避坑： 多项式选择不是随便来的。宽多项式不一定比窄的强。我见过有人为了省资源选了个窄多项式，结果误码率高的吓人。选择多项式要依赖于你信道的错误模型。
一句话总结核心逻辑
嗯，整个 CRC 的核心逻辑就这么简单。发送方算个余数附在后面，接收方再算一次看余数是否为 0。没有复杂的数学，就是移位加异或。
我个人建议：刚开始接触时别急着看硬件实现，先在纸上算几笔，把“多项式等于二进制”这个映射刻在脑子里。后面做协议分析时你会发现，这东西比打表好理解多了。