Re: [oc] Binary Divides for uP core

[Richard Herveille <richard@asics.ws>]

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