Multiplication In FPGA(1)

 EDA中国门户网站3x-j6@g*SZ`

Multiplication is basically a shift add operation.  There are, however, many variations on how to do it.  Some are more suitable for FPGA use than others.   This page is a brief tutorial on multiplication hardware.  The hyperlinked items in this list are currently in the text.  The remaining items will be added in a future release of this page.EDA中国门户网站?H%EDaun

EDA中国门户网站5olyj*s4J P4L
jYw

Scaling Accumulator Multipliers

&XP#V+d!MZ4E0A scaling accumulator multiplier performs multiplication using an iterative shift-add routine.  One input is presented in bit parallel form while the other is in bit serial form.  Each bit in the serial input multiplies the parallel input by either 0 or 1.  The parallel input is held constant while each bit of the serial input is presented.  Note that the one bit multiplication either passes the parallel input unchanged or substitutes zero.  The result from each bit is added to an accumulated sum.  That sum is shifted one bit before the result of the next bit multiplication is added to it.EDA中国门户网站]gC4}Wh

 EDA中国门户网站{h:}Akj

EDA中国门户网站&K$A9U4ev!F"xH

Serial by Parallel Booth Multipliers

&A$d |1M9I$G#]0The simple serial by parallel booth multiplier is particularly well suited for bit serial processors implemented in FPGAs without carry chains because all of its routing is to nearest neighbors with the exception of the input.   The serial input must be sign extended to a length equal to the sum of the lengths of the serial input and parallel input to avoid overflow, which means this multiplier takes more clocks to complete than the scaling accumulator version.  This is the structure used in the venerable TTL serial by parallel multiplier.

EDA中国门户网站G"m"e:~2l*G(p\cV)v"m4Z

Ripple Carry Array Multipliers

A ripple carry array multiplier (also called row ripple form) is an unrolled embodiment of the classic shift-add multiplication algorithm.  The illustration shows the adder structure used to combine all the bit products in a 4x4 multiplier.  The bit products are the logical and of the bits from each input.  They are shown in the form x,y in the drawing.  The maximum delay is the path from either LSB input to the MSB of the product, and is the same (ignoring routing delays) regardless of the path taken.  The delay is approximately 2*n.

EDA中国门户网站+el"H/J%^

This basic structure is simple to implement in FPGAs, but does not make efficient use of the logic in many FPGAs, and is therefore larger and slower than other implementations.EDA中国门户网站U+Q+`[Z
@.E:K1B

Row Adder Tree Multipliers

CiqRO?[ hG0Row Adder tree multipliers rearrange the adders of the row ripple multiplier to equalize the number of adders the results from each partial product must pass through.   The result uses the same number of adders, but the worst case path is through log2(n) adders instead of through n adders.  In strictly combinatorial multipliers, this reduces the delay.  For pipelined multipliers, the clock latency is reduced.   The tree structure of the routing means some of the individual wires are longer than the row ripple form.  As a result a pipelined row ripple multiplier can have a higher throughput in an FPGA (shorter clock cycle) even though the latency is increased.EDA中国门户网站 u tu#Un5w

EDA中国门户网站W{ ]:j2K6{

Carry Save Array Multipliers

EDA中国门户网站zp0hCPX#ng

Look-Up Table (LUT) Multipliers

r8FU#OEjz'c`0Look-Up Table multipliers are simply a block of memory containing a complete multiplication table of all possible input combinations.  The large table sizes needed for even modest input widths make these impractical for FPGAs. 

The following table is the contents for a 6 input LUT for a 3 bit by 3 bit multiplication table.