CRC算法原理与实现07——Verilog单步计算任意CRC-Anlogic-安路社区-FPGA CPLD-ChipDebug

CRC算法原理与实现07——Verilog单步计算任意CRC

yuanxiaowa徽章-元老玩家-ChipDebug等级-LV1-ChipDebug4天前更新
120
CRC算法原理与实现

转自徐晓康的博客
CRC算法原理与实现01——概述
CRC算法原理与实现02——数学原理与模2运算
CRC算法原理与实现03——参数说明、计算步骤与应用场景
CRC算法原理与实现04——软硬件实现方法简介 – 徐晓康的博客
CRC算法原理与实现05——并行计算公式推导
CRC算法原理与实现06——自编Python计算任意CRC
CRC算法原理与实现07——Verilog单步计算任意CRC
CRC算法原理与实现08——Verilog多步计算任意CRC – 徐晓康的博客
CRC算法原理与实现09——C语言计算任意CRC

20250218183727392-image

前言

用Verilog算CRC已经有了两个比较不错的网站，可以在线生成Verilog代码，如：

  1. Generator for CRC HDL code

    它对应的开源库：GitHub – mbuesch/crcgen: Generator for CRC HDL code (VHDL, Verilog, MyHDL)

20250218183748161-image

图片[4]-CRC算法原理与实现07——Verilog单步计算任意CRC-Anlogic-安路社区-FPGA CPLD-ChipDebug

  1. OutputLogic.com » CRC Generator

图片[5]-CRC算法原理与实现07——Verilog单步计算任意CRC-Anlogic-安路社区-FPGA CPLD-ChipDebug

20250218183759129-image

这两个网站能够生成任意CRC算法的Verilog单步计算模块，单步的概念是只输入一次数据就算出CRC，这适用于数据长度较短的的情形。

因为CRC算法的主要部分是异或运算，如果单步计算时数据太长则组合逻辑路径就会很长，易造成时序问题，所以对于长数据的CRC运算，推进使用多步算法，也就是分多个时钟周期算出CRC，基本等价于在长的异或逻辑中插入多级寄存器。关于多步CRC的Verilog实现，参考本系列的下一篇博客。

CRC算法的主体是异或运算，但仍然包括输入反转，输出反转，输出异或等操作，上述网站生成的代码没有将这些操作包含进去，所以，在应用时还需要在模块外部进行一些额外的处理。

我更喜欢傻瓜式的模块，将实现细节都封装在模块内部，外部调用就会非常便捷，因此我自编了实现任意CRC算法的Verilog单步计算模块，将所有关于CRC的计算步骤均封装为模块内部，并通过parameter来更改不同参数，以适应所有的CRC算法。

对于CRC计算主体——异或运算，我编写了Python程序，只需输入不同的CRC配置参数，即可生成可直接复制到Verilog模块中的异或运算代码。

至此，本博文实现了适用于任意CRC算法的单步Verilog模块，最后仿真验证了CRC计算的正确性。

本博文提供的模块和Python代码的易用性已超越上述两个网站，你不再需要去关注上述网站生成的代码怎么用，只需要仔细看懂本博文，你就能实现CRC自由！

一. 数学原理

参考：CRC算法原理与实现05——并行计算公式推导

通用CRC算法公式：

20250218183830774-1739875098230

其中，，

二. 任意CRC的Verilog代码——单步

输入数据，单步计算出CRC，因为CRC计算的主要逻辑是纯组合逻辑的异或操作，所以，单步CRC适用于短数据的情况，太长的数据从避免组合逻辑太长的角度考虑需要多步计算。单步CRC部分代码如下：

2.1 模块端口定义

