Continue to Site

Welcome to EDAboard.com

Welcome to our site! EDAboard.com is an international Electronics Discussion Forum focused on EDA software, circuits, schematics, books, theory, papers, asic, pld, 8051, DSP, Network, RF, Analog Design, PCB, Service Manuals... and a whole lot more! To participate you need to register. Registration is free. Click here to register now.

Restoring Division Agorithm

Status
Not open for further replies.

promach

Advanced Member level 4
Joined
Feb 22, 2016
Messages
1,199
Helped
2
Reputation
4
Reaction score
5
Trophy points
1,318
Activity points
11,636
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]
 

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]

hi,

i think you should understand the restoring algorithm, (check how it set the quotient).
21 &22, if the sub_out = {reg_r,reg_q[31]} - {1'b0,reg_b}; is negative that means quotient bit is zero and need to restore the number for further division.

and 38:: they are setting the output,,, just check the algorithm how they set it...in restoring algorithm first division they will set the lsb, next division quotient is shifted to the left and set the next quotient bit...type restoring division and check 2nd result..its explains everything

regards
 
Thanks. I have understood restoring division algorithm.

The following quote is extracted from the book "Computer Principles and Design in Verilog HDL" by Yamin Li, published by A JOHN WILEY & SONS

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).

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 ?

I have tried to diff both restoring and non-storing source code as below:
https://www.diffchecker.com/GThluODV

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_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]
 

hi,
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 ?

in non-restoring , there is no restoration of the result is negative, here you need to add or subtract, input is 15 width wide and storing to

Code:
    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
sub_add (which will be minus operation in first step) .((reg_q[31] is the shifted bit from dividend ))
then::
Code:
reg_r <= sub_add[15:0];
stored to reg_r
so basically reg_r[15] will reflect whether you need to do addition or subtraction.

assign r = reg_r[15]? reg_r + reg_b : reg_r; here you are getting the remainder by checking reg_r[15].

one more thing did you checked the output using any simulator ? i doubt the above must be a signed operation !!!! so just wanted to clarify it ..

you can do a simple non-restoring division using a binary number like 1010 by 0011(using paper pen) then you will understand the concept clearly ..
if you wanted to do in hardware there are some non restoring algorithms which will use two bit shift /cycle(above one uses only one )

non-restoring is little bit complex than restoring, better you can look into some binary examples

regards
 
Last edited:
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 ?

Another questions,

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] ?
 

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 ?

in he final step, your working reg is 0001 0001. for setting the quotient for your last addition /subtraction, you need to left shit the register by 1. so your quotient will be proper but your remainder is not ,because it is left shifted by 1.( this is because of both remainder and quotient are in same register) so only remainder need to be right shifted.

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] ?
to understand above you had to understand the examples in page 10 of your document..

your code is working not how they explained it . then one more thing in the examples, they are using signed operation, but in code they didn't used any signed register,
step 1 and 2 is signed operation::(1110 1110&1111 1000 clearly mentioned that its <0) . so what they done in code is, instead of using signed operation they just took ,that is last bit, in your case r[15] for checking its is <0 or>0 . they cant use sub_add[16] because its out of range , mean shifted MSB bit.

then for your first question:: did you know how you get the remainder? assign r = reg_r[15]? reg_r + reg_b : reg_r; ? this piece of code is adjusting the remainder after calculation. check page 9 for this...

regards
 

Hi dipin,

I found that there is a bug around reg_r[15]. The author did not consider all test cases.

To simplify the situation, shall we use only 4-bits "a", 2-bits "b" just as follows:

Using the MSB bit of reg_r does not work when a=5 or 7 and when a=3
Please correct me for any mistakes I made.


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

 
Last edited by a moderator:

eda boubt.JPG

hi,

Code:
/************************************************
  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

Code:
/************************************************
  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

( i disabled all the system verilog lines , in your tool you can use it)

your this code working fine. only mistake is you made is assigning 3 to you 2 bit input :).
then probably you dont know how to check the wave form. yours is a serial design and output comes only when busy go down(need 4 clock cycle to complete operation).
check the output at above waveform. check output when busy line go down :). i used quartus for generating above waveform.
and which tool you are using for compilation ?
and because of your design using unsigned registers, you need to select unsigned outputs in waveform window

regards
 
Last edited:


dipin:

I am confused on your sentence "mistake is you made is assigning 3 to your 2 bit input".

could you elaborate on this ?
 

Last edited by a moderator:

hi,

your first input is 5,3. why its showing 5,-1 ?
2nd input 7,3 why 7,-1?
from post #8
and because of your design using unsigned registers, you need to select unsigned outputs in waveform window

i dont know what tool you are using, in quartus select a,b,q and r --> right click --> select radix --> select unsigned . check how to do this in your tool.

your all problem will be solved.
regarding #11 :: i must have mentioned 3&2. your simulation tool showing 3 & 2 as -1 and -2(your design using unsigned numbers) check signed numbers to know how its happening. so you need to change the radix to unsigned. currently its showing signed decimal.

regards
 

dipin,

thanks for the unsigned advice, but it is not the only reason for incorrect outputs at time=50ns and 100ns when the outputs are "ready=1".

I have attached the waveform after following your unsigned advice. I am using iverilog and gtkwave with the following code.

lYotQAI.png



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

 
Last edited by a moderator:

hi,
just increase the input (a&b) width and all register width accordingly.say 6 & 3
there will be an over flow or draw back in the design, thats why you wont get the out put for max input limit.
check the max input limit in your original design .

regards
 

hi,
Capture.JPG

check above image . i increased the design bitwidth to 6 & 3

regards
 

dipin,

For overflow, are you referring to reg_r ?
is the incorrect output related to MSB of reg_r which is reg_r[1] ?

However, even after I had increased bit width of reg_r to match the bit width of the dividend which is 'a', I do not have the correct output as well.
Any advice ?
 
Last edited:

dipin,

After some modification with advice from the author, the code had to be modified as follows:

Waveform:
Screenshot from 2017-04-19 00-13-53.png


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

 

Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top