📚 课程目录第2章 CRC工作原理

CRC工作原理：多项式除法与校验码生成过程

说实话，刚入行那会儿，我一直以为CRC（循环冗余校验）是什么黑魔法。后来一看，说白了就是二进制版的“带余除法”。你想想看，我们小时候做除法——被除数除以除数，得到商和余数。CRC干的也是这事，只不过换成二进制多项式。

我记得第一次在项目里手撸CRC生成逻辑，被一个多项式搞了半天。后来吃了亏，才老老实实把模2除法（也就是异或运算）的细节摸透了。今天咱们就把它掰开揉碎讲清楚。

2.1 多项式表示法——从比特到代数

CRC的核心是多项式。这里的多项式不是初中数学那个，而是二进制系数多项式。系数只能是0或1，运算时加法不进位（其实就是异或）。

举个例子：数据位 1101 对应多项式：1·x³ + 1·x² + 0·x¹ + 1·x⁰ = x³ + x² + 1。

为什么这么搞？因为用多项式形式，可以套用现成的代数工具——比如可整除性、不可约多项式（有点类似质数的概念）。

个人小习惯：我一般把多项式写成二进制掩码形式。比如CRC-8常用多项式 x⁸ + x² + x + 1，对应二进制 1 0000 0111（低8位有效，最高位隐含的1不写）。这样在纸上推演快很多。

标准算法	多项式（十六进制）	二进制（含隐含高位）	常见用途
CRC-8	0x07	1 0000 0111	传感器、简单数据包
CRC-16-CCITT	0x1021	1 0001 0000 0010 0001	Modbus、XMODEM
CRC-32	0x04C11DB7	1 0000 0100 1100 0001 0001 1101 1011 0111	以太网、ZIP、PNG

2.2 模2除法——没有借位的二进制除法

CRC的除法叫“模2除法”，也叫“多项式长除”。它的特点很反直觉：

减法 = 异或：没有借位，1-1=0，0-1=1，1-0=1，0-0=0。其实就是按位异或。
商只看最高位：当被除数当前剩余的最高位是1，商的这一位就写1，然后做异或；否则写0，然后直接拉下一位。

我做测试那会儿，经常用这种方法手算然后跟硬件CRC结果比对。有一次焊好板子后通信总报错，我拿笔算了半天，发现是驱动里多项式高低位顺序写反了……这是后话，先看个具体步骤。

实操演练：4位数据 + CRC-3（多项式x³ + x + 1）

假设：数据 = 1011（二进制），多项式 = 1011（二进制，对应x³ + x + 1，最高位隐含的1也写出方便对齐），生成4位CRC校验码（R=3）。

步骤一：数据左移3位，后面补0 → 1011 000。

步骤二：做模2除法：

        1010  (商，不保存)
       ---------
1011 ) 1011 000
       1011    (异或，结果最高位1，拉下一位)
       ----
        0000 0   (最高位0，商0，拉下一位)
        0000 0
        -----
         000 00  (最高位0，商0，拉下一位)
         000 00
         -----
           0 000 (最高位0，做到最后，余数 = 000)

余数 = 000？嗯，这例子纯属巧合，很多情况下余数不为0。我们再换一组：数据 = 1101，多项式不变，

        1001
       ---------
1011 ) 1101 000
       1011
       ----
        110 0
        101 1
        -----
         11 10
         10 11
         -----
          1 01  (最终余数 = 101)

余数 = 101，这就是CRC校验码。发送时把 101 附加在数据后面：1101 101。接收端用同一个多项式去除整个码字，如果余数为0，表示没有错误（或错误概率极低）。

  关键理解：CRC的核心就是利用多项式除法做一个“指纹”。别人用同样的多项式再算一次，看指纹是否匹配。不匹配 → 传输过程肯定动了手脚。

2.3 发送与接收的完整流程

我把这套流程画成一张图，你会看得更清楚。

2.4 几个你可能会踩的坑

讲完通用流程，聊聊我实际调试中遇到的几个问题。这些东西你不亲自动手很难注意到。

多项式高位对齐问题：有些文档写的多项式是 0x07，但实际硬件实现时，隐含的最高位（x⁸）必须显式参与异或。我见过有人直接用 0x07 做8位CRC，结果永远算不对。
初始值与结果异或：很多标准（如CRC-32）约定初始值不全是0，结果还要跟一个异或值做最终处理。如果你完全照搬手算的模2除法，跟标准库的结果对不上。我第一次调的时候，硬是对比了两天才发现差别。
字节序（MSB/LSB优先）：数据是按最高位先送还是最低位先送？不同协议不一样。比如Modbus用LSB优先，而以太网用MSB优先。选错了，CRC就全乱了。

我曾经踩过的坑：有一次做UDS诊断的CRC-16校验，多项式、初始值、异或值都对，但就是校验不过。后来发现是硬件把输入字节的比特翻转了（大端小端没对齐）。改了一个位序反转配置项，立马好了。所以CRC不只是数学问题，还是字节序问题。

2.5 硬件加速 vs 软件查表

真实项目里很少有人用长除逻辑逐位算，太慢了。常见两种方式：

方式	原理	速度	适用场景
硬件CRC单元	专用移位寄存器 + 异或门	一个时钟周期出结果	高速接口（以太网、PCIe）
软件查表法	预计算256个余数表，每次查一个字节	每个字节几个时钟周期	单片机、低速协议

我个人习惯：只要芯片有硬件CRC外设（比如STM32），直接用硬件。省心、省电、省时间。但调试阶段，我会在PC上写一个软件查表版做对比，用来确认硬件配置是否正确。

// CRC-8 查表法示例（多项式 0x07）
uint8_t crc8_table[256];
void crc8_init_table(void) {
    for (int i = 0; i < 256; i++) {
        uint8_t crc = i;
        for (int j = 0; j < 8; j++) {
            if (crc & 0x80)
                crc = (crc << 1) ^ 0x07;
            else
                crc <<= 1;
        }
        crc8_table[i] = crc;
    }
}
uint8_t crc8_compute(uint8_t *data, uint32_t len) {
    uint8_t crc = 0;
    for (uint32_t i = 0; i < len; i++) {
        crc = crc8_table[crc ^ data[i]];
    }
    return crc;
}

提示：查表法的表可以用Python提前算好，然后直接复制成C数组。不要在单片机上浪费CPU做初始化运算。

2.6 小结

CRC本质上就是二进制多项式的模2除法。你弄懂那个“异或代替减法”的规则，剩下的就是多项式选择、字节序、初始值处理这些工程细节。我建议你现在就拿笔算一个：数据1010，多项式1101，手动算出CRC码，再写个代码验证。两者一致了，信心自然就有了。