并行CRC—Verilog代码实现

2023-11-12

在线crc代码代码生成:http://outputlogic.com/
该网站提供的crc并行算法原理:http://outputlogic.com/?p=158

假设crc位宽为N,即生成多项式的最高次幂为N;假设并行数据D宽度为M。
crc并行计算可粗略的表述为(实际所有都是异或):
在这里插入图片描述
重点在与得到 crc系数矩阵AData系数矩阵B
特别说明:系数矩阵中元素为1表示该项参与异或,为0表示不参与异或(任何数据与自身异或都为零),为偶数同理(因此可取模2简化表述)。

1.构造系数方阵F

根据生成多项式G(x)构造系数N×N方阵F
在这里插入图片描述
其中E为N-1维单位阵。
以生成多项式为G=x5+x2+1的crc-5为例,G可表示为100101,省去最高项为00101,则F为:
在这里插入图片描述

2.计算CRC系数

求F的M次方FM(方阵乘法)再取模二,所得即为并行代码中的crc系数。
以N=5为例,矩阵与系数的对应关系如下:
也可以先对结果旋转,使C的序号和矩阵脚标序号对应,下图表示的是最初始的方阵乘法结果
在这里插入图片描述

3.计算DATA系数

求F的N次方FN(方阵乘法)再取模二,所得即为并行代码中的data系数。不过该系数中只有后面几列用得上,后续细说。

  1. 如果N=M,则Step2和Step3中的结果直接用:
    在这里插入图片描述
  2. 如果N>M,此为大多数应用场景,则D的系数为Step3结果的后M列:
    承上N=5,假设M=4,则D的系数如下:
    标灰色的部分不使用
    在这里插入图片描述
  3. 如果N<M,按实际M值计算:
    1. 如N<M<2N,则还需计算F2M
    2. 如2N<M<3N,则还需计算F2M和F3M
    3. 其他类推。
      承上N=5,假设M=8,并则将F5记为F1(黄色)、F10记为F2(蓝色和灰色),则D的系数与F1、F2的关系如下:
      在这里插入图片描述

3.1.DATA系数真相

如果仔细观察F的结构会发现每多乘一次,上一次获得的列就往后移一次。因此事实上:
F(:,0)就是D[0]列的系数;
F2(:,0)是D[1]列的系数,F2(:,1)是D[0]的系数;
F3(:,0)是D[2]列的系数,F3(:,1)是D[1]的系数,F3(:,2)是D[0]的系数;
以此类推。

4.合并系数

将Step2和Step3的C系数和D系数整合,所有的数值都相异或。

写个matlab函数用于获取两个系数矩阵,如下:

function [b1,b3] = CrcCoefByCC(N,G)
% N;                   %数据位宽
% G; 				   %生成多项式
M=size(G,2);           %生成多项式位宽(最高次)

%% 构造F
F=zeros(M,M);
for i=1:M-1
    F(i,i+1)=1;
end
F(:,1)=G;

%% Cin系数
b1=mod(F^N,2);

%% D系数
x=ceil(N/M);            %向上取整
b2=zeros(M,M*x);        %D系数初值[ F^(xM) , ... , F^(2M) , F^M ]
for i=1:x
    b2(:,(x-i)*M+1:(x-i+1)*M)=mod(F^(i*M),2);
end
b3=b2(:,M*x-N+1:M*x);   %D系数:取后N列,与D位宽N对应

%% D系数另一种算法:每次取第一列
for i=1:N
    bb=mod(F^i,2);
    b4(:,N-i+1)=tcc(:,1);
end

end

5.验证

http://outputlogic.com/ 网址中生成的代码为准进行验证。

  1. crc5 = x5+x2+1 data width =4:
    在这里插入图片描述结果:
    在这里插入图片描述
    matlab系数计算结果:
    因为该网站生成结果小序号在前,因此为对比方便对结果进行了旋转:
%% 旋转,小序号在前、在上
b1=rot90(rot90(b1));
b3=rot90(rot90(b3));

在这里插入图片描述2. crc5= x5+x2+1,data width = 13:

在这里插入图片描述3. 常用的crc31,篇幅过大不放了,也经过了验证。

6.其他选项

