CRC 数学原理：多项式除法与模2运算
要搞懂 CRC，你得先明白一个事儿：CRC 本质上不是算数字，而是算多项式。说白了，就是把一串二进制数据看成是一个多项式的系数，然后用这个多项式去除以一个固定的“生成多项式”，余数就是 CRC 校验值。
我当年刚接触 CRC 时，总觉得这东西很玄。直到有一次用 QSPI 通信，数据总对不上，折腾半天发现是 CRC 计算时加法没按模2来。嗯，从那儿以后，我再也不敢跳过数学原理了。
模2加法与减法——其实就是异或
模2运算和我们平常的十进制运算不太一样。它没有进位，也没有借位。你想想看，加法结果只取最低位：
- 0 + 0 = 0
- 0 + 1 = 1
- 1 + 0 = 1
- 1 + 1 = 0（没有进位！）
这不就是异或（XOR）嘛。模2减法跟加法一模一样，因为 1 - 1 = 0，1 - 0 = 1，0 - 1 = 1（相当于加 1）。所以加法和减法在模2世界里是同一件事。我在项目中习惯用异或门来做 CRC 硬件模块，其实就是利用了这个特性。
模2乘法与除法
模2乘法跟普通二进制乘法类似，但中间结果相加时要用模2加法（即异或）。举个例子：
1011 (x³ + x + 1)
× 1101 (x³ + x² + 1)
--------
1011
0000 (中间结果左移一位)
1011
1011
--------
1111111 (异或累加)
模2除法就更关键了。它其实是 CRC 计算的核心步骤。步骤如下：
- 用被除数的最高位对齐除数的最高位。
- 做模2减法（异或），得到部分余数。
- 将部分余数左移一位，引入被除数的下一位。
- 重复直到所有位都处理完。
注意：每次做减法时，只有当部分余数的最高位是 1，才执行异或；如果是 0，则直接跳过（相当于减 0）。这就是为什么硬件里可以用移位寄存器来实现。
| 运算 | 规则 | 等价运算 |
|---|---|---|
| 模2加法 | 无进位，逐位 XOR | a ⊕ b |
| 模2减法 | 同加法，无借位 | a ⊕ b |
| 模2乘法 | 普通乘法 + XOR 累加 | 多项式乘法 |
| 模2除法 | 长除法，减法用 XOR | 多项式除法 |
多项式除法与 CRC 的关系
把数据看作多项式系数，生成多项式就是除数。做一次模2除法后，得到的余数就是 CRC 码。举个例子，假设数据是 1101（即 x³ + x² + 1），生成多项式是 1011（x³ + x + 1）：
-------- (商不重要)
1011 ) 1101000 (数据左移3位，补3个0)
1011
----
0110
0000
----
1100
1011
----
0111
0000
----
1110
1011
----
0101 → 余数 101 (即 CRC 值)
这里余数 101 就是 CRC-3 校验值。我在写 QSPI 驱动时，经常用这个流程来调试软件 CRC 模块。如果你算出来余数和硬件对不上，八成是补零位数或者生成多项式写反了。
核心要点：整个模2除法过程，每一步的减法都是用异或实现的。硬件实现时，一个移位寄存器 + 几个异或门就能搞定，这也是 CRC 在嵌入式系统中如此流行的原因。
我的一个习惯：在设计 CRC 查表法时，我会先手算一遍小数据的多项式除法，确认生成多项式和补零规则正确。这能省掉后面不少调试时间。
注意：多项式的表示方式有多种。有的资料省略最高次项（如 0x04C11DB7 代表 CRC-32），有的会写全。我在项目中曾因为把多项式高位低位搞反，导致通信双方 CRC 始终不匹配，后来统一用“生成多项式二进制串”才解决问题。
上面这张图把整个 CRC 计算过程串了一遍。数据多项式和生成多项式作为输入，经过模2除法（本质是移位和异或），最后得到固定长度的余数，那就是我们要的 CRC 校验值。我在做 QSPI 驱动时，硬件 CRC 模块就是按这个流程工作的——只是它用寄存器并行处理，速度更快。