极客工场

Appearance

共 2,522 字预计阅读约 8 分钟

CRC 与 LFSR：一块移位寄存器的两种用法 ​

更新时间：2026-09-12。本文是「集成电路大类 · 芯片设计」**进阶层（intermediate）**数字逻辑基础第二十八篇。入门篇的奇偶校验只能发现奇数个 bit 错；真实通信和存储里挑大梁的是 CRC。而实现 CRC 的那块电路，换个接法就是产生伪随机序列的 LFSR——两者是同一枚硬币。

本文要回答的问题 ​

  • 什么是 GF(2) 的模二运算？为什么这里「加法」就是异或、没有进位？
  • CRC 为什么叫「循环冗余校验」，发送端和接收端各做一次什么运算？
  • 生成多项式怎么选，CRC 到底能抓住哪些错误、为什么抓得这么稳？
  • LFSR 的斐波那契型和伽罗瓦型怎么接，最长序列为什么是 2ⁿ−1？
  • 为什么说「CRC 电路就是一个 LFSR」，它们还能用在哪？

一、GF(2)：一个只有 0、1 且加法=异或的世界 ​

CRC 的全部运算都在 **GF(2)（二元域）**上。规则极简：

  • 加法/减法都是异或：0+0=0，0+1=1，1+1=0（没有进位、没有借位，加减同构）；
  • 乘法就是与、除法就是长除但每步的减法换成异或——叫模二除法。

一串 bit 可看成一个系数只在 GF(2) 上的多项式，例如 1101 表示 M(x)=x³+x²+1。这样做的好处是：运算全是异或和移位，硬件极便宜（几个 XOR + 寄存器），且多项式代数能给出可证明的检错能力。

二、CRC：把帧做一次模二除法，余数附在尾上 ​

约定一个收发双方都知道的 r 次生成多项式 G(x)（如 CRC-32 以太网用的那个 33 位多项式）。发送流程：

  1. 数据 M(x) 后面补 r 个 0（左移 r 位，即乘以 xʳ）；
  2. 用 G(x) 对它做模二除法，得商（丢弃）和一个不足 r 次的余数 R(x)；
  3. 把余数（r bit，叫 FCS/CRC 校验码）替换掉补的 0，附在数据后发出。

模二除法的每一步不用比较大小：当前余数最高位是 1 就「商 1」并把 G(x) 对齐异或进来，是 0 就商 0（什么也不做），然后右移处理下一位——和普通长除形式一样，只是减号变 XOR。关键性质：「补 0 后的数据」减（异或）余数 R 后，必能被 G(x) 整除（余数被消掉）。所以接收端：

  • 把收到的整串（数据+CRC）再用同一个 G(x) 模二除一次；
  • 若传输无错，余数（syndrome）恰为 0；余数非 0，就知道出了错，丢弃或请求重传。
bash
发送: T(x) = xʳ·M(x) + R(x)，  其中 R = (xʳ·M) mod G
接收: T(x) mod G(x) == 0 ?  无错 / 有错

三、CRC 能检什么错：来自 G(x) 的数学保证 ​

设传输错误叠加一个错误多项式 E(x)（在翻了的 bit 位置为 1）。接收端余数为 0 当且仅当 E(x) 恰好被 G(x) 整除。因此只要挑选 G(x) 使常见错误模式都不能整除它，就能保证检出。标准多项式（CRC-8/16/32）经过精心选择，可保证：

  • 所有单个 bit 错（只要 G(x) 至少两项）；
  • 所有奇数个 bit 错（若 G(x) 含因子 x+1）；
  • 所有长度 ≤ r 的突发错（连续一段 bit 翻转），以及绝大多数更长的突发错（漏检率约 2⁻ʳ）；
  • 任意双 bit 错（G(x) 取不可约多项式等条件）。

这就是为什么 32 位 CRC 的漏检率低到约 1/2³²，远非 1 位奇偶可比。它仍只检错、不纠错（要求重传即可），要纠错得用 汉明/ECC。选 CRC 时不要自创多项式，直接用对应领域的标准（CRC-CCITT、CRC-32 等），初值、输入/输出是否取反、字节序（reflect）必须收发完全一致——CRC 调不通九成是这些配置没对齐，而不是算法错。

四、LFSR：同样的异或+移位，用来发生最长序列 ​

