CRC算法原理及其Verilog实现

2024-06-06 20:38
文章标签 算法 实现 原理 crc verilog

本文主要是介绍CRC算法原理及其Verilog实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一.CRC简介

CRC校验是一种在数据通信系统和其它串行传输系统中广泛使用的错误检测手段。通用的CRC标准有CRC-8CRC-16CRC-32CRC-CCIT,其中在网络通信系统中应用最广泛的是CRC-32标准。本文将以CRC-32为例,说明CRC编码的实现方式以及如何用verilog语言对CRC编码进行描述。

 

二.模2运算

   在说明CRC编码方式之前,首先介绍一下模2运算法则,在CRC运算过程中会使用到模2除法运算。模2运算是一种二进制运算法则,与四则运算相同,模2运算也包括模2加、模2减、模2乘、模2除四种运算。模2运算用“+”表示加法运算,用“-”、“×”或“.”、“/”分别表示减法、乘法和除法运算。与普通四则运算法则不同的是,模2加法是不带进位的二进制加法运算,模2减法是不带借位的二进制减法运算。同时,模2乘法在累加中间结果时采用的是模2加法运算;模2除法求商过程中余数减除数采用的是模2减法运算。因此,两个二进制数进行模2加减法运算时,相当于两个二进制数进行按位异或运算,每一位的结果只与两个数的当前位有关。模2除法在确定商时,与普通二进制除法也略有区别。普通二进制除法中,当余数小于除数时,当前位的商为0,当余数大于等于除数时,当前位的商为1。模2除法在确定当前位的商时,只关心余数的首位,首位为1则商为1,首位为0则商为0

1.2加法的定义:

     0+0=00+1=11+0=11+1=0

  举例如下:

     1010+0110=1100

2.2减法的定义:

     0-0=00-1=11-0=11-1=0

  举例如下:

     1010-0110=1100

3.2乘法的定义:

     0×0=00×1=01×0=01×1=1

  举例如下:

     1011×101=100111

  列竖式计算:

       1011

     × 101

   ——————

       1011

      0000

       1011

   ——————

     100111

  其中横线之间的累加过程,采用的是2进制加法,不进位。

4.2除法:

     0/1=01/1=1

  举例如下:

     1011/101=10,余数为100

  列竖式计算: 

             10  

        ————

      101  1011

            101

        ————

              100


.CRC实现原理

    CRC校验的基本思想是:利用线性编码理论,在发送端根据要发送的k位二进制码序列,以一定的规则产生一个校验用的r位监督码(即CRC码),并附在信息码后面,构成一个新的共k+r位的二进制码序列,最后发送出去。在接受端,则根据信息码和CRC码之间所遵行的规则进行校验,以确定传输过程中是否出错,并纠错。一般而言,监督码的位宽r越大,纠错能力就越能,例如,CRC32的纠错能力比CRC16要强。CRC校验获得监督码的方式是,将k位信息码转换成多项式,然后除以一个生成多项式,获得余数即为监督码。

在求解一个k位二进制信息码的CRC之前,首先需要将二进制信息码转换成多项式。一个二进制数序列的各个位是它对应多项式的系数,例如,二进制序列1101对应的多项式为:

      M(x)= X3×X2+X0

通过这种转换方式获得的多项式称为信息多项式。在进行CRC计算时,除了信息多项式之外,还需要有一个生成多项式G(x)。生成多项式G(x)要求次数大于0,并且要求0次幂的系数为1。根据以上约束,以及对纠错能力的要求,人们提出了一些通用的CRC生成多项式,例如:CRC16CRC32等。

CRC16的生成多项式为:G(x)= X15+X10+X2+1

CRC32的生成多项式为:G(x)= X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1

CRC的值等于信息多项式M(x)乘以2n,再除以生成多项式G(x)所得的余数,除法采用模2除法。其中,n表示的是生成多项式Gx)的最高次幂,CRC16n16CRC32n32


四.CRC-32串行计算公式推导

根据二进制信息码转换成多项式的方法,对于任意一个长度为(m+1)的二进制信息码,可以转换成一个最高次幂为m的多项式:

                             M(x)= Mm×2m+ Mm-1×2m-1+ … + M1×21+ M0×20

为求此二进制序列的CRC值,首先将M(x)乘以232,然后再除以生成多项式Gx),所得余数即为CRC32的值。Gx)亦为一个二进制多项式。设除法运算获得的商为Q(x),余数为Rx),那么:

   M(x)×232/ G(x) = Mm×2m×232/ G(x) + Mm-1×2m-1×232/ G(x) + … + M1×21×232/ G(x)+ M0×20×232/ G(x)  --------(公式一)

 M(x)×232/ G(x) = Q(x) + R(x)/ G(x)                                             --------(公式二)  

我们从最高位开始解,将M(x)中最高次项的系数Mm作为一个特殊的M(x)即带入公式二:

 Mm×232/ G(x) = Qm(x) + Rm(x)/ G(x)                                           --------(公式三)

