CRC计算流程详解和FPGA实现

一、概念

        CRC校验,中文翻译过来是:循环冗余校验,英文全称是:Cyclic Redundancy Check。是一种通过对数据产生固定位数的校验码,以检验数据是否存在错误的技术。

        其主要特点是检错能力强、开销小,易于电路实现。像网络通信上,就使用了CRC32进行数据校验。

1.1 CRC的数学基础

        其数学基础是,使用除法求余数。

        1、将K位的信息码写成如下多项式形式:\sum_{n=0}^{K-1}a_{n}x^{n}

        2、将信息码左移R位,变成如下多项式形式:\sum_{n=0}^{K-1}a_{n}x^{n+R}

        3、将移位后的信息码,除以指定的生成多项式,最后得到的余数即为CRC校验值。

        转换成二进制信息表述如下:

        1、K位的信息码,右移R位,得到新的K+R位的信息码,

        2、将新的K+R位的信息码,除以指定的二进制数,得到的余数即为CRC校验值。

        当然,此处采用的是模2运算,即没有借位。实质上在运行加减法的时候,采用的是异或运算。

1.2 其他重要概念

        CRC 校验的核心是模2除法运算,但是还存在一些其他的规则,描述如下:

        初始值:给CRC一个计算初始值,可以是0,也可以为其他值,会将待计算的信息码的值与初始值进行异或。(网上大部分关于CRC的校验计算,初始值都是默认取0,但是实际应用中,比如CRC32,其初始值是0xFFFFFFFF)

        结果异或值:将计算结果与结果异或值进行异或运算后输出,目的是防止全0数据的CRC一直为0,

        数据反转:CRC中数据 反转,指的是一个字节的数据中,高bit变低bit,低bit变高bit。 比如0x55,经过数据反转后,变为0xAA。

        生成多项式:模2除法中的除数,根据多项式可以生成二进制除数,不同的CRC校验有不同的多项式。

1.3 CRC校验的标准流程

        1、初始值赋值给crc_reg;

        2、判断信息码是否需要反转,若需要则进行数据反转,不需要则保持不变,结果赋值给crc_reg;

        3、信息码(或者反转后的信息码)左移R位,即信息码后面补上R个二进制的0;(R为校验码的位宽,同时也是生成多项式的最高次幂)

        4、crc_reg与补0后的信息码(高位)进行异或运算,并赋值给crc_reg;

        5、crc_reg与信息码进行模2除法运算,运算的余数结果赋值给crc_reg;

        6、判断输出结果是否需要反转,若需要则进行数据反转,不需要则保持不变,结果赋值给crc_reg;

        7、crc_reg与结果异或值进行异或运算,得到最终的校验值。

二、CRC32

2.1 CRC32相关信息

        最近在考虑使用FPGA实现UDP协议,就研究到了CRC32校验,像赛灵思提供的MAC核内部就实现了CRC32校验方式。于是我就抱着学习的态度,研究了一下CRC32。关于CRC8、CRC16等等其余的CRC校验方式,此处就不赘述了。

        CRC32校验里面提到了几个概念:

1、生成多项式(generator polynomial)

        CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1。

        二进制可以表示为33'b1_0000_0100_1100_0001_0001_1101_1011_0111。

        十六进制表示为32‘h104C11DB7。

        生成多项式,即为除数。

2、待校验的数据

        待校验的数据即为被除数,即上面描述的信息码。

        最终获得的结果,即为CRC校验值。

2.2 CRC32校验流程

具体的操作流程:

  1、初始值赋值给crc_reg;

 2、判断信息码是否需要反转,若需要则进行数据反转,不需要则保持不变,结果赋值给crc_reg;

3、信息码(或者反转后的信息码)左移32位,即信息码后面补上32个二进制的0;

4、crc_reg与补0后的信息码(高32位)进行异或运算,并赋值给crc_reg;

 5、crc_reg与信息码进行模2除法运算,运算的余数结果赋值给crc_reg;

 6、判断输出结果是否需要反转,若需要则进行数据反转,不需要则保持不变,结果赋值给crc_reg;

7、crc_reg与结果异或值进行异或运算,得到最终的校验值。

        按照C语言编写了此CRC32校验流程,在VScode中进行测试。设置不同的反转信息、初始值、结果异或值,输出结果与CRC计算工具相一致。

CRC计算器工具:

CRC(循环冗余校验)在线计算_ip33.comicon-default.png?t=N7T8http://www.ip33.com/crc.html

//8位数据反转
uint8_t invertuint8(uint8_t data) 
{
    uint8_t tmp;
    tmp = 0;

    for(int i = 0; i<8;i++){
        if(data & (1<<i) ){
            tmp |= 1<< (7-i);
        }
    }

    return tmp;
}

