数学的优雅：剖开CRC的多项式除法核心

看似复杂的CRC校验，其核心建立在优雅的数学基础之上。本文将为您揭开CRC算法的数学面纱，让您真正理解多项式除法的精妙之处。

模2运算：CRC世界的特殊算术

CRC计算建立在一种特殊的代数系统上—— 模2运算 （Modulo-2 Arithmetic）。这与我们熟悉的十进制算术有很大不同。

模2加法和减法

在模2世界中，加法和减法有一个惊人的特性： 它们其实就是异或（XOR）操作 ！

输入 A	输入 B	结果 (A + B mod 2)
0	0	0
0	1	1
1	0	1
1	1	0

重要特性 ：

1 + 1 = 0（而不是2）
没有进位概念
加法和减法结果相同：A - B = A + B

这种特性非常适合数字电路实现，因为异或门既简单又高效。

模2乘法和除法

模2乘法和除法与我们熟悉的二进制乘除类似，但使用模2加法（即异或）进行计算：

乘法示例 ：

  1101 (被乘数)
×  101 (乘数)
--------11010000
1101
--------
111001 (结果)

关键点 ：乘法通过移位和模2加法完成，没有传统算术中的进位加法。

多项式表示：二进制数据的另一种视角

CRC算法的精妙之处在于它将二进制数据视为多项式。

如何将二进制转换为多项式？

每一位二进制数代表多项式的一项系数（0或1），而位的位置代表x的指数。

示例：

二进制数 1101 转换为多项式：1·x³ + 1·x² + 0·x¹ + 1·x⁰ = x³ + x² + 1
二进制数 1011 转换为多项式：x³ + x + 1

生成多项式：CRC的核心

每个CRC变体都有一个特定的 生成多项式 （Generator Polynomial），它决定了CRC的检错能力和计算方式。

常见CRC标准的生成多项式：

CRC-8: x⁸ + x² + x + 1 (对应二进制: 100000111)
CRC-16: x¹⁶ + x¹⁵ + x² + 1 (对应二进制: 11000000000000101)
CRC-32: x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1 (对应二进制: 1 00000100 11000001 00011101 10110111)

CRC计算过程：一步步分解

现在让我们将模2运算和多项式表示结合起来，看看完整的CRC计算过程。

步骤1：原始数据补零

假设我们要计算数据 1101 的CRC，使用生成多项式 1011（即x³ + x + 1）：

在原始数据末尾添加 n个零 ，其中n是生成多项式的次数（位数-1）
生成多项式 1011 是3次多项式（最高次项是x³），所以添加3个零
原始数据 1101 变为 1101000

步骤2：执行模2除法

现在用生成多项式 1011 除补零后的数据 1101000：

          1110    ← 商（通常丢弃不用）--------
1011 ) 1101000    ← 被除数（补零后的数据）1011       ← 对齐最高位，执行模2减（异或）-----1100      ← 中间结果1011      ← 生成多项式对齐新最高位-----1110     ← 中间结果1011     ← 生成多项式对齐新最高位-----1010    ← 中间结果1011    ← 生成多项式对齐新最高位-----001    ← 余数（这就是CRC值！）

步骤3：得到CRC校验值

除法得到的余数 001 就是我们要求的CRC校验值。由于余数位数应比生成多项式次数少1，这里我们得到3位余数中的最后2位是有效位，但通常我们会保留所有位作为CRC值。

完整CRC码

将原始数据与CRC值组合：1101 + 001 = 1101001

接收方可以使用同样的生成多项式验证这个数据的完整性。

为什么多项式除法能检测错误？

现在我们来解答这个关键问题：为什么这种方法能有效检测错误？

数学原理

发送方 ：计算数据D(x)除以G(x)的余数R(x)，发送[D(x) + R(x)]
接收方 ：用G(x)除接收到的数据[D(x) + R(x)]

如果传输没有错误：

[D(x) + R(x)] / G(x) = D(x)/G(x) + R(x)/G(x)
由于R(x)是D(x)/G(x)的余数，所以D(x) = Q(x)·G(x) + R(x)
因此[D(x) + R(x)] = Q(x)·G(x) + R(x) + R(x) = Q(x)·G(x) + 0
因为R(x) + R(x) = 0（模2加法）
所以接收方除法余数为0，表明数据正确

如果传输有错误：

接收到的数据变为[D(x) + R(x) + E(x)]，其中E(x)是错误多项式
除以G(x)得到的余数不为0（除非E(x)恰好能被G(x)整除，这种情况概率很低）

检错能力分析

CRC能够检测：

所有单比特错误 ：E(x) = xⁱ，不能被G(x)整除（因为G(x)至少有2项）
所有双比特错误 ：E(x) = xⁱ + xʲ = xʲ(xⁱ⁻ʲ + 1)，只要G(x)选择适当
任何奇数个错误 ：如果G(x)包含因子(x+1)
大多数突发错误 ：特别是长度小于等于生成多项式次数的突发错误

实际示例：手动计算CRC-4

让我们用一个更完整的例子巩固理解：

输入数据 ：11010111 (8 bits)
生成多项式 ：10011 (x⁴ + x + 1, CRC-4)

补零：生成多项式次数为4，补4个零 → 110101110000
模2除法 ：

逐位计算过程：110101110000 ÷ 10011第一步： 11010 ⊕ 10011 = 10011
第二步： 10011 ⊕ 10011 = 00000
第三步： 00001 ⊕ 00000 = 00001
第四步： 00001 ⊕ 00000 = 00001
第五步： 00001 ⊕ 00000 = 00001
第六步： 00001 ⊕ 00000 = 00001
第七步： 00000 ⊕ 00000 = 00000
第八步： 00000 ⊕ 00000 = 00000余数：0001 → CRC值 = `0001`