移位相减除法器

基本算法

与使用移位相加实现加法一样，移位减法可以实现除法，基本算法如下描述

  1. 将除数向左移位直到比被除数大
  2. 使用移位后的除数与被除数比较，若除数大，则商向左移位1位后末尾补0；若除数小，则被除数累减除数，商向左移位1位后末尾补1
  3. 除数向右移位1位，重复2，知道除数小于原除数

RTL代码

移位相减算法比较简单，一个Verilog模块即可描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
module shiftsub_divider #(
	parameter WIDTH = 4
)(
	input clk,    // Clock
	input rst_n,  // Asynchronous reset active low

	input [2 * WIDTH - 1:0]dividend,
	input [WIDTH - 1:0]divisor,

	input din_valid,

	output reg [2 * WIDTH - 1:0]dout,
	output reg [2 * WIDTH - 1:0]remainder
);

定义端口，其中remainder前WIDTH位均为0，可以不连接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
reg [3 * WIDTH - 1:0]divisor_lock;
reg [WIDTH - 1:0]divisor_ref;
always @ (posedge clk or negedge rst_n) begin
	if(~rst_n) begin
		{divisor_lock,divisor_ref} <= 'b0;
	end else if(din_valid == 1'b1) begin
		divisor_lock[3 * WIDTH - 1:2 * WIDTH] <= divisor;
		divisor_lock[WIDTH - 1:0] <= 'b0;
		divisor_ref <= divisor;
	end else if(divisor_lock >= '{divisor_ref}) begin
		divisor_lock <= divisor_lock >> 1;
		divisor_ref <= divisor_ref;
	end else begin
		divisor_lock <= divisor_lock;
		divisor_ref <= divisor_ref;
	end
end

divisor_lock为移位后的除数，宽度为3 * WIDTH是为了确保移位后的除数比被除数大。divisor_ref保存最初始除数的值，divisor_lock >= '{divisor_ref}为终止条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
always @ (posedge clk or negedge rst_n) begin
	if(~rst_n) begin
		{remainder,dout} <= 'b0;
	end else if(din_valid == 1'b1) begin
		remainder <= dividend;
		dout <= 'b0;
	end else if((dout == 'b0) && (remainder < divisor_lock)) begin
		remainder <= remainder;
		dout <= dout;
	end else if(divisor_lock >= '{divisor_ref})begin
		if(remainder >= divisor_lock) begin
			remainder <= remainder - divisor_lock;
			dout <= {dout[2 * WIDTH - 2:0],1'b1};
		end else begin
			remainder <= remainder;
			dout <= {dout[2 * WIDTH - 2:0],1'b0};
		end
	end else begin
		{remainder,dout} <= {remainder,dout};
	end
end

endmodule

执行移位相减，其中(dout == 'b0) && (remainder < divisor_lock)是为了从除数恰好小于被除数时开始运算

测试

测试方法为随机产生数据，再使用Verilog自带的/和%运算符获取期待值后再与真实结果比较

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
77
module tb_divider (
);

parameter WIDTH = 4;

logic clk;    // Clock
logic rst_n;  // Asynchronous reset active low
logic [2 * WIDTH - 1:0]dividend;
logic [WIDTH - 1:0]divisor;

logic din_valid;

logic [2 * WIDTH - 1:0]dout;
logic [2 * WIDTH - 1:0]remainder;

shiftsub_divider #(
	.WIDTH(WIDTH)
) dut (
	.clk(clk),    // Clock
	.rst_n(rst_n),  // Asynchronous reset active low

	.dividend(dividend),
	.divisor(divisor),

	.din_valid(din_valid),

	.dout(dout),
	.remainder(remainder)
);

//产生时钟信号
initial begin
	clk = 'b0;
	forever begin
		#50 clk = ~clk;
	end
end

//产生复位信号
initial begin
	rst_n = 1'b1;
	# 5 rst_n = 'b0;
	#10 rst_n = 1'b1;
end

logic [2 * WIDTH - 1:0]dout_exp;
logic [WIDTH - 1:0]remainder_exp;
initial begin
  	//初始化
	{dividend,divisor,din_valid} = 'b0;
	forever begin
		@(negedge clk);
      	//产生随机输入并启动
		dividend = (2 * WIDTH)'($urandom_range(0,2 ** (2 * WIDTH)));
		divisor = (WIDTH)'($urandom_range(1,2 ** WIDTH - 1));
		din_valid = 1'b1;
		
      	//计算期待结果
		remainder_exp = dividend % divisor;
		dout_exp = (dividend - remainder_exp) / divisor;

      	//等待运算结果
		repeat(4 * WIDTH) begin
			@(negedge clk);
			din_valid = 'b0;
		end
      
      	//期待结果与真实结果比较
		if((remainder == remainder_exp) && (dout_exp == dout)) begin
			$display("successfully");
		end else begin
			$display("failed");
		end
	end
end

endmodule