Efficient design of FIR filters using hybrid multiple constant multiplications on FPGA

The multiple constant multiplication (MCM) block, which realizes the multiplication of constants by a variable, is a ubiquitous operation in digital signal processing (DSP) systems. It can be implemented using generic multipliers or shifts and adders/subtractors. This paper addresses the problem of finding the minimum number of adders/subtractors to realize the MCM block while a number of multipliers are available to realize some constant multiplications. Such a situation appears in the design of DSP systems on field programmable gate arrays (FPGAs) which also include generic multipliers. We present a 0-1 integer linear programming (ILP) formulation of this problem, yielding an exact common subexpression elimination (CSE) method. Due to the NP-completeness of this problem, we also introduce an approximate graph-based (GB) algorithm. Experimental results show that the proposed methods can find better solutions than a state-of-art algorithm and the use of different number of multipliers in the MCM block leads to filter designs with different number of slices, delay, and power dissipation which enable a designer to choose the one that fits best in an application.