//32位数据反转
uint32_t invertuint32(uint32_t data)
{
    uint32_t tmp;
    tmp = 0;

    for(int i = 0; i<32;i++){
        if(data &(1<<i) ){
            tmp |= 1<< (31-i);
        }
    }

    return tmp;
}


uint32_t CRC32(uint8_t& data)
{
    uint8_t in_reverse_en = 1; //输入数据是否反转
    uint8_t out_reverse_en = 1;//输出数据是否反转



    uint32_t poly = 0x04C11DB7; //生成多项式0x1_04C11DB7 ,仅取低32位,最高为1通过左移直接处理
    uint32_t init_value = 0xFFFFFFFF;//初始值
    uint32_t out_xor_value = 0xFFFFFFFF;//结果异或值

    uint32_t crc_reg;
    uint32_t data_reg;
    uint32_t data_shift;

//第一步,赋初值
    crc_reg = init_value;
//第二步,输入是否反转
    if(in_reverse_en == 1)
        data_reg = invertuint8(data);
    else    
        data_reg = data;
    printf("data:%x\n",data);
    printf("data_reg:%x\n",data_reg);

//第三步,信息码左移32位,赋值。由于字宽限制,仅左移24位,实际上8次移位异或运算后,其余数与原有运算相一致。
    data_shift = (data_reg <<24);
//第四步,初始值与数据异或操作
    crc_reg = crc_reg ^ data_shift;
//第五步,模2除法
    for(int i=0;i<8;i++){
        if(crc_reg & 0x80000000)//最高位是1时
            crc_reg = (crc_reg << 1) ^ poly; //左移将生成多项式的第32bits处理掉,相当于异或
        else
            crc_reg = crc_reg << 1;
    }
//
//第六步,输出是否反转

    if(out_reverse_en == 1)
        crc_reg = invertuint32(crc_reg);
//第七步,与结果异或值进行异或运算

    crc_reg = crc_reg^out_xor_value;


    return crc_reg;
}


int main(int argc, char *argv[])
{

    uint8_t data = 0x55;
    uint32_t CRC_result;


    CRC_result = CRC32(data);

    printf("CRC_result:%x\n",CRC_result);

    getchar();

    return 0;
}

       

三、CRC32的FPGA实现

         原理已经清楚了,按照上述流程就可以实现CRC32。但是FPGA有更简易的实现形式。就属于找规律的范畴了。对于CRC32,上一个校验值(或者初始值)进行CRC校验的时候,CRC校验的单个bits的校验结果固定与上一个校验值的某几个bits有关。

        所以可以直接采用bit运算的方式输出CRC校验结果。具体找规律这里不再分析,直接上示例代码(正点原子的代码)。也有现成的CRC FPGA代码生成工具,可以直接调用。

CRC代码生成工具一:Easics CRC Toolicon-default.png?t=N7T8http://crctool.easics.be/

CRC代码生成工具二:OutputLogic.com » CRC Generatoricon-default.png?t=N7T8http://outputlogic.com/?page_id=321

module crc32_d8(
    input                 clk     ,  //时钟信号
    input                 rst_n   ,  //复位信号,低电平有效
    input         [7:0]   data    ,  //输入待校验8位数据
    input                 crc_en  ,  //crc使能,开始校验标志
    input                 crc_clr ,  //crc数据复位信号            
    output   reg  [31:0]  crc_data,  //CRC校验数据
    output        [31:0]  crc_next   //CRC下次校验完成数据
    );

//*****************************************************
//**                    main code
//*****************************************************

//输入待校验8位数据,需要先将高低位互换
wire    [7:0]  data_t;

assign data_t = {data[0],data[1],data[2],data[3],data[4],data[5],data[6],data[7]};

//CRC32的生成多项式为:G(x)= x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 
//+ x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x^1 + 1

assign crc_next[0] = crc_data[24] ^ crc_data[30] ^ data_t[0] ^ data_t[6];
assign crc_next[1] = crc_data[24] ^ crc_data[25] ^ crc_data[30] ^ crc_data[31] 
                     ^ data_t[0] ^ data_t[1] ^ data_t[6] ^ data_t[7];
assign crc_next[2] = crc_data[24] ^ crc_data[25] ^ crc_data[26] ^ crc_data[30] 
                     ^ crc_data[31] ^ data_t[0] ^ data_t[1] ^ data_t[2] ^ data_t[6] 
                     ^ data_t[7];
