Re: [oc] Binary Divides for uP core

[Richard Herveille <richard@asics.ws>]

Correct, these are called high-radix dividers (comparable to high-radix
multipliers).
If you are targeting ASICS and have time to/want to generate the tables
this works great and is faster than a radix-2 (1-bit at a time) divider.
If you are (also) targeting FPGAS, this is a NONO. Because it will make
the divider slower. This is caused by the fact that the ripple-carry
structure in FPGAS is much faster than the other structures. So your
critical path is not the adder/subtractor structure, but the lookup-tables.

Richard

>You can also multiply using a combination of look-up table and adder.
>Instead of doing a shift and add one bit at a time you can process two,
>three, four, ... bits at a time. Some of the CRC32 generators used to
>do this (way back).
>
>Also (way back), some implimentations of division generated 1/n then
>performed a multiply.
>
>     m / n = m * (1 / n)
>
>The accuracy of the remainder is not the same.
>
>Jim Dempsey
>
>
>----- Original Message -----
>From: "Richard Herveille" <richard@asics.ws>
>To: <cores@opencores.org>
>Sent: Tuesday, January 15, 2002 2:30 AM
>Subject: Re: [oc] Binary Divides for uP core
>
>
> >
> > As everybody knows (or should know), a hardware multiplier is simply a
> > bunch of adders.
> > The proces is called "multiplication by repeated addition".
> > Each adder adds a shifted-and-anded part to the final result, see example.
> >
> > A=10, B=2 A*B=
> >
> >   1010
> >     10
> > -----
> >   0000    ((1010 && 0) << 0)
> > 10100    ((1010 && 1) <<1)
> > ----- +
> > 10100
> >
> > The final result always fits into Abits + Bbits (4+2=6 bits in the
> > example), i.e.
> > the result of a k*k bit multiplication always fits into 2k bits.
> > Also there is no (real) difference between unsigned and signed
>multiplication.
> >
> >
> > Now for the difficult part division:
> >
> > Differences from the multiplication
> > 1) The most common implementation is a bunch of subtractors.
> >     This process is called "Division by repeated subtraction".
> >     Other implementations use BSD numbers and/or adder-subtractor
>structures.
> > 2) In a divider bits become available one at a time, starting at the MSB.
> >     intuitive: Try to divide 1189/4 by hand, you also start at the MSD.
> > 3) Because of point-2 dividers are inherently slower than multipliers
> >     Also single clock division is (almost) impossible.
> >     note: Single cycle IS possible (pipeline your design).
> > 4) A 2K by K division does NOT always fit into K bits
> >     example 0100/01
> > 5) There's a big difference between signed and unsigned division.
> >
> > Here are some common implementations you should try to find, because these
> > are the simplest to implement:
> > "Restoring Unsigned Divider"
> > "Non-Restoring Unsigned Divider"
> > "Non-Restoring Signed Divider"
> > "Division by repeated multiplication"
> > The last method works great, if a hardware multiplier is available.
> > There are also some structures which combine multipliers and dividers.
> >
> >
> > Richard
> >
> >
> > >Hi,
> > >
> > >Does anybody know the routine for doing a binary division in HDL?
> > >I'm developing a uP core and would like to do divisions in one
> > >clock cycle if possible? The multiple instruction was easy to
> > >figure out but I'm still stuck on the division one.
> > >
> > >Paul
> > >
> > >
> > >--
> > >To unsubscribe from cores mailing list please visit
> > >http://www.opencores.org/mailinglists.shtml
> >
> > --
> > To unsubscribe from cores mailing list please visit
>http://www.opencores.org/mailinglists.shtml
> >
>
>--
>To unsubscribe from cores mailing list please visit 
>http://www.opencores.org/mailinglists.shtml

--
To unsubscribe from cores mailing list please visit http://www.opencores.org/mailinglists.shtml