Fixed point signed multiplication algorithm

[praveen]

Hello,
I am implementating Fixed point signed multiplication. Is there a
algorithm to implement it. I have done the usual method of
multiplication i.e partial products ...shift and add method. But its
very slow. If you know any algorithm which will faster do mention. Any
reference will be great. How does the signed multipliers in xilinx
that fast. what algorithm do they use. I need to first implement in on
MATLAB and see the result.

waiting for reply
praveen

 

[Terje Mathisen]

praveen wrote:

Hello,
I am implementating Fixed point signed multiplication. Is there a
algorithm to implement it. I have done the usual method of
multiplication i.e partial products ...shift and add method. But its
very slow. If you know any algorithm which will faster do mention. Any
reference will be great. How does the signed multipliers in xilinx
that fast. what algorithm do they use. I need to first implement in on
MATLAB and see the result.

Do you need the full (double-wide) result, or just the lower N bits of
an NxN bit imul?

The fastest pure sw method I know (for relatively small values of N) is
to use branchless conversion to absolute values, do the multiplication
via a lookup table of squares, and then a branchless fixup of the sign
at the end.

Terje

--
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"

 

[Ken McElvain]

In VHDL, use a signed type and use '*' - synthesis should
generate a good result.

In current verilog, just use a signed type.

In older verilog versions you can simply sign extend the
inputs to the width of the result and perform an unsigned
multiply. Synplify will recognize this as a signed multiply
and trim the input arguments back down.

Synthesis tools should give you a good implementation directly.
All you need to do is figure out where the binary point went
and take the bits you want.


praveen wrote:

Hello,
I am implementating Fixed point signed multiplication. Is there a
algorithm to implement it. I have done the usual method of
multiplication i.e partial products ...shift and add method. But its
very slow. If you know any algorithm which will faster do mention. Any
reference will be great. How does the signed multipliers in xilinx
that fast. what algorithm do they use. I need to first implement in on
MATLAB and see the result.

waiting for reply
praveen

 

[Ray Andraka]

Praveen,

have a look at the multipliers page on my website. I cover several ways
to do multiplication there. The fastest in-the-fabric multipliers in
Xilinx use 2xN partial products combined in an adder tree. The embedded
multiplier blocks aren't constrained by the FPGA LUT structure, so they
use a modified booth design that is appropriate to ASICs, but not to
multipliers done using FPGA LUTs.

praveen wrote:

Hello,
I am implementating Fixed point signed multiplication. Is there a
algorithm to implement it. I have done the usual method of
multiplication i.e partial products ...shift and add method. But its
very slow. If you know any algorithm which will faster do mention. Any
reference will be great. How does the signed multipliers in xilinx
that fast. what algorithm do they use. I need to first implement in on
MATLAB and see the result.

waiting for reply
praveen

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759