Fixed point signed multiplication algorithm

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
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

Re: Fixed point signed multiplication algorithm

Quoted text here. Click to load it

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

--
"almost all programming can be viewed as an exercise in caching"


Re: Fixed point signed multiplication algorithm
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:

Quoted text here. Click to load it


Re: Fixed point signed multiplication algorithm
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:

Quoted text here. Click to load it

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
We've slightly trimmed the long signature. Click to see the full one.

Site Timeline