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 [1].

Generation of the minimal cost multiplier block is an NP-complete problem. The currently best heuristic method is provided by our recent paper [1], 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.

**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).

**Hcub.**New MCM algorithm from our recently accepted paper [1].**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 [4]. RAG-n is described in [3].**BHM**. This is an improved version of the BHA (i.e., the ``add/subtract/shift'' algorithm from [2]. We have implemented this algorithm in C++ using the BHA pseudo-code given in [2] and the BHM improvements from [3].**Common subexpression elimination**. This is one of the newer common subexpression elimination based MCM algorithms by V. Lefèvre [5]. 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)

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

- Yevgen Voronenko and Markus Püschel

**Multiplierless Multiple Constant Multiplication**

ACM Transactions on Algorithms, Vol. 3, No. 2, 2007

[ Figures (PNG) ] - D. R. Bull and D. H. Horrocks

**Primitive operator digital filters**

*IEE Proceedings G*, 138(3):401-412, 1991

[ BIB ] - 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 ] - 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 ] - V. Lefèvre.

**Multiplication by an integer constant**

*Technical report, INRIA, 2001.*[ BIB | HTML ]

See also the Spiral Multiplierless Constant Multiplication website.

Copyright (c) 2006-2009 by Yevgen Voronenko for the Spiral project, Carnegie Mellon University

Contact: help at spiral dot net