第2章 CRC数学基础：模2除法、多项式表示

各位，要真正搞懂CRC，数学基础绕不开。说白了，CRC的底层就两个东西：模2除法和多项式表示。你别怕数学，我当年学的时候也觉得头大，后来发现这东西其实比普通算术还简单——只需要会“按位异或”就行。

2.1 模2除法到底是怎么算的？

先问一个问题：普通除法里，我们做减法要借位。但模2除法呢？不借位，只异或。你想想看，这是不是有点像二进制加法不进位？没错，模2加法和减法其实就是同一个操作——异或（XOR）。

我用一个例子带你走一遍。假设被除数 101010，除数 1101（4位）。我们做模2除法求余数：

       11001   ← 商我们不关心
     _______
1101) 101010
     1101    ← 第一轮：对齐最高位，异或
     ----
      1111   ← 结果
      1101   ← 第二轮：再对齐
      ----
       0100  ← 注意这里高位0要保留！实际是100
       0000  ← 除数1101比0100大，商这一位是0
       ----
        1000
        1101  ← ？不对，已经不够了。其实要补位
        实际上最终余数是 001

等一下，这个写法容易乱。我更习惯用表格步骤来展示，看下表：

我承认看表格也可能懵。其实模2除法就跟我们算CRC一样，寄存器左移，移一位异或一次。我在项目中曾经手算过一个32位的CRC值，算到半夜才发现自己少移了一位……后来我都是用程序验证的。

给你一个口诀：位数对齐，高位异或，结果截短，重复直到不够除。

2.2 怎么用多项式来表示这些二进制数？

二进制数和多项式其实是一一对应的。假设我们有二进制数 1101，从最高位到最低位分别是第3、2、1、0位（注意从0开始）。那么它对应的多项式就是：

1·x³ + 1·x² + 0·x¹ + 1·x⁰ = x³ + x² + 1

你看，哪一位是1，那个幂次的系数就是1；是0，系数就是0。很好理解吧？说白了，就是把位权从“2的n次方”换成了“x的n次方”。

为什么要这么干？因为模2多项式的加法和乘法，自动满足异或运算的规律。比如：

(x³ + x² + 1) + (x² + x) = x³ + (x² + x²) + x + 1 = x³ + 0 + x + 1 = x³ + x + 1

注意：x² + x² 系数是1+1，在模2下就是0，所以这两项直接消失。这不是和异或一模一样吗？

下面这张SVG图帮你理清这个对应关系：

2.3 常见的生成多项式长什么样？

工程上常用的生成多项式都标准化了。我列一个表，这些都是我在实际项目中用过的：

注意：多项式的最高次项系数总是1，所以在二进制表示中最高位固定为1，正好对应位宽。比如CRC-8需要9位二进制数来表示（因为最高次x⁸需要系数位）。

2.4 多项式表示在CRC计算中的优势

用多项式来描述CRC，最大的好处是数学上严谨。你可以把整个通信链路抽象成一个多项式除法系统。比如：

• 发送数据 = M(x) · x^n（n是生成多项式的次数，相当于在数据末尾补n个0）
• CRC校验码 = [M(x) · x^n] mod G(x)
• 发送帧 = M(x) · x^n + CRC
• 接收端检查：(M(x) · x^n + CRC) mod G(x) 是否等于0

这些公式看起来很抽象？其实你只要理解一件事：CRC本质上就是求余数。多项式只是给这个余数找了个“代数学名字”，方便我们证明它的检错能力。

我在做车载以太网协议栈时，需要证明CRC-32能够100%检测出≤32位的突发错误。用多项式理论推导一遍，心里就踏实了。否则光靠猜，谁敢往车上用？