LFSR 和 CRC 是什么原理？

更新时间：2026-09-21。问题驱动短答页。数学结构与实现见 CRC 与 LFSR，数据纠错见 Hamming/ECC。

一句话回答

LFSR（线性反馈移位寄存器）每个时钟把若干选定级的输出异或后塞回第一级，这些“抽头”对应 GF(2)（二元域）上一个生成多项式的系数；因为模 2 运算里加和减都是异或，整个状态机就是在做多项式递推。选到本原多项式时，n 位 LFSR 能在重复前遍历除全 0 外的全部 2ⁿ−1 个状态，因此输出看似随机、实则确定可复现的伪随机序列。CRC 用的是同一套“除以生成多项式取余数”的结构，只不过边移入数据边算余式，余数就是校验码。

LFSR 怎么跑

// 4 位 LFSR，多项式 x^4 + x + 1（taps: bit4 与 bit1）
reg [4:1] r = 4'hF;
wire fb = r[4] ^ r[1];
always @(posedge clk)
  r <= {r[3:1], fb};

• 每拍整体移位，反馈位是抽头的异或。
• 全 0 是死状态（进去出不来），所以要用非 0 seed。
• taps 选对（本原多项式）才有最长 2ⁿ−1 周期。

为什么能做伪随机和 CRC

• GF(2) 上的线性递推：状态转移确定、周期长、统计上接近白噪声，适用于测试激励、扰码、BIST 图案生成（见 BIST/MBIST）。
• CRC = 多项式除法取余：把数据流看作 GF(2) 多项式，用生成多项式去除，发送方附带余数，接收方重算余数比对。位翻转会改变余式，因而能检出常见突发错误。
• 两者硬件都是“移位 + 抽头异或”，面积小、速度快。

关键参数与坑

• 多项式/taps 必须双方一致，否则 CRC 对不上。
• 初值 (init/seed)、输入/输出是否取反、**位序（MSB/LSB first）**都会影响 CRC 结果，标准（CRC-16/32）都规定了这些细节。
• LFSR 不是密码学安全随机数：输出可从足够长样本反推。
• 全零状态要靠 seed 或额外逻辑避开。

常见坑

• taps 抄错，周期变短或锁死全 0。
• CRC 只实现了“移位异或”，却忽略标准规定的初值和最终异或，结果与协议对不上。
• 位序搞反（按字节从高位还是低位喂）。
• 把 LFSR 当强随机源用于安全场景。

总结

LFSR 在每拍按 GF(2) 生成多项式的抽头异或反馈、移位推进，因模 2 加减即异或，本原多项式下可遍历 2ⁿ−1 个非零状态产生长周期确定可复现的伪随机序列；CRC 则是把输入当作 GF(2) 多项式做同样的移位异或除法、以余式为校验码，二者共用“移位+抽头异或”的极简结构，关键是多项式、初值、位序和取反约定必须一致。