Ideas on Divider design

[Sunita Jain]

Hello all,
I need a little input regarding the design of N-bit divider. Lets say
both Dividend and divisor are 8 bit nos. I mean the values may vary
from 0-255(or 127). Whats the best approach to model it in structural
format?
I have tried by using the concept of long division where I consider
the dividend to be 16 bits and then carry on by subtraction/shifting
and shifting the quotient. but due to modelling of the control logic
in my case it takes double the no. of clock cycles it taks for normal
long division process..Any ideas on how this can be achieved in a more
simple and quicker manner...
Regards,
Sunita

 

[John_H]

"Sunita Jain" <sunitajain@gmail.com> wrote in message
news:9bfc40d7.0410220725.23b4c747@posting.google.com...

Hello all,
I need a little input regarding the design of N-bit divider. Lets say
both Dividend and divisor are 8 bit nos. I mean the values may vary
from 0-255(or 127). Whats the best approach to model it in structural
format?
I have tried by using the concept of long division where I consider
the dividend to be 16 bits and then carry on by subtraction/shifting
and shifting the quotient. but due to modelling of the control logic
in my case it takes double the no. of clock cycles it taks for normal
long division process..Any ideas on how this can be achieved in a more
simple and quicker manner...
Regards,
Sunita

I, too, did the long division as one would do by hand to figure out how long
a combinatorial divide would take. What I discovered is that the
intermediate stages don't need to do a test subtraction then use the sign to
determine if the next stage uses the untouched value or the subtraction
(requiring 2 stages) but instead performs the (addition/)subtraction
regardless. If the numerator is smaller than the denominator, what does one
do with a negative number? Add the numerator to the doubled result from the
previous stage rather than subtract. The same negative check on that result
applies. The reason we can get away with this in the Verilog but not in
paper long division is the base 2 versus base 10 problem.

The caveat here is that the numerator has to be less than 2x the denominator
allowing the first result bit to be a 1. For a generic division, the
numerator can be preshifted and the result appropriately shifted back.

Another neat benefit in this long-division style form is that rounding can
be included by shifting half the numerator into the division a bit at a time
in the LSbit of the add/subtract stage.

I put together an Excel file to prove to myself the technique works. The
results are great. With the rounding included as a single extra bit, my
error in random 16-bit numbers is always within +/-0.5.

An example for a non-rounded division:

If we have a known result, it might work better...
To get a result of 27 with a denominator of 33, the numerator would be 891.
Since 891>2*33, the denominator needs to be shifted. Just doing a raw shift
of 8 bits (multiplying the denominator by 256) we evaluate the fraction
891/8448

891 -8448 = -7557 <0 0
-7557*2 +8448 = -6666 <0 0
-6666*2 +8448 = -4884 <0 0
-4884*2 +8448 = -1320 <0 0
-1320*2 +8448 = 5808 >0 1
5808*2 -8448 = 3168 >0 1
3168*2 -8448 = -2112 <0 0
-2112*2 +8448 = 4224 >0 1
4224*2 +8448 = 0 =0 1

The =0 also gives a bit result of 1. The binary number derived from the
signs - 9'b000011011 - is 9'd27, the expected result.

Division is fun!