( ESNUG 278 Item 8 ) ----------------------------------------------- [1/28/98]
From: Nestor Caouras <nestor@ece.concordia.ca>
Subject: Division & Multiplication Using Alta PSW, Synopsys, & Xilinx
> In my efforts to build an efficient divider (unsigned for the time
> being), I have used a method which separates the "y/x" quotient into a
> product of "1/x" and "y". The "1/x" part is implemented in a ROM (in and
> FPGA). So the input "x" addresses the ROM and the "1/x" value is
> outputed and then multiplied with the "y" factor. Neither "x" nor "y"
> are constants which makes implemtation a little more difficult (and less
> efficient).
>
> My synthesis procedure of the method I used is the following and yields
> less than acceptable results:
>
> 1. Block diagram design in SPW (Alta Group's (Cadence) Signal
> Processing Worksystem)
> 2. VHDL code generation from SPW
> 3. Synthesis using Synopsys 3.4b
> 4. Place & route using Xilinx Alliance M1.3 and a -1 speed grade part.
>
> Any kind of input about this method or another better method for
> implemeting division (or its sub-operations) would be greatly appreciated.
> VHDL algorithms for signed or unsigned division can also be useful to my
> project. Also, any info on where to obtain a good multiplication
> algorithm would be very time saving.
>
> - Nestor Caouras
> Concordia University Montreal, Quebec, Canada
From: NgOsSmPiAtMh@passport.ca (Gregory Smith)
I assume your application can't tolerate the time required for 'bit-by-bit'
long division? Can you put several of these in skew-parallel to reduce
the effective time? It makes a huge difference what kinds of errors you
can tolerate. Your 1/x table, unless x is always close to some center
value, will become very inaccurate for large x. Have you considered a 'log'
approach? Use tables to approximate log2(x) and log2(y), and then another
table for 2^(y-x). The choice of 2 is important. For instance, 2^z can be
done by looking-up the fractional part of z and then barrel shifting by the
integer part. With this method the errors are uniform relative to the
magnitude of x and y.
For log x: rewrite x=2^k*(1+d), where k is an integer such that
(sqrt(0.5)-1) < d < (sqrt(2)-1) about -0.293 .. 0.414
'k' can be found by a 'normalize' function which finds the MSB; then
compare the normalized result to sqrt(2) and shift again if larger. Now d
is in the range above, and 'k' is the integer part of your log. The
fractional part (which may be negative) is log2(1+d); Since 1+d is close
to 1, this can be approximated efficiently by
log2(1+d) = (l/ln(2)) d + lookup[d]
where the lookup table doesn't have to be very big (i.e. only use the first
few MSB's of d). You may not have to go to such lengths, but this will
reduce the table size at the expense of additional logic. The result above
(log2(1+d)) will always fall in the range [-0.5,0.5].
Of course you can just normalize so 'd' is in [0..0.999] and lookup the
fractional log from there. log2(1+d) will also be in [0..0.9999].
Concerning a good multiplication algorithm, many VLSI texts cover this.
Look for 'Booth Coding' or 'Booth Multiplier'; that will at least bring you
to the right place.
- Gregory Smith
---- ---- ---- ---- ---- ---- ----
From: "Prof. Vitit Kantabutra" <vkantabu@computer.org>
I have some new algorithms for high-radix division that don't use
complicated table look-up. The most recent paper is available at
http://math.isu.edu/~vkantabu/radix8.pdf, and can be viewed with Adobe
Acrobat Reader 3.0 or later.
- Prof. Vitit Kantabutra
Idaho State University
|
|
