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 algorithm problem

Status
Not open for further replies.

kommu4946

Member level 4
Joined
Feb 21, 2014
Messages
71
Helped
13
Reputation
26
Reaction score
11
Trophy points
1,288
Location
India
Activity points
1,846
Hi,

I have found restoring division algorithm in below pdf.**broken link removed**

i used 4 bits for dividend ,divisor,quotient, what i observed is for 15/10,the algorithm is giving quotient as 14 and reminder as 3 but actually it should be 1 and 5 respectively.Is there any bit length problem in algorithm or any limitation of restoring algorithm is there? I have written verilog code for it and randomly given inputs and it is working for 15/1...to..15/9 and from 15/10 on wards results are not matching with paper pen type division .Please find the code and tb
Code:
module restore_divider#(parameter BIT_WIDTH = 16)
(
input     wire                    clk,
input     wire                    n_rst,
input     wire [BIT_WIDTH -1 :0]  dividend,
input     wire [BIT_WIDTH -1 :0]  divisor,
input     wire                    data_vld,
output    reg  [BIT_WIDTH -1 :0]  reminder,
output    reg  [BIT_WIDTH -1 :0]  quotient,
output    reg                     div_out_vld 
    );
    

parameter      INIT      = 4'b0001,
               SHIFT     = 4'b0010,
               RESTORE   = 4'b0100,
               DIV_END   = 4'b1000;

reg            [BIT_WIDTH-1 :0]   count;

//wire signed    [BIT_WIDTH-1 :0]   temp;
wire           [BIT_WIDTH-1 :0]   temp;
reg            [BIT_WIDTH-1 :0]   accum;
reg            [BIT_WIDTH-1 :0]   mq;
reg                        [3:0]  state;
assign temp               = accum - divisor;







