Multiplierless multiple constant multiplication
Top Cited Papers
- 1 May 2007
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 3 (2)
- https://doi.org/10.1145/1240233.1240234
Abstract
A variable can be multiplied by a given set of fixed-point constants using a multiplier block that consists exclusively of additions, subtractions, and shifts. The generation of a multiplier block from the set of constants is known as the multiple constant multiplication (MCM) problem. Finding the optimal solution, namely, the one with the fewest number of additions and subtractions, is known to be NP-complete. We propose a new algorithm for the MCM problem, which produces solutions that require up to 20% less additions and subtractions than the best previously known algorithm. At the same time our algorithm, in contrast to the closest competing algorithm, is not limited by the constant bitwidths. We present our algorithm using a unifying formal framework for the best, graph-based MCM algorithms and provide a detailed runtime analysis and experimental evaluation. We show that our algorithm can handle problem sizes as large as 100 32-bit constants in a time acceptable for most applications. The implementation of the new algorithm is available at www.spiral.net.Keywords
This publication has 16 references indexed in Scilit:
- Complexity Reduction of Digital Filters Using Shift Inclusive Differential CoefficientsIEEE Transactions on Signal Processing, 2004
- Multiplierless approximation of transforms with adder constraintIEEE Signal Processing Letters, 2002
- Cascaded coefficient number systems lead to FIR filters of striking computational efficiencyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Subexpression sharing in filters using canonic signed digit multipliersIEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 1996
- Use of minimum-adder multiplier blocks in FIR digital filtersIEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 1995
- Constant integer multiplication using minimum addersIEE Proceedings - Circuits, Devices and Systems, 1994
- Multiplication by integer constantsSoftware: Practice and Experience, 1986
- Some complexity issues in digital signal processingIEEE Transactions on Acoustics, Speech, and Signal Processing, 1984
- Variations on the Common Subexpression ProblemJournal of the ACM, 1980
- Signed-Digit Numbe Representations for Fast Parallel ArithmeticIEEE Transactions on Electronic Computers, 1961