其中,Mm的值为1,因为最高次项必须为1Rm(x)是余数,是一个最高次幂为31的多项式。再将公式三代入公式一:

  M(x)×232/ G(x) = Mm×2m×232/ G(x) + Mm-1×2m-1×232/ G(x) + … + M1×21×232/ G(x)+M0×20×232/ G(x)

          ={Qm(x)×2m + Rm(x)/ G(x)×2m} + Mm-1×2m-1×232/G(x)+ … + M1×21×232/ G(x) + M0×20×232/ G(x)

          = Qm(x)×2m + {Rm(x)×2/G(x)×2m-1+Mm-1×2m-1×232/G(x)} + … + M1×21×232/ G(x) + M0×20×232/ G(x)

= Qm(x)×2m + {(Rm(x)×2 + Mm-1×232)/ G(x)}×2m-1+ … + M1×21×232/ G(x)+ M0×20×232/ G(x)

--------(公式四)

公式四中,设

        {(Rm(x)×2 + Mm-1×232)/ G(x)}= Qm-1(x) + Rm-1(x)/ G(x)           --------(公式五)

再代入到公式四中,那么公式四转化为,相当于只留下可以整除的Q(x),而将余数R(x)一层一层拆解

 M(x)×232/ G(x)= Qm(x)×2m+Qm-1(x)×2m-1+{(Rm-1(x)×2 + Mm-2×232)/G(x)}×2m-2+ …+M1×21×232/G(x)+M0×20×232/G(x)

以此类推,最终获得公式:

 M(x)×232/G(x)=Qm(x)×2m+Qm-1(x)×2m-1+Qm-2(x)×2m-2+…+Q1(x)×21+Q0(x)+R0(x)/G(x)      --------(公式六)

根据CRC的定义,多项式R0(x)对应的系数即为我们的CRC32的值。

以上推导过程表明:一个m+1位的二进制序列,可以按位求取CRC32的值。运算时,首先从最高位(第m+1位,设最右边的为第1位)开始计算,然后依次计算较低位。当输入第n个位(n<m+1)时,首先将第n+1位运算后的结果乘以2,再将第n的值(0或1)乘以232,两者相加后除以生成多项式G(x)。因此,每一位的CRC32运算就转化成了一个最高次幂为32的多项式除以一个最高次幂为32的多项式(生成多项式),结果(余数)为一个最高次幂不超过31的多项式。


五.CRC32串行计算的LFSR实现

上一节已经推导出了CRC的串行实现方法,但如何将公式六用Verilog语言表示出来呢?用Verilog描述CRC32的串行计算方法时,使用到了一种叫做LFSRLinear feedback shift register)的结构。下图为该LFSR的结构图,其中寄存器3到寄存器25没有在图中画出。

CRC算法原理及其Verilog实现 - Lucien - 技术无极-创意无限

                              图1.CRC32的串行移位寄存器实现

如图所示,各个寄存器储存着上一次CRC32运算的结果,寄存器的输出即为CRC32的值。让我们回顾一下CRC32的生成多项式:

  G(x)= 232+226+223+ 222+216+212+211+210+28+27+25+24+22+21+1

当输入新的位参与运算时,信息多项式为:

  M(x)= Mn×232

上一次CRC计算的结果为:

  Rn+1(x) = A31×231+ A30×230+ A29×229+ … + A2×22+ A1×21+ A0×1

根据上一节推导出的公式,新的CRC32Rn(x){Rn+1(x)×2 + M(x)}/ G(x)的余数。

  Q(x) = Rn+1(x)×2 + M(x),则:

  Q(x) =A31+Mn)×232+ A30×231+ A29×230+ … +A1×22+ A0×21

在计算Q(x)/G(x)的结果时,根据模2运算法则,如果A31+ Mn的结果为1,则商为1,余数为Q(x)-G(x);如果A31+ Mn的结果为0,则商为0,余数为Q(x)本身。其中,A31+ Mn是模2加法,不进位;Q(x)-G(x)2减法,不借位。

当上一个CRC32结果的最高位A31和输入的数值Mn2加法结果为1时,上一次CRC结果右移一位,完成乘2的过程,再与G(x)多项式的系数进行异或运算,完成减法。由于任何数与0异或保持不变,所以LFSR中只有在G(x)多项式为1的系数处才放置异或门。运算完毕以后把结果存入寄存器即为新的CRC32值。

当上一个CRC32结果的最高位A31和输入的数值Mn2加法结果为0时,Q(x)不够除,Q(x)本身作为余数存入寄存器,获得新的CRC32值。由于A31+ Mn的结果为0,异或门不起作用,Q(x) = A30×231+ A29×230+ … +A1×22+ A0×21,由Rn+1(x)右移一位获得, Q(x)0次幂为0,刚好把A31+ Mn的结果作为输入。