assign crc_next[3] = crc_data[25] ^ crc_data[26] ^ crc_data[27] ^ crc_data[31] 
                     ^ data_t[1] ^ data_t[2] ^ data_t[3] ^ data_t[7];
assign crc_next[4] = crc_data[24] ^ crc_data[26] ^ crc_data[27] ^ crc_data[28] 
                     ^ crc_data[30] ^ data_t[0] ^ data_t[2] ^ data_t[3] ^ data_t[4] 
                     ^ data_t[6];
assign crc_next[5] = crc_data[24] ^ crc_data[25] ^ crc_data[27] ^ crc_data[28] 
                     ^ crc_data[29] ^ crc_data[30] ^ crc_data[31] ^ data_t[0] 
                     ^ data_t[1] ^ data_t[3] ^ data_t[4] ^ data_t[5] ^ data_t[6] 
                     ^ data_t[7];
assign crc_next[6] = crc_data[25] ^ crc_data[26] ^ crc_data[28] ^ crc_data[29] 
                     ^ crc_data[30] ^ crc_data[31] ^ data_t[1] ^ data_t[2] ^ data_t[4] 
                     ^ data_t[5] ^ data_t[6] ^ data_t[7];
assign crc_next[7] = crc_data[24] ^ crc_data[26] ^ crc_data[27] ^ crc_data[29] 
                     ^ crc_data[31] ^ data_t[0] ^ data_t[2] ^ data_t[3] ^ data_t[5] 
                     ^ data_t[7];
assign crc_next[8] = crc_data[0] ^ crc_data[24] ^ crc_data[25] ^ crc_data[27] 
                     ^ crc_data[28] ^ data_t[0] ^ data_t[1] ^ data_t[3] ^ data_t[4];
assign crc_next[9] = crc_data[1] ^ crc_data[25] ^ crc_data[26] ^ crc_data[28] 
                     ^ crc_data[29] ^ data_t[1] ^ data_t[2] ^ data_t[4] ^ data_t[5];
assign crc_next[10] = crc_data[2] ^ crc_data[24] ^ crc_data[26] ^ crc_data[27] 
                     ^ crc_data[29] ^ data_t[0] ^ data_t[2] ^ data_t[3] ^ data_t[5];
assign crc_next[11] = crc_data[3] ^ crc_data[24] ^ crc_data[25] ^ crc_data[27] 
                     ^ crc_data[28] ^ data_t[0] ^ data_t[1] ^ data_t[3] ^ data_t[4];
assign crc_next[12] = crc_data[4] ^ crc_data[24] ^ crc_data[25] ^ crc_data[26] 
                     ^ crc_data[28] ^ crc_data[29] ^ crc_data[30] ^ data_t[0] 
                     ^ data_t[1] ^ data_t[2] ^ data_t[4] ^ data_t[5] ^ data_t[6];
assign crc_next[13] = crc_data[5] ^ crc_data[25] ^ crc_data[26] ^ crc_data[27] 
                     ^ crc_data[29] ^ crc_data[30] ^ crc_data[31] ^ data_t[1] 
                     ^ data_t[2] ^ data_t[3] ^ data_t[5] ^ data_t[6] ^ data_t[7];
assign crc_next[14] = crc_data[6] ^ crc_data[26] ^ crc_data[27] ^ crc_data[28] 
                     ^ crc_data[30] ^ crc_data[31] ^ data_t[2] ^ data_t[3] ^ data_t[4]
                     ^ data_t[6] ^ data_t[7];
assign crc_next[15] =  crc_data[7] ^ crc_data[27] ^ crc_data[28] ^ crc_data[29]
                     ^ crc_data[31] ^ data_t[3] ^ data_t[4] ^ data_t[5] ^ data_t[7];
assign crc_next[16] = crc_data[8] ^ crc_data[24] ^ crc_data[28] ^ crc_data[29] 
                     ^ data_t[0] ^ data_t[4] ^ data_t[5];
assign crc_next[17] = crc_data[9] ^ crc_data[25] ^ crc_data[29] ^ crc_data[30] 
                     ^ data_t[1] ^ data_t[5] ^ data_t[6];
assign crc_next[18] = crc_data[10] ^ crc_data[26] ^ crc_data[30] ^ crc_data[31] 
                     ^ data_t[2] ^ data_t[6] ^ data_t[7];
assign crc_next[19] = crc_data[11] ^ crc_data[27] ^ crc_data[31] ^ data_t[3] ^ data_t[7];
assign crc_next[20] = crc_data[12] ^ crc_data[28] ^ data_t[4];
assign crc_next[21] = crc_data[13] ^ crc_data[29] ^ data_t[5];
assign crc_next[22] = crc_data[14] ^ crc_data[24] ^ data_t[0];
assign crc_next[23] = crc_data[15] ^ crc_data[24] ^ crc_data[25] ^ crc_data[30] 
                      ^ data_t[0] ^ data_t[1] ^ data_t[6];
