基于迭代单元的恢复余数开方器

基本算法

该开方器的算法与“手算”（以前并不知道开方还有这种手算的方法）算法相似，使用迭代解决，文字描述如下

  1. 将0为余数的初值a，0作为结果初值b
  2. 将被开方数前两位{I(2m + 1),I(2m)}取出，与01比较大小。若前两位大，则{I(2m + 1),I(2m)} - 01为输出余数（a(m)），输出结果1(b(m))，否则{I(2m + 1),I(2m)}为输出余数（a(m)），输出结果0（b(m)）
  3. 将被开方数的从高位数第3,4位{I(2m - 1),I(2m - 2)}取出，比较{a(m),I(2m - 1),I(2m - 2)}和{b(m),2'b01}的大小，若前一项大，则输出余数a(m - 1)为前一项减后一项，输出结果b(m - 1)为{b(m),1};否则，输出余数为前一项（直接输出），输出结果b(m - 1)为{b(m),0}
  4. …
  5. 直到计算完被开方数结束

迭代单元

算法

迭代单元的算法比较简单，描述如下：

  1. 组合输入余数和当前开方数的两位{b,I(i),I(i - 1)}，组合输入结果和01为{a,2'b01}
  2. 比较大小，若组合余数大则输出余数为组合余数减去组合结果，输出结果{a,1}；否则余数输出组合余数，结果输出{a,0}

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
module square_cell #(
	parameter WIDTH = 4,
	parameter STEP = 0
)(
	input clk,    // Clock
	input rst_n,  // Asynchronous reset active low

	input [2 * WIDTH - 1:0]radicand,
	input [WIDTH - 1:0]last_dout,
	input [2 * WIDTH - 1:0]remainder_din,

	output reg [WIDTH - 1:0]this_dout,
	output reg [2 * WIDTH - 1:0]remainder_dout
);

wire [2 * WIDTH - 1:0]target_data = {remainder_din[2 * WIDTH - 3:0],radicand[2 * STEP +:2]};
wire [2 * WIDTH - 1:0]try_data = {last_dout,2'b01};

always @(posedge clk or negedge rst_n) begin
	if(~rst_n) begin
		{this_dout,remainder_dout} <= 'b0;
	end else begin
		if(target_data >= try_data) begin
			this_dout <= {last_dout[WIDTH - 2:0],1'b1};
			remainder_dout <= target_data - try_data;
		end else begin
			this_dout <= {last_dout[WIDTH - 2:0],1'b0};
			remainder_dout <= target_data;
		end
	end
end
endmodule

顶层与Testbench

顶层单元

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
module square_extractor #(
	parameter WIDTH = 4
)(
	input clk,    // Clock
	input rst_n,  // Asynchronous reset active low

	input [2 * WIDTH - 1:0]radicand,

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

genvar i;
generate
	for (i = WIDTH - 1; i >= 0; i = i - 1) begin:square
		wire [2 * WIDTH - 1:0]remainder_dout,remainder_din;
		wire [WIDTH - 1:0]this_dout,last_dout;
		if(i == WIDTH - 1) begin
			assign remainder_din = 'b0;
			assign last_dout = 'b0;
		end else begin
			assign remainder_din = square[i + 1].remainder_dout;
			assign last_dout = square[i + 1].this_dout;
		end
		square_cell #(
			.WIDTH(WIDTH),
			.STEP(i)
		) u_square_cell (
			.clk(clk),    // Clock
			.rst_n(rst_n),  // Asynchronous reset active low

			.radicand(radicand),
			.last_dout(last_dout),
			.remainder_din(remainder_din),

			.this_dout(this_dout),
			.remainder_dout(remainder_dout)
		);
	end
endgenerate

assign dout = square[0].this_dout;
assign remainder = square[0].remainder_dout;

endmodule

TestBench

Testbench输入随机的输入后，等待完成，完成后取结果和余数看是否能恢复出正确的输入

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

parameter WIDTH = 4;

logic clk;    // Clock
logic rst_n;  // Asynchronous reset active low

logic [2 * WIDTH - 1:0]radicand;

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

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

	.radicand(radicand),

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

initial begin
	clk = 0;
	forever begin
		#50 clk = ~clk;
	end
end

initial begin
	rst_n = 1'b1;
	#5 rst_n = 1'b0;
	#10 rst_n = 1'b1;
end

logic [2 * WIDTH - 1:0]act;
logic [2 * WIDTH - 1:0]dout_ex;
initial begin
	radicand = 'b0;
	forever begin
		@(negedge clk);
		radicand = (2 * WIDTH)'($urandom_range(0,2 ** (2 * WIDTH)));
		repeat(4 * WIDTH) begin
			@(negedge clk);
		end
		dout_ex = '{dout};
		act = dout_ex * dout_ex + remainder;
		if(act != radicand) begin
			$stop;
		end
	end
end

endmodule