六.CRC32串行计算的Verilog实现

        根据第五节中的描述,一位数据的CRC32值为:


               crc32_new = {crc32_old[30:0],1'b0} ^ ({32{(crc32_old[31] ^ datain)}} & POLYNOMIAL) ;


       其中,crc32_old为之前存储在LFSR中的值,可以是上一次计算的结果,也可以中第一次计算时的初始值。datain表示的是新参与运算的一位数值。POLYNOMIAL是生成多项式的系数对应的二进制序列,POLYNOMIAL=32'h04C11DB7,是个常数。上述Verilog语句中,如果crc32_old[31]^datain为0,则crc32_new由crc32_old左移一位(即乘以2)后获得;如果crc32_old[31]^datain为1,在POLYNOMIAL为1的位上,{crc32_old[30:0],1'b0}与1相异或获得新的CRC32值crc32_new。此语句实现的逻辑,刚好满足CRC32的定义,是对第五节中提及的LFSR行为的描述。

求一个二进制序列的CRC32值时,可以让二进制序列的各个位依次计算CRC32,最终的结果即为二进制序列的CRC32值。例如一个长度为8的二进制序列,它的CRC32值为:

function [`CRC_WIDTH-1:0] crc_data1;

input [`CRC_WIDTH-1:0] crc;

input data1;

begin 

crc_data1={crc[`CRC_WIDTH-2:0],1'b0} ^ ({`CRC_WIDTH{(crc[`CRC_WIDTH-1]^data1)}} & POLYNOMINAL);

end

endfunction


function [`CRC_WIDTH-1:0] crc_data;

input [`INPUT_DATA_WIDTH-1:0] data;

input [`CRC_WIDTH-1:0] crc;

integer i;

begin

crc_data=crc;

for(i=0;i<=`INPUT_DATA_WIDTH-1;i=i+1) begin

crc_data=crc_data1(crc_data,data[`INPUT_DATA_WIDTH-1-i]);

end

end

endfunction


always@(posedge rst or posedge clk)

if(rst)
crc_buf<=0;
  else
crc_buf<=crc_data(data_buf,0);


七.有关Verilog和VHDL的一点感悟

以上代码使用了Verilog中的函数和for循环,硬件描述语言里的函数和for循环只是为了缩短代码量,跟软件里的思想有点不一样。在写函数和for循环的时候,应该要想一想这个在硬件电路上表现为什么,而且for循环的次数要固定,因为是要生成一个固定的电路。上面这个程序在一个时钟就可以把CRC计算出,而每次计算for循环都要用到上一次的值,刚开始我认为这个电路结构是这样的:有多少级的for循环就有多少级的组合逻辑,因为数据处理是有先后顺序的嘛。

以下是综合后的模块视图,可以看到只有两级的延迟,源程序是给8bit数据加CRC16。

这个例子让我觉得我们用硬件描述语言只是给出行为级的描述,至于呈现什么样的电路交给综合器。写出的程序看似像软件(for循环、函数),但综合器可根据描述给出最适合的结果。


Verilog:

always既可描述组合逻辑,也可以描述时序逻辑;assign只能描述组合逻辑。

always中的变量必须是reg,但赋值可以是阻塞(<=),也可以是非阻塞(=),reg信号并不只对应非阻塞,reg信号也可用阻塞产生时序逻辑,reg信号也可用非阻塞产生组合逻辑,生成时序还是组合的关键应该是always后面跟的条件以及我们如何描述电路。reg信号只表示该信号将在always中使用,并不代表该信号一定是触发器。

如下程序,表示的是移位寄存器,综合成什么样的电路不取决于变量的类型,而是取决于电路的描述,如果描述出来是个移位寄存器,不管用阻塞还是非阻塞,都会综合成所想要的电路,但并不推荐这么写。

always @(posedge clk or posedge rst) begin
if (rst) begin
// reset
datar1 = 1'd0;
datar2 = 1'd0;
end
else begin
datar2 = datar1;
datar1 = data;
end
end

感觉说了这么多也是蛮绕的,最后给出结论:

1.时序逻辑,可综合成FF

always @(posedge clk or posedge rst) begin
if (rst) begin
// 异步reset
end
else begin

//用非阻塞<=
end
end

2.组合逻辑

always @(a or b) begin
begin

q=a+b;//用阻塞=
end

3.时序加逻辑

always @(posedge clk or posedge rst) begin
if (rst) begin
// 异步reset
end
else begin

q<=a+b; //用非阻塞<=
end
end

平时我们用2、3形式比较多。




这篇关于CRC算法原理及其Verilog实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1037176

相关文章

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

golang版本升级如何实现

《golang版本升级如何实现》:本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型(范围、哈希、列表、键值),主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区(Range Partitioning1、新建分区表:2、分

MySQL 定时新增分区的实现示例

《MySQL定时新增分区的实现示例》本文主要介绍了通过存储过程和定时任务实现MySQL分区的自动创建,解决大数据量下手动维护的繁琐问题,具有一定的参考价值,感兴趣的可以了解一下... mysql创建好分区之后,有时候会需要自动创建分区。比如,一些表数据量非常大,有些数据是热点数据,按照日期分区MululbU