|
前段时间在为fpga做一个crc32校验的模块，本来不想找现成的代码，准备自己看原理来编写，没想到原理很简单，由于输入数据的频率非常高，考虑到数据同步，实际的编写过程还是有点周折的，以为一天搞定的事情，花了至少三、四天吧。网上提供的crc32源代码基本都是c语言或者汇编，用硬件描述语言的非常少，因此把自己总结以及网上搜集整理的学习心得总结一下，并放出两种实现方式的verilog源代码。结果和winrar的crc校验结果比较过，均正确。
如何生成CRC校验码
(1) 设G(X)为W阶，在数据块末尾添加W个0，使数据块为M+ W位，则相应的多项式为XrM(X)；
(2) 以2为模，用对应于G(X)的位串去除对应于XrM(X)的位串，求得余数位串；
(3) 以2为模，从对应于XrM(X)的位串中减去余数位串，结果就是为数据块生成的带足够校验信息的CRC校验码位串。
这个二进制除法的没有优化的伪代码大概可以这样写（设除数有P个bits）：
{
任命余数r = 被除数的前(P-1)位;
while(被除数还有剩余bit没有补入到r中)
{
补入一个bit到r中;
r = 补位后的r作为被除数 除以 除数 所得的余数;
}
把r拿出来
}
这个G(X)不用自己去选择，现在基本都成标准的多项式了，去网上一搜就有一堆。
我们知道G(x)的最高位一定是1，而商1还是商0是由被除数的最高位决定的。而我们并不关心商究竟是多少，我们关心的是余数。例如上例中的G(x)有5 位。我们可以看到每一步作除法运算所得的余数其实就是被除数的最高位后的四位于G(x)的后四位XOR而得到的。那被除数的最高位有什么用呢？我们从打记号的两个不同的余数就知道原因了。当被除数的最高位是1时，商1然后把最高位以后的四位于G(x)的后四位XOR得到余数；如果最高位是0，商0然后把被除数的最高位以后的四位于G(x)的后四位XOR得到余数，而我们发现其实这个余数就是原来被除数最高位以后的四位的值。也就是说如果最高位是0就不需要作XOR的运算了。到这我们总算知道了为什么先前要这样建立模型，而算法的原理也就清楚了。
关于除数多项式Poly（以下简称 Poly）。我曾经看过一篇中文文档中说，“不要问我为什么Poly的最高位和最低位都是1，因为这是规定”。规定当然是规定，但是做出这种规定也应当是有原因的吧？根据我的个人理解（当然，也许这是错误的理解），首先最高位必须为1，这个bit位在英文文档中称为 “Active” bit，为什么呢？如果Poly最高位不是1那么除法无法进行下去而得到有我们所需要的位数的余数（当Poly最高位为0而被除数高位为1时无法抵消）。而低位为什么也必须为1呢？在有的使用场合是把CRC的Poly和被除数都做了反射之后再进行的，这种情况下低位反射成了高位，基于前面同样的理由，所以必须保持最低位也为1。
查表法综述
可是上面实现的算法却是非常的低效。现在假设有和32bit的register。根据同样的原理我们可以得到如下的算法：
While (还有剩余没有处理的数据)
Begin
检查register头字节，并取得它的值
求不同偏移处多项式的和
register左移一个字节，最右处存入新读入的一个字节
把register的值和多项式的和进行XOR运算
End
对于每一个bit来说，都有0或者1都有其异或规则，那么同样的，每一个头字节也会对应和值。如果我们以8bit为单位移位，8 bit就该有 256个值与它对应。于是我们可以预先建立一个表然后，编码时只要取出输入数据的头一个字节然后从表中查找对应的值即可。这样就可以大大提高编码的速度了。
算法如下：
1、将寄存器向右边移动一个字节。
2、将刚移出的那个字节与我们的字符串中的新字节进行XOR运算，得出一个指向值表table[0..255]的索引。
3、将索引所指的表值与寄存器做XOR运算。
4、如果数据没有全部处理完，则跳到步骤1。
这个算法的C语言描述如下：
temp = (oldcrc ^ abyte) & 0×000000FF;
crc = (( oldcrc >> & 0×00FFFFFF) ^ crc32tbl[temp];
return crc;
说实话，查找表算法如果不画图实在是很难描述清楚，所以我也不多费口舌了，网上有不少好文章来详细介绍，有兴趣的朋友去查阅就行了。
从CRC 的编码规则可以看出，CRC编码实际上是将代发送的m位二进制多项式t（x）转换成了可以被g（x）除尽的m+r位二进制多项式，所以解码时可以用接受到的数据去除g（x），如果余数位零，则表示传输过程没有错误；如果余数不为零，则在传输过程中肯定存在错误。许多CRC的硬件解码电路就是按这种方式进行检错的。同时可以看做是由t（x）和CRC校验码的组合，所以解码时将接收到的二进制数据去掉尾部的r位数据，得到的就是原始数据。
实际程序
crc32查表verilog程序如下：
`timescale 1ns / 1ps
module crc32_table
(
crc_clk,
rst_n,
data,
valid,
crc32,
done
);
// input
input crc_clk;
input rst_n;
input valid;
input done;
input [15:0] data;
// output
output [31:0] crc32;
wire [31:0] crc32;
// parameter
parameter state_size = 3;
parameter IDLE = 3′b001, // wait for valid signal
CRC1 = 3′b010, // handle data
CRC2 = 3′b100;
// internal
reg [15:0] data_buf; // buffer for input data
reg [31:0] crc32_r;
reg [31:0] register;
reg [31:0] register_r;
reg [state_size-1:0] state;
reg [31:0] crctab[255:0];
always @( posedge crc_clk or negedge rst_n )
begin
if( !rst_n )
begin
state <= IDLE;
//state_next <= state;
register <= 32′hffffffff;
register_r <= 32′hffffffff;
data_buf <= 16′h0;
crctab[0] <= 32′h00000000;
…….. // 这些是crc32的表值，网上有很多
crctab[255] <= 32′h2D02EF8D;
end
else
begin
case( state )
IDLE:
begin
if( valid ) // data is valid
begin
data_buf <= data;
register_r <= 32′hffffffff;
state <= CRC1;
crc32_r <= register;
end
else if( done ) // data is complete
begin
crc32_r <= crc32_r;
register <= 32′hffffffff;
state <= IDLE;
end
// 调试时注意valid和done交接时数据包的处理有没有问题
else
begin
state <= IDLE;
end
end
CRC1:
begin
register_r <= ( crctab[register[7:0] ^ data_buf[7:0]] ) ^ {8′h0,register[31:8]};
state <= CRC2;
end
CRC2:
begin
register <= ( crctab[register_r[7:0] ^ data_buf[15:8]] ) ^ {8′h0,register_r[31:8]};
state <= IDLE;
end
endcase
end
end
assign crc32 = done?~crc32_r:32′d0;
endmodule
标准表值请见此文件：http://likunarmstrong.googlepages.com/crc_table.txt
下面是优化过直接计算crc32值的程序。
//////////////////////////////////////////////////////////////////////////////
//
// crc calculation
// This VERILOG code was generated using CRCGEN.PL version 1.7
// Last Modified: 01/02/2002
// Options Used:
// Module Name = crc32
// CRC Width = 32
// Data Width = 16
// CRC Init = F
// Polynomial = [0 -> 32]
// 1 1 1 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1
//
//////////////////////////////////////////////////////////////////////////////
module crc32 (
crc,
d,
calc,
init,
d_valid,
clk,
reset
);
output [15:0] crc;
reg [15:0] crc;
input [15:0] d;
input calc;
input init;
input d_valid;
input clk;
input reset;
//////////////////////////////////////////////////////////////////////////////
// Internal Signals
//////////////////////////////////////////////////////////////////////////////
wire [31:0] next_crc;
reg [31:0] crc_reg;
//////////////////////////////////////////////////////////////////////////////
// Infer CRC-32 registers
//
// The crc_reg register stores the CRC-32 value.
// The crc register is the most significant 16 bits of the
// CRC-32 value.
//
// Truth Table:
// —–+———+———-+———————————————-
// calc | d_valid | crc_reg | crc
// —–+———+———-+———————————————-
// 0 | 0 | crc_reg | crc
// 0 | 1 | shift | bit-swapped, complimented msbyte of crc_reg
// 1 | 0 | crc_reg | crc
// 1 | 1 | next_crc | bit-swapped, complimented msbyte of next_crc
// —–+———+———-+———————————————-
//
//////////////////////////////////////////////////////////////////////////////
always @ (posedge clk or negedge reset)
begin
if (!reset) begin
crc_reg <= 32′hFFFFFFFF;
crc <= 16′hFFFF;
end
else if (init) begin
crc_reg <= 32′hFFFFFFFF;
crc <= 16′hFFFF;
end
else if (calc & d_valid) begin
crc_reg <= next_crc;
crc <= ~{next_crc[16], next_crc[17], next_crc[18], next_crc[19],
next_crc[20], next_crc[21], next_crc[22], next_crc[23],
next_crc[24], next_crc[25], next_crc[26], next_crc[27],
next_crc[28], next_crc[29], next_crc[30], next_crc[31]};
end
else if (~calc & d_valid) begin
crc_reg <= {crc_reg[15:0], 16′hFFFF};
crc <= ~{crc_reg[0], crc_reg[1], crc_reg[2], crc_reg[3],
crc_reg[4], crc_reg[5], crc_reg[6], crc_reg[7],
crc_reg[8], crc_reg[9], crc_reg[10], crc_reg[11],
crc_reg[12], crc_reg[13], crc_reg[14], crc_reg[15]};
end
end
//////////////////////////////////////////////////////////////////////////////
// CRC XOR equations
//////////////////////////////////////////////////////////////////////////////
assign next_crc[0] = crc_reg[22] ^ crc_reg[25] ^ d[5] ^ d[3] ^ d[6] ^ crc_reg[16] ^ crc_reg[28] ^ d[15] ^ d[9] ^ crc_reg[26];
assign next_crc[1] = crc_reg[22] ^ crc_reg[17] ^ d[3] ^ crc_reg[27] ^ d[15] ^ d[4] ^ crc_reg[25] ^ d[8] ^ crc_reg[23] ^ d[2] ^ crc_reg[29] ^ d[6] ^ crc_reg[16] ^ crc_reg[28] ^ d[14] ^ d[9];
assign next_crc[2] = crc_reg[22] ^ crc_reg[17] ^ d[1] ^ crc_reg[30] ^ d[15] ^ crc_reg[24] ^ d[13] ^ d[7] ^ crc_reg[18] ^ crc_reg[25] ^ d[8] ^ d[2] ^ crc_reg[23] ^ d[6] ^ crc_reg[29] ^ crc_reg[16] ^ d[14] ^ d[9];
assign next_crc[3] = crc_reg[17] ^ d[1] ^ crc_reg[31] ^ crc_reg[30] ^ crc_reg[24] ^ crc_reg[19] ^ d[13] ^ d[7] ^ crc_reg[18] ^ crc_reg[25] ^ d[5] ^ d[12] ^ d[8] ^ crc_reg[23] ^ d[6] ^ d[14] ^ crc_reg[26] ^ d[0];
assign next_crc[4] = crc_reg[22] ^ crc_reg[31] ^ d[3] ^ crc_reg[27] ^ d[15] ^ crc_reg[24] ^ d[4] ^ crc_reg[19] ^ d[13] ^ d[7] ^ crc_reg[20] ^ crc_reg[18] ^ d[12] ^ d[11] ^ crc_reg[16] ^ crc_reg[28] ^ d[9] ^ d[0];
assign next_crc[5] = crc_reg[22] ^ crc_reg[17] ^ d[15] ^ crc_reg[19] ^ crc_reg[20] ^ crc_reg[21] ^ d[12] ^ d[5] ^ d[8] ^ d[10] ^ d[11] ^ crc_reg[23] ^ d[2] ^ crc_reg[29] ^ crc_reg[16] ^ d[14] ^ d[9] ^ crc_reg[26];
assign next_crc[6] = crc_reg[22] ^ crc_reg[17] ^ d[1] ^ crc_reg[27] ^ crc_reg[30] ^ crc_reg[24] ^ d[4] ^ d[13] ^ d[7] ^ crc_reg[20] ^ crc_reg[21] ^ crc_reg[18] ^ d[8] ^ d[10] ^ d[11] ^ crc_reg[23] ^ d[14] ^ d[9];
assign next_crc[7] = crc_reg[31] ^ d[15] ^ crc_reg[24] ^ crc_reg[19] ^ d[13] ^ d[7] ^ crc_reg[21] ^ crc_reg[18] ^ d[5] ^ d[12] ^ d[8] ^ d[10] ^ crc_reg[23] ^ crc_reg[16] ^ crc_reg[26] ^ d[0];
assign next_crc[8] = crc_reg[17] ^ d[3] ^ crc_reg[27] ^ d[15] ^ d[4] ^ crc_reg[24] ^ crc_reg[19] ^ crc_reg[20] ^ d[7] ^ d[12] ^ d[5] ^ d[11] ^ crc_reg[16] ^ crc_reg[28] ^ d[14] ^ crc_reg[26];
assign next_crc[9] = crc_reg[17] ^ d[3] ^ crc_reg[27] ^ d[4] ^ d[13] ^ crc_reg[20] ^ crc_reg[21] ^ crc_reg[18] ^ crc_reg[25] ^ d[10] ^ d[11] ^ d[2] ^ crc_reg[29] ^ d[6] ^ crc_reg[28] ^ d[14];
assign next_crc[10] = d[1] ^ crc_reg[30] ^ d[15] ^ crc_reg[19] ^ d[13] ^ crc_reg[21] ^ crc_reg[18] ^ crc_reg[25] ^ d[12] ^ d[10] ^ d[2] ^ crc_reg[29] ^ d[6] ^ crc_reg[16];
assign next_crc[11] = crc_reg[17] ^ d[1] ^ d[3] ^ crc_reg[31] ^ crc_reg[30] ^ d[15] ^ crc_reg[19] ^ crc_reg[20] ^ crc_reg[25] ^ d[12] ^ d[11] ^ d[6] ^ crc_reg[16] ^ crc_reg[28] ^ d[14] ^ d[0];
assign next_crc[12] = crc_reg[22] ^ crc_reg[17] ^ crc_reg[31] ^ d[3] ^ d[15] ^ d[13] ^ crc_reg[20] ^ crc_reg[21] ^ crc_reg[18] ^ crc_reg[25] ^ d[10] ^ d[11] ^ d[2] ^ d[6] ^ crc_reg[29] ^ crc_reg[16] ^ crc_reg[28] ^ d[14] ^ d[9] ^ d[0];
assign next_crc[13] = crc_reg[22] ^ crc_reg[17] ^ d[1] ^ crc_reg[30] ^ crc_reg[19] ^ d[13] ^ crc_reg[21] ^ crc_reg[18] ^ d[5] ^ d[12] ^ d[8] ^ d[10] ^ crc_reg[23] ^ d[2] ^ crc_reg[29] ^ d[14] ^ crc_reg[26] ^ d[9];
assign next_crc[14] = crc_reg[22] ^ d[1] ^ crc_reg[31] ^ crc_reg[27] ^ crc_reg[30] ^ crc_reg[24] ^ d[4] ^ crc_reg[19] ^ d[13] ^ d[7] ^ crc_reg[20] ^ crc_reg[18] ^ d[12] ^ d[8] ^ d[11] ^ crc_reg[23] ^ d[9] ^ d[0];
assign next_crc[15] = d[3] ^ crc_reg[31] ^ crc_reg[24] ^ crc_reg[19] ^ crc_reg[20] ^ d[7] ^ crc_reg[21] ^ crc_reg[25] ^ d[12] ^ d[8] ^ d[10] ^ d[11] ^ crc_reg[23] ^ d[6] ^ crc_reg[28] ^ d[0];
assign next_crc[16] = crc_reg[0] ^ d[3] ^ d[15] ^ crc_reg[24] ^ crc_reg[20] ^ d[7] ^ crc_reg[21] ^ d[10] ^ d[11] ^ d[2] ^ crc_reg[29] ^ crc_reg[16] ^ crc_reg[28];
assign next_crc[17] = crc_reg[22] ^ crc_reg[17] ^ d[1] ^ crc_reg[30] ^ crc_reg[21] ^ crc_reg[25] ^ d[10] ^ d[2] ^ d[6] ^ crc_reg[29] ^ crc_reg[1] ^ d[14] ^ d[9];
assign next_crc[18] = crc_reg[22] ^ d[1] ^ crc_reg[31] ^ crc_reg[30] ^ d[13] ^ crc_reg[18] ^ d[5] ^ d[8] ^ crc_reg[23] ^ d[9] ^ d[0] ^ crc_reg[26] ^ crc_reg[2];
assign next_crc[19] = crc_reg[31] ^ crc_reg[27] ^ crc_reg[24] ^ d[4] ^ crc_reg[19] ^ d[7] ^ d[12] ^ d[8] ^ crc_reg[23] ^ d[0] ^ crc_reg[3];
assign next_crc[20] = crc_reg[4] ^ d[3] ^ crc_reg[24] ^ crc_reg[20] ^ d[7] ^ crc_reg[25] ^ d[11] ^ d[6] ^ crc_reg[28];
assign next_crc[21] = crc_reg[5] ^ crc_reg[21] ^ crc_reg[25] ^ d[5] ^ d[10] ^ d[2] ^ d[6] ^ crc_reg[29] ^ crc_reg[26];
assign next_crc[22] = d[1] ^ d[3] ^ crc_reg[27] ^ crc_reg[30] ^ d[15] ^ d[4] ^ crc_reg[25] ^ d[6] ^ crc_reg[16] ^ crc_reg[28] ^ crc_reg[6];
assign next_crc[23] = crc_reg[22] ^ crc_reg[17] ^ crc_reg[31] ^ d[15] ^ crc_reg[7] ^ crc_reg[25] ^ d[2] ^ d[6] ^ crc_reg[29] ^ crc_reg[16] ^ d[14] ^ d[9] ^ d[0];
assign next_crc[24] = crc_reg[17] ^ d[1] ^ crc_reg[8] ^ crc_reg[30] ^ d[13] ^ crc_reg[18] ^ d[5] ^ d[8] ^ crc_reg[23] ^ d[14] ^ crc_reg[26];
assign next_crc[25] = crc_reg[9] ^ crc_reg[31] ^ crc_reg[27] ^ crc_reg[24] ^ d[4] ^ crc_reg[19] ^ d[13] ^ d[7] ^ crc_reg[18] ^ d[12] ^ d[0];
assign next_crc[26] = crc_reg[22] ^ crc_reg[10] ^ d[15] ^ crc_reg[19] ^ crc_reg[20] ^ d[12] ^ d[5] ^ d[11] ^ crc_reg[16] ^ d[9] ^ crc_reg[26];
assign next_crc[27] = crc_reg[17] ^ crc_reg[27] ^ d[4] ^ crc_reg[20] ^ crc_reg[21] ^ d[8] ^ d[10] ^ d[11] ^ crc_reg[11] ^ crc_reg[23] ^ d[14];
assign next_crc[28] = crc_reg[22] ^ d[3] ^ crc_reg[24] ^ d[13] ^ d[7] ^ crc_reg[21] ^ crc_reg[18] ^ d[10] ^ crc_reg[12] ^ crc_reg[28] ^ d[9];
assign next_crc[29] = crc_reg[22] ^ crc_reg[19] ^ crc_reg[25] ^ d[12] ^ d[8] ^ crc_reg[13] ^ crc_reg[23] ^ d[2] ^ d[6] ^ crc_reg[29] ^ d[9];
assign next_crc[30] = d[1] ^ crc_reg[30] ^ crc_reg[24] ^ crc_reg[20] ^ d[7] ^ crc_reg[14] ^ d[5] ^ d[8] ^ d[11] ^ crc_reg[23] ^ crc_reg[26];
assign next_crc[31] = crc_reg[31] ^ crc_reg[27] ^ d[4] ^ crc_reg[24] ^ d[7] ^ crc_reg[21] ^ crc_reg[25] ^ crc_reg[15] ^ d[10] ^ d[6] ^ d[0];
endmodule
这个程序应该是是非常晦涩难懂的，如果想知道原理，请去xilinx官方网站下载设计文档xapp209。同名的压缩包里面自带了一个perl程序，通过运行参数的不同，可以自动生成从crc8到crc256的所有verilog程序，输入数据宽度也可调。有兴趣的朋友可以去看看。
|
