Title :
Multiple tunable constant multiplications: Algorithms and applications
Author :
Aksoy, Levent ; Costa, Eduardo ; Flores, Paulo ; Monteiro, José
Author_Institution :
INESC-ID, Lisbon, Portugal
Abstract :
The multiple constant multiplications (MCM) problem, that is defined as finding the minimum number of addition and subtraction operations required for the multiplication of multiple constants by an input variable, has been the subject of great interest since the complexity of many digital signal processing (DSP) systems is dominated by an MCM operation. This paper introduces a variant of the MCM problem, called multiple tunable constant multiplications (MTCM) problem, where each constant is not fixed as in the MCM problem, but can be selected from a set of possible constants. We present an exact algorithm that formalizes the MTCM problem as a 0-1 integer linear programming (ILP) problem when constants are defined under a number representation. We also introduce a local search method for the MTCM problem that includes an efficient MCM algorithm. Furthermore, we show that these techniques can be used to solve various optimization problems in finite impulse response (FIR) filter design and we apply them to one of these problems. Experimental results clearly show the efficiency of the proposed methods when compared to prominent algorithms designed for the MCM problem.
Keywords :
FIR filters; digital signal processing chips; integer programming; linear programming; optimisation; addition operations; digital signal processing systems; finite impulse response filter; input variable; integer linear programming problem; local search method; multiple tunable constant multiplications; number representation; optimization problems; subtraction operations; Adders; Algorithm design and analysis; Cost function; Finite impulse response filter; Logic gates; Signal processing algorithms;
Conference_Titel :
Computer-Aided Design (ICCAD), 2012 IEEE/ACM International Conference on
Conference_Location :
San Jose, CA