 # Multiplier Block Generator

## Explanation

A multiplier block implements a parallel multiplication of a variable with a fixed set of constants. Such multiplier blocks are relevant, for example, for FIR filters. Below we show a general multiplier block and a very simple example - a multiplier block for the parallel multiplication with the constants 23 and 81, generated by our tool .  Parallel multiple constant multiplication (MCM) An example multiplier block, implementing multiplication by 23 and 81

Generation of the minimal cost multiplier block is an NP-complete problem. The currently best heuristic method is provided by our recent paper , which also serves as an overview on the best existing methods. Below we provide an online interface to our algorithm (called Hcub) and two competing methods.

Other multiplierless problems

## Generator

Input: A list of integer or fixed-point constants c_1, ..., c_n.

Output: Pseudo code and the corresponding directed acyclic graph (DAG) for the multiplier block implementing the parallel multiplications c_1*x, ..., c_n*x. The only operations used in the generated DAG and code are additions, subtractions, shifts and negations (if there are negative constants).

Parameter ValueExplanation
Constants Integer or floating point constants. Maximum 20 constants. Floating point constants will be converted into integers using the number of fractional bits given below. Maximum 25 bits after conversion.
Fractional bits Constants will be scaled by 2^f, where f is the value given here. Use 0 for integer constants.
Algorithm MCM algorithm to use. Hcub is our algorithm , BHM , and RAG-n  (limited to 19 bit constants).
Depth limit Maximum allowed adder tree depth. Reducing the depth increases the adder cost. Small depth results in lower latency in hardware.
Secondary optimization 'Randomize' will lead to somewhat different results on every run. 'Reduce adder size' is deterministic and minimizes non-output fundamental sum (NOFS) which is the sum of intermediate constants. This leads to smaller adders in hardware.

## Benchmark

Two example benchmarks from . The plots compare the number of constants (n) and constant bitwidth (b) versus the average number of add/subtract operations in the generated multiplier block for b=19 and n=10, respectively. Note, that we do not count shifts. We compare our new algorithm Hcub  to the other algorithms described below.  Number of constants vs. op-count for b=19 bits Constant bitwidth vs. op-count for n=10 constants
• Hcub. New MCM algorithm from our recently accepted paper .
• RAG-n. Previously the best published MCM algorithm that we are aware of. We have reimplemented the algorithm, and generated the required lookup table up to 19 bits. Further, we improved the algorithms by inserting our complete A-distance test for distance 2, in which case the original implementation used a heuristic only. RAG-n relies on the availability of optimal single constant decomposition table . RAG-n is described in .
• BHM. This is an improved version of the BHA (i.e., the ``add/subtract/shift'' algorithm from . We have implemented this algorithm in C++ using the BHA pseudo-code given in  and the BHM improvements from .
• Common subexpression elimination. This is one of the newer common subexpression elimination based MCM algorithms by V. Lefèvre . The algorithm uses more sophisticated methods for identifying common subexpressions than those used in previous works. The author has kindly provided us with his implementation.

Our software is available under GNU GPL license. Commercial license can be obtained on request.

synth-jan-14-2009.tar.gz (new: depth limits, randomization, NOFS reduction)

synth-feb-20-2006.tar.gz

To use RAG-n download and unzip the file below. Pass the file as an argument to -ac1 option

20min.chains.gz

## References

1. Yevgen Voronenko and Markus Püschel
Multiplierless Multiple Constant Multiplication
ACM Transactions on Algorithms, Vol. 3, No. 2, 2007
[ Figures (PNG) ]
2. D. R. Bull and D. H. Horrocks
Primitive operator digital filters
IEE Proceedings G, 138(3):401-412, 1991
[ BIB ]
3. A. G. Dempster and M. D. Macleod
Use of minimum-adder multiplier blocks in FIR digital filters
IEEE Transactions in Circuits and Systems-II: Analog and Digital Signal Processing, 42(9):569-577, 1995
[ BIB ]
4. A. G. Dempster and M. D. Macleod.
Constant integer multiplication using minimum adders
IEE Proceedings - Circuits, Devices and Systems, 141(5):407-413, 1994
[ BIB ]
5. V. Lefèvre.
Multiplication by an integer constant
Technical report, INRIA, 2001. [ BIB | HTML ]