CRC 循环冗余校验
互动教程 — 从零理解数据校验的核心算法
0 开始前：你需要知道的
如果你已经熟悉二进制，可以跳过这一节。
什么是二进制？
我们日常用十进制（0-9），但计算机只认识二进制——只有 0 和 1 两个数字。每个 0 或 1 叫做一个 bit（比特/位）。
十进制: 0 1 2 3 4 5 6 7
二进制: 000 001 010 011 100 101 110 111
什么是"运算"？
对数字做一些规则操作。比如加法是运算，XOR 也是一种运算——下面马上会讲。
什么是"幂次"？
就是 x 的几次方。x¹ = x，x² = x×x，x³ = x×x×x。在 CRC 里，幂次对应二进制中从右往左数的位置（从0开始）。
x⁴ + x + 1
对应二进制（从高位到低位）：
位置: 4 3 2 1 0
1 0 0 1 1 ← 有这项就写1，没有就写0
1 CRC 是什么？
CRC（Cyclic Redundancy Check）是一种错误检测技术。发送方在数据后面附加一段校验码，接收方通过同样的计算来判断数据是否在传输中出错。
类比：想象你在寄快递。你把物品（数据）放进箱子，然后用一把特殊的锁（CRC 算法）锁上。收件人收到后，用同一把锁验证——如果箱子被打开过或物品被调换，锁的校验就会不匹配。
核心思想很简单：
数据 ÷ 约定好的除数 = 商 ... 余数（就是 CRC 校验码）
但这个"除法"不是普通除法，而是用 XOR（异或）运算代替减法的特殊除法。下面两节会分别讲 XOR 和这种特殊除法。
2 先搞懂 XOR（异或）
XOR 是 CRC 的基础运算。规则极其简单：相同为0，不同为1。
| A | B | A XOR B |
|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
对多bit数据，逐位做 XOR：
1 1 0 1
XOR 1 0 1 1
─────────
0 1 1 0
逐位看：1 XOR 1 = 0，1 XOR 0 = 1，0 XOR 1 = 1，1 XOR 1 = 0
记住 XOR 的一个关键特性：
A XOR B XOR B = A（同一个数 XOR 两次，等于没 XOR）
这个特性后面验证数据时会用到。
3 什么是"模2除法"？
你小时候学过的长除法是这样的：
普通除法: 110101 ÷ 10011
每一步用"减法"消掉最高位，有借位等问题...
模2除法和普通长除法几乎一样，唯一的区别：用 XOR 代替减法。
| 普通除法 | 模2除法（CRC用） |
|---|
| 每一步操作 | 减法 | XOR |
| 借位/进位 | 有 | 没有！ |
| 只看最高位 | 需要比较大小 | 最高位是1就对上去 |
模2除法的规则（只有3条）：
规则1 看被除数当前最高位，如果是 1，就把除数对齐到这里
规则2 对齐后，逐位做 XOR
规则3 XOR 结果的最高位一定是 0（因为 1 XOR 1 = 0），然后往右看下一个 1，重复
一句话总结：看到1就对上去XOR，XOR完最高位变0，往右移找下一个1，直到处理完所有位。剩下的就是余数。
4 生成多项式详解
多项式就是模2除法里的除数。它决定了"用什么去除"。
多项式的两种写法：
写法1：代数形式
x⁴ + x + 1
意思是：第4位、第1位、第0位是1，其余是0。
写法2：二进制形式（实际计算用这个）
幂次: 4 3 2 1 0
系数: 1 0 0 1 1 → 10011
转换规则（记住这3点就够了）：
• 最高幂次 = CRC的位数（x⁴ → CRC-4 → 余数4位）
• 二进制位数 = 幂次 + 1（x⁴ → 5位二进制除数）
• 代数式里有的幂次 → 对应位写1，没有 → 写0
常见标准多项式：
| 名称 | 代数形式 | 二进制 | 应用场景 |
|---|
| CRC-4-ITU | x⁴ + x + 1 | 10011 | 电信 |
| CRC-8 | x⁸ + x² + x + 1 | 100000111 | 蓝牙、I2C |
| CRC-16-USB | x¹⁶ + x¹⁵ + x² + 1 | 11000000000000101 | USB |
| CRC-32 | x³² + x²⁶ + ... + 1 | (很长) | 以太网、ZIP、PNG |
实际开发中怎么选？
你不需要自己发明多项式，查规范就行：
- 通信协议：查协议文档（如USB规范里写了用CRC-5/16）
- 文件格式：查格式文档（如PNG规范里写了用CRC-32）
- 自己玩：数据短就用 CRC-4/8，数据长就用 CRC-16/32
互动：多项式转换器
输入幂次（如 4,1,0 表示 x⁴+x¹+x⁰），看对应的二进制：
5 完整手算示例
发送数据 110101，用 CRC-4 多项式 10011（x⁴+x+1）。
第1步 数据末尾补 4 个 0（CRC-4 → 补4位）
110101 → 1101010000
第2步 做模2除法（下面逐步展示）
10011)1101010000 ← 被除数（数据+补零）
10011 ← 第1位是1，对上去 XOR
─────
10010 ← XOR结果: 11010 XOR 10011 = 01001，去掉前导0 → 1001
10011 ← 当前最高位是1，再对上去 XOR
─────
00011 ← XOR结果: 10010 XOR 10011 = 00001 → 1
11 ← 前面都是0，跳过，直到看到1
──
... ← 继续，直到处理完所有位
最终余数: ???? ← 最后4位就是CRC校验码
上面只是示意。下面是真正的逐步计算（和互动计算器结果一致）：
被除数: 1 1 0 1 0 1 0 0 0 0 除数: 10011
10011 ← 位置0: 看到1，XOR
───────────────────
0100110000 ← 结果，前导0跳过
10011 ← 位置1: 看到1，XOR
──────────────────
000000000 ← 结果全是0！
后面全是0，不用再除了。
余数 = 0000
等等，余数是 0000？
是的，对于数据 110101 和多项式 10011，余数恰好是 0000。这不代表算法有问题——只是这组数据碰巧"整除"了。换一个数据试试，比如 101101，你就会得到非零余数。去下面的互动计算器试试吧！
第3步 拼接发送
最终发送: 110101 + 0000 = 1101010000
接收方收到后，用同样的多项式去除，如果余数为0就说明数据没问题。
6 动手试试！
输入数据和多项式，看 CRC 是怎么一步步算出来的。
7 验证：点击翻转位来模拟传输错误
下面是上一步算出的完整数据。点击任意一个 bit 可以翻转它（0变1，1变0），模拟传输中出错：
■ 原始数据
■ CRC校验码
■ 被翻转的位（已出错）
试试看：
1. 先点"验证数据" → 余数为0，通过
2. 点击翻转任意一个 bit → 再验证 → 余数不为0，检测到错误！
3. 翻转两个 bit → 验证 → 有些多项式也能检测到！
4. 思考：有没有翻转后余数还是0的情况？（这就是为什么需要选择好的多项式）
8 总结 & 实际应用
回顾整个流程：
发送方: 数据 ──→ 补零 ──→ 模2除法 ──→ 余数(CRC) ──→ 数据+CRC 发出去
│
↓
接收方: 收到数据+CRC ──→ 用同样的多项式做模2除法 ──→ 余数=0? 通过!
──→ 余数≠0? 出错了!
实际应用中的 CRC：
| 场景 | 常用多项式 | CRC 位数 |
|---|
| 以太网 | CRC-32 | 32 |
| ZIP / PNG | CRC-32 | 32 |
| USB | CRC-5 / CRC-16 | 5 / 16 |
| 串口通信 | CRC-16-MODBUS | 16 |
为什么 CRC 能检测错误？
因为合法的"数据+CRC"组合一定能被多项式整除（余数为0）。传输中任何一位出错，接收方再除就会有余数。不同多项式的检测能力不同——位数越高，能检测的错误越多。CRC-32 能检测出 99.99% 以上的错误。