关于CRC硬件并行化运算的实现方法的探讨
数据校验的基础运算原理是模2运算，也就是异或运算。
简单讲述一下CRC的原理， CRC校准首先要确定一个多项式M(x), 例如
根据这个多项式的最高系数5， 在数据后补充5位0. 然后对新增0的数据进行模2除法。例如数据0010, 根据上式， M(x)可以写成 110101。那么模2的最终结果为 11111，那么把这个运算结果替换为原先补充的5位0，这就是用于校验的冗余码。这样输出传输后，接收方利用同样的多项式运算，得到的结果是0， 即数据没有传输错误。
更多的CRC内容介绍可以网上查询资料，此处不再赘述。
那么在高速通信中，数据以串行传输的方式在外部传输，但是在内部数据处理还是以并行数据为主。如何实现CRC硬件计算的并行化处理呢？
第一种方法，把运算过程实现，也就是输入与对应的位数做异或。然后多次并行例化这个过程，把上一轮计算的结果作为下一次计算的输入。运算结果的流程如下图：
reg [5:0] lsfr_tmp [3:0] ;
genvar i;
generate for (i = 0; i < 4; i = i + 1) begin: cdc_cal
always @ (posedge clk or posedge rst) begin
if (rst) begin
lsfr_tmp[i] <= 'd0;
end
else if (i != 0) begin
lsfr_tmp[i][0] <= lsfr_tmp[i-1][4] ^ data[3-i];
lsfr_tmp[i][1] <= lsfr_tmp[i-1][0] ;
lsfr_tmp[i][2] <= lsfr_tmp[i-1][4] ^ data[3-i] ^ lsfr_tmp[i-1][1];
lsfr_tmp[i][3] <= lsfr_tmp[i-1][2] ;
lsfr_tmp[i][4] <= lsfr_tmp[i-1][4] ^ data[3-i] ^ lsfr_tmp[i-1][3];
end
else begin
lsfr_tmp[0] <= 'd0;
lsfr_tmp[0][0] <= data_in[3] ;
lsfr_tmp[0][2] <= data_in[3] ;
lsfr_tmp[0][4] <= data_in[3] ;
end
end
end
endgenerate
assign crc_out = lsfr_tmp[3] ;
这种方法确实可行，在中间插入流水线的话，数据的吞吐率应该也不小。
但我们还有第二种方法，根据多项式的LSFR，推导参考资料[1]可以自动生成Verilog代码如下，得出最终的冗余码与输入和多项式之间的映射关系。
还是以4 bits的数据输入和上面的多项式为例，根据得到的verilog CRC并行化代码如下，它的输出与上一次的CRC冗余码也存在关系：
//-----------------------------------------------------------------------------
// CRC module for data[3:0] , crc[4:0]=1+x^2+x^4+x^5;
//-----------------------------------------------------------------------------
module crc(
input [3:0] data_in,
input crc_en,
output [4:0] crc_out,
input rst,
input clk);
reg [4:0] lfsr_q,lfsr_c;
assign crc_out = lfsr_q;
always @(*) begin
lfsr_c[0] = lfsr_q[1] ^ lfsr_q[2] ^ lfsr_q[3] ^ data_in[0] ^ data_in[1] ^ data_in[2];
lfsr_c[1] = lfsr_q[2] ^ lfsr_q[3] ^ lfsr_q[4] ^ data_in[1] ^ data_in[2] ^ data_in[3];
lfsr_c[2] = lfsr_q[1] ^ lfsr_q[2] ^ lfsr_q[4] ^ data_in[0] ^ data_in[1] ^ data_in[3];
lfsr_c[3] = lfsr_q[2] ^ lfsr_q[3] ^ data_in[1] ^ data_in[2];
lfsr_c[4] = lfsr_q[0] ^ lfsr_q[1] ^ lfsr_q[2] ^ lfsr_q[4] ^ data_in[0] ^ data_in[1] ^ data_in[3];
end // always
always @(posedge clk, posedge rst) begin
if(rst) begin
lfsr_q <= {5{1'b1}};
end
else begin
lfsr_q <= crc_en ? lfsr_c : lfsr_q;
end
end // always
endmodule // crc
那么它们之间的关系是如何得出的呢？根据参考资料2 提供的资料来看，关系的得出如下。
首先，输入的数据以及多项式的值会影响输出的结果。
其次，整个过程是模2运算，也就是非0即1。那么，可以把输入数据和多项式对数据结果的影响分开计算，最后整合。且我们可以用独热码的形式计算输入的每一位对输出的影响。
因此，首先考虑输入数据对结果的影响，将多项式的初始数值设为0；输入数据分别设为0001, 0010, 0100, 1000. 带入到上图的LFSR中计算，最后得到的输出数据为：
然后，设输入数据为0000， 多项式的初始数值为00001, 00010, 00100, 01000, 10000；带入LFSR中计算，得到的输出数据为：
根据上述的两表，可得out[0]跟输入数据0,1,2 bit以及多项式的1，2，3bit有关。因此做异或运算；然后依次类推，得到了所有的映射关系。然后就可以得到上述Verilog中lfsr的运算关系了。
当然，如果你的CRC的多项式初始数值默认为0，即与之前的CRC校验冗余码无关，那么其实可以不用计算多项式数值的情况，只看第一个表。现在拿第一个表的对应关系，计算下0010的冗余码。就是11111.
-
CRC校验
+关注
关注
0文章
84浏览量
15207 -
Verilog语言
+关注
关注
0文章
113浏览量
8224 -
LSFR算法
+关注
关注
0文章
2浏览量
1056
发布评论请先 登录
相关推荐
在Virtex-5 FPGA中使用CRC硬模块
Xmodem协议中CRC算法的FPAG实现
一种基于矩阵的并行CRC校验算法
基于CRC-32并行在千兆以太网中应用
基于FPGA的并行CRC算法的UART控制器
基于Matlab和GPU的BESO方法的全流程并行计算策略
如何使用FPGA实现32位并行数据的CRC16编码器
使用FPGA实现高速CRC并行算法的设计研究
并行CRC电路HDL代码的快速生成
USB数据传输中CRC校验码的并行算法实现
CRC校验码并行计算的FPGA实现
关于STM32F4xx的硬件CRC32校验
一种并行CRC计算的通用算法及其实现
N32G45x硬件CRC计算Modbus的CRC16
工商网监
评论