CRC 编码过程：编码算法、模2除法、余数计算
好了，咱们直接进入正题。CRC 编码的核心说白了就三步：补零 → 模2除 → 拿余数。别看公式唬人，当年我第一回看教材也是晕的，后来自己动手写了几行代码才明白——不过就是二进制里的“异或”操作。
编码算法：到底在做什么？
发端数据是一个二进制流，我们把它看成多项式 M(x)。比如数据 1011 就是 x³ + x + 1。收发双方事先约定好一个生成多项式 G(x)，比如 1001（即 x³ + 1）。
编码就是想给 M(x) 后面附上 r 位余数，使得整个多项式能被 G(x) 整除。这里的 r 就是 G(x) 的最高次次数。
具体流程
- 原数据
M左移r位（就是末尾补r个0），得到M' - 用
M'对G(x)做模2除法，得到余数R - 最终发送的码字 =
M' + R（注意这里的加法是直接拼接，不是模2加）
^ 一位一位除。下面会给你演示。
模2除法：和普通除法差在哪？
很多人卡在这里。说白了，模2除法做的是按位异或，没有进位，也没有借位。你想想看，普通二进制除法里我们要“够减”才商1，然后做减法；模2除法里只要当前位的最高位是1，就商1，然后做异或。
| 对比项 | 普通二进制除法 | 模2除法（CRC） |
|---|---|---|
| 减法 | 带借位的二进制减 | 按位异或（无进位/借位） |
| 商位判定 | 被除数>=除数才商1 | 被除数最高位=1就商1 |
| 结果 | 商+余数（带权重） | 余数长度固定（r位） |
举个例子，数据 1101，生成多项式 1011（r=3），左移补3个0得到 1101000。做模2除法：
1011 (商，但我们一般不关心)
-----
1011 ) 1101000
1011
----
0110 (异或结果)
0000
----
1100
1011
----
1110
1011
----
101 ← 余数 3位（前面补0成 0101？注意这里不足3位补0到r位）
实际余数是 101（因为最高位已经是第一位了，长度刚好3）。所以编码后的码字是 1101 101。
1001 余数可能是 11（2位），你得左边补0成 011 再拼回去。否则接收端怎么除都除不尽，白白怀疑人生。
余数计算的本质
其实余数 R(x) 就是 M(x)·x^r mod G(x)。这个模运算在 GF(2) 域里进行，完全等价于模2除法。为什么这样设计？因为只要余数 R 存在，M' + R 就能被 G(x) 整除，接收端一除，余数为0就认为没出错。
来个代码看看，Python 里实现起来非常直接：
def crc_encode(data_bits, poly):
# data_bits 是整数，比如 0b1011
# poly 是生成多项式整数，比如 0b1001
# 第一步：计算 r 位
r = poly.bit_length() - 1
# 第二步：数据左移 r 位
m_prime = data_bits << r
# 第三步：模2除法求余数
# 用长除法思想：当 m_prime 的位数 >= poly 的位数时，异或
temp = m_prime
while temp.bit_length() >= poly.bit_length():
# 取最高位对齐
shift = temp.bit_length() - poly.bit_length()
temp ^= (poly << shift)
# 此时 temp 就是余数，长度 <= r
remainder = temp
# 第四步：返回编码后的码字（整数）
codeword = (data_bits << r) | remainder
return codeword, remainder
# 试试
cw, rem = crc_encode(0b1011, 0b1001)
print(f"编码码字: {bin(cw)}") # 0b101111 对应 1011 后面加 11？不对，这里 poly=1001 r=3，余数应该是3位
注意上面例子里 poly=0b1001 即 1001（x³+1），r=3。数据 1011 左移3位得到 1011000，模2除后余数应该是 110 还是 011？你可以自己验算。我故意留了个小悬念——实际跑一下就知道，正确答案是余数 110，所以码字 1011 110。要是余数不足3位，就像前面说的，左边补0。
流程图：CRC 编码三步走
下面这张图把整个流程串起来，建议你盯着看两分钟，再去写代码。
1011，多项式用 1001。然后拿上面的 Python 代码验证余数。这样一遍下来，你再也不会把“补0个数”和“余数不足”搞混。
嗯，到这里 CRC 编码的三大块就讲透了。我个人觉得最难理解的是模2除法为什么跟普通除法长得不一样——其实你只要记住“异或替代减法，没有进位”，然后用代码模拟一次，一切都通了。早些年我调蓝牙基带协议的 CRC 时，就是因为忘了补足余数位，折腾了一下午，后来干脆写了个打印中间过程的调试函数，才找到问题。所以强烈建议你：动手敲代码，别光看。