assign crc_next[24] = crc_data[16] ^ crc_data[25] ^ crc_data[26] ^ crc_data[31] 
                      ^ data_t[1] ^ data_t[2] ^ data_t[7];
assign crc_next[25] = crc_data[17] ^ crc_data[26] ^ crc_data[27] ^ data_t[2] ^ data_t[3];
assign crc_next[26] = crc_data[18] ^ crc_data[24] ^ crc_data[27] ^ crc_data[28] 
                      ^ crc_data[30] ^ data_t[0] ^ data_t[3] ^ data_t[4] ^ data_t[6];
assign crc_next[27] = crc_data[19] ^ crc_data[25] ^ crc_data[28] ^ crc_data[29] 
                      ^ crc_data[31] ^ data_t[1] ^ data_t[4] ^ data_t[5] ^ data_t[7];
assign crc_next[28] = crc_data[20] ^ crc_data[26] ^ crc_data[29] ^ crc_data[30] 
                      ^ data_t[2] ^ data_t[5] ^ data_t[6];
assign crc_next[29] = crc_data[21] ^ crc_data[27] ^ crc_data[30] ^ crc_data[31] 
                      ^ data_t[3] ^ data_t[6] ^ data_t[7];
assign crc_next[30] = crc_data[22] ^ crc_data[28] ^ crc_data[31] ^ data_t[4] ^ data_t[7];
assign crc_next[31] = crc_data[23] ^ crc_data[29] ^ data_t[5];

always @(posedge clk or negedge rst_n) begin
    if(!rst_n)
        crc_data <= 32'hff_ff_ff_ff;
    else if(crc_clr)                             //CRC校验值复位
        crc_data <= 32'hff_ff_ff_ff;
    else if(crc_en)
        crc_data <= crc_next;
	else;
end

endmodule

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/482598.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【prompt六】MaPLe: Multi-modal Prompt Learning

1.motivation 最近的CLIP适应方法学习提示作为文本输入,以微调下游任务的CLIP。使用提示来适应CLIP(语言或视觉)的单个分支中的表示是次优的,因为它不允许在下游任务上动态调整两个表示空间的灵活性。在这项工作中,我们提出了针对视觉和语言分支的多模态提示学习(MaPLe),以…

“架构(Architecture)” 一词的定义演变历史(依据国际标准)

深入理解“架构”的客观含义&#xff0c;不仅能使IT行业的系统架构设计师提升思想境界&#xff0c;对每一个积极的社会行动者而言&#xff0c;也具有长远的现实意义&#xff0c;因为&#xff0c;“架构”一词&#xff0c;不只限于IT系统&#xff0c;而是指各类系统(包括社会系统…

python(django)之流程接口管理后台开发

1、在models.py中加入流程接口表和单一接口表 代码如下&#xff1a; from django.db import models from product.models import Product# Create your models here.class Apitest(models.Model):apitestname models.CharField(流程接口名称, max_length64)apitester model…

C#,图论与图算法,计算图(Graph)的岛(Island)数量的算法与源程序

1 孤岛数 给定一个布尔矩阵,求孤岛数。一组相连的1形成一个岛。例如,下面的矩阵包含5个岛: 在讨论问题之前,让我们先了解什么是连接组件。无向图的连通分量是一个子图,其中每两个顶点通过一条路径相互连接,并且不与子图外的其他顶点连接。 所有顶点相互连接的图只有一个…

java数据结构与算法基础-----字符串------正则表达式---持续补充中

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 目前校招的面试&#xff0c;经常会遇到各种各样的有关字符串处理的算法。掌…

【docker系列】深入理解 Docker 容器管理与清理

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

JVM——运行时数据区

前言 由于JAVA程序是交由JVM执行的&#xff0c;所以我们所说的JAVA内存区域划分也是指的JVM内存区域划分&#xff0c;JAVA程序具体执行的过程如下图所示。首先Java源代码文件会被Java编译器编译为字节码文件&#xff0c;然后由JVM中的类加载器加载各个类的字节码文件&#xff0…

解决win10安装软件提示Microsoft Store界面

解决方法 1. 打开设置&#xff0c;找到应用 2. 应用与功能&#xff0c;选择任何来源

Day18:LeedCode 513.找树左下角的值 112. 路径总和 106.从中序与后序遍历序列构造二叉树

