CRC 原理概述
摘要:循环冗余校验(CRC, Cyclic Redundancy Check)是一种基于多项式除法(modulo-2)的差错检测码。它将数据视为一个二进制多项式 D(x),生成多项式为 G(x),通过“除法”得到的余数 R(x)即为 CRC:
- 将 D(x) 左移 k 位(在二进制串末尾补 k个 0),其中 k = degG(x)。
- 用 G(x)对扩展后的多项式做模 2 除法(每步减法即异或,不带借位),得到余数 R(x),degR(x) < k。
- 将 R(x)R(x)R(x) 附加到原始数据后(或与原数据一起传输/存储),接收端做同样的除法检查余数是否为 0。
一、以 CRC-8 为例(常用多项式 0x07)
我们选用最常见的 CRC-8 生成多项式:
G(x)=x^8+x^2+x+1
- 二进制表示(含最高次项)为
1000 00111
通常在硬件/软件里只存低 8 位:0x07
,最高的 x8x^8x8 隐式存在。
- 数据宽度:32 bit
- CRC 宽度:8 bit
记 payload 二进制为
D[31] D[30] … D[0]
我们在数据后面补 8 个 “0” 得到 40 位的除数。
二、寄存器移入算法(LFSR 风格)
不必手工做 40 步“长除法”,常用移位寄存器算法:
寄存器 R ← 0x00// 1) 处理每个数据位
for i = 31 … 0:fb = (R[7] ⊕ D[i]) // 反馈 = 高位和当前输入位异或R = (R << 1) & 0xFF // 左移,低位补 0if fb == 1:R = R ⊕ 0x07 // 多项式低 8 位// 2) 处理填入的 8 个 “0” 位
for i = 7 … 0:fb = R[7] // 此时数据位总是 0R = (R << 1) & 0xFFif fb == 1:R = R ⊕ 0x07// R 最终即为 CRC-8 余数
CRC = R
R[7]
表示寄存器的最高位(MSB)。- “⊕” 表示按位异或。
(R<<1)&0xFF
保证寄存器只保留 8 位。
三、示例:演示首 8 步与尾 8 步
- 我们取一个示例 32‐bit payload(十六进制):
D = 0x1234_5678
- 其二进制(MSB 开头)前 8 位为
D[31:24] = 0001 0010
- 末 8 位补 0 的过程模拟如下(只列首 8 步和尾 8 步,中间同理):
步骤 | 输入位 D[i] | R[7] prev | fb = R[7]⊕D[i] | R<<1 | R′ = (R<<1)⊕0x07 (if fb) | R_after |
---|---|---|---|---|---|---|
1 | D[31]=0 | 0 | 0⊕0=0 | 0x00 | — | 0x00 |
2 | D[30]=0 | 0 | 0 | 0x00 | — | 0x00 |
3 | D[29]=0 | 0 | 0 | 0x00 | — | 0x00 |
4 | D[28]=1 | 0 | 1 | 0x00 | 0x00⊕0x07=0x07 | 0x07 |
5 | D[27]=0 | 0 (R[7]) | 0 | 0x0E | — | 0x0E |
6 | D[26]=0 | 0 | 0 | 0x1C | — | 0x1C |
7 | D[25]=1 | 0 | 1 | 0x38 | 0x38⊕0x07=0x3F | 0x3F |
8 | D[24]=0 | 0 | 0 | 0x7E | — | 0x7E |
(中间 24 步略)
- 下传完所有 D[31:0] 后,再“送入”8 个 0:
步骤 | 输入位=0 | R[7] prev | fb | R<<1 | R′ | R_after |
---|---|---|---|---|---|---|
33 | — | 0x7E→ MSB=0 | 0⊕0=0 | 0xFC | — | 0xFC |
34 | — | 1 | 1 | 0xF8 | 0xF8⊕0x07=0xFF | 0xFF |
… | … | … | … | … | … | … |
40 | — | (…whatever) | … | … | … | CRC |
- 最终
R
的值就是那 8 位余数——即 CRC-8。
注意:上面给出的是一种“无初始值、无反射、无末尾异或”的简单 CRC-8 计算。
实际协议(如 SMBus、Maxim-Dallas、X-25)常在此基础上加
- Initial XOR(预置寄存器为 0xFF)
- Bit-reflect(输入/输出比特顺序翻转)
- Final XOR(余数再与 0xFF 异或)
等处理,详情请参见各协议规范。
四、总结
- CRC 把二进制串看成多项式,用 G(x) 做模 2 除法,余数即校验码。
- 对 32 bit payload、8 bit CRC,多项式常用x^8+x^2+x+1(0x07)。
- 移位寄存器算法每送入一位都做一次“反馈”判断 + 条件异或,简洁且易硬件/软件实现。
- 最后不断移入 k 个 0,就得到长度为 k的余数。
五、Verilog生成CRC代码
下面给出一个纯组合并行计算 CRC-8 的 Verilog 示例,针对固定 32 位 payload、常用多项式 x^8+x^2+x+1(多项式低 8 位=0x07),算法完全对应上面讲的 LFSR 移位除法:
5.1 LFSR 移位除法:
//-----------------------------------------------------------------------------
// Module : crc8_parallel
//
// 计算 32‐bit data_in 的 CRC‐8 余数 (多项式 x^8 + x^2 + x + 1)
// 完全组合逻辑实现,仿真时一个 delta‐cycle 内算出结果
//-----------------------------------------------------------------------------module crc8_parallel (input wire [31:0] data_in,output wire [7:0] crc_out
);// CRC‐8 多项式 (低 8 位,高位 x^8 隐式存在)localparam [7:0] POLY = 8'h07;// LFSR 一步更新函数:cur 是当前寄存器,bit_in 是移入的新数据位function [7:0] next_crc;input [7:0] cur;input bit_in;reg fb;beginfb = cur[7] ^ bit_in; // MSB ⊕ 输入位 = 反馈next_crc = {cur[6:0], 1'b0}; // 左移一位if (fb)next_crc = next_crc ^ POLY; // 有反馈时再与多项式异或endendfunctioninteger i;reg [7:0] crc;// 组合逻辑:先把 data_in[31] … data_in[0] 串行送入 LFSR,// 然后不断注入 8 个 0(相当于 data << 8),最终 crc 就是余数always @* begincrc = 8'h00; // 初始余数全 0// 1) 串行处理 32 位数据for (i = 31; i >= 0; i = i - 1) begincrc = next_crc(crc, data_in[i]);end// 2) 注入 8 个 0for (i = 7; i >= 0; i = i - 1) begincrc = next_crc(crc, 1'b0);endendassign crc_out = crc;endmodule
5.2 时序版(cycle-by-cycle)实现
如果你需要时序版(cycle-by-cycle)实现,也很简单,只要用一个 8 位寄存器串行移入 40 位就行。下面给出一个带启动/就绪信号、每时钟处理一位的版本:
//-----------------------------------------------------------------------------
// Module : crc8_serial
// 时序版 CRC‐8 计算器:一个时钟一个 bit,总共 40 个时钟计算完毕
// Ports:
// clk, rst_n - 同步复位
// start - 置 1 时开始计算,内部会捕捉 data_in
// data_in - 32 位待校验数据
// busy - 高电平表示正在计算
// crc_out - 计算完毕后的 CRC‐8
//-----------------------------------------------------------------------------module crc8_serial (input wire clk,input wire rst_n,input wire start,input wire [31:0] data_in,output reg busy,output reg [7:0] crc_out
);localparam [7:0] POLY = 8'h07;reg [7:0] crc_reg;reg [5:0] bit_cnt; // 0…39// 计算一步 LFSRfunction [7:0] next_crc;input [7:0] cur;input bit_in;reg fb;beginfb = cur[7] ^ bit_in;next_crc = {cur[6:0], 1'b0};if (fb)next_crc = next_crc ^ POLY;endendfunction// 状态机:idle → busy 40 个周期 → donealways @(posedge clk) beginif (!rst_n) beginbusy <= 1'b0;crc_reg <= 8'h00;bit_cnt <= 6'd0;crc_out <= 8'h00;end else beginif (start && !busy) begin// 启动:捕捉初始状态busy <= 1'b1;crc_reg <= 8'h00;bit_cnt <= 6'd39; // 32+8-1 = 39end else if (busy) begin// 送入第 bit_cnt 位:前 32 周期送 data_in[31:0],// 后 8 周期送 0if (bit_cnt >= 8)crc_reg <= next_crc(crc_reg, data_in[bit_cnt-1]); elsecrc_reg <= next_crc(crc_reg, 1'b0);if (bit_cnt == 0) beginbusy <= 1'b0;crc_out <= crc_reg; // 最终余数endbit_cnt <= bit_cnt - 1;endendendendmodule
以上两种实现:
- 并行版(
crc8_parallel
)一次性在组合逻辑里跑完,延迟约为 40 级异或/移位链。 - 时序版(
crc8_serial
)40 个时钟周期内完成,用流水寄存器拆分了逻辑深度,更易综合并节省面积。
5.3 参数化的时序(serial)CRC 模块
下面给出一个参数化的时序(serial)CRC 模块,它支持任意宽度的输入、任意次方的生成多项式、可配置的初始值和输出异或。核心思路与前面讲的 LFSR 相同,只是把常数硬编码改成了参数。
//-----------------------------------------------------------------------------
// Module : crc_serial_param
// Description : 可配置 DATA_WIDTH、CRC_WIDTH、生成多项式 POLY(低 CRC_WIDTH
// 位)、初始寄存器值 INIT、最终输出异或值 FINAL_XOR 的串行 CRC 计算器。
// 每个时钟处理一位 bit,总共 DATA_WIDTH+CRC_WIDTH 个周期完成。
//-----------------------------------------------------------------------------module crc_serial_param #(//—— 参数化接口 ——parameter integer DATA_WIDTH = 32, // 待校验数据位宽parameter integer CRC_WIDTH = 8, // 余数位宽// 生成多项式低 CRC_WIDTH 位,多项式最高 x^CRC_WIDTH 隐式存在parameter [CRC_WIDTH-1:0] POLY = 8'h07, parameter [CRC_WIDTH-1:0] INIT = {CRC_WIDTH{1'b0}}, // 初始寄存器值parameter [CRC_WIDTH-1:0] FINAL_XOR = {CRC_WIDTH{1'b0}} // 输出前的异或
)(input wire clk,input wire rst_n,input wire start, // 高脉冲开始一次 CRC 计算input wire [DATA_WIDTH-1:0] data_in, // 待校验数据output reg busy, // 计算中output reg [CRC_WIDTH-1:0] crc_out // 计算结果
);//—— 内部状态 —— reg [CRC_WIDTH-1:0] crc_reg;integer bit_cnt; // 从 DATA_WIDTH+CRC_WIDTH-1 递减到 0//—— LFSR 一步更新函数 —— function [CRC_WIDTH-1:0] next_crc;input [CRC_WIDTH-1:0] cur;input bit_in;reg fb;reg [CRC_WIDTH-1:0] tmp;beginfb = cur[CRC_WIDTH-1] ^ bit_in; // MSB ⊕ 新输入tmp = {cur[CRC_WIDTH-2:0], 1'b0}; // 左移一位if (fb)tmp = tmp ^ POLY; // 根据多项式条件异或next_crc = tmp;endendfunction//—— 状态机/计数器 —— always @(posedge clk) beginif (!rst_n) beginbusy <= 1'b0;crc_reg <= INIT;bit_cnt <= DATA_WIDTH + CRC_WIDTH - 1;crc_out <= {CRC_WIDTH{1'b0}};end else beginif (start && !busy) begin// 启动计算:复位 CRC 寄存器、设置计数器、置 busybusy <= 1'b1;crc_reg <= INIT;bit_cnt <= DATA_WIDTH + CRC_WIDTH - 1;endelse if (busy) begin// 逐位喂入:高 DATA_WIDTH 周期取 data_in,高位先入if (bit_cnt >= CRC_WIDTH)crc_reg <= next_crc(crc_reg, data_in[bit_cnt - CRC_WIDTH]);elsecrc_reg <= next_crc(crc_reg, 1'b0); // 补 CRC_WIDTH 个“0”// 计数到 0 时结束if (bit_cnt == 0) beginbusy <= 1'b0;crc_out <= crc_reg ^ FINAL_XOR; // 最终输出可再异或endbit_cnt <= bit_cnt - 1;endendendendmodule
如何使用
举例生成一个常见的 CRC-8 (x⁸ + x² + x + 1),对 32 位 数据,初始寄存器全 0xFF
,输出再异或 0x55
:
crc_serial_param #(.DATA_WIDTH (32),.CRC_WIDTH (8),.POLY (8'h07), // 低 8 位:x^8+x^2+x+1.INIT (8'hFF), // 常见预置 0xFF.FINAL_XOR (8'h55) // 最终取反异或
) u_crc (.clk (clk),.rst_n (rst_n),.start (start),.data_in(data32),.busy (busy),.crc_out(crc8)
);
- 改变
POLY
参数即可支持不同生成多项式(例如 CRC-16 的16'h1021[15:0]
)。 INIT
、FINAL_XOR
也可按协议需求调整。
这样,你就得到了一个高度可复用的串行 CRC 计算核,既可综合,也易于集成到各种总线和协议中。
七、代码详解
在那段参数化的串行 CRC 代码里,next_crc
这个函数正是把「当前的 CRC 寄存器值」和「新送入的一位数据」合成成「下一时刻的 CRC 寄存器值」,也就是常说的 LFSR(线性反馈移位寄存器)那一步更新逻辑。
1. 数学上,它在做什么?
2. 代码里如何映射这一步?
function [CRC_WIDTH-1:0] next_crc;input [CRC_WIDTH-1:0] cur; // 上一时刻的寄存器 Rinput bit_in; // 新送入的数据位 dreg fb; // feedbackreg [CRC_WIDTH-1:0] tmp;
beginfb = cur[CRC_WIDTH-1] ^ bit_in; // ① 反馈 = R 的 MSB ⊕ dtmp = {cur[CRC_WIDTH-2:0], 1'b0}; // ② 左移一位: x·R(x)if (fb)tmp = tmp ^ POLY; // ③ 如果 fb=1,就多项式减(⊕)一次next_crc = tmp; // ④ 得到新余数
end
endfunction
- ① 反馈位 (fb):
在做多项式除法时,最高次项系数 rn−1与当前输入位 d 异或,决定是否要用 G(x) 去“减”一次。 - ② 左移一位:
相当于多项式乘以 x。 - ③ 条件异或多项式:
如果反馈位为 1,才把移位后的结果与POLY
(多项式的低 nnn 位)异或,完成一次模 2 的除法(减法)。 - ④ 返回新寄存器值:
这就是下一时刻的 CRC 寄存器状态。
3. 为什么这么做能实现 CRC?
- 模 2 除法中的 减法 就是异或。
- 每送入一位数据,就相当于先把余数乘 x(左移),再加上这位数据;如果新的最高次项系数变成了 1,就要减一次生成多项式,保持余数次数 < n。
- LFSR 正是这个思路的硬件实现:一个 n 位移位寄存器+若干 Tap 处的反馈异或。
4. 举个 4 位宽的小例子
5. 小结
next_crc(cur, bit_in)
抽象了一次「左移+条件异或」的 LFSR 步骤。- 它保证:每把一位数据喂进去,CRC 寄存器就恰好做了一次多项式模 2 除法。
- 串行地调用
DATA_WIDTH+CRC_WIDTH
次,就完成了对整帧数据的 CRC 计算。