包括输入翻转、预设初值、输出翻转,这些都是可选项,可增强算法的检错能力。
参看crc caculator中的设置:
在这里插入图片描述

6.1输入翻转

是指将输入值在字节内进行bit反转(换序),同时字节间保持原序。
进行输入反转时,仅影响Data的系数,有两种方法完成此操作。

  1. 在对Data的系数计算完成后,对结果里面的Data系数翻转。

  2. 在Data被使用前,进行字节内的bit位置反转操作。
    以输入为16bit为例:
    assign data1={din[8],din[9],din[10],din[11],din[12],din[13],din[14],din[15],din[0],din[1],din[2],din[3],din[4],din[5],din[6],din[7]};

6.2预设初值

即在进行第一次crc运算前,预先设定Cin项初值,默认情况下为全零,如802.3中使用的crc32的预设初值为32’hFFFFFFFF。

6.3输出翻转+取反

在输出至端口时,对计算得到的crc进行全bit位的换序和取反
以crc-16为例:
assign crc_out = ~ { crc_new[0], crc_new[1], crc_new[2], crc_new[3], crc_new[4], crc_new[5], crc_new[6], crc_new[7],
crc_new[8], crc_new[9], crc_new[10], crc_new[11], crc_new[12], crc_new[13], crc_new[14], crc_new[15]};

7.Matlab生成并行crc代码(不计算)

再改改,添加格式输出,将生成多项式输入方式改为Hex。
需要注意的是生成多项式的最高位因为必然为1,因此常常被省略,如crc5=1+x2+x5,最高次为5,也就是共6位(即100101),但通常都省略掉最高位,记为00101。

function [crc_str_mid,crc_str_rlt] = CrcCoefByCC(N,FI,datain,G,M,crcin,FO,XOR)
% N;数据位宽
% M:生成多项式位宽(不包含最高项)
% G:生成多项式(省略最高项)
% FI:1,输入翻转(字节内)
% FO:1,输出取反且翻转
% crc_str_mid:中间输出,与输出选项FO无关,用于下轮计算
% crc_str_out:结果输出,与输出选项FO有关
% N=8;M=32;G='04c11db7';FI=0;FO=0;XOR=0;
% datain='b';
% crcin='5C86227B';%12的中间结果
cc     = str2num(reshape(dec2bin(hex2dec(G),M),M,1));       %高位在前
crcin  = str2num(reshape(dec2bin(hex2dec(crcin),M),M,1));   %高位在前
datain = str2num(reshape(dec2bin(hex2dec(datain),N),N,1));  %高位在前 十六进制
% datain = str2num(reshape(dec2bin(datain,N),N,1));  %高位在前 十进制
%% 构造F
F=zeros(M,M);
for i=1:M-1
    F(i,i+1)=1;
end
F(:,1)=cc;
%% Cin系数
ct=mod(F^N,2);
%% D系数
% % D系数计算方法一:一次性计算M列
% x=ceil(N/M);            %向上取整
% b2=zeros(M,M*x);        %D系数初值[ F^(xM) , ... , F^(2M) , F^M ]
% for i=1:x
%     b2(:,(x-i)*M+1:(x-i+1)*M)=mod(F^(i*M),2);
% end
% tc1=zeros(M,N);
% tc1=b2(:,M*x-N+1:M*x);   %D系数:取后N列,对应D位宽N
% D系数另一种算法:每次取一列
tc2=zeros(M,N);
for i=1:N
    tcc=mod(F^i,2);
    tc2(:,N-i+1)=tcc(:,1);
end
%% crc计算
% datain必须为字节单位,不够则高位自动补零
x=ct*crcin;

if FI==1
    datain=flipud(datain);  % 输入上下翻转
end
y=tc2*datain;
crc_mid = mod(x+y,2);       % 中间值,用于下一次计算
crc_rlt = crc_mid;          % 输出结果,根据输出选项

if XOR==1
    crc_rlt=~crc_rlt;
end
if FO==1
    crc_rlt=flipud(crc_rlt);% 输出上下翻转
end

crc_str_mid ='';
crc_str_rlt ='';
for i=1:M
    crc_str_mid  = strcat(crc_str_mid, sprintf('%d',crc_mid(i))); %转为2进制字符串
    crc_str_rlt  = strcat(crc_str_rlt, sprintf('%d',crc_rlt(i))); %转为2进制字符串
