不恢复余数除法器

基本算法

不恢复余数除法器的基本算法来自于恢复余数除法器，区别在于当余数变负时不停下恢复余数而是继续运行迭代，并在迭代中加上移位后除数而不是减去移位后除数，基本算法如下所示

  1. 将除数向左移位到恰好大于被除数
  2. 若余数为正：余数减去移位后除数；若余数为负：余数加上移位后除数；
  3. 若现余数为正，该位结果为1，否则为0，将除数向右移位一位
  4. 重复2,3，知道移位后除数小于原除数

RTL代码

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
78
79
80
81
82
module norestore_divider #(
	parameter WIDTH = 4
)(
	input clk,    // Clock
	input rst_n,  // Asynchronous reset active low

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

	input din_valid,

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

// parameter JUDGE = 2 ** (2 * WIDTH);

reg [2 * WIDTH:0]remainder_r;
reg [3 * WIDTH - 1:0]divisor_move;
reg [WIDTH - 1:0]divisor_lock;
reg [2 * WIDTH:0]judge;
always @ (*) begin
	if(remainder_r[2 * WIDTH] == 1'b0) begin
		judge = remainder_r - divisor_move;
	end else begin
		judge = remainder_r + divisor_move;
	end
end

always @ (posedge clk or negedge rst_n) begin
	if(~rst_n) begin
		{remainder_r,divisor_lock,divisor_move,dout} <= 'b0;
	end else begin
		if(din_valid == 1'b1) begin	//lock input data
			remainder_r[WIDTH * 2 - 1:0] <= dividend;
			remainder_r[2 * WIDTH] <= 'b0;
			divisor_move[3 * WIDTH - 1:2 * WIDTH] <= divisor;
			divisor_move[2 * WIDTH - 1:0] <= 'b0;
			divisor_lock <= divisor;
			dout <= 'b0;
		end else if((divisor_move > '{remainder_r}) && (dout == 'b0)) begin
         //开始运算条件
			remainder_r <= remainder_r;
			dout <= 'b0;
			divisor_move <= divisor_move >> 1;
			divisor_lock <= divisor_lock;
		end else if(divisor_move >= '{divisor_lock}) begin
			if(remainder_r[2 * WIDTH] == 1'b0) begin
				remainder_r <= judge;
				if(judge[2 * WIDTH] == 'b0) begin
					dout <= {dout[2 * WIDTH - 2:0],1'b1};
				end else begin
					dout <= {dout[2 * WIDTH - 2:0],1'b0};
				end
			end else begin
				remainder_r <= judge;
				if(judge[2 * WIDTH] == 'b0) begin
					dout <= {dout[2 * WIDTH - 2:0],1'b1};
				end else begin
					dout <= {dout[2 * WIDTH - 2:0],1'b0};
				end
			end
			divisor_move <= divisor_move >> 1;
			divisor_lock <= divisor_lock;
		end else if(remainder_r[2 * WIDTH - 1] == 1'b1) begin
         //调整余数
			remainder_r <= remainder_r + divisor_lock;
			dout <= dout;
			divisor_lock <= divisor_lock;
			divisor_move <= divisor_move;
		end else begin
			remainder_r <= remainder_r;
			divisor_lock <= divisor_lock;
			divisor_move <= divisor_move;
			dout <= dout;
		end
	end
end

assign remainder = remainder_r[WIDTH - 1:0];

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
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 [WIDTH - 1:0]remainder;

norestore_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(5 * WIDTH) begin
			@(negedge clk);
			din_valid = 'b0;
		end
		if((remainder == remainder_exp) && (dout_exp == dout)) begin
			$display("successfully");
		end else begin
			$display("failed");
			$stop;
		end
	end
end

endmodule