很多工程里的“校验”看起来只是几个异或、一次移位、一个固定常数表。可一旦追问为什么这样做能发现错误，为什么某些常数比另一些常数更好，为什么同一个多项式还会有正向、反向、初值、最终异或这些变体，表面上的位操作就会迅速露出背后的代数结构。
这篇文章从一个更基础的问题开始：如果一串数据在传输或存储过程中被改坏了，接收端凭什么只看一小段校验字段就能判断“这不是原来的东西”？生成多项式正是为这个问题服务的。它不是代码里的神秘常数，而是一条代数规则：规定哪些比特串是合法码字，哪些扰动会被排除在合法集合之外。
沿着这条线往下走，有限域、位串多项式、整除、余数、移位寄存器和异或会自然连在一起。最终会看到：CRC 这类循环校验码并不是“恰好用了异或”，而是因为它选择在 $GF(2)$ 上做多项式运算，所以加法、减法和消项都必然落到异或上。
1 生成多项式要解决什么问题
错误检测为什么需要一点代数？可以先从最朴素的奇偶校验看起：把一串比特里 1 的个数压缩成一个校验位。它很便宜，也很直观，但它只能保证发现奇数个比特翻转。两个比特同时翻转时，奇偶性不变，错误就会漏掉。
这说明校验码真正要解决的问题不是“算出一个摘要”这么简单，而是要把原始消息嵌入一个更大的合法集合里。发送端发出的不只是消息本身，而是“消息 + 校验字段”构成的码字；接收端要判断收到的比特串是否仍然属于这组合法码字。
生成多项式解决的就是“如何定义合法码字集合”这个问题。循环校验码的思路是：不要只数 1 的个数，而是把整段比特看成一个多项式，再用一个固定的生成多项式 $g(x)$ 去约束它。只要接收端拿到的整体不能被 $g(x)$ 整除，就说明传输或存储过程中发生了错误。
这种约束有两个工程好处。第一，它把检错问题转化成整除和余数问题，分析起来足够明确；第二，它仍然只需要非常便宜的位运算，因为在二进制有限域里，加法没有进位，减法和加法相同，最后会自然落到异或。
下面这张图先把这个过程压成一条直观路径：原始比特串先被解释成 $GF(2)$ 上的多项式，再通过生成多项式求余，最后把余数作为校验字段并入发送码字。后面的章节会逐步拆开这条路径里的每个环节。
2 生成多项式如何定义合法码字集合
生成多项式到底生成了什么？$g(x)$ 是循环校验码的核心参数。它不是从某条消息临时推导出来的，也不是随手选的魔法常数，而是在设计编码方案或制定协议时预先选定的一条代数约束。
在一个具体系统里，发送端和接收端必须使用同一个 $g(x)$。否则，发送端构造出来的合法码字，接收端可能会判成非法；接收端认为合法的码字，发送端也未必真的按同一套规则产生。至于应该选哪个 $g(x)$，要看校验位宽、最大消息长度、目标错误模型和兼容要求。
2.1 从消息到合法码字
设原始消息多项式为 $m(x)$，生成多项式的次数为 $r$。如果要附加 $r$ 个校验比特，第一步通常是把消息左移 $r$ 位，也就是乘以 $x^r$：
\[x^r m(x)\]然后用 $g(x)$ 去除它，得到余数 $p(x)$：
\[p(x) = x^r m(x) \bmod g(x)\]最后构造发送多项式：
\[c(x) = x^r m(x) + p(x)\]因为后面会看到，在 $GF(2)$ 中加法和减法相同，所以也可以把这一步理解为“把余数补到消息尾部，让整体余数归零”。于是：
\[c(x) \bmod g(x) = 0\]这就是生成多项式生成的东西：所有能被 $g(x)$ 整除的合法码字集合。接收端并不需要恢复中间的商，只要检查收到的整体对 $g(x)$ 的余数是否为零。
2.2 生成多项式不是消息的一部分
这里容易混淆的一点是：$m(x)$ 来自待发送数据，$g(x)$ 来自编码规则。消息变了，$m(x)$ 会变；协议不变，$g(x)$ 通常不会变。
例如一个协议规定使用某个 32 位 CRC 多项式，那么所有消息都用这同一个 $g(x)$ 求余。不同消息会得到不同余数，但这些余数的目的相同：把“消息 + 校验字段”拼成一个能被 $g(x)$ 整除的码字。
这正是生成多项式比奇偶校验更系统的地方。奇偶校验只把所有位置压成一个“奇偶性”；生成多项式则给每个位置分配不同的多项式权重，并通过整除关系约束整个序列。
3 为什么比特串可以变成多项式
上面一直在写 $m(x)$、$g(x)$ 和 $c(x)$，但工程里真正拿到的是 0 和 1。位串为什么可以看成多项式？原因是我们可以把一串比特解释为多项式的系数。
例如比特串 101101 可以写成：
省略系数为 $0$ 的项后得到：
\[x^5 + x^3 + x^2 + 1\]这里的 $x$ 不是某个具体数值，而是一个形式变量。把位串看成多项式，并不是为了真的求 $x=2$ 时的整数值，而是为了使用多项式的除法、余数、因式和整除关系。
这个视角有一个非常重要的工程含义：左移一位相当于乘以 $x$。例如：
\[x^5 + x^3 + x^2 + 1\]左移后变成：
\[x^6 + x^4 + x^3 + x\]也就是比特串末尾补一个 $0$。这正好对应校验计算中常见的移位寄存器行为。
4 为什么多项式运算最终变成异或
二进制校验为什么天然落在 $GF(2)$ 上？有限域可以先不从抽象定义理解。对工程师来说，最重要的是它提供了一套封闭的算术规则：在这个集合里做加、减、乘、除，结果仍然留在这个集合里。二进制校验最常用的有限域是 $GF(2)$，它只有两个元素：$0$ 和 $1$。
4.1 GF(2) 加法与异或
加法为什么会变成异或？在 $GF(2)$ 中，加法规则如下：
\[0 + 0 = 0\] \[0 + 1 = 1\] \[1 + 0 = 1\] \[1 + 1 = 0\]这正好就是 XOR。关键点在最后一行：两个 $1$ 相加不会产生进位，而是回到 $0$。因此，在这个世界里不存在十进制或普通二进制整数加法里的“进位传播”。这让校验计算可以被写成并行的异或网络，也能被软件用机器字快速处理。
减法也没有额外规则，因为在 $GF(2)$ 中：
\[a - b = a + b\]例如：
\[1 - 1 = 0\] \[1 + 1 = 0\]所以多项式长除法里原本的“减去某一项”，在实现里也只是异或掉某一组比特。
4.2 有限域和普通整数运算的差异
很多误解来自把 CRC 一类算法当作普通整数除法。二者的外形相似，但算术规则不同。
| 对比项 | 普通整数/普通多项式 | $GF(2)$ 上的多项式 |
|---|---|---|
| 系数范围 | 整数、实数等 | 只有 $0$ 和 $1$ |
| 加法 | 可能产生进位或系数累加 | 异或，无进位 |
| 减法 | 与加法不同 | 与加法相同 |
| 左移含义 | 整数乘以 2 | 多项式乘以 $x$ |
| 除法结果 | 商和余数按普通减法得到 | 商和余数按异或消项得到 |
因此，看到“多项式除法”时，不要把它想成 CPU 的整数除法指令。它更接近一个按最高项对齐、用异或不断消去最高项的过程。
4.3 为什么除法步骤会变成异或
说“多项式除法用异或实现”容易让人误解，好像除法本身突然变成了某种按位操作。更准确的说法是：多项式除法仍然是在反复用除式的倍数消掉当前最高项，只是每一步原本要做的“减法”，在 $GF(2)$ 里等价于加法，而加法又等价于 XOR。
普通多项式除法的一步可以抽象成：
\[\text{当前多项式} - x^k g(x)\]其中 $x^k g(x)$ 表示把生成多项式移动到和当前最高项对齐的位置。这个动作的目的不是得到最终商，而是先把当前最高项消掉，让余下多项式的次数逐步降低。
但在 $GF(2)$ 中：
\[a-b=a+b\]所以这一步变成：
\[\text{当前多项式} + x^k g(x)\]而 $GF(2)$ 的加法逐位看就是 XOR。因此，落到比特串上，就是：
当前比特串 XOR 对齐后的生成多项式
例如当前多项式是：
\[x^6+x^4+x^3\]生成多项式是：
\[g(x)=x^3+x^2+1\]为了消掉当前最高项 $x^6$，需要把 $g(x)$ 乘以 $x^3$：
\[x^3g(x)=x^6+x^5+x^3\]然后做消项：
\[(x^6+x^4+x^3)+(x^6+x^5+x^3)=x^5+x^4\]其中 $x^6$ 和 $x^3$ 都各出现两次，在 $GF(2)$ 中会抵消掉：
\[1+1=0\]写成比特就是：
1011000
1101000
-------
0110000
所以，除法和异或之间的关系可以概括为一条链：
多项式除法 = 反复用除式的倍数做减法消最高项
GF(2) 中减法 = 加法
GF(2) 中加法 = XOR
所以 GF(2) 多项式除法的每一步消项 = XOR
生成多项式决定“要拿哪一组位置参与消项”，异或则是这个消项动作在二进制有限域里的实现方式。
4.4 生成多项式与异或的手算示例
为了避免一开始就陷入 32 位多项式，可以先看一个很小的手算例子。这里的消息和生成多项式都不是从真实协议里摘出来的，而是为了演示机制而人为选定。
先选一段 4 bit 消息 1011。消息多项式 $m(x)$ 来自待校验数据本身，所以这里有：
因为 1011 从左到右分别对应 $x^3$、$x^2$、$x$、常数项的系数，也就是：
再选一个便于手算的玩具生成多项式 1101：
选择它的理由很朴素：最高项是 $x^3$，所以它是三次多项式；常数项为 $1$，不会退化成单纯移位；中间有一个 $x^2$ 项，反馈关系也不会太空。它不是从 1011 推导出来的，而是编码方案预先选定的参数。
生成多项式的次数由最高非零项决定。1101 的最高非零项是 $x^3$，所以次数为 $3$，也就是：
因此，计算校验位时先把消息左移三位：
\[x^3 m(x) = x^6 + x^4 + x^3\]接着求余：
\[x^3 m(x) \bmod g(x) = p(x)\]对应的被除数比特串是 1011000，除数是 1101。接下来做的不是普通整数除法，而是“最高位对齐后用异或消项”：
1011000
1101
----
0110000
1101
----
0000100
这里每一次横线下方的结果，都是上一行与对齐后的 1101 做 XOR。例如第一步：
1011
1101
----
0110
写成多项式就是：
\[(x^6+x^4+x^3)+(x^6+x^5+x^3)=x^5+x^4\]同一位置上两个 $1$ 相加会消掉，因为：
\[1+1=0\]这就是生成多项式和异或之间最直接的关系：生成多项式决定“哪些位置要参与消项”，而在 $GF(2)$ 中消项的实现就是 XOR。多项式里某一项系数为 $1$，对应硬件或软件里那个位置需要异或；系数为 $0$，对应那个位置不参与异或。
做完 $GF(2)$ 上的多项式除法后，余数为：
\[p(x) = x^2\]因为这里 $r=3$，余数字段要固定写成 3 位，对应 $x^2$、$x$、常数项三个系数。所以 $p(x)=x^2$ 写成校验字段就是 100，而不是只写一个 1。那么发送多项式为：
对应比特串就是 1011100。接收端不需要知道中间的商，只需要检查：
如果不为 $0$，就说明收到的比特串不属于这个生成多项式定义的合法集合。
4.5 余数长度与校验位宽
上面的例子里，消息 1011 后面追加的是 3 位校验字段 100，最终得到 1011100。这里的“3 位”不是随意决定的，而是由生成多项式的次数决定：如果生成多项式 $g(x)$ 的次数是 $r$，那么任何多项式除以 $g(x)$ 后，余数次数都小于 $r$：
因此余数最多需要 $r$ 个比特表示。这也是为什么一个 $r$ 次生成多项式对应 $r$ 位校验值。常见的“32 位校验”背后，就是一个次数为 $32$ 的生成多项式。
5 错误检测的整除模型
错误检测为什么会变成整除问题？设发送端发出的合法码字为 $c(x)$，传输或存储过程中出现错误模式 $e(x)$。接收端实际拿到的是：
\[r(x) = c(x) + e(x)\]接收端检查：
\[r(x) \bmod g(x)\]由于 $c(x)$ 本身能被 $g(x)$ 整除，有：
\[c(x) \bmod g(x) = 0\]所以：
\[r(x) \bmod g(x) = e(x) \bmod g(x)\]这条式子非常关键。它说明检错能力只取决于错误模式 $e(x)$ 是否会被 $g(x)$ 整除。如果错误模式不能被 $g(x)$ 整除，就一定能被发现；如果错误模式刚好也是 $g(x)$ 的倍数，就会漏检。
5.1 单比特错误的检测条件
单比特错误为什么容易发现？因为它可以写成：
\[e(x) = x^k\]这里的 $x^k$ 只有一个非零项，在数学上叫单项式。单项式是指只包含一项的多项式，例如 $x^3$、$x^7$ 或 $1$。前文说的生成多项式仍然是算法预先选定的 $g(x)$，例如 $x^3+x^2+1$ 就有多个非零项，因此不是单项式。
只有形如 $x^a$ 这样的单项式，才可能整除另一个单项式 $x^k$。如果生成多项式 $g(x)$ 含有多个非零项，它就不可能整除单比特错误对应的 $x^k$。实际使用的生成多项式都至少包含最高项和常数项，通常还包含若干中间项，因此单比特错误通常都能被检测出来。
5.2 突发错误的代数保证
突发错误为什么是循环校验码擅长的场景？因为很多真实错误不是均匀散布的，而是集中在一段连续比特里。例如磁盘、链路、电气噪声、串行传输中的干扰，常常会造成一段连续位置上的比特异常。这类错误可以抽象成突发错误。
长度不超过 $r$ 的突发错误，其错误多项式可以写成：
\[e(x) = x^i b(x)\]其中 $b(x)$ 的次数小于 $r$，且首尾项非零。若生成多项式 $g(x)$ 的次数为 $r$，并且包含常数项，那么 $g(x)$ 不会整除这种低于自身次数的突发模式。因此，次数为 $r$ 的生成多项式可以保证检测长度不超过 $r$ 的突发错误。
这就是循环校验码在通信和存储系统中长期有生命力的原因之一：它不是平均意义上“看起来不错”，而是对某些常见错误形态有明确的代数保证。
5.3 奇数个比特错误和因子 $x+1$
如果生成多项式包含因子 $x+1$，那么它可以检测所有奇数个比特翻转。原因是把一个错误多项式代入 $x=1$：
\[e(1)\]在 $GF(2)$ 中，这个值等于错误比特个数的奇偶性。如果错误比特个数为奇数，则：
\[e(1) = 1\]而任何包含因子 $x+1$ 的多项式，在 $x=1$ 处取值为 $0$。因此奇数权重的错误多项式不可能被这样的生成多项式整除。
这个结论也提醒我们：生成多项式的因子结构会直接影响它能系统性排除哪些错误模式。
6 循环结构的引入
用 $g(x)$ 定义合法码字集合之后，还要看清楚另一个细节：校验计算处理的是有顺序的 bit 流，而不是一堆无序的 0 和 1。不同位置上的 bit 对余数的影响不同，所以算法必须在读入数据时保留这种先后关系。
最自然的做法是让状态随输入向前推进。每来一个新 bit，已经读过的内容就在状态里挪到更高的位置，新 bit 进入空出来的低位。状态宽度可以保持不变，但各个 bit 所处的位置和权重会改变，这就是移位在校验计算里的意义。
可以把第 4 章里的小例子继续拿来观察这件事。消息仍然选 1011，生成多项式仍然选：
也就是二进制 1101。因为它是三次多项式，所以余数寄存器宽度为 $3$。为了计算校验字段，需要先在消息后面补 3 个零，得到待除的比特流：
1011 000
如果按手算长除法看，每一步都是“把下一个 bit 带下来，然后看当前临时多项式是否已经出现 $x^3$ 项”。如果出现，就用 1101 异或消掉最高项；如果没有，就继续读下一个 bit。右边则用一个 3 位移位寄存器表示同一件事：先把新 bit 移入最低位，如果最高位被移出为 1，就把生成多项式的低 3 位抽头 101 异或进寄存器。
| 输入 bit | 手算长除法视角 | 移位寄存器视角 |
|---|---|---|
| 初始 | 余数 000 |
寄存器 000 |
1 |
带下后为 001，次数还小于 3，不消项，余数 001 |
000 左移并移入 1 得 001，无移出最高位，状态 001 |
0 |
带下后为 010，不消项，余数 010 |
001 左移并移入 0 得 010，无移出最高位，状态 010 |
1 |
带下后为 101，不消项，余数 101 |
010 左移并移入 1 得 101，无移出最高位，状态 101 |
1 |
带下后临时为 1011，出现 $x^3$ 项；1011 XOR 1101 = 0110，余数 110 |
101 左移并移入 1 得低 3 位 011，移出最高位为 1；011 XOR 101 = 110 |
0 |
带下后临时为 1100；1100 XOR 1101 = 0001，余数 001 |
110 左移并移入 0 得低 3 位 100，移出最高位为 1；100 XOR 101 = 001 |
0 |
带下后为 010，不消项，余数 010 |
001 左移并移入 0 得 010，无移出最高位，状态 010 |
0 |
带下后为 100，不消项，余数 100 |
010 左移并移入 0 得 100，无移出最高位，状态 100 |
两列最后都得到余数 100，也就是前面手算出的校验字段。左边是在纸面上维护一个“当前余数”，右边是在电路里维护一个“寄存器状态”；它们不是两套算法，而是同一个 $GF(2)$ 多项式模除过程的两种表达。
这个例子也能看出 LFSR 里的“反馈”到底来自哪里。1101 的最高位表示除式最高项 $x^3$，它负责判断何时需要消项；真正反馈进 3 位状态的是低阶部分 101，对应 $x^2$ 和常数项。当某一步移出了最高位 1，说明临时多项式中出现了需要被消掉的 $x^3$ 项，于是寄存器就异或 101，这正是手算里用 1101 对齐后异或消项的硬件化写法。
6.1 状态推进与乘以 $x$
在多项式表示里，这种“往前挪一格”正好对应乘以 $x$。例如当前已经读到的状态是：
\[a_3x^3+a_2x^2+a_1x+a_0\]再读入一个新 bit $b$ 时，新的未约简状态可以写成：
\[x(a_3x^3+a_2x^2+a_1x+a_0)+b\]也就是旧状态整体乘以 $x$，再把新 bit 放到最低次项。这样，每个 bit 会因为读入顺序不同而落到不同次数的位置上，顺序信息就被保留下来。
如果考虑固定长度 $n$ 的码字，普通左移会让最高位被移出这个长度；如果把最高位再绕回最低位，就得到循环移位。在多项式上，这相当于在下面这个关系下做运算：
\[x^n = 1\]也就是在模 $x^n - 1$ 的多项式世界里工作：
\[GF(2)[x] / (x^n - 1)\]这解释了为什么循环码和生成多项式天然联系在一起：一个循环码可以看作由某个生成多项式 $g(x)$ 生成的倍数集合，而 $g(x)$ 通常是 $x^n - 1$ 的因子。
6.2 从数学结构到移位寄存器
多项式模除法每一步都在做同一件事：
- 看当前最高项是否需要消去。
- 如果需要，就把生成多项式对齐到这个最高项。
- 用异或消去这一组项。
- 继续向低次项推进。
这正好可以用线性反馈移位寄存器表示。寄存器保存当前余数，输入比特逐个进入；当反馈位为 $1$ 时，把生成多项式中对应的抽头异或到寄存器里。所谓“抽头”，本质上就是生成多项式里哪些系数为 $1$。
需要注意的是，最高项用来决定寄存器宽度，通常不再画成一个额外反馈抽头。比如 $g(x)=x^4+x+1$ 的系数是 10011，其中 $x^4$ 表示 4 位余数宽度，真正参与反馈的是低阶项里的 $x$ 和 $1$，也就是低 4 位 0011。
7 多项式长度与检测能力
生成多项式是不是越长越好？校验位宽越大，随机错误漏检概率通常越低，但这不等于“位宽越长就自动更适合”。生成多项式的选择要同时看错误模型、消息长度、协议约束和实现成本。
7.1 汉明距离关心的是最小不可区分差异
汉明距离先从两串等长 bit 的比较理解：如果两个 bit 串在某些位置不同，不同位置的个数就是它们的汉明距离。例如：
101100
100110
这两串有两个位置不同，所以汉明距离是 $2$。放到校验码里，更关心的是所有合法码字之间的最小汉明距离，也就是任意两个合法码字至少相差多少个 bit。这个最小距离越大，越能保证发现更多低重量错误。
如果一个码的最小汉明距离为 $d$，那么它可以检测任意少于 $d$ 个比特的错误：
\[w(e) < d\]其中 $w(e)$ 表示错误模式中非零项的个数。生成多项式会影响这个距离，但距离还与消息长度有关。同一个生成多项式，在短帧上可能具有很高的检测能力，到了很长的数据块上保证就会下降。
7.2 常见多项式不代表所有场景最优
工程上常见的多项式往往来自标准、历史兼容和实现生态。例如很多系统使用 32 位校验，但不同协议可能选用不同的 32 位生成多项式。选择时需要回答几个问题：
| 问题 | 影响 |
|---|---|
| 最大消息长度是多少 | 决定目标汉明距离能保持到多长 |
| 错误更像随机翻转还是突发错误 | 决定该优先优化哪类错误模型 |
| 是否必须兼容既有协议 | 决定能不能更换多项式 |
| 软件还是硬件实现 | 影响查表、并行展开和寄存器抽头设计 |
| 是否需要检测全零前缀、尾部填充等异常 | 影响初值、终值异或和数据预处理 |
因此，生成多项式不是一个孤立常数，而是一组工程假设的压缩表达。
7.3 多项式表示也会带来混淆
同一个生成多项式可能有不同写法。例如有的文档省略最高项，因为最高项必然为 $1$；有的文档使用正常位序，有的文档使用反射位序；有的实现把多项式写成适合右移寄存器的形式。
以常见 32 位校验多项式为例，其正常表示常写为 0x04C11DB7，反射实现中常见的表示则是 0xEDB88320。这两个数看起来不同，但常常描述的是同一组代数约束在不同位序下的实现形态。
所以阅读协议或代码时，至少要同时确认：
- 多项式宽度。
- 多项式十六进制表示是否省略最高项。
- 输入比特是否反射。
- 输出余数是否反射。
- 初始寄存器值。
- 最终是否异或固定值。
只看一个 poly 参数，很容易把数学对象和实现约定混在一起。
8 从代数到实现的工程约束
从代数走向实现时会遇到哪些约束？一旦进入工程实现，核心问题就从“能不能算”变成“怎样在给定资源下算得足够快、足够稳定、足够容易验证”。CRC 的实现形态很多，bit 串行、byte 查表、slicing-by-N、FPGA 并行 XOR 网络、ASIC 流水线，本质上都在实现同一个状态转移，只是把“多轮移位与异或”折叠到不同的时间和空间里。
理解这件事，最好从最朴素的串行电路开始。串行电路最接近前文的多项式长除法；并行电路则是把若干次串行转移提前展开，化简成一组组合 XOR 方程。两者不是两套算法，而是同一个线性状态机的不同实现。
8.1 串行实现：最接近多项式长除法
按 bit 串行处理最容易和数学过程对齐。每来一个输入比特，寄存器移位一次，根据反馈位决定是否异或生成多项式抽头。这种方式面积小、逻辑简单、适合低速链路、调试模型或资源受限场景。
串行 CRC 电路通常由三部分组成：
| 结构 | 作用 |
|---|---|
| 余数寄存器 | 保存当前多项式除法的中间余数，也就是 CRC 状态 |
| 反馈 XOR | 把输入 bit 和寄存器最高位组合起来，决定本轮是否需要按生成多项式消项 |
| 抽头 XOR | 根据生成多项式低阶项中哪些系数为 $1$，把反馈位异或到对应寄存器路径上 |
以前面提到的低阶结构为例，若选择：
\[g(x)=x^4+x+1\]那么余数寄存器宽度为 $4$，可以记为 $s_3,s_2,s_1,s_0$。最高项 $x^4$ 不对应一个额外抽头，它只说明余数宽度是 4；真正决定反馈异或位置的是低阶项 $x$ 和 $1$。
如果采用高位先输入的一种常见写法，设当前输入 bit 为 $d$，反馈位为 $f$，则一次状态更新可以写成：
\[f=d+s_3\] \[s_3'=s_2\] \[s_2'=s_1\] \[s_1'=s_0+f\] \[s_0'=f\]这里的加号仍然是 $GF(2)$ 加法，也就是 XOR。这个状态方程比电路图更重要：电路图会因为左移、右移、反射、多项式表示方式而变形，但状态方程明确说明了每一拍的旧状态、输入和新状态之间的关系。
它的限制也很明显：每个周期只处理一个 bit，吞吐率直接受时钟和接口宽度限制。如果数据路径本身是 8 bit、32 bit 或 512 bit 宽，逐 bit 处理就会成为瓶颈。
8.2 串行状态如何展开成并行状态
并行 CRC 的关键不是重新发明一种算法，而是把串行状态转移连续代入多次。可以把一次串行更新抽象成一个函数：
\[s_{t+1}=T(s_t,d_t)\]如果每个周期要处理 $k$ 个 bit，那么目标就是直接得到：
\[s_{t+k}=T(T(\cdots T(s_t,d_0),d_1)\cdots,d_{k-1})\]由于 CRC 在 $GF(2)$ 上是线性的，连续代入以后，新状态的每一位仍然只是“旧状态若干位”和“输入若干位”的 XOR。中间状态不需要真的保存成寄存器，它们可以被代入、消去，最后变成一片组合 XOR 网络。
先看两拍展开，仍沿用上一节的状态方程。第一个输入 bit 记为 $d_0$：
\[f_0=d_0+s_3\]第一拍后：
\[s_{3,1}=s_2\] \[s_{2,1}=s_1\] \[s_{1,1}=s_0+d_0+s_3\] \[s_{0,1}=d_0+s_3\]第二个输入 bit 记为 $d_1$。此时反馈位不再是 $d_1+s_3$，而是 $d_1+s_{3,1}$，也就是：
\[f_1=d_1+s_2\]第二拍后得到：
\[s_{3,2}=s_1\] \[s_{2,2}=s_0+d_0+s_3\] \[s_{1,2}=d_0+s_3+d_1+s_2\] \[s_{0,2}=d_1+s_2\]这已经能看出并行化的本质：处理两个 bit 后的新状态，全部可以直接由旧状态 $s_3,s_2,s_1,s_0$ 和输入 $d_0,d_1$ 算出。继续代入到 4 bit、8 bit、32 bit，本质上只是方程规模变大。
形式上，也可以把一次状态更新写成矩阵变换：
\[s_{t+1}=A s_t+B d_t\]连续处理 $k$ 个 bit 后变成：
\[s_{t+k}=A^k s_t+\sum_{i=0}^{k-1}A^{k-1-i}B d_i\]这里所有乘法和加法都发生在 $GF(2)$ 上。矩阵里的 $1$ 表示某个状态位或输入位会参与 XOR，矩阵里的 $0$ 表示不参与。硬件生成器、脚本工具或综合前的参数化 RTL，通常就是在自动完成这件事。
8.3 并行硬件：把多轮状态转移折叠成 XOR 网络
把串行状态展开以后，硬件里看到的就不再是一条每拍移动一次的短反馈链，而是一组组合 XOR 方程。仍以 $g(x)=x^4+x+1$、一次处理 4 bit 为例，按上一节的高位先输入约定，展开 4 拍后可得到：
\[n_3=s_3+s_2+d_1+d_0\] \[n_2=s_2+s_1+d_2+d_1\] \[n_1=s_3+s_1+s_0+d_3+d_2+d_0\] \[n_0=s_3+s_0+d_3+d_0\]其中 $n_3,n_2,n_1,n_0$ 是一次并行更新后的新余数状态。把这些加号换成 XOR，就得到硬件实现中的组合逻辑。
并行度从 1 bit 提高到 $k$ bit 后，每个周期的数据吞吐率提高了，但代价也很直接：
| 变化 | 影响 |
|---|---|
| 输入位数增加 | 每个新状态位可能依赖更多输入位 |
| XOR 扇入增加 | 单级 XOR 过深会拉长组合延迟 |
| 连线更多 | FPGA 上可能受布线和 LUT 映射影响，ASIC 上可能受线延迟和功耗影响 |
| 方程更复杂 | 参数化生成、形式验证和测试向量覆盖更重要 |
实际设计中通常不会让一个很大的 XOR 直接堆成一条长链，而是会做平衡 XOR 树，必要时插入流水线寄存器。流水线能改善时序，但会改变延迟：吞吐率可能保持一拍一个数据字，结果却要晚若干拍出来。因此接口协议还要一起处理 valid、last、包尾 CRC 对齐等控制信号。
8.4 查表实现：软件里的并行展开
软件中常见的 byte-at-a-time 查表法，本质上也是并行展开，只不过它把连续 8 次移位和条件异或预先算好，存进表里。处理一个字节时，不再逐 bit 做 8 轮状态转移，而是用当前余数的一部分和输入字节形成索引，再查表更新余数。
如果把串行状态转移记为 $T$，那么一张 256 项的表可以理解为预存了所有可能 8 bit 输入对余数的影响：
\[T^8(\text{state}, \text{byte})\]更激进的 slicing-by-N 方法会同时使用多张表，把多个字节的影响并行折叠进余数。例如 slicing-by-4 可以一次合并 4 个字节的影响，减少循环次数。它的代价是表空间增加、缓存压力上升，并且更容易暴露端序、反射输入和平台字节序之间的差异。
所以，查表法和硬件并行 CRC 的思想是相通的：都在提前合并多轮串行状态转移。区别在于，软件用内存表保存预计算结果，硬件用组合 XOR 网络直接算出结果。
8.5 参数化实现最容易错在边界
很多校验错误不是多项式本身错了，而是边界约定不一致。尤其当同一个模块要支持不同位宽、不同多项式、不同输入位序时，下面这些点比 XOR 方程本身更容易出错：
| 易错点 | 典型后果 |
|---|---|
| bit 输入顺序不一致 | 与标准测试向量不匹配 |
| 初值设错 | 空消息或短消息结果异常 |
| 反射处理重复或遗漏 | 软件和硬件结果互为位反转变体 |
| 末尾补零规则理解错误 | 余数计算偏移一个校验宽度 |
| 数据字节序和 bit 序混淆 | 多字节接口下结果随平台或总线定义变化 |
| 并行展开的输入顺序写反 | 低速 bit 串行模型正确，高速并行模块错误 |
| 流水线延迟没有对齐控制信号 | CRC 值正确但出现在错误的数据包边界 |
严肃实现通常会保留三个层次的参照物：第一是数学定义，也就是 $g(x)$、初值、反射和最终异或；第二是 bit 串行黄金模型，用来描述最小一步状态转移；第三是并行实现，用自动脚本或形式等价检查证明它等价于连续多拍串行模型。
8.6 工程取舍：面积、时序、吞吐率和可验证性
从工程角度看，CRC 实现的选择通常不是“串行好”或“并行好”，而是看数据路径、时钟目标和验证成本。
| 实现方式 | 适合场景 | 主要代价 |
|---|---|---|
| bit 串行 LFSR | 低速链路、小面积控制逻辑、黄金模型 | 吞吐率低 |
| byte 查表 | CPU 软件、通用库、协议栈 | 表空间、缓存行为、端序处理 |
| slicing-by-N | 高吞吐软件 CRC | 表更大，代码和数据布局更复杂 |
| k bit 并行 XOR 网络 | FPGA/ASIC 高速数据通路 | XOR 扇入、布线、时序收敛 |
| 流水线并行 CRC | 超高频或超宽数据路径 | 延迟增加，控制信号对齐更复杂 |
对 FPGA 来说，宽并行 CRC 往往受 LUT 映射和跨区域布线影响。一个看起来只是“很多 XOR”的逻辑，如果扇入很大、跨越很宽的数据总线，可能会比预期更难收敛。对 ASIC 来说，问题更多落在门级延迟、线延迟、功耗和可测试性上。
因此，比较稳妥的实现路径通常是：
- 先写一个清晰的 bit 串行参考模型。
- 用脚本或矩阵方法从参考模型生成 $k$ bit 并行方程。
- 用随机测试和标准测试向量比较串行模型与并行模型。
- 对很宽的并行网络做 XOR 树平衡和必要的流水线切分。
- 把数据、
valid、last、初始化、输出异或等控制路径一起验证。
只要抓住“并行实现等价于连续多次串行状态转移”这条线，查表法、硬件展开和流水线优化就不会显得像彼此无关的技巧。它们都是在同一个生成多项式约束下，把时间上的多次 XOR 换成空间上的预计算或组合逻辑。
9 常见误解与边界
理解有限域和生成多项式后，很多流行说法可以被更精确地限定。
9.1 “校验值越长越安全”并不完整
更长的校验值通常降低随机漏检概率，也能覆盖更长的突发错误。但如果多项式选择不合适，或者消息长度远超该多项式的设计区间，实际汉明距离可能并不理想。位宽是重要变量，但不是唯一变量。
9.2 “生成多项式只是一个常数”会遮蔽设计目标
生成多项式的因子、权重、阶、与消息长度的关系，都会影响检错性质。把它只当作代码里的 POLY 常量，会让人忽视它背后的错误模型和协议假设。
9.3 “结果不一致就是多项式错了”经常误判
同一个数学多项式，在不同实现约定下会产生不同中间值和不同十六进制常数。排查时应先确认参数全集，而不是立刻更换多项式。
9.4 “循环校验码能保证数据正确”是过度表述
校验码只能检测它能够区分的错误模式。它不提供密码学意义上的抗伪造能力，也不能替代认证码或数字签名。对偶发传输错误和存储错误，它很有效；对主动攻击者，它不是安全边界。
10 一个具体 CRC 算法的定义过程
前面一直在讨论 $g(x)$、$m(x)$ 和 $r$，但在真实协议里，一个 CRC 算法并不只写一句“用某个多项式”。它通常会被定义成一组参数：校验宽度、生成多项式、输入位序、初始值、输出处理方式和测试向量。下面用常见的 CRC-32/IEEE 作为例子，说明这些量各自从哪里来。
10.1 参数表定义了算法边界
一个典型 CRC-32/IEEE 参数集可以写成：
| 参数 | 常见取值 | 含义 |
|---|---|---|
| Width | 32 |
余数寄存器宽度，也是最终 CRC 宽度 |
| Poly | 0x04C11DB7 |
生成多项式的十六进制表示，通常省略最高项 |
| Init | 0xFFFFFFFF |
余数寄存器初始值 |
| RefIn | true |
输入字节内 bit 是否按反射顺序处理 |
| RefOut | true |
输出余数是否反射 |
| XorOut | 0xFFFFFFFF |
最终输出前异或的固定值 |
| Check | 0xCBF43926 |
字符串 123456789 的标准校验结果 |
这张表里的 Poly 只决定代数约束的一部分；Init、RefIn、RefOut 和 XorOut 则决定工程实现和协议兼容约定。两个实现只有在这些参数全部一致时，才应该得到同一个最终 CRC 值。
10.2 生成多项式的确定
CRC-32/IEEE 的正常多项式表示常写作 0x04C11DB7。这个数不是从某一条消息算出来的，也不是随手拍脑袋写下来的。CRC-32 需要 32 位校验值，因此候选生成多项式首先被限定为 32 次二进制多项式：
其中每个系数 $a_i$ 只能是 $0$ 或 $1$。在这个候选空间里，设计者会根据目标消息长度、突发错误检测能力、低重量错误检测能力、硬件实现复杂度和标准兼容性等条件筛选多项式。0x04C11DB7 可以理解为被 CRC-32/IEEE 这一路标准化路径选中并固定下来的那个 32 次生成多项式。
由于最高项 $x^{32}$ 是隐含的，参数表里通常只记录从 $x^{31}$ 到 $x^0$ 的 32 个系数。0x04C11DB7 对应的完整生成多项式是：
这里的 $g(x)$ 不是从某一条消息 $m(x)$ 推导出来的，而是在算法定义时预先选定。它的作用是规定合法码字必须满足的整除关系。协议或文件格式一旦规定了这个多项式，发送端、接收端、软件库、硬件模块都要围绕同一个 $g(x)$ 工作。
如果使用反射实现，代码里还常看到 0xEDB88320。这不是另一个随意替换的多项式，而是同一个代数约束在低位先处理时的表示形式。也因此，讨论“用了哪个多项式”时，必须同时说明位序约定。
10.3 校验位宽 $r$ 的确定
$r$ 来自生成多项式的次数。CRC-32/IEEE 的生成多项式最高项是 $x^{32}$，所以：
\[r=32\]这意味着计算过程中维护的是 32 位余数，最终输出也是 32 位校验值。抽象公式里的：
\[p(x)=x^r m(x) \bmod g(x)\]在这个例子里就变成：
\[p(x)=x^{32}m(x) \bmod g(x)\]不过工程实现未必真的显式把消息后面补 32 个零再做长除法。很多反射算法、查表算法和硬件 LFSR 会把补零、初值和最终异或折叠进状态转移里，但它们仍然是在实现同一个余数约束。
10.4 消息多项式 $m(x)$ 的确定
$m(x)$ 来自待校验的数据本身。给定一段字节序列，先按照算法规定的 bit 顺序把它展开成比特流，再把这些比特当作 $GF(2)$ 上的多项式系数。
例如消息字节是 0x31，也就是字符 1。如果按正常高位先处理，它对应的 bit 序列是：
00110001
可以表示为：
\[m(x)=x^5+x^4+1\]如果算法规定输入反射，那么同一个字节会按低位先进入状态机。此时实现层面的处理顺序变了，代码里看到的移位方向、查表索引和多项式常数也会随之变化。也就是说，$m(x)$ 不是一个脱离位序约定的裸字节数组，而是“数据内容 + bit 进入顺序”共同确定的多项式对象。
10.5 初值、反射和最终异或的作用
Init、RefIn、RefOut 和 XorOut 不改变生成多项式本身，但会改变最终呈现出来的校验值。
| 参数 | 主要作用 |
|---|---|
| Init | 让初始状态不是全零，可影响短消息、前导零和协议兼容行为 |
| RefIn | 规定输入 bit 进入余数状态机的方向 |
| RefOut | 规定输出余数是否按位反射后再呈现 |
| XorOut | 对最终余数做固定后处理，常用于历史兼容或增强边界可区分性 |
因此，一个完整 CRC 算法可以理解成下面这组定义：
\[\text{CRC Algorithm}=(r, g(x), \text{Init}, \text{RefIn}, \text{RefOut}, \text{XorOut})\]其中 $g(x)$ 决定合法码字集合，$r$ 决定余数宽度，$m(x)$ 由输入数据和 bit 顺序确定，其他参数则定义状态机如何初始化、如何读入数据以及如何输出结果。很多实现不一致的问题，本质上不是“多项式算错了”，而是这组参数里有一项没有对齐。
11 继续深入的学习主线
继续深入时应该抓住哪条主线？如果只保留一条主线，可以这样记：
- 比特不是普通整数，而是 $GF(2)$ 上的系数。
- 位串可以表示为多项式。
- 生成多项式定义了合法码字集合。
- 校验过程是在检查接收多项式是否能被生成多项式整除。
- 错误检测能力取决于错误多项式是否会落入生成多项式的倍数集合。
- 工程实现是把多项式模除折叠成移位、异或、查表或并行 XOR 网络。
进一步学习时，可以沿着三条路径展开。
第一条是数学路径：研究循环码、有限域扩展、BCH 码和 Reed-Solomon 码。它能解释为什么生成多项式的根、因子和最小距离之间存在深层关系。
第二条是实现路径：从 bit 串行算法推导 byte 查表，再推导 slicing-by-N 和并行矩阵展开。它能解释为什么同一个校验规则在软件、FPGA 和 ASIC 中会呈现完全不同的形态。
第三条是工程选择路径：根据消息长度、错误模型、兼容要求和资源约束选择多项式与参数。它能帮助我们判断什么时候沿用标准，什么时候需要重新评估校验方案。
有限域和生成多项式看起来抽象，但它们真正的价值在于给低成本位运算提供了可分析的保证。只要抓住“余数”和“整除”这两个核心概念，很多校验算法的复杂表象都会收束到同一套清晰的机制上。
12 参考资料
- W. W. Peterson, D. T. Brown, “Cyclic Codes for Error Detection”, Proceedings of the IRE, 1961.
- Ross N. Williams, “A Painless Guide to CRC Error Detection Algorithms”, 1996, https://www.ross.net/crc/download/crc_v3.txt
- Philip Koopman, “Best CRC Polynomials”, Carnegie Mellon University, https://users.ece.cmu.edu/~koopman/crc/
- CRC RevEng, “Catalogue of parametrised CRC algorithms”, https://reveng.sourceforge.io/crc-catalogue/all.htm
- RFC Editor, “RFC 3385: Internet Protocol Small Computer System Interface (iSCSI) Cyclic Redundancy Check (CRC)/Checksum Considerations”, https://www.rfc-editor.org/rfc/rfc3385
- W3C, “Portable Network Graphics (PNG) Specification, Second Edition”, https://www.w3.org/TR/PNG/