end
crc_str_mid=dec2hex(bin2dec(crc_str_mid),M/4);%转为16进制字符串
crc_str_rlt=dec2hex(bin2dec(crc_str_rlt),M/4);%转为16进制字符串

%% 输出verilog代码,仅计算则注释掉
t1='';
[gc,~]=find(flipud(cc)==1);
for i=2:size(gc)
    t1=strcat(t1,sprintf('+x^%d',gc(i)-1));
end
cct=strcat(sprintf('// CRC module for data[%d:0] \tcrc[%d:0]=1',N-1,M-1),t1);
dlmwrite('crc.txt',cct,'delimiter','');
for i=1:M
    t2='';
    t3='';
    for j=1:M
        if ct(M+1-i,M+1-j)==1
            t2=strcat(t2,sprintf('Cin[%d]^',j-1));
        end
    end
    for j=1:N
        if tc2(M+1-i,N+1-j)==1
            if FI==1
                t3=strcat(t3,sprintf('D[%d]^',N+1-j-1));
            else
                t3=strcat(t3,sprintf('D[%d]^',j-1));
            end
        end
    end
    cct=strcat(sprintf('assign Cout[%d]=',i-1),t2,t3);
    cct=strcat(cct(1:size(cct,2)-1),';');
    dlmwrite('crc.txt',cct,'-append','delimiter','');
end

end

8.常见crc

场景 位数 多项式 多项式简写 省略最高位简写
crc-5 usb2.0 5 x5+x2+1 0x25 0x05
crc-8 8 x8+x2+x+1 0x107 0x07
crc-16 usb2.0 16 x16+x15+x2+1 0x18005 0x8005
crc-32 802.3 32 x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 0x104c11db7 0x04c11db7

9.附crc32源码

crc32常用于网络报文的校验

// CRC module for
//       data(7:0)
//       crc(31:0)=1+x^1+x^2+x^4+x^5+x^7+x^8+x^10+x^11+x^12+x^16+x^22+x^23+x^26+x^32;
//       输出翻转+取反
//       输入翻转
//       预设初值

module crc_byte(
	input           clock,
	input           reset,
	input           crc_en,
	input   [7:0]   data_in,
	output  [31:0]  data_out
);
//
//    Internal Declaration
//
	reg     [31:0]  r_q;
	wire    [31:0]  r_c;
//
//    Main Block
//
// 输出翻转
assign  data_out = ~{r_q[0], r_q[1], r_q[2], r_q[3], r_q[4], r_q[5], r_q[6], r_q[7],
					r_q[8], r_q[9], r_q[10], r_q[11], r_q[12], r_q[13], r_q[14], r_q[15],
					r_q[16], r_q[17], r_q[18], r_q[19], r_q[20], r_q[21], r_q[22], r_q[23],
					r_q[24], r_q[25], r_q[26], r_q[27], r_q[28], r_q[29], r_q[30], r_q[31]};
					
