## CRC 算法数学基础

多项式除法、模2运算与生成多项式

说实话，很多工程师做CRC调试时，上来就查表、调库。一旦出问题，数学原理就成了最大的盲区。我自己带团队做通信协议栈时，遇到过整整两周定位不了CRC错——最后发现，连模2除法和多项式除法的根本区别都没搞清楚。

这一章，咱们就把CRC的数学根子刨出来。不需要多深，但一定要准。

---

模2运算：CRC的算术基础

CRC加减运算，用的是模2加减。听起来玄乎？其实就是异或。

举个例子：

• 1011 + 1101 = 0110（模2加法）
• 1011 - 1101 = 0110（模2减法，结果相同）

你想想看，模2加法里，1+1=0，没有进位。1+0=1，0+0=0。这个特性和硬件电路的异或门完全对应，所以CRC特别适合用FPGA或ASIC实现。

咱们再看模2乘法和除法：

运算	普通算术结果	模2运算结果	备注
1 + 1	2	0	就是异或
1 + 0	1	1	无变化
1 × 1	1	1	和普通乘法一致
1 × 0	0	0	乘法规则不变

多项式表示：把数据变成数学对象

为什么CRC叫循环冗余校验？因为它把二进制数据看成多项式。

一个二进制串 1011，可以映射成多项式：

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

明白了吧？二进制数中第 n 位对应多项式中 xⁿ 的系数。系数只能是0或1——这就是模2域里的元素。

为什么要用多项式表示？因为多项式操作的数学性质好。移位操作对应乘以 x 或除以 x，这正是硬件实现时最擅长的。

---

生成多项式：CRC的灵魂

每个CRC算法都有个生成多项式，简称 G(x)。它是通信双方约定好的、固定不变的多项式。

常见生成多项式举例：

CRC标准	二进制表示（高位省略）	多项式
CRC-8	100011101	x⁸ + x⁴ + x³ + x² + 1
CRC-16-IBM	1000000000000101	x¹⁶ + x¹⁵ + x² + 1
CRC-32	100000100110000010001110110110111	x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1

我建议你记住一个原则：生成多项式的次数决定校验比特数。CRC-8生成多项式次数为8，校验码也是8位；CRC-32次数32，校验码32位。

多项式除法：CRC计算的核心操作

CRC计算的核心，就是用待发送数据对应的多项式 M(x)，除以生成多项式 G(x)，取余数作为校验码。

具体步骤：

1. 将数据 M(x) 左移 r 位（r = G(x) 的次数），即乘以 xʳ
2. 用 xʳ·M(x) 除以 G(x)，做模2除法
3. 余数 R(x) 就是CRC校验码
4. CRC编码 = M(x)·xʳ + R(x)

下面是个手工计算示例：

待发送数据：1101011011（10位）
生成多项式：10011（5位，次数4）

第一步：数据左移4位 → 11010110110000
第二步：模2除法
         1100001010（商）
    ──────────────
10011 ) 11010110110000
        10011
        ─────
         10011
         10011
         ─────
          00001  （余数前5位全是0，下一步用下一数据位）
          00000
          ─────
           00011
           00000
           ─────
            00110
            00000
            ─────
             01100
             00000
             ─────
              11000
              10011
              ─────
               10110
               10011
               ─────
                0101 ← 最终余数

第三步：CRC校验码 = 0101（4位）
最终发送码字：1101011011 0101

我自己带新人时，最常强调的就是这个除法。手动演算一次，胜过看十遍理论。

下面是用Python实现的多项式除法函数：

def crc_remainder(data, generator):
    """
    data: 二进制字符串，如 '1101011011'
    generator: 二进制字符串，如 '10011'
    返回：余数（二进制字符串）
    """
    data_len = len(data)
    gen_len = len(generator)
    # 左移 r 位（补0）
    dividend = data + '0' * (gen_len - 1)
    dividend = list(dividend)
    
    for i in range(data_len):
        if dividend[i] == '1':
            for j in range(gen_len):
                dividend[i + j] = str(int(dividend[i + j]) ^ int(generator[j]))
    
    remainder = ''.join(dividend[-(gen_len - 1):])
    return remainder

# 使用示例
print(crc_remainder('1101011011', '10011'))
# 输出：0101

嗯，这里要注意：实际工程中，很多CRC实现会使用查表法、反射法等手段优化速度，但数学原理不变。

知识体系结构图

咱们把这一章的核心逻辑画成一张图，方便你回顾：

---

本章核心要点

• 模2加减就是异或，是CRC的算术基础
• 多项式表示将二进制数据转化为数学形式，便于移位和除法运算
• 生成多项式是双方约定，其次数决定了校验码位数
• 多项式除法取余数，得到CRC校验码