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.
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).
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
Our software is available under GNU GPL license. Commercial license can be obtained on request.
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 ]