// 根据输入反转要求,已改变以下Data序号
// assign  r_c[0]  = r_q[24] ^ r_q[30] ^ data_in[0] ^ data_in[6];	// 无输入翻转
assign  r_c[0]  = r_q[24] ^ r_q[30] ^ data_in[7] ^ data_in[1];		// 输入翻转:0 7互换 1 6互换
assign  r_c[1]  = r_q[24] ^ r_q[25] ^ r_q[30] ^ r_q[31] ^ data_in[7] ^ data_in[6] ^ data_in[1] ^ data_in[0];
assign  r_c[2]  = r_q[24] ^ r_q[25] ^ r_q[26] ^ r_q[30] ^ r_q[31] ^ data_in[7] ^ data_in[6] ^ data_in[5] ^ data_in[1] ^ data_in[0];
assign  r_c[3]  = r_q[25] ^ r_q[26] ^ r_q[27] ^ r_q[31] ^ data_in[6] ^ data_in[5] ^ data_in[4] ^ data_in[0];
assign  r_c[4]  = r_q[24] ^ r_q[26] ^ r_q[27] ^ r_q[28] ^ r_q[30] ^ data_in[7] ^ data_in[5] ^ data_in[4] ^ data_in[3] ^ data_in[1];
assign  r_c[5]  = r_q[24] ^ r_q[25] ^ r_q[27] ^ r_q[28] ^ r_q[29] ^ r_q[30] ^ r_q[31] ^ data_in[7] ^ data_in[6] ^ data_in[4] ^ data_in[3] ^ data_in[2] ^ data_in[1] ^ data_in[0];
assign  r_c[6]  = r_q[25] ^ r_q[26] ^ r_q[28] ^ r_q[29] ^ r_q[30] ^ r_q[31] ^ data_in[6] ^ data_in[5] ^ data_in[3] ^ data_in[2] ^ data_in[1] ^ data_in[0];
assign  r_c[7]  = r_q[24] ^ r_q[26] ^ r_q[27] ^ r_q[29] ^ r_q[31] ^ data_in[7] ^ data_in[5] ^ data_in[4] ^ data_in[2] ^ data_in[0];
assign  r_c[8]  = r_q[0] ^ r_q[24] ^ r_q[25] ^ r_q[27] ^ r_q[28] ^ data_in[7] ^ data_in[6] ^ data_in[4] ^ data_in[3];
assign  r_c[9]  = r_q[1] ^ r_q[25] ^ r_q[26] ^ r_q[28] ^ r_q[29] ^ data_in[6] ^ data_in[5] ^ data_in[3] ^ data_in[2];
assign  r_c[10] = r_q[2] ^ r_q[24] ^ r_q[26] ^ r_q[27] ^ r_q[29] ^ data_in[7] ^ data_in[5] ^ data_in[4] ^ data_in[2];
assign  r_c[11] = r_q[3] ^ r_q[24] ^ r_q[25] ^ r_q[27] ^ r_q[28] ^ data_in[7] ^ data_in[6] ^ data_in[4] ^ data_in[3];
assign  r_c[12] = r_q[4] ^ r_q[24] ^ r_q[25] ^ r_q[26] ^ r_q[28] ^ r_q[29] ^ r_q[30] ^ data_in[7] ^ data_in[6] ^ data_in[5] ^ data_in[3] ^ data_in[2] ^ data_in[1];
assign  r_c[13] = r_q[5] ^ r_q[25] ^ r_q[26] ^ r_q[27] ^ r_q[29] ^ r_q[30] ^ r_q[31] ^ data_in[6] ^ data_in[5] ^ data_in[4] ^ data_in[2] ^ data_in[1] ^ data_in[0];
assign  r_c[14] = r_q[6] ^ r_q[26] ^ r_q[27] ^ r_q[28] ^ r_q[30] ^ r_q[31] ^ data_in[5] ^ data_in[4] ^ data_in[3] ^ data_in[1] ^ data_in[0];
assign  r_c[15] = r_q[7] ^ r_q[27] ^ r_q[28] ^ r_q[29] ^ r_q[31] ^ data_in[4] ^ data_in[3] ^ data_in[2] ^ data_in[0];
assign  r_c[16] = r_q[8] ^ r_q[24] ^ r_q[28] ^ r_q[29] ^ data_in[7] ^ data_in[3] ^ data_in[2];
assign  r_c[17] = r_q[9] ^ r_q[25] ^ r_q[29] ^ r_q[30] ^ data_in[6] ^ data_in[2] ^ data_in[1];
assign  r_c[18] = r_q[10] ^ r_q[26] ^ r_q[30] ^ r_q[31] ^ data_in[5] ^ data_in[1] ^ data_in[0];
assign  r_c[19] = r_q[11] ^ r_q[27] ^ r_q[31] ^ data_in[4] ^ data_in[0];
assign  r_c[20] = r_q[12] ^ r_q[28] ^ data_in[3];
assign  r_c[21] = r_q[13] ^ r_q[29] ^ data_in[2];
assign  r_c[22] = r_q[14] ^ r_q[24] ^ data_in[7];
assign  r_c[23] = r_q[15] ^ r_q[24] ^ r_q[25] ^ r_q[30] ^ data_in[7] ^ data_in[6] ^ data_in[1];
assign  r_c[24] = r_q[16] ^ r_q[25] ^ r_q[26] ^ r_q[31] ^ data_in[6] ^ data_in[5] ^ data_in[0];
assign  r_c[25] = r_q[17] ^ r_q[26] ^ r_q[27] ^ data_in[5] ^ data_in[4];
assign  r_c[26] = r_q[18] ^ r_q[24] ^ r_q[27] ^ r_q[28] ^ r_q[30] ^ data_in[7] ^ data_in[4] ^ data_in[3] ^ data_in[1];
assign  r_c[27] = r_q[19] ^ r_q[25] ^ r_q[28] ^ r_q[29] ^ r_q[31] ^ data_in[6] ^ data_in[3] ^ data_in[2] ^ data_in[0];
assign  r_c[28] = r_q[20] ^ r_q[26] ^ r_q[29] ^ r_q[30] ^ data_in[5] ^ data_in[2] ^ data_in[1];
assign  r_c[29] = r_q[21] ^ r_q[27] ^ r_q[30] ^ r_q[31] ^ data_in[4] ^ data_in[1] ^ data_in[0];
assign  r_c[30] = r_q[22] ^ r_q[28] ^ r_q[31] ^ data_in[3] ^ data_in[0];
assign  r_c[31] = r_q[23] ^ r_q[29] ^ data_in[2];