module myCrcOneStep
#(
  parameter DIN_WIDTH = 4, // 输入数据位宽, 取值范围为4的倍数: 如4, 8, 12, ...
  parameter WIDTH = 16,                // CRC宽度, 取值范围4~64
  parameter [0:0] REFLECT_IN = 1,      // 输入是否翻转, 取值范围0或1, 1表示反转, 0表示不反转
  parameter [WIDTH-1 : 0] XOR_IN = 'hFFFF, // 输入异或值, 取值范围全1或全0
  parameter [0:0] REFLECT_OUT = 1,     // 输出是否翻转, 取值范围0或1, 1表示反转, 0表示不反转
  parameter [WIDTH-1 : 0] XOR_OUT = 'hFFFF // 输出异或值, 取值范围全1或全0
)(
  output wire [WIDTH-1 : 0] crc_out, // CRC输出
  output reg                crc_out_valid, // CRC输出是否有效, 高电平有效

  input  wire [DIN_WIDTH-1 : 0] din, // 输入数据
  input  wire                   din_valid, // 输入数据有效, 高电平有效

  input  wire clk,
  input  wire rstn
);

2.2 输入寄存与补0

//++ 输入寄存与补齐到整数字节 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
// DIN_WIDTH向大取最接近的8的倍数, 如1~8取8, 9~16取16, 17~24取24, ...
localparam DIN_WIDTH_TO_8 = ((DIN_WIDTH + 7) / 8) * 8;