always @(posedge clk)
begin
    if(!n_rst)
    begin
        count            <= 0;
        accum            <= 0;
        mq               <= 0;
        state            <= INIT;
        reminder         <= 0;
        quotient         <= 0;
        div_out_vld      <= 0;
        
    end
    else
    begin
        case(state)
            INIT: begin
                    count     <= 0;
                    accum     <= 0;
                    quotient  <= 0; 
                    reminder  <= 0; 
                    div_out_vld <= 0;
                        if(data_vld)
                        begin
                            mq   <= dividend;
                            state <= SHIFT;
                        end   
                        else
                        begin
                            mq   <= mq;
                            state <= INIT;
                        end                    
            end
            SHIFT :begin
                mq     <= mq << 1'b1;
                accum  <= {accum ,mq[BIT_WIDTH-1]};
                state  <= RESTORE;
            end
            RESTORE: begin
                    if(temp[BIT_WIDTH-1] == 1'b0)
                    begin
                        accum <= temp;
                        mq    <= {mq[BIT_WIDTH-1:1],1'b1};
                        
                    end
                    else
                    begin
                        accum <= temp + divisor;
                        mq    <= {mq[BIT_WIDTH-1:1],1'b0};;
                    end
                    count <= count + 1'b1;
                    if(count == BIT_WIDTH-1)
                        state <= DIV_END;
                    else
                        state <= SHIFT;
             end
             DIV_END : begin
                quotient     <= mq;
                reminder     <= accum;
                div_out_vld  <= 1'b1;
                state        <= INIT;
              end
       endcase
    end
end
endmodule
and tb is
Code:
module tb_sim();
   parameter BIT_WIDTH  = 4;
   reg                             clk;
   reg                             n_rst;
   reg [BIT_WIDTH -1 :0]           dividend;
   reg [BIT_WIDTH -1 :0]           divisor;
   reg                             data_vld;
   wire  [BIT_WIDTH -1 :0]         reminder;
   wire  [BIT_WIDTH -1 :0]         quotient;
   wire                            div_out_vld;
   
   initial
   begin
    clk              = 0;
    n_rst            = 0;
    dividend         = 0;
    divisor          = 0;
    data_vld         = 0;
    repeat(5) @(posedge clk);
    n_rst            = 1;
    dividend         = 15;
    divisor          = 10;
    data_vld         = 1'b1;
    @(posedge clk);
    data_vld         = 1'b0;
    repeat(20) @(posedge clk);
    n_rst            = 1;
    dividend         = 15;
    divisor          = 9;
    data_vld         = 1'b1;
    @(posedge clk);
    data_vld         = 1'b0; 
    repeat(20) @(posedge clk);
    n_rst            = 1;
    dividend         = 15;
    divisor          = 8;
    data_vld         = 1'b1;
    @(posedge clk);
    data_vld         = 1'b0; 
  end
  
  always #10 clk = ~clk;
   
  restore_divider#(.BIT_WIDTH(BIT_WIDTH))
  DUT
   (
    .clk            (clk            ),
    .n_rst          (n_rst          ),
    .dividend       (dividend       ),
    .divisor        (divisor        ),
    .data_vld       (data_vld       ),
    .reminder       (reminder       ),
    .quotient       (quotient       ),
    .div_out_vld    (div_out_vld    )
       );   
endmodule
 

Seriously, you want someone to actually debug this for you? Do it yourself by compiling your code and testbench, then load the design in a simulator and add all the signals in the divider in the waveform viewer. Run the simulation follow the calculations in the waveform viewer and see where it messes up.
 
Seriously, you want someone to actually debug this for you? Do it yourself by compiling your code and testbench, then load the design in a simulator and add all the signals in the divider in the waveform viewer. Run the simulation follow the calculations in the waveform viewer and see where it messes up.

Thanks for your suggestion ,here i did manual performed algorithm described in that link and simulated the code for that values they are matching but not equal to pen and paper type division.see the figure and algorithm flow for 15/10

accum mq
0000 1111 <------------ load initially mq with dividend and zero to accum
0001 111_ <------------ shift accum and mq together
0001
-1010 (using 2's complement) 111_ <------------ subtract divisor from accum (add 2's complement of 1010)
-------
0111 (here result is positive) 1111 <------------ filled lsb of mq with 1

increament count to 1

0111 1111
1111 111_ <--------------- shift accum and mq together
1111
-1010
------
0101(here result is positive) 1111 <--------------- filled lsb with 1

inreament count to 2

0101 1111
1011 111_ <-------------- shift accum and mq together
1011
-1010
------
0001 (here result is positive) 1111 <----------------- filled lsb with 1


inrement count to 3

0001 1111
0011 111_ <-------------------- shift accum and mq together
0011
-1010
--------
1001 (here result is negative) 1110 <-------------------- filled lsb with 0
0011 (restored sum ) (reminder) 1110 (quotient)
so 15/10 reminder 3 and quotient is 14 ?

In the verilog code even i tried with declaring temp as signed or unsigned it is giving same results.
 

Hi,

15 = 0xF = 0b1111
10 = 0xA = 0b1010 two's complement is 0b0110
Result init = 0b0000

First test if 0b1111 > 0b1010
True: result = result shifted one bit left + 0b0001 ( now result is 0b0001 = 1)
Now add: 0b1111 + 0b0110 = 0b0101 = remainder = 5

( if not true, then shift result one bit left, without adding something
Don't subtract anything from 0b1111)

Finished
(This is not complete....it just shows the important steps for your example)

Klaus
 

Hi,

15 = 0xF = 0b1111
10 = 0xA = 0b1010 two's complement is 0b0110
Result init = 0b0000

First test if 0b1111 > 0b1010
True: result = result shifted one bit left + 0b0001 ( now result is 0b0001 = 1)
Now add: 0b1111 + 0b0110 = 0b0101 = remainder = 5

( if not true, then shift result one bit left, without adding something
Don't subtract anything from 0b1111)

Finished
(This is not complete....it just shows the important steps for your example)

Klaus
Can you just elaborate the above procedure further and what is wrong with the algorithm given in the above pdf link.

Regards
 

Hi,

I don´t see how you did the two´s complement.
(I can´t find 0b1010 --> 0b0110)

What exactely is unclear with my explanation?
(I don´t want to discuss the whole division theory here. Others have done this before, much better than I can)

Klaus
 

• (i) Shift the register pair (P,A) one bit left
• (ii) Subtract the contents of B from P, put the result back in P
• (iii) If the result is -ve, set the low-order bit of A to 0 otherwise to 0
• (iv) If the result is -ve, restore the old value of P by adding the
contents of B back in P
Not a very well proofread presentation.

How about looking at a more hardware oriented presentation: https://people.cs.pitt.edu/~childers/CS0447/lectures/division.pdf

Or if you need to understand the algorithm better as program steps: https://en.wikipedia.org/wiki/Division_algorithm#Restoring_division

Your code doesn't appear to do any of the checks for negative values and restoring, nor does it seem to even do the subtraction steps, or at least I can't see where that is done in your uncommented code.

Here is another paper, which goes into detail on each step of the restoring division algorithm that might help: **broken link removed**
 
Not a very well proofread presentation.

How about looking at a more hardware oriented presentation: https://people.cs.pitt.edu/~childers/CS0447/lectures/division.pdf

Or if you need to understand the algorithm better as program steps: https://en.wikipedia.org/wiki/Division_algorithm#Restoring_division

Your code doesn't appear to do any of the checks for negative values and restoring, nor does it seem to even do the subtraction steps, or at least I can't see where that is done in your uncommented code.

Here is another paper, which goes into detail on each step of the restoring division algorithm that might help: **broken link removed**

The first link provided you is exactly same as the link i mentioned except some typo error.Actually i resolved the issue i un commented temp to signed and increased bitwidth of temp by 1,Then it is giving proper results.The problem is overflow of addition of 2's complement of divisor and temp.
I don´t see how you did the two´s complement.
(I can´t find 0b1010 --> 0b0110)

I did add 2's complement of 10 only but i specified it as 15-10 in binary representation.

Regards
 
Last edited:

Hi,

I think your two´s complement calculation is wrong.

10 in decimal = 0b1010

15 in decimal is 0b1111

so is you want to calculate : 15 - 10 = 5 then
you can use true subtraction: 0b1111 - 0b1010 = 0b0101

or you may add the negative value of 10 (= -10)
15 +(-10) = 5
0b1111 + 0b0110 = 0b0101

****
I wonder why you don´t do it exactely as in decimal.


Klaus
 

Hi,

I think your two´s complement calculation is wrong.

10 in decimal = 0b1010

15 in decimal is 0b1111

so is you want to calculate : 15 - 10 = 5 then
you can use true subtraction: 0b1111 - 0b1010 = 0b0101

or you may add the negative value of 10 (= -10)
15 +(-10) = 5
0b1111 + 0b0110 = 0b0101

****
I wonder why you don´t do it exactely as in decimal.


Klaus

I did 2's complement after shifting in every step in iteration 1 accum is 0001 (after left shift) and divisor is1010 whose 2's complement is 0110.

0001
+0110
--------
0111
-------

like this i did for every step in post #3 (please see it)

Regards
 

Hi,


0001
+0110
--------
0111
-------

Good example to show your mistake.

--> When the input is 0b0001 you don´t subtract anything.

Aagin, again, please do it in decimal to see your problem.

Klaus
 

I think there is a mismatch between what you are saying and what iam refering( IAM REFERING ALGORITHM IN THE LINK you are refering normal pencil and paper type i guess).

Lets follow the normal decimal divison
for dividend 15 and divisor 10
10)15(1
10
-----
5 (now this reminder is lessthan divisor so no need of further subtraction hence it is the final reminder and quotient is 1)

Now lets assume dividend is 254 and divisor is 2
2)254(127 <--- final quotient
-200
-----------
54 (reminder is greater than divisor so futher subtract is needed)
-40
-----------
14 (reminder is greater than divisor so further operation is needed)
-14
---------------
0 <----- final reminder

Now the above procedure is just pencil and paper type method only we can not implement hardware similar way ,so thats way shift and restore method is there (iam not sure it please correct me if iam wrong)

if i follow your procedure

First test if 0b1111 > 0b1010
True: result = result shifted one bit left + 0b0001 ( now result is 0b0001 = 1)
Now add: 0b1111 + 0b0110 = 0b0101 = remainder = 5
( if not true, then shift result one bit left, without adding something
Don't subtract anything from 0b1111)

00000010)11111110(11
-00000010
------------
11111100
-00000010
------------
11111011
like this we need to do the operation till the reminder is less than 2 which takes 254 clock cycles in implementation
 

0001
+0110
--------
0111
-------
I think you missed KlausST point entirely...

1 (0001) - 10 (1010) /= 7 (0111)

-10 in 2's complement can't be represented in only 4 bits. It requires 5 bits so you can have the MSB mean -2^4 (-16).
 
I think you missed KlausST point entirely...

1 (0001) - 10 (1010) /= 7 (0111)

-10 in 2's complement can't be represented in only 4 bits. It requires 5 bits so you can have the MSB mean -2^4 (-16).
Actually i resolved the issue uncommented temp to signed and increased bitwidth of temp by 1,Then it is giving proper results.The problem is overflow of addition of 2's complement of divisor and temp.
In post # 8 i did resolved by increasing bit width to 1 Then problem got resolved.
Thanks ads-ee and Klaus


Regards
 

Status
Not open for further replies.

Part and Inventory Search

Welcome to EDABoard.com

Sponsor

Back
Top