always @(posedge clock) begin
	if (reset)
		r_q <= 32'hFFFFFFFF;		// 预设初值
	else if (crc_en == 1'b1)
		r_q <= r_c;
end

endmodule
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

并行CRC—Verilog代码实现 的相关文章

  • LM5118 DC-DC电源降压芯片带载能力不够问题

    1 现象 主机系统带载到2A时 系统反复重启 2 分析 示波器测量VCC 5V 稳压源一显示到2A VCC 5V就会掉到0V 把如下二极管断开 万用表测量电流到3 7A就是掉下 3 解决 查规格书可知电流检测电阻的计算 原来为0 03R 按
  • javascript解析XML生成树形结构

    前两天一个朋友去一家公司面试 面试题是用javascript解析一个XML 生成树形结构 今天闲着没事就试了试 源代码
  • Unity自带的相应事件

    Unity自带的相应事件 代码 条件 各个响应事件 鼠标移入移出 鼠标按下 抬起 点击 鼠标拖拽 选择事件接口 系统按键事件的接口 代码 using UnityEngine using UnityEngine EventSystems pu

随机推荐

  • 数据结构题目-哈希

    目录 A Hash表 线性探测法解决冲突 B 求3阶B 树的深度 C 输出3阶B 树的构造过程 D Hash表 链表法解决冲突 仅作储存代码使用 A Hash表 线性探测法解决冲突 include
  • Python当中reverse()函数

    Hello大家好 今天我想和大家分享一下Python当中的reverse 函数 reverse 函数顾名思义就是反转的意思 但是我们要注意反转的内容只能是python当中的列表 千万不要忘记了 例子如下 arr 1 2 3 4 5 6 ar
  • js数据类型之对象object类型(数组与自定义对象)

    对象object 数组与自定义对象 JavaScript 中的所有事物都是对象 字符串 数值 数组 函数 此外 JavaScript 允许自定义对象 JavaScript 提供多个内建对象 比如 String Date Array 等等 对
  • CoordinatorLayout+AppBarLayout+CollapsingToolbarLayout+Toolbar实现渐变透明的状态栏

    在之前的一篇博文里面我已经说明了CoordinatorLayout使用过程中遇到的问题 之后又发现结合CollapsingToolbarLayout使用时的另一个问题 CollapsingToolbarLayout里面的ImageView为
  • [架构之路-208]- 人人都是产品经理 - 什么是产品经理?产品经理具体是做什么的?

    目录 一 什么是产品经理 产品经理具体做什么 二 产品经理的岗位职责 三 产品经理的职业规划 一 什么是产品经理 产品经理具体做什么 在外行人看来 产品经理常常被误认为是 经理 其实产品经理只是一个岗位名称 并不是真正意义上的 经理 或者说
  • 深入浅出UML类图(五)

    实例分析3 售票机控制程序 某运输公司决定为新的售票机开发车票销售的控制软件 图I给出了售票机的面板示意图以及相关的控制部件 图I 售票机面板示意图 售票机相关部件的作用如下所述 1 目的地键盘用来输入行程目的地的代码 例如 200表示总站
  • python的几个重要基本概念

    1 整数 小数 布尔值和空值 整数 int类型 计算机中整数是有最大值的 与计算机的存储能力有关 即使是这样计算机中的整数值也是很大很大的 这一点基本上不需要担心的 小数 也称 浮点数 float类型 小数就是带小数点的数包括 1 0 等等
  • sqlite数据库-------清除数据,数据库文件大小不变解决方法

    现象 删除表格的全部数据 DELETE FROM Name 原因 当在sqlite中删除了大量数据后 数据库文件的大小还是那样 没有变 原因是 从Sqlite删除数据后 未使用的磁盘空间被添加到一个内在的 空闲列表 中用于存储你下次插入的数
  • IP协议号与传输层端口

    网络层 数据包的包格式里面有个很重要的字段叫做协议号 比如在传输层如果是tcp连接 那么在网络层ip包里面的协议号就将会有个值是6 如果是udp的话那个值就是17 传输层 传输层 通过接口关联 端口的字段叫做端口 应用层 协议号是存在于IP
  • 设计模式:桥接模式(c++实现案例)

    桥接模式 桥接模式是一种结构型设计模式 可将业务逻辑或一个大类拆分为不同的层次结构 从而能独立地进行开发 桥接模式通过将继承改为组合的方式来解决这个问题 具体来说 就是抽取其中一个维度并使之成为独立的类层次 这样就可以在初始类中引用这个新层
  • 2016年蓝桥杯省赛C/C++ A组-寒假作业

    题目 现在小学的数学题目也不是那么好玩的 看看这个寒假作业 每个方块代表1 13中的某一个数字 但不能重复 比如 6 7 13 9 8 1 3 4 12 10 2 5 以及 7 6 13 9 8 1 3 4 12 10 2 5 就算两种解法
  • ug产品摆正高级技巧_UG NX如何摆正产品零件模型

    原标题 UG NX如何摆正产品零件模型 有时 我们拿到一个产品模型 按F8也是一个歪的视图 如图 那么该如何才能将产品摆正呢 其实很简单 我们只需要移动下就好了 按ctrl t移动对象 选中模型 变化选项里面运动选择从csys到csys 指
  • 数据结构——串——王道

    目录 串 定义 串和线性表的联系及不同 串的基本操作 存储结构 顺序存储 链式存储 基本操作的实现 字符串模式匹配算法 朴素模式匹配算法 KMP算法 串 定义 串 即字符串 String 是由零个或多个字符组成的有限序列 一般记为 其中 S
  • 编写cuda代码查看自己机器的显卡信息

    代码如下 cudaDeviceProp 是一个结构体 一些参数就是cudaDeviceProp 结构体中的参数 cudaGetDeviceProperties cudade 0 这个函数就是实例化 第一个参数就是实例化 第二个参数是哪一个显
  • Windows如何开启虚拟化,以安装虚拟机?

    参考 Windows如何开启虚拟化 以安装虚拟机 作者 一只青木呀 发布时间 2020 08 28 20 58 45 网址 https blog csdn net weixin 45309916 article details 108286
  • STM32Cube 中的STM32例程EXAMPLE

    STM32 Cube 其实包含的大量的程序例子 一些模块程序编写不需要再去找其他例子 在这就能找到 在这里插入图片描述 https img blog csdnimg cn 7862d4aba5b54d4da2db87586b4ae859 p
  • Spring源码--Bean的加载

    bean的加载在AbstractBeanFactory的doGetBean中 protected
  • Allegro怎么进行走线

    1 切换到走线模式 点击走线 在options中进行走线参数设置 如下图
  • 2022蓝桥杯省赛——顺子日期

    问题描述 本题为填空题 只需要算出结果后 在代码中使用输出语句将所填结果输出即可 小明特别喜欢顺子 顺子指的就是连续的三个数字 123 456 等 顺子日期指的就是在日期的 yyyymmdd 表示法中 存在任意连续的三位数是一个顺子的日期
  • 并行CRC—Verilog代码实现

    CRC并行Verilog 1 构造系数方阵F 2 计算CRC系数 3 计算DATA系数 3 1 DATA系数真相 4 合并系数 5 验证 6 其他选项 6 1输入翻转 6 2预设初值 6 3输出翻转 取反 7 Matlab生成并行crc代码