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
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.
Can you just elaborate the above procedure further and what is wrong with the algorithm given in the above pdf link.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
Not a very well proofread presentation.• (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**
I don´t see how you did the two´s complement.
(I can´t find 0b1010 --> 0b0110)
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
0001
+0110
--------
0111
-------
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)
I think you missed KlausST point entirely...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).
In post # 8 i did resolved by increasing bit width to 1 Then problem got resolved.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.
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?