基于Verilog的CRC算法实现_crc verilog实现

CRC概述

CRC即Cyclic Redundancy Check，循环冗余校验，是一种数字通信中的常用信道编码技术。能识别是否出错，接收端检验时余数为0就没出错，但不具有纠错功能。

CRC码的组成

CRC码是由两部分组成的，前部分是信息码，就是需要校验的信息，后部分是校验码，如果CRC码长共n bit，信息码长k bit，就称为(n,k)码，剩余的r bit即为校验位。如：(7,3)码：110 1001，前三位110为信息码，1001为校验码。

校验码的生成与检验

1. 生成多项式的最高次幂表明了校验位的位宽，将原信息码左移r bit，右侧补零，如 G（X）=X^3+X+1, 则1100–> 1100 000；
2. 用1100 000除以g(x) (注意，使用的是模2除法,见下文)，得到的余数即为CRC校验码；
3. 将校验码续接到信息码的尾部，形成CRC码。
   注：生成多项式的系数就是二进制除数比如：
   
   
   

模2除法

模2加减法
模2除法每一步用到模2加减法,关于模2加减法,其实就是按位异或,规则如下:

//不需要考虑进位和借位
0 ± 0 = 0
1 ± 1 = 0
0 ± 1 = 1
1 ± 0 = 1
例: 1101 ± 1001 = 0100
计算如下:
		  1 1 0 1 
		± 1 0 0 1 
		-----------
		  0 1 0 0
1
2
3
4
5
6
7
8
9
10
11

模2除法：
同样不需要考虑进位和借位
规则:假设被除数X,和除数P,余数R

X除以P，对X和P做模2加减法，即按位异或
所得余数R去除首位，即左移一位:

若R第一位为0,将其作为新的被除数,除以0。此时其首位为0,商即为0
若R第一位为1,将其作为新的被除数,除以P。此时其首位为1,商即为1

重复第2步直到R位数少于P位数
例:1111000对除数1101做模2除法:

      1 0 1 1     //商
---------------
1 1 1 1 0 0 0     //被除数,注意首位为1
1 1 0 1	          //被除数首位为1,除以除数
---------------
  0 1 0 0 0 0     //余数去除首位,作为新的被除数
  0 0 0 0         //被除数首位为0,除以0
---------------
    1 0 0 0 0     //余数去除首位,作为新的被除数
    1 1 0 1       //被除数首位为1,除以除数  
---------------
      1 0 1 0     //余数去除首位,作为新的被除数
      1 1 0 1     //被除数首位为1,除以除数
---------------
        1 1 1     //余数,此时余数位数少于除数,不能继续除了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Verilog实现

网上看了许多方法，都是根据生成多项式做类似PRBS生成那样的操作，能看懂，但真看不出来和模2除法有什么关系。
只有这篇文章写明白了如何从“模2除法”出发得到verilog代码：FPGA(一)——基于Verilog的CRC算法实现。

module CRC3_D4 (
				clk,
                rst_n,
                din,	//din=1010
                crc_start,
                crc_vld,
                crc_o
                );
                
input           	clk;
input           	rst_n;
input		[3:0]   din;
input           	crc_start;
output	reg	        crc_vld;
output		[2:0]   crc_o;

//除数：polynomial g(x)=x^3+x+1=1011
parameter poly = 3'b011;
//因为每次异或后的首位都是0，且总是被去掉，所以首位不参与运算也行

reg		[6:0]	din_r;
reg		[1:0]	cnt;
reg				flag;

//被除数怎么操作
always @ (posedge clk or negedge rst_n) begin
	if(!rst_n)
		din_r <= 0;
	else if(crc_start)
		din_r <= {din,3'b000};//被除数补零
	else if(flag) begin
		if(din_r[6]) begin//若最高位为1，与除数异或，左移
			din_r[6:4] <= din_r[5:3] ^ poly;
			din_r[3:0] <= {din_r[2:0],1'b0};
		end
		else	//若最高位为0，与0异或，左移，就是直接左移
			din_r[6:0] <= {din_r[5:0],1'b0};
	end
end 

// 引入flag和cnt信号，控制移位异或操作的进行
always @ (posedge clk or negedge rst_n) begin
	if(!rst_n)
		cnt <= 0;
	else if(flag) begin
		if(cnt==2'd3)
	//要想余数位数小于除数(4)，总共需移位被除数4次
		cnt <= 0;
		else
		cnt <= cnt + 1'b1;
	end
end

always @ (posedge clk or negedge rst_n) begin
	if(!rst_n)
		flag <= 0;
	else if(crc_start)
		flag <= 1;
	else if(cnt==2'd3)
		flag <= 0;
end

//输出
always @ (posedge clk or negedge rst_n) begin
	if(!rst_n) begin
		crc_vld <= 0;
	end
	else if(cnt==2'd3)begin//计数到3结束
		crc_vld <= 1'b1;
		//crc_o <= din_r[6:4]; 这样得到的crc_o是基于上一拍din_r得到的
	end
	else 
	crc_vld <= 1'b0;
end
assign crc_o = crc_vld? din_r[6:4]: 3'b0;
endmodule
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

在输出crc_o时，如果用时序逻辑cnt=3做判断条件，读取到的时倒数第二个din_r；只有组合逻辑vld=1做判断条件，读取到的才是最后的din_r

tb:

module CRC3_D4_tb ();
reg             clk;
reg             rst_n;
reg     [3:0]  din;
reg             crc_start;
wire            crc_vld;
wire    [2:0]   crc_o;

CRC3_D4 CRC3_D4_inst  (    
				.clk            (clk      ),
                .rst_n          (rst_n    ),
                .din            (din      ),
                .crc_start      (crc_start),
                .crc_vld        (crc_vld  ),
                .crc_o          (crc_o    )
                );

always #5 clk = ~clk;
initial begin
    clk = 1'b0;
    rst_n = 1'b0;
    din = 'b0;
    crc_start = 1'b0;
    
    #100;
    rst_n = 1'b1;
    
    @(posedge clk) ;
    din = 4'b1010;
    crc_start = 1'b1;
    @(posedge clk) ;
    crc_start = 1'b0;
    #500;
    $stop; 
end
endmodule

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

手算：