Search

Digital Finite Impulse Response (FIR) filters are frequently used in Digital Signal Processing (DSP) by virtue of stability and easy implementation. The problem of designing the multiplier block of a digital FIR filter has received a significant amount of attention during the last decade, as the filters require a large number of multiplications, leading to excessive area, delay, and power consumption even if implemented in a full custom integrated circuit. Previous works have focused on the design of filters with minimum area by replacing the multiplication operations with constant coefficients by addition, subtraction, and shifting operations. Since shifts can be implemented with only wires in hardware, the design problem can be defined as the minimization of the number of addition/subtraction operations to implement the coefficient multiplications. This problem is generally known as the MCM problem. In the last decade, many efficient algorithms have been proposed for the MCM problem. These algorithms can be categorized in two classes: Common Subexpression Elimination (CSE) and graph-based algorithms. While the CSE algorithms basically find the common non-zero digit patterns on the representations of the constants, the graph-based algorithms are not restricted to a particular number representation and synthesize the constants iteratively by building a graph. However, in the algorithms proposed for the MCM problem, an addition/subtraction operation is assumed to be a two-input operation that is generally implemented using a Ripple Carry Adder (RCA) block yielding great latency in the implementation of MCM. In high-speed applications, particularly in DSP systems, Carry-Save Adder (CSA) blocks are preferred to RCA blocks taking into account the increase in area. Despite the large number of algorithms designed for the minimization of addition/subtraction operations based on RCAs, there are only a few algorithms proposed for the optimization of the number of CSA blocks. Although these algorithms give good results, they are based on heuristics, i.e., provide no indication on how far from the minimum their solutions are. To the best of our knowledge, there is no exact algorithm proposed for the optimization of the number of CSA blocks in MCM. In this paper, an exact CSE algorithm designed for the minimization of the number of CSA blocks is introduced. In the exact CSE algorithm, initially, all possible implementations of filter coefficients and partial terms using CSAs are found when filter coefficients are defined under a number representation, and a combinational network that represents the implementations of constants is constructed. Then, the minimization of the number of CSA blocks problem is defined as a 0-1 Integer Linear Programming (ILP) problem with a cost function to be minimized and constraints to be satisfied.… [ABSTRACT FROM AUTHOR]