目录
CRC(循环冗余校验)基本概念
1. 核心定位
2. 两个核心概念
① 信息位（原始数据）
② 生成多项式 G(x)
CRC 最关键：模 2 除法
两条核心规则
关于CRC码的所有可能疑问
为什么要用多项式这种麻烦写法
CRC码的根本原理是什么？
为什么要在原始数据后加r个0？
为什么校验位r = 生成多项式二进制除数的位数 k − 1？
为什么余数的位数一定小于除数的位数？
为什么模 2 除法中，被除数可以省去最高位的0？
为什么最后保留r位数？
CRC直观运算过程
演示
动态演示
解释
CRC(循环冗余校验)基本概念
1. 核心定位
CRC 属于差错检测编码。
✅ 功能：检测传输有没有出错
❌ 不能自动定位错误位置，不能纠错（对比海明码：海明码可以纠正 1 位错误）
应用场景：以太网、USB、硬盘、串口通信，工程里用得极多。
2. 两个核心概念
① 信息位（原始数据）
你想要发送的二进制数据，比如 1010。
② 生成多项式 G(x)
发送方、接收方必须提前约定好同一个 G (x)，不能不一样。
G（x）是人为约定的，做题时会给出，并且不同情况大概率是不一样的
举例，把多项式转二进制：
等价于：
，其中
x^3 有 → 写 1；
x^2没有 →写 0；
x^1有→写 1；
x^0有→写 1
得到二进制：1011
由此得到的二进制数将作为模 2 除法中的除数
规则：G (x) 二进制的位数 = 校验位位数 + 1 例子1011一共 4 位 → 校验位是 3 位。
✔ 硬性要求：G (x) 二进制最高位一定是 1，最低位也一定是 1，并且必须≥1位
CRC 最关键：模 2 除法
模 2 除法的商只有 0 和 1。
以下以
生成多项式：
即除数为1 0 1 1
原始信息：
1 0 1 0 1 1 0 0
为例子
在做运算前，需要对原始信息进行处理：
规则：G (x) 二进制的位数 = 校验位位数 + 1
例子1 0 1 1一共 4 位 → 校验位是 3 位。
原始数据后加“校验位位数”个0，就变成了：
1 0 1 0 1 1 0 0 0 0 0
这个即为被除数
两条核心规则
每次选取和除数位数相同的一串比特，作为当前运算窗口。
异或（⊕）：
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
异或：相同为 0，不同为 1
窗口最高位如果是1：商写1，窗口和除数做异或；
窗口最高位如果是0：商写0，窗口和全 0 串异或（等于不变）。
然后一直循环下去，但是这样太麻烦了。
大多数时候会省去每一步的中被除数最高位的0，并拉下原来数的后几位，使该轮被除数等于除数的位数：
//至于各种技巧的原因，后文会解释
除数固定不变，除数最高位一定是 1（CRC 生成多项式要求）
一直做到剩下的余数位数，比除数少 1 位为止，这个余数就是 CRC 校验位。
重点：余数的位数固定 = 校验位位数。不够就在前面补 0。
该例子中，CRC 校验位为0 1 1
随后将之前补在后面"校验位位数”个0,替换为CRC 校验位
即为
1 0 1 0 1 1 0 0 0 1 1
接下来就把这个CRC码发送给接受方就可以了
发送：信息位 + CRC 余数，整体作为 CRC 码发送
接收：对收到的整个 CRC 码，用同一个生成多项式做模 2 除法
- 余数 = 0：大概率无错
- 余数≠0：传输发生错误
原理稍后会讲
关于CRC码的所有可能疑问
为什么要用多项式这种麻烦写法？
用生成多项式是为了方便抽象描述 CRC 的纠错 / 检错能力，方便硬件电路设计；
二进制只是多项式的简写形式。
多项式和二进制是一一对应的两种写法，多项式是抽象模型，二进制是它的比特实例。
① 方便理论分析检错能力
我们如果只写二进制1011，只能看到一串 0、1。 写成多项式，能直接用代数定理证明：
- 能不能检测所有奇数个错误
- 最多能检测多少位连续突发错
- 多大的错误模式会发生漏检
比如：只要多项式包含x+1因子，就一定能检出所有奇数个比特翻转。
这个结论用二进制串很难直接看出来，多项式代数推导很方便。
② 不依赖总长度，通用性强
比如 G(x)=x^3+x+1，
它永远对应 4 位除数1011。
不管你的信息是 8 位、32 位、1000 位，这个生成多项式不变。
多项式描述的是规则，不是固定长度的比特串。
③ 方便硬件电路实现（CRC 底层硬件）
CRC 硬件是用移位寄存器 + 异或门搭建。 多项式的每一项，直接对应电路上要不要接一个异或门。
G(x)=x^3+x+1：
- x^3：寄存器最高位
- x^1：第 1 位接异或
- x^0：最低位 硬件工程师看到多项式，直接画出电路。如果只写二进制1011，不容易映射到硬件。
CRC码的根本原理是什么？
通俗来说，CRC是在原始数据后加上某个数，使其可以被约定的数（G(x)）整除。
举一个十进制的例子：
原始信息：123，除数 73（k=2，r=1）
我们想要构造一个新数字，等于 123 拼接一位余数。
//其实这里余数也可能是两位，但是在二进制中会严格遵循：余数位数=（除数位数-1），仅举例
这里要空出个位，就要乘以 10（十进制左移 1 位）：
123 * 10 =1230
1230 ÷73，得到余数 8。
把个位的 0 替换成余数 8，得到 1238。 1238 ÷73 刚好整除。
这里乘以 10，就是十进制末尾补 1 个 0，和二进制末尾补 r 个 0 是一模一样的目的：腾出末尾位置，用来放余数。
这样，接受方再此以同样的方法进行检验，若没有余数，那么就大概率没有错误
为什么要在原始数据后加r个0？
根据上一步说的根本原理，我们是想要这个数被约定的数整除的
但我们不能直接硬改原始数据——毕竟里边是存有信息的，于是我们可以在其后面添加几位来实现这一目的。
如果不补这 r 个 0：
我们只能算出余数R
得到余数R，但是没有空余位置把 R 拼到 M 后面。 原始信息 M 的末尾没有空位，没法把校验位塞进去。
临时补的 0不是要发送的数据，只是占位符，最后会被余数覆盖掉。
❌ 不是因为除法计算必须补 0 才能算除法！
单独拿原始信息10101100，照样可以做模 2 除法。
补 0 是CRC 编码的特殊要求，目的是预留位置放校验位，构造出能被 G 整除的码字。
为什么校验位r = 生成多项式二进制除数的位数 k − 1？
原理：
CRC 的二进制模 2 除法的通用性质：余数的位数一定小于除数的位数。
为什么余数的位数一定小于除数的位数？
若除数为1011，1001<1011，也可以是余数啊？
1001是 4 位，数值上小于1011。
但是在模 2 长除法的竖式流程里： 只要剩余比特串长度等于除数长度（4 位），并且最高位是 1，运算就不会停止，会继续异或除数。
同时又有规定：除数的最高位一定为1
所以最终停止运算的时候，剩下的串最高位一定是 0。 所以最终的有效余数，不会出现最高位为 1 的 k 位比特串。
总结： 不是 “余数位数天生一定小于除数位数”。 是 CRC 模 2 竖式的运算终止规则，保证了最后得到的余数有效位数最多 k−1 位。
所以
除数 k 位，余数最多只能有 k-1 位。 所以我们预留 k-1个位置存放余数，这就是校验位。
注意：CRC 的 r 完全由生成多项式决定，和原始信息长度无关！
为什么模 2 除法中，被除数可以省去最高位的0？
这一步中，我们直接删去了第二部前几位的0
为什么可以这样做？其实很容易理解
举我们算十进制除法的例子：
我们并不会将789与1对齐，因为7>1
同理，在二进制中除数首位必定为1且1>0，我们就可以省略那个0了
是省略，不是删除
为什么最后保留r位数？
同理，是为了填充第一步中补充r个0的空缺，让这个数可以被整除
CRC直观运算过程
演示
以
生成多项式：
即除数为1 0 1 1
原始信息：
1 0 1 0 1 1 0 0
为例子
除数是1 0 1 1
我们先以此创建4个数据位
然后将最高位的1变为“1探测器”，当前位置有1时激活：
然后把后续的1的数据位变为“”反转器“——当激活时，1->0 , 0->1
并将其与“1探测器”连接
这就构成了CRC的运算器：数据右进左出，演示流程
到这里之前，不断地向前移动就模拟了我们进位的动作
此时，“1探测器”上有1，同时激活“反转器”；
这里也就模拟了：
将除数与被除数最高位1对齐，并即将要进行异或运算的操作，下一步：
这一步进行了异或运算并向前继续移动；此时“1探测器”上没有1，不激活——这就模拟了我们省略0的操作；
此时激活，再此重复操作，直到全部出去
到此，我们神奇的发现
1 0 0 1 1 0 0 1 0 1 1
蓝色的是我们手算时的商，而红色就是我们要的CRC 校验位
动态演示
CRC
解释
“1探测器”就相当于我们手算中的对齐操作；
如果为0，就不做任何运算，换到下一位，即”省略高位的0“
后边的”反转器“其实就是1参与的异或运算：
1 ⊕ 0 = 1
1 ⊕ 1 = 0
相当于反转
至于0数据位，0参与的异或运算：
0 ⊕ 1 = 1
0 ⊕ 0 = 0
其实就是不变，方便理解，也可以把他们称为”不变位“
这么整体的流程就是：
和被除数的1对齐了，就异或；
没有对齐，就移位到对齐
参考以及推荐：[CRC校验]手算与直观演示_哔哩哔哩_bilibili
