第二章 CRC数学原理：模2除法、生成多项式、余数与校验码
咱们搞通信的，整天和CRC打交道。你说它到底是个啥？说白了，CRC就是一套模2除法的游戏规则。我当年第一次接触的时候也觉得玄乎，后来自己动手算了几遍，发现其实挺朴素的。
2.1 模2除法：不是你想的那种除法
普通的算术除法你熟：10÷3＝3余1，有进位有借位。模2除法不一样——它没有进位，也没有借位。你想想看，那种感觉就好像只关心异或结果是不是0。
规则很简单：
- 0－0 ＝ 0，1－1 ＝ 0，0－1 ＝ 1，1－0 ＝ 1 —— 和异或一模一样
- 除数与被除数的位对齐后，执行按位异或，然后下移得到新余数
- 整个过程不许借位，每步只异或，绝不进一
举个例子你就秒懂了。咱们被除数是 110101，生成多项式取 101（二进制）。按模2除法跑一遍：
110101
除数 101)
101
---
111
101
---
101
101
---
00 ← 这就是最后的余数注意看，当高位是0时，我们直接跳过，等于补了一个0去异或。我在项目里第一次手算时，直接写着 101 去减 111 得到 010，然后拉下一位 … 后来才意识到，模2除法里 1 XOR 1 = 0 正好没有借位陷阱，但很容易漏掉对齐规则。嗯，这里要留个心。
2.2 生成多项式：选得好，纠错就赢在起跑线
生成多项式就是做除法的那个“除数”。数学上写成 G(x) = x^n + ... + 1 的形式，n 是校验位数。比如我们最常说的 CRC-16，生成多项式是 x^16 + x^15 + x^2 + 1，二进制就是 11000000000000101。
常用生成多项式一览（这张表你最好记一下，面试也可能问）：
| 名称 | 生成多项式（二进制） | 校验位数 | 应用场景 |
|---|---|---|---|
| CRC-8 | 100000111 | 8 | 传感器、1-Wire |
| CRC-16-CCITT | 10001000000100001 | 16 | XMODEM、蓝牙 |
| CRC-32 | 100000100110000010001110110110111 | 32 | 以太网、ZIP、PNG |
| CRC-64-ECMA | 1100111001000001101...（共65位） | 64 | 大型文件校验、存储 |
你有没有发现，这些多项式都以1结尾（且高位也是1）。为什么？因为如果 x^0 系数是0，那多项式其实能整除一个 x，就会漏检一些奇数位错误。我踩过一个坑：某次产品用了自定义的7位多项式，结果误码率高了30%，换成标准CRC-16后瞬间正常。所以，别自己发明多项式，除非你非常清楚自己在做什么。
- 多项式的最高位和最低位都是1
- 对于任意长度的突发错误，多项式对应的码字必须是不可约的
- 工程上优先用国际标准多项式，别求新求异
2.3 余数与校验码：一对儿分不开的兄弟
模2除法做完后，最后剩下的那个余数，就是CRC校验码（也叫FCS，Frame Check Sequence）。发送的时候，把这个余数附加到原始数据后面一起发出去。接收端收到后，用同样的生成多项式再做一次模2除法，如果余数为0，数据大概率没错，否则就标记重传。
举个例子：数据 110101 用多项式 101 做除法，得到余数 00（我们前面算的）。那发出去的就是 11010100。接收端拿 11010100 除以 101，余数如果再次是 00，就认为OK。
你可能会问：万一出错了呢？余数还可能是0吗？理论上有可能，但概率极低。所以CRC才叫“循环冗余校验”，不是“正确校验”。
2.4 整个流程：用一张图讲清楚
下面是我画的CRC计算与校验流程图，从左到右展示了发送端和接收端的动作。不复杂，你一看就懂。
你看，发送端干三件事：拿原始数据 + 多项式 → 模2除法出余数 → 附加余数。接收端也三件事：用同样的多项式再做一遍除法 → 检查余数 → 非零就报错。整个过程本质就是校验“能不能整除”。
2.5 几个容易混淆的点
- 余数长度始终等于多项式次数 —— 比如CRC-16的余数一定是16位。如果不够，高位补0。
- 发送时余数要取反吗？ 有些标准（如CRC-32）要求对余数取反后再附加，目的是避免全0数据产生全0校验码。你查标准文档时留意这个细节。
- 硬件实现 vs 软件实现： 硬件通常用LFSR（线性反馈移位寄存器）一步到位，软件用查表法加速。但数学原理都是模2除法，不变。
我记得刚开始做FEC调优时，有个老哥说“你看懂CRC那点事，后面纠错才能玩得转”。当时不当回事，后来查表查多了才信——模2除法和多项式选型是CRC的根基，根不稳，上面盖什么房子都白搭。嗯，就这样，这一章先到这。