[syntax=verilog]
/************************************************
The Verilog HDL code example is from the book
Computer Principles and Design in Verilog HDL
by Yamin Li, published by A JOHN WILEY & SONS
************************************************/
module div_restoring (a,b,start,clk,clrn,q,r,busy,ready,count);
input [31:0] a; // dividend
input [15:0] b; // divisor
input start; // start
input clk, clrn; // clk,reset
output [31:0] q; // quotient
output [15:0] r; // remainder
output reg busy; // busy
output reg ready; // ready
output [4:0] count; // counter
reg [31:0] reg_q;
reg [15:0] reg_r;
reg [15:0] reg_b;
reg [4:0] count;
wire [16:0] sub_out = {reg_r,reg_q[31]} - {1'b0,reg_b}; // sub
wire [15:0] mux_out = sub_out[16]? // restoring
{reg_r[14:0],reg_q[31]} : sub_out[15:0]; // or not
assign q = reg_q;
assign r = reg_r;
always @ (posedge clk or negedge clrn) begin
if (!clrn) begin
busy <= 0;
ready <= 0;
end else begin
if (start) begin
reg_q <= a; // load a
reg_b <= b; // load b
reg_r <= 0;
busy <= 1;
ready <= 0;
count <= 0;
end else if (busy) begin
reg_q <= {reg_q[30:0],~sub_out[16]}; // << 1
reg_r <= mux_out;
count <= count + 5'b1; // counter++
if (count == 5'h1f) begin // finished
busy <= 0;
ready <= 1; // q,r ready
end
end
end
end
endmodule
[/syntax]
anyone could relate the restoring part of https://paste2.org/7MUm29FL to https://en.wikipedia.org/wiki/Division_algorithm#Restoring_division ?
1) For lines 21 and 22, sub_out[16] is '1' if the subtraction overflowed (became negative), but WHY {reg_r[14:0],reg_q[31]} when the subtraction result is negative, and WHY sub_out[15:0] when it is otherwise ?
2) For line 38, what does reg_q <= {reg_q[30:0],~sub_out[16]}; trying to achieve ?
Code:[syntax=verilog] /************************************************ The Verilog HDL code example is from the book Computer Principles and Design in Verilog HDL by Yamin Li, published by A JOHN WILEY & SONS ************************************************/ module div_restoring (a,b,start,clk,clrn,q,r,busy,ready,count); input [31:0] a; // dividend input [15:0] b; // divisor input start; // start input clk, clrn; // clk,reset output [31:0] q; // quotient output [15:0] r; // remainder output reg busy; // busy output reg ready; // ready output [4:0] count; // counter reg [31:0] reg_q; reg [15:0] reg_r; reg [15:0] reg_b; reg [4:0] count; wire [16:0] sub_out = {reg_r,reg_q[31]} - {1'b0,reg_b}; // sub wire [15:0] mux_out = sub_out[16]? // restoring {reg_r[14:0],reg_q[31]} : sub_out[15:0]; // or not assign q = reg_q; assign r = reg_r; always @ (posedge clk or negedge clrn) begin if (!clrn) begin busy <= 0; ready <= 0; end else begin if (start) begin reg_q <= a; // load a reg_b <= b; // load b reg_r <= 0; busy <= 1; ready <= 0; count <= 0; end else if (busy) begin reg_q <= {reg_q[30:0],~sub_out[16]}; // << 1 reg_r <= mux_out; count <= count + 5'b1; // counter++ if (count == 5'h1f) begin // finished busy <= 0; ready <= 1; // q,r ready end end end end endmodule [/syntax]
In the restoring division algorithm described in the previous section, if the result of the subtraction r is negative, b is added back to r. That is, the remainder is restored by r + b, where r is the remainder in the current iteration. The restored remainder r + b is then shifted to the left by one bit, that is, 2(r + b). Then b is subtracted from the shifted remainder, that is, 2(r + b) − b.
Because 2(r + b) − b = 2r + b, we can use the negative remainder r directly for the calculation of the next iteration. This is the idea of the nonrestoring division algorithm. That is, if the partial remainder is negative, we shift it to the left directly and add b to the shifted partial remainder. If the partial remainder is not negative, we shift it to the left and subtract b from the shifted partial remainder (same as the restoring algorithm).
[syntax=verilog]/************************************************
The Verilog HDL code example is from the book
Computer Principles and Design in Verilog HDL
by Yamin Li, published by A JOHN WILEY & SONS
************************************************/
module div_nonrestoring (a,b,start,clk,clrn,q,r,busy,ready,count);
input [31:0] a; // dividend
input [15:0] b; // divisor
input start; // start
input clk, clrn; // clk,reset
output [31:0] q; // quotient
output [15:0] r; // remainder
output reg busy; // busy
output reg ready; // ready
output [4:0] count; // count
reg [31:0] reg_q;
reg [15:0] reg_r;
reg [15:0] reg_b;
reg [4:0] count;
wire [16:0] sub_add = reg_r[15]?
{reg_r,reg_q[31]} + {1'b0,reg_b} : // + b
{reg_r,reg_q[31]} - {1'b0,reg_b}; // - b
assign q = reg_q;
assign r = reg_r[15]? reg_r + reg_b : reg_r; // adjust r
always @ (posedge clk or negedge clrn) begin
if (!clrn) begin
busy <= 0;
ready <= 0;
end else begin
if (start) begin
reg_q <= a; // load a
reg_b <= b; // load b
reg_r <= 0;
busy <= 1;
ready <= 0;
count <= 0;
end else if (busy) begin
reg_q <= {reg_q[30:0],~sub_add[16]}; // << 1
reg_r <= sub_add[15:0];
count <= count + 5'b1; // count++
if (count == 5'h1f) begin // finish
busy <= 0;
ready <= 1; // q,r ready
end
end
end
end
endmodule[/syntax]
However, when I try to understand non-restoring division algorithm. I found it strange at the need of checking reg_r[15] at lines 20 and 24. It is not the negative overflow bit in this module here. Any reason why ?
wire [16:0] sub_add = reg_r[15]?
{reg_r,reg_q[31]} + {1'b0,reg_b} : // + b
{reg_r,reg_q[31]} - {1'b0,reg_b}; //-b
reg_r <= sub_add[15:0];
Thanks.
I have tried the manual calculation myself and failed twice with two different numbers, not sure what I did wrong.
Then I tried to refer to https://people.cs.pitt.edu/~cho/cs0447/currentsemester/handouts/lect-ch3p2_2up.pdf#page=5 , but I found it strange at why at the last step, shift “left half of remainder” right by 1 ?
to understand above you had to understand the examples in page 10 of your document..what is really the purpose of line 24: assign r = reg_r[15]? reg_r + reg_b : reg_r; ?
For lines 20 and 24, why use reg_r[15] instead of sub_add[16] ?
Code Verilog - [expand] 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 /************************************************ The Verilog HDL code example is from the book Computer Principles and Design in Verilog HDL by Yamin Li, published by A JOHN WILEY & SONS ************************************************/ module div_nonrestoring (a,b,start,clk,clrn,q,r,busy,ready,count); input [3:0] a; // dividend input [1:0] b; // divisor input start; // start input clk, clrn; // clk,reset output [3:0] q; // quotient output [1:0] r; // remainder output reg busy; // busy output reg ready; // ready output [1:0] count; // count reg [3:0] reg_q; reg [1:0] reg_r; reg [1:0] reg_b; reg [1:0] count; wire [2:0] sub_add = reg_r[1]? {reg_r,reg_q[3]} + {1'b0,reg_b} : // + b {reg_r,reg_q[3]} - {1'b0,reg_b}; // - b assign q = reg_q; assign r = reg_r[1]? reg_r + reg_b : reg_r; // adjust r always @ (posedge clk or negedge clrn) begin $display("ready = %2b, reg_r = %2b, reg_q = %4b, sub_add[2] = %2b, reg_r[1] = %2b, r = %d", ready, reg_r[1:0], reg_q[3:0], sub_add[2], reg_r[1], r); if (!clrn) begin busy <= 0; ready <= 0; end else begin if (start) begin reg_q <= a; // load a reg_b <= b; // load b reg_r <= 0; busy <= 1; ready <= 0; count <= 0; end else if (busy) begin reg_q <= {reg_q[2:0],~sub_add[2]}; // << 1 reg_r <= sub_add[1:0]; count <= count + 1; // count++ if (count == 3) begin // finish busy <= 0; ready <= 1; // q,r ready end end end end endmodule
Code Verilog - [expand] 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 /************************************************ The Verilog HDL code example is from the book Computer Principles and Design in Verilog HDL by Yamin Li, published by A JOHN WILEY & SONS ************************************************/ `timescale 1ns/1ns module div_nonrestoring_tb; reg [3:0] a; reg [1:0] b; reg start; reg clk,clrn; wire [3:0] q; wire [1:0] r; wire busy; wire ready; wire [1:0] count; div_nonrestoring div (a,b,start,clk,clrn,q,r,busy,ready,count); initial begin $dumpfile("div_nonrestoring.vcd"); $dumpvars(0,div_nonrestoring_tb); clrn = 0; start = 0; clk = 1; a = 4'h9; b = 2'h2; #5 clrn = 1; start = 1; #10 start = 0; #40 start = 1; #5 a = 4'h7; b = 2'h2; #10 start = 0; #40 start = 1; #5 a = 4'h7; b = 2'h3; #10 start = 0; #50 $finish; end always #5 clk = !clk; endmodule
/************************************************
The Verilog HDL code example is from the book
Computer Principles and Design in Verilog HDL
by Yamin Li, published by A JOHN WILEY & SONS
************************************************/
`timescale 1ns/1ns
module division;
reg [3:0] a;
reg [1:0] b;
reg start;
reg clk,clrn;
wire [3:0] q;
wire [1:0] r;
wire busy;
wire ready;
wire [1:0] count;
div_nonrestoring div ( .a(a),
.b(b),
.start(start),
.clk(clk),
.clrn(clrn),
.q(q),
.r(r),
.busy(busy),
.ready(ready),
.count(count)
);
initial begin
// $dumpfile("div_nonrestoring.vcd");
// $dumpvars(0,div_nonrestoring_tb);
clrn = 0;
start = 0;
clk = 1;
a = 4'h9;
b = 2'h2;
#5 clrn = 1;
start = 1;
#10 start = 0;
#40 start = 1;
#5 a = 4'h7;
b = 2'h2;
#10 start = 0;
#40 start = 1;
a = 4'h7;
b = 2'h1;
#10 start = 0;
// #50 $finish;
end
always #5 clk = !clk;
endmodule
/************************************************
The Verilog HDL code example is from the book
Computer Principles and Design in Verilog HDL
by Yamin Li, published by A JOHN WILEY & SONS
************************************************/
module div_nonrestoring (a,b,start,clk,clrn,q,r,busy,ready,count);
input [3:0] a; // dividend
input [1:0] b; // divisor
input start; // start
input clk, clrn; // clk,reset
output [3:0] q; // quotient
output [1:0] r; // remainder
output reg busy; // busy
output reg ready; // ready
output [1:0] count; // count
reg [3:0] reg_q;
reg [1:0] reg_r;
reg [1:0] reg_b;
reg [1:0] count;
wire [2:0] sub_add = reg_r[1]?
{reg_r,reg_q[3]} + {1'b0,reg_b} : // + b
{reg_r,reg_q[3]} - {1'b0,reg_b}; // - b
assign q = reg_q;
assign r = reg_r[1]? reg_r + reg_b : reg_r; // adjust r
always @ (posedge clk or negedge clrn) begin
// $display("ready = %2b, reg_r = %2b, reg_q = %4b, sub_add[2] = %2b, reg_r[1] = %2b, r = %d", ready, reg_r[1:0], reg_q[3:0], sub_add[2], reg_r[1], r);
if (!clrn) begin
busy <= 0;
ready <= 0;
end else begin
if (start) begin
reg_q <= a; // load a
reg_b <= b; // load b
reg_r <= 0;
busy <= 1;
ready <= 0;
count <= 0;
end else if (busy) begin
reg_q <= {reg_q[2:0],~sub_add[2]}; // << 1
reg_r <= sub_add[1:0];
count <= count + 1; // count++
if (count == 3) begin // finish
busy <= 0;
ready <= 1; // q,r ready
end
end
end
end
endmodule
dipin, I have created https://www.edaplayground.com/x/j4v
You could just run and add only the signals "a", "b", "q", "r" and "ready" as shown below or in https://i.imgur.com/z4DjVqA.png
View attachment 137648
and also notethe changes i made in your test bechmistake is you made is assigning 3 to you 2 bit input
and because of your design using unsigned registers, you need to select unsigned outputs in waveform window
Code Verilog - [expand] 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 /************************************************ The Verilog HDL code example is from the book Computer Principles and Design in Verilog HDL by Yamin Li, published by A JOHN WILEY & SONS ************************************************/ `timescale 1ns/1ps module div_nonrestoring (a,b,start,clk,clrn,q,r,busy,ready,count); input [3:0] a; // dividend input [1:0] b; // divisor input start; // start input clk, clrn; // clk,reset output [3:0] q; // quotient output [1:0] r; // remainder output reg busy; // busy output reg ready; // ready output [1:0] count; // count reg [3:0] reg_q; reg [1:0] reg_r; reg [1:0] reg_b; reg [1:0] count; wire [2:0] sub_add = reg_r[1]? {reg_r,reg_q[3]} + {1'b0,reg_b} : // + b {reg_r,reg_q[3]} - {1'b0,reg_b}; // - b assign q = reg_q; assign r = reg_r[1]? reg_r + reg_b : reg_r; // adjust r always @ (posedge clk or negedge clrn) begin // $display("ready = %2b, reg_r = %2b, reg_q = %4b, sub_add[2] = %2b, reg_r[1] = %2b, r = %d", ready, reg_r[1:0], reg_q[3:0], sub_add[2], reg_r[1], r); if (!clrn) begin busy <= 0; ready <= 0; end else begin if (start) begin reg_q <= a; // load a reg_b <= b; // load b reg_r <= 0; busy <= 1; ready <= 0; count <= 0; end else if (busy) begin reg_q <= {reg_q[2:0],~sub_add[2]}; // << 1 reg_r <= sub_add[1:0]; count <= count + 1; // count++ if (count == 3) begin // finish busy <= 0; ready <= 1; // q,r ready end end end end endmodule
Code Verilog - [expand] 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 /************************************************ The Verilog HDL code example is from the book Computer Principles and Design in Verilog HDL by Yamin Li, published by A JOHN WILEY & SONS ************************************************/ `timescale 1ns/1ps module div_nonrestoring_tb; reg [3:0] a; reg [1:0] b; reg start; reg clk,clrn; wire [3:0] q; wire [1:0] r; wire busy; wire ready; wire [1:0] count; div_nonrestoring div ( .a(a), .b(b), .start(start), .clk(clk), .clrn(clrn), .q(q), .r(r), .busy(busy), .ready(ready), .count(count) ); initial begin $dumpfile("div_nonrestoring.vcd"); $dumpvars(0,div_nonrestoring_tb); clrn = 0; start = 0; clk = 1; a = 4'h5; b = 2'h3; #5 clrn = 1; #5 start = 1; #10 start = 0; #40 start = 1; a = 4'h7; b = 2'h3; #10 start = 0; #40 start = 1; a = 4'h5; b = 2'h2; #10 start = 0; #40 start = 1; a = 4'h7; b = 2'h2; #10 start = 0; #50 $finish; end always #5 clk = !clk; endmodule
Code Verilog - [expand] 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 /************************************************ The Verilog HDL code example is from the book Computer Principles and Design in Verilog HDL by Yamin Li, published by A JOHN WILEY & SONS ************************************************/ `timescale 1ns/1ps module div_nonrestoring (a,b,start,clk,clrn,q,r,busy,ready,count); input [3:0] a; // dividend input [1:0] b; // divisor input start; // start input clk, clrn; // clk,reset output [3:0] q; // quotient output [1:0] r; // remainder output reg busy; // busy output reg ready; // ready output [1:0] count; // count reg [3:0] reg_q; reg [2:0] reg_r; reg [1:0] reg_b; reg [1:0] count; wire [2:0] sub_add = reg_r[2]? {reg_r[1:0],reg_q[3]} + {1'b0,reg_b} : // + b {reg_r[1:0],reg_q[3]} - {1'b0,reg_b}; // - b assign q = reg_q; assign r = reg_r[2]? reg_r[1:0] + reg_b : reg_r[1:0]; // adjust r always @ (posedge clk or negedge clrn) begin // $display("ready = %2b, reg_r = %2b, reg_q = %4b, sub_add[2] = %2b, reg_r[1] = %2b, r = %d", ready, reg_r[1:0], reg_q[3:0], sub_add[2], reg_r[1], r); if (!clrn) begin busy <= 0; ready <= 0; end else begin if (start) begin reg_q <= a; // load a reg_b <= b; // load b reg_r <= 0; busy <= 1; ready <= 0; count <= 0; end else if (busy) begin reg_q <= {reg_q[2:0],~sub_add[2]}; // << 1 reg_r <= sub_add; count <= count + 1; // count++ if (count == 3) begin // finish busy <= 0; ready <= 1; // q,r ready end end end end endmodule
Code Verilog - [expand] 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 /************************************************ The Verilog HDL code example is from the book Computer Principles and Design in Verilog HDL by Yamin Li, published by A JOHN WILEY & SONS ************************************************/ `timescale 1ns/1ps module div_nonrestoring_tb; reg [3:0] a; reg [1:0] b; reg start; reg clk,clrn; wire [3:0] q; wire [1:0] r; wire busy; wire ready; wire [1:0] count; div_nonrestoring div ( .a(a), .b(b), .start(start), .clk(clk), .clrn(clrn), .q(q), .r(r), .busy(busy), .ready(ready), .count(count) ); initial begin $dumpfile("div_nonrestoring.vcd"); $dumpvars(0,div_nonrestoring_tb); clrn = 0; start = 0; clk = 1; a = 4'h5; b = 2'h3; #5 clrn = 1; #5 start = 1; #10 start = 0; #40 start = 1; a = 4'h6; b = 2'h3; #10 start = 0; #40 start = 1; a = 4'h7; b = 2'h3; #10 start = 0; #40 start = 1; a = 4'h5; b = 2'h2; #10 start = 0; #40 start = 1; a = 4'h6; b = 2'h2; #10 start = 0; #40 start = 1; a = 4'h7; b = 2'h2; #10 start = 0; #50 $finish; end always #5 clk = !clk; endmodule
We use cookies and similar technologies for the following purposes:
Do you accept cookies and these technologies?
We use cookies and similar technologies for the following purposes:
Do you accept cookies and these technologies?