513. 找树左下角的值 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 思路:出该二叉树的 最底层 最左边 节点的值找出深度最大的第一个结点(左结点先遍历) 方法一…

【数据挖掘】实验5:数据预处理(1)

实验5&#xff1a;数据预处理&#xff08;1&#xff09; 一&#xff1a;实验目的与要求 1&#xff1a;熟悉和掌握数据预处理&#xff0c;学习数据清洗、数据集成、数据变换、数据规约、R语言中主要数据预处理函数。 二&#xff1a;实验内容 【缺失值分析】 第一步&#xff1…

java selenium 元素点击不了

最近做了一个页面爬取&#xff0c;很有意思被机缘巧合下解决了。 这个元素很奇怪&#xff0c;用xpath可以定位元素&#xff0c;但是就是click()不了。 试过了网上搜的一些办法&#xff1a; //尝试一 WebElement a_tag driver.findElement(By.xpath("xxx")); a_tag…

【SysBench】OLTP 基准测试示例

前言 本文采用 MySQL 沙盒实例作为测试目标&#xff0c;使用 sysbench-1.20 对其做 OLTP 基准测试。 有关 MySQL 沙盒的更多信息&#xff0c;请参阅 玩转 MySQL Shell 沙盒实例&#xff0c;【MySQL Shell】6.8 AdminAPI MySQL 沙盒 。 1、部署一个 MySQL 沙盒实例 使用 mysq…

云计算 3月18号 (mysql安装及操作)

一、Mysql 1.1 MySQL数据库介绍 1.1.1 什么是数据库DB&#xff1f; DB的全称是database&#xff0c;即数据库的意思。数据库实际上就是一个文件集合&#xff0c;是一个存储数据的仓库&#xff0c;数据库是按照特定的格式把数据存储起来&#xff0c;用户可以对存储的数据进行…

mac 安装 nvm 【真解决问题】

前提 没有node环境已有git 下载 我用的gitee极速下载 git clone https://gitee.com/mirrors/nvm.git ~/.nvm && cd ~/.nvm && git checkout git describe --abbrev0 --tags配置 1. 配置变量 在用户的目录下新增文件 .zshrc export NVM_DIR"$HOME/…

[数据结构]二叉树(下)

一、二叉树的节点和深度关系 1.满二叉树 我们可以假设二叉树有N个节点&#xff0c;深度为h我们可以恒容易得到满二叉树每行的节点数&#xff0c;然后错位相减,算出节点与高度的关系。 2.完全二叉树 注意我这个是因为最后一行的节点数为1。 二、向上调整建堆和向下调整建堆的时…

【Node.js】CSR、SSR、SEO

SSR 和 CSR SSR &#xff08;Server-Side Rendering&#xff09;服务端渲染&#xff0c;请求数据和拼装都在服务端完成&#xff0c;相当于在服务端直接完成html。 而 Vue,react 等框架&#xff0c;是在客户端完成渲染拼接的&#xff0c;属于CSR&#xff08;Client-Side Rende…

Linux/openEuler系统部署spring boot+vue前后端分离项目(nginx均衡代理)

Linux/openEuler系统部署spring bootvue前后端分离项目&#xff08;nginx均衡代理&#xff09; 1、系统环境准备&#xff0c;安装openjdk和nginx还有MySQL&#xff0c;咱们本文先连接主机mysql进行登录&#xff08;linux上的mysql服务可以先不安装&#xff09; 可以看我前面的…

【神经网络】得分函数,损失函数~

目录 引言 一、神经网络概述 1 定义 2 基本原理 二、得分函数 1 定义 2 应用方法 3 与神经网络 三、损失函数 1 定义 2实现方法 3 与神经网络 四、得分函数与损失函数的协同作用 1 关系 2 实际应用 六、代码事例 &#xfffc;、总结与展望 引言 在人工智能与机…

40 openlayers setCenter 之后 绘制了Overlay 地图定位异常

前言 这是之前在 生产环境碰到的一个问题 这个其实就是 业务上一个地图点击点位展示详情, 然后再点击另外一个点位 展示详情, 切换中心店的这个过程 其主要的问题是 使用 openlayers 的 Map.View.setCenter() 了之后, 整个地图的中心点切换到了一个莫名其妙的地方 然后 经…

Linux的学习之路:2、基础指令(1)

一、ls指令 上篇文章已经说了一点点的ls指令&#xff0c;不过那还是不够的&#xff0c;这篇文章会介绍更多的指令&#xff0c;最起码能使用命令行进行一些简单的操作&#xff0c;下面开始介绍了 ls常用选项 -a 列出目录下的所有文件&#xff0c;包括以 . 开头的隐含文件。 -d…