reg [DIN_WIDTH_TO_8-1 : 0] din_r;
always @(posedge clk) begin
  if (~rstn)
    din_r <= 'd0;
  else if (din_valid)
    din_r <= {{(DIN_WIDTH % 8){1'b0}}, din};
end
//-- 输入寄存与补齐到整数字节 ------------------------------------------------------------

2.3 输入按字节反转

//++ 输入按字节反转 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
wire [DIN_WIDTH_TO_8-1:0] din_reflected;

generate
if (REFLECT_IN == 1) begin
  // 对每个字节进行位反转
  genvar i;
  for (i = 0; i < DIN_WIDTH_TO_8 / 8; i = i + 1) begin
    assign din_reflected[i*8+7 : i*8] = { din_r[i*8], din_r[i*8+1], din_r[i*8+2], din_r[i*8+3],
                                          din_r[i*8+4], din_r[i*8+5],din_r[i*8+6], din_r[i*8+7]
                                        };
  end
end else begin
  assign din_reflected = din_r;
end
endgenerate
//-- 输入按字节反转 ------------------------------------------------------------

2.4 输入低位补0后高位与初始值异或

//++ 输入低位补0后高位与初始值异或 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
wire [DIN_WIDTH_TO_8+WIDTH-1 : 0] din_xor;
assign din_xor = {din_reflected, {(WIDTH){1'b0}}} ^ {XOR_IN, {(DIN_WIDTH_TO_8){1'b0}}};
//-- 输入低位补0后高位与初始值异或 ------------------------------------------------------------

2.5 模2运算

这部分是CRC计算的核心，对于不同的CRC算法，这部分代码会不一样，本文提供的Python程序可根据输入的CRC配置与输入数据位宽生成这段代码，无需手动编写。

//++ 模2计算 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
wire [WIDTH-1 : 0] crc_calc;
// 此部分代码由Python程序生成 请勿手动修改 begin
/*
单步计算CRC
CRC宽度: 5
CRC多项式: 0x05
输入数据位宽: 12
*/
assign crc_calc[0] = din_xor[5] ^ din_xor[8] ^ din_xor[10] ^ din_xor[11] ^ din_xor[14]
                    ^ din_xor[15] ^ din_xor[16] ^ din_xor[17] ^ din_xor[18];
assign crc_calc[1] = din_xor[6] ^ din_xor[9] ^ din_xor[11] ^ din_xor[12] ^ din_xor[15]
                    ^ din_xor[16] ^ din_xor[17] ^ din_xor[18] ^ din_xor[19];
assign crc_calc[2] = din_xor[5] ^ din_xor[7] ^ din_xor[8] ^ din_xor[11] ^ din_xor[12]
                    ^ din_xor[13] ^ din_xor[14] ^ din_xor[15] ^ din_xor[19] ^ din_xor[20];
assign crc_calc[3] = din_xor[6] ^ din_xor[8] ^ din_xor[9] ^ din_xor[12] ^ din_xor[13]
                    ^ din_xor[14] ^ din_xor[15] ^ din_xor[16] ^ din_xor[20];
assign crc_calc[4] = din_xor[7] ^ din_xor[9] ^ din_xor[10] ^ din_xor[13] ^ din_xor[14]
                    ^ din_xor[15] ^ din_xor[16] ^ din_xor[17];
// 此部分代码由Python程序生成 请勿手动修改 end
//-- 模2计算 ------------------------------------------------------------

2.6 输出反转

//++ 输出反转 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
wire [WIDTH-1 : 0] crc_reflected;
generate
if (REFLECT_OUT == 1) begin // 输出是否翻转
  genvar i;
  for (i = 0; i < WIDTH; i = i + 1) begin : reverse
    assign crc_reflected[i] = crc_calc[WIDTH-1-i];
  end
end else begin
  assign crc_reflected = crc_calc;
end
endgenerate
//-- 输出反转 ------------------------------------------------------------

2.7 输出异或

//++ 输出异或 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
assign crc_out = crc_reflected ^ XOR_OUT; // 输出结果与XOR_OUT异或
always @(posedge clk) begin
  if (~rstn)
    crc_out_valid <= 1'b0;
  else if (din_valid)
    crc_out_valid <= 1'b1;
  else
    crc_out_valid <= 1'b0;
end
//-- 输出异或 ------------------------------------------------------------

三. 用Python程序生成单步CRC模2运算的Verilog代码

核心代码是根据一. 数学原理中的并行计算公式，生成具体的单步计算公式，如下所示。

3.1 单步CRC计算公式

def _crc_one_step_formula(self, din_width: int) -> np.ndarray:
    # Verilog CRC计算单步并行公式
    N = self.N
    # 判断din_width是否大于0
    if din_width == 0:
        raise ValueError("din_width must be greater than 0")
    # 生成数据行向量, 输入位宽变为8的倍数, 然后加上N
    total_width = ((din_width + 7) // 8) * 8 + N
    d_symbols = symbols(' '.join([f'd{i:02d}' for i in range(total_width)]))
    D = np.array([list(d_symbols[::-1])])
    # 取前total_width-d_min个元素
    d_min = min(din_width, N)
    D = D[:, :(total_width - d_min)]
    # 后补d_min个0
    D = np.concatenate((D, np.zeros((1, d_min), int)), axis=1)
    # 生成状态转移矩阵
    T = self.T
    # 进行并行CRC计算
    verilog_one_step = 0
    j, i = divmod(total_width, N)
    for k in range(j):
        start_idx = k * N
        end_idx = (k + 1) * N
        sub_D = D[:, start_idx:end_idx]
        exp = N * (j - 1 - k) + i
        T_exp = np.linalg.matrix_power(T,  exp) % 2
        term = np.dot(sub_D,  T_exp)
        verilog_one_step += term
    # 处理余数项
    if i > 0:
        sub_D_last = D[:, j * N: j * N + i]
        eye_matrix = np.eye(i,  dtype=int)
        term_last = np.dot(sub_D_last, eye_matrix)
        verilog_one_step[0, :i] += term_last[0, :]
    return verilog_one_step

3.2 根据公式生成Verilog代码

最后代码会自动复制到剪切板，直接粘贴即可。

def generate_verilog_crc_one_step_code(self, din_width) -> str:
    """
    将输入行向量转换为Verilog crc_calc赋值语句
    :param din_width: 输入数据宽度
    :return: 生成的Verilog代码字符串
    """
    verilog_crc_one_step_list = []
    verilog_crc_one_step_list.append('// 此部分代码由Python程序生成 请勿手动修改 begin')
    verilog_crc_one_step_list.append('/*')
    verilog_crc_one_step_list.append('单步计算CRC')
    verilog_crc_one_step_list.append('CRC宽度: ' + str(self.N))
    verilog_crc_one_step_list.append('CRC多项式: '
                                        + f'0x{self.crc_config.poly:0{(self.N+3)//4}x}')
    verilog_crc_one_step_list.append('输入数据位宽: ' + str(din_width))
    verilog_crc_one_step_list.append('*/')
    # 单步CRC计算公式
    row_vector = self._crc_one_step_formula(din_width)
    crc_list = [str(item) for item in row_vector[0]][::-1]
    for i in range(len(crc_list)):
        item = crc_list[i].replace('+', '^')
        item = re.sub(r'\bd(\d{2})\b', lambda m: f"din_xor[{int(m.group(1))}]", item)
        new_item = f'assign crc_calc[{i}] = ' + item + ';'
        # 对过长的行进行分割
        split_items = self._split_long_line(new_item)
        verilog_crc_one_step_list.extend(split_items)
    verilog_crc_one_step_list.append('// 此部分代码由Python程序生成 请勿手动修改 end')
    verilog_crc_one_step_code = '\n'.join(verilog_crc_one_step_list)
    # 代码复制到剪贴板, 便于直接粘贴
    pyperclip.copy(verilog_crc_one_step_code)
    return verilog_crc_one_step_code

四. 多种CRC算法的仿真验证

测试环境：Vivado 2021.2

4.1 CRC-5-USB

  • 多项式：0x05
  • 初始异或值：0x1F
  • 输入反转：是
  • 输出反转：是
  • 最终异或值：0x1F

4.1.1 生成Verilog代码

import myCRC

# 生成单步CRC的Verilog代码
crc_custom = myCRC.CRCConfig(
    # 只需要这两个参数
    width       = 5,
    poly        = 0x1F,
)
# 直接用以下代码效果一样
# crc_custom = myCRC.CRC_5_USB # 可选CRC_8_MAXIM, CRC_16_CCITT等myCRC类中定义好的CRC配置

din_width = 12
verilog_code = myCRC.CRCVerilog(crc_custom).generate_verilog_crc_one_step_code(din_width)
print(verilog_code)

运行结果：

// 此部分代码由Python程序生成 请勿手动修改 begin
/*
单步计算CRC
CRC宽度: 5
CRC多项式: 0x1f
输入数据位宽: 12
*/
assign crc_calc[0] = din_xor[5] ^ din_xor[6] ^ din_xor[11] ^ din_xor[12] ^ din_xor[17] 
                    ^ din_xor[18];
assign crc_calc[1] = din_xor[5] ^ din_xor[7] ^ din_xor[11] ^ din_xor[13] ^ din_xor[17] 
                    ^ din_xor[19];
assign crc_calc[2] = din_xor[5] ^ din_xor[8] ^ din_xor[11] ^ din_xor[14] ^ din_xor[17] 
                    ^ din_xor[20];
assign crc_calc[3] = din_xor[5] ^ din_xor[9] ^ din_xor[11] ^ din_xor[15] ^ din_xor[17];
assign crc_calc[4] = din_xor[5] ^ din_xor[10] ^ din_xor[11] ^ din_xor[16] ^ din_xor[17];
// 此部分代码由Python程序生成 请勿手动修改 end

4.1.2 Testbench（部分）

//++ 实例化待测模块 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
localparam DIN_WIDTH = 12; // 4的倍数
localparam WIDTH = 5;
localparam REFLECT_IN = 1;
localparam XOR_IN = 5'h1F;
localparam REFLECT_OUT = 1;
localparam XOR_OUT = 5'h1F;

logic [WIDTH-1 : 0] crc_out;
logic crc_out_valid;
logic [DIN_WIDTH-1 : 0] din;
logic  din_valid;
logic  clk;
logic  rstn;

myCrcOneStep #(
  .DIN_WIDTH   (DIN_WIDTH  ),
  .WIDTH       (WIDTH      ),
  .REFLECT_IN  (REFLECT_IN ),
  .XOR_IN      (XOR_IN     ),
  .REFLECT_OUT (REFLECT_OUT),
  .XOR_OUT     (XOR_OUT    )
) myCrcOneStep_inst (.*);
//-- 实例化待测模块 ------------------------------------------------------------

initial begin
  rstn = 0;
  #(CLKT * 10)
  rstn = 1;
  din = 'h234;
  din_valid = 1;
  #(CLKT*1)
  din = 'h300;
  #(CLKT*1)
  din = 'h101;
  #(CLKT*1)
  din = 'h007;
  #(CLKT*1)
  din_valid = 0;
  #(CLKT * 10) $stop;
end

4.1.3 仿真验证

20250218184419826-image

图片[9]-CRC算法原理与实现07——Verilog单步计算任意CRC-Anlogic-安路社区-FPGA CPLD-ChipDebug

从上图可以看出：

  1. 输入'h234‘，CRC为01
  2. 输入'h300‘，CRC为05
  3. 输入'h101‘，CRC为07
  4. 输入'h007‘，CRC为0c

与CRC网页计算结果对比，完全一致，各位同学自行测试，部分结果如下图所示。

20250218184508977-image

图片[11]-CRC算法原理与实现07——Verilog单步计算任意CRC-Anlogic-安路社区-FPGA CPLD-ChipDebug

4.2 CRC-16-MAXIN

  • 多项式：0x8005
  • 初始异或值：0x0000
  • 输入反转：是
  • 输出反转：是
  • 最终异或值：0xFFFF

4.2.1 生成Verilog代码

import myCRC

# 生成单步CRC的Verilog代码
crc_custom = myCRC.CRCConfig(
    # 只需要这两个参数
    width       = 16,
    poly        = 0x8005,
)

din_width = 12
verilog_code = myCRC.CRCVerilog(crc_custom).generate_verilog_crc_one_step_code(din_width)
print(verilog_code)

运行结果：

// 此部分代码由Python程序生成 请勿手动修改 begin
/*
单步计算CRC
CRC宽度: 16
CRC多项式: 0x8005
输入数据位宽: 12
*/
assign crc_calc[0] = din_xor[16] ^ din_xor[17] ^ din_xor[18] ^ din_xor[19] ^ din_xor[20] 
                    ^ din_xor[21] ^ din_xor[22] ^ din_xor[23] ^ din_xor[24] ^ din_xor[25] 
                    ^ din_xor[26] ^ din_xor[27] ^ din_xor[28] ^ din_xor[29] ^ din_xor[31];
assign crc_calc[1] = din_xor[17] ^ din_xor[18] ^ din_xor[19] ^ din_xor[20] ^ din_xor[21] 
                    ^ din_xor[22] ^ din_xor[23] ^ din_xor[24] ^ din_xor[25] ^ din_xor[26] 
                    ^ din_xor[27] ^ din_xor[28] ^ din_xor[29] ^ din_xor[30];
assign crc_calc[2] = din_xor[16] ^ din_xor[17] ^ din_xor[30];
assign crc_calc[3] = din_xor[17] ^ din_xor[18] ^ din_xor[31];
assign crc_calc[4] = din_xor[18] ^ din_xor[19];
assign crc_calc[5] = din_xor[19] ^ din_xor[20];
assign crc_calc[6] = din_xor[20] ^ din_xor[21];
assign crc_calc[7] = din_xor[21] ^ din_xor[22];
assign crc_calc[8] = din_xor[22] ^ din_xor[23];
assign crc_calc[9] = din_xor[23] ^ din_xor[24];
assign crc_calc[10] = din_xor[24] ^ din_xor[25];
assign crc_calc[11] = din_xor[25] ^ din_xor[26];
assign crc_calc[12] = din_xor[12] ^ din_xor[26] ^ din_xor[27];
assign crc_calc[13] = din_xor[13] ^ din_xor[27] ^ din_xor[28];
assign crc_calc[14] = din_xor[14] ^ din_xor[28] ^ din_xor[29];
assign crc_calc[15] = din_xor[15] ^ din_xor[16] ^ din_xor[17] ^ din_xor[18] ^ din_xor[19] 
                    ^ din_xor[20] ^ din_xor[21] ^ din_xor[22] ^ din_xor[23] ^ din_xor[24] 
                    ^ din_xor[25] ^ din_xor[26] ^ din_xor[27] ^ din_xor[28] ^ din_xor[30] 
                    ^ din_xor[31];
// 此部分代码由Python程序生成 请勿手动修改 end

4.2.2 Testbench（部分）

localparam DIN_WIDTH = 12; // 4的倍数
localparam WIDTH = 16;
localparam REFLECT_IN = 1;
localparam XOR_IN = 16'h0000;
localparam REFLECT_OUT = 1;
localparam XOR_OUT = 16'hFFFF;

4.2.3 仿真验证

20250218184705598-image

图片[13]-CRC算法原理与实现07——Verilog单步计算任意CRC-Anlogic-安路社区-FPGA CPLD-ChipDebug

  1. 输入'h234‘，CRC为42FF
  2. 输入'h300‘，CRC为0FFF
  3. 输入'h101‘，CRC为AF3F
  4. 输入'h007‘，CRC为3DBE

与CRC网页计算结果对比，完全一致，各位同学自行测试，部分结果如下图所示。

20250218184719516-image图片[15]-CRC算法原理与实现07——Verilog单步计算任意CRC-Anlogic-安路社区-FPGA CPLD-ChipDebug

4.3 CRC-32

  • 多项式：0x8005
  • 初始异或值：0x0000
  • 输入反转：是
  • 输出反转：是
  • 最终异或值：0xFFFF

4.3.1 生成Verilog代码

import myCRC

# 生成单步CRC的Verilog代码
crc_custom = myCRC.CRCConfig(
    # 只需要这两个参数
    width       = 32,
    poly        = 0x04C11DB7,
)

din_width = 36
verilog_code = myCRC.CRCVerilog(crc_custom).generate_verilog_crc_one_step_code(din_width)
print(verilog_code)

运行结果：

略，太长了

4.3.2 Testbench（部分）

localparam DIN_WIDTH = 36; // 4的倍数
localparam WIDTH = 32;
localparam REFLECT_IN = 1;
localparam XOR_IN = 32'hFFFFFFFF;
localparam REFLECT_OUT = 1;
localparam XOR_OUT = 32'hFFFFFFFF;
...
initial begin
  rstn = 0;
  #(CLKT * 2.6)
  rstn = 1;
  din = 'h8_2340_1230;
  din_valid = 1;
  #(CLKT*1)
  din = 'h5_AAAA_BCBC;
  #(CLKT*1)
  din = 'h3_8740_1000;
  #(CLKT*1)
  din = 'h0_0000_1441;
  #(CLKT*1)
  din_valid = 0;
  #(CLKT * 5) $stop;
end

4.3.3 仿真验证

图片[16]-CRC算法原理与实现07——Verilog单步计算任意CRC-Anlogic-安路社区-FPGA CPLD-ChipDebug

20250218184838252-image

  1. 输入'h823401230‘，CRC为6A6271B3
  2. 输入'h5AAAABCBC‘，CRC为725C47A9
  3. 输入'h387401000‘，CRC为CB549CDE
  4. 输入'h000001441‘，CRC为E957514E

与CRC网页计算结果对比，完全一致，各位同学自行测试，部分结果如下图所示。

20250218184849702-image

图片[19]-CRC算法原理与实现07——Verilog单步计算任意CRC-Anlogic-安路社区-FPGA CPLD-ChipDebug

五. 源码与工程分享

用于生成Verilog代码的Python脚本和对应的Jupyter Notebook文件开源，两处仓库同步。

Gitee：myCRC: 计算CRC的代码

Github：zhengzhideakang/myCRC: 计算CRC的代码

Vivado仿真工程则通过网盘分享，VerilogOneStep Vivado2021.2工程 20250210.7z。

 
评分
欢迎为Ta评分
分享
请登录后发表评论

    没有回复内容

搜索
开启精彩搜索
FPGA SOC ARM RISCV IC 开发调试技术交流分享
FPGA SOC ARM RISCV IC 开发调试技术交流分享
FPGA SOC ARM RISCV IC 开发调试技术交流分享
热门帖子

在手机上浏览此页面