Re: combinational divider
On Fri, 27 Jun 2003 05:36:47 0700, hswnetin wrote:
> Hi all,
>
> I am mailing to this group for the first time. I am working in dsp
> related project where the divider is biggest problem for me. I have to
> design a combinational divider. Divider is a integer divider like, c =
> a/b. Where a, b and c takes the following values.
>
> a / b = c
> 10 / 1 = 10
> 10 / 2 = 5
> 10 / 3 = 3
> 10 / 4 = 2
> 10 / 5 = 2
> 10 / 6 = 1
> 10 / 7 = 1
> 10 / 8 = 1
> 10 / 9 = 1
> 10 / 10 = 1
> 10 / 11 = 0 .....
>
> Like this the result is rounded value. Please help me in designing
> combinational divider?
>
> Thanks in advance.
>
> Regards,
> hswnetin
What's your objective, minimum latency or maximum thoughput? If you are
looking for shortest divide time then a convergence divide using
multipliers is your best bet. If what you want is to do the greatest
number of divide operations then unrolling the divide loop into a cascaded
set of registered adder/subtractors is your best bet. It's also possible
to do two bits at a time at each stage using some prediction logic and a
shifter. I suspect that in todays technology the simplest solution, one
bit at a time, will give you the highest throughput.
If what you were hoping for was a single clock cycle divide algorithm
equivalent to a Wallace tree multiplier, then your out of luck. Division
is is done by successive approximation, in the simple case you produce one
bit per stage, in the convergence divide algorithm you can double the
number of bits at each stage. But in either case it takes more than one
stage. The only exception is dividing small numbers. You can use a lookup
table to find a reciprocal or a log but obviously the size of the lookup
is limited by the practical size of RAM/ROM. For 16 bit integers lookup
would be your best bet. For single precision floating point you could
conceivably use an off chip DRAM based table. For double precision
floating point you would use a small lookup table to get the first
approximation and then you would use your multipliers for the additional
approximations.