把目光从「校验」转到「序列发生」。**线性反馈移位寄存器（LFSR）**是一排寄存器，把其中若干级的输出按一个多项式（抽头/tap）异或后反馈到输入端，每拍移位一次：

  • 斐波那契型（外异或/标准型）：各级输出 → 抽头异或网络 → 反馈到第 1 级输入，结构直观但多个 XOR 串在反馈路上；
  • 伽罗瓦型（内异或/混合型）：异或门插在级间，反馈位为 1 时对特定抽头级做异或。XOR 不串联、单拍延迟小，正是 CRC 串行计算的硬件形式，运行速度更快，更常用。
chip-design/intermediate/09-crc-lfsr.md D2 示意图

若反馈抽头对应的特征多项式是本原多项式（primitive）且初值非全 0，n 级 LFSR 会在回到初值前遍历全部 2ⁿ−1 个非零状态，序列长度最大，叫最长序列（m-sequence / maximum-length）。序列统计性质接近随机（0/1 近等概率、游程分布规则），所以当伪随机数/伪随机二进制序列（PRBS）用。注意两个纪律：①全 0 是死锁状态（反馈永远算出 0），要加非 0 初值或「进入全 0 自动跳出」逻辑（自启动）；②多项式不能随手点抽头，非本原多项式会让周期远短于 2ⁿ−1。

五、CRC 与 LFSR 是同一块电路，以及它们的用武之地 ​

对照就会发现它们同构：CRC 接收端「数据串行移入、按 G(x) 抽头做级间异或、移位 r+」的电路，就是一个以生成多项式为特征多项式的伽罗瓦型 LFSR——CRC 是把外部比特流「除」过这个多项式收集余数，LFSR 是让它自由振荡产生序列。一块电路、两种输入方式、两种用途：

用途怎么用这块 XOR+移位结构
CRC/FCS 检错帧位流串行除 G(x)，以太网/USB/SATA/压缩包/UART 可选帧校验
PRBS 伪随机自由运行最长序列，测试码型、链路误码率测试（PRBS7/31）、仿真激励
扰码/解扰（scrambler）让发送数据 0/1 更均衡、利于时钟恢复，PCIe/以太网 PHY
BIST 自测试LFSR 当廉价伪随机测试向量发生器（TPG）、多输入特征寄存器 MISR 压缩响应，见 DFT 入门
低开销计数/置乱功耗噪声更平均的计数器、轻量加扰（非密码安全！）

最后一句安全提醒：LFSR 是线性结构，输出有强代数规律、极易由短序列反推，绝不能当密码学随机源或加密用；要安全随机数得用 CSPRNG/真随机源。理解到「GF(2) 多项式 + 移位异或寄存器」这个统一内核，CRC 调试、PRBS、扰码、BIST 这些看起来分散的数字设计话题就一下子连起来了。

与现有篇目的衔接 ​

总结 ​

一句话总结：CRC 建立在 GF(2) 上，这里加减都是异或、无进位借位，比特流被看成系数只在 {0,1} 的多项式；发送端在数据后补 r 个 0，用收发约定的 r 次生成多项式 G(x) 做模二除法（当前余数最高位为 1 就把 G(x) 对齐异或、为 0 就移位），把不足 r 位的余数 FCS 附到帧尾，使整帧能被 G(x) 整除，接收端用同一 G(x) 再除一次，余数为 0 即无错；精心选择的标准 G(x) 可数学保证检出全部单 bit 错、奇数个错、长度 ≤r 的突发错，长突发漏检率约 2⁻ʳ，远超 1 位奇偶校验，但 CRC 只检错不纠错，且初值/字节反射/输出取反必须收发一致。另一面，n 级线性反馈移位寄存器把若干级按抽头多项式异或后反馈、每拍移位，斐波那契型把异或放反馈路、伽罗瓦型把异或插在级间（更快），当特征多项式本原且初值非零时遍历全部 2ⁿ−1 个非零态产生最长伪随机序列，全 0 会死锁、抽头不能乱选；而 CRC 接收端的串行除法电路本质就是以 G(x) 为特征多项式的伽罗瓦 LFSR，同一块 XOR+移位寄存器可用于 CRC 检错、PRBS 测试码型、链路扰码/解扰和 BIST 的向量发生与响应压缩，但因其线性可被短序列反推，绝不能当密码学随机源——抓住「GF(2) 多项式加移位异或寄存器」这个统一内核，CRC、PRBS、scrambler、LFSR/BIST 这些分散话题就连成了一件事。