Optimization of Linear Phase FIR Filters in Dynamically Expanding Subexpression Space

The most advanced techniques in the design of multiplierless finite impulse response (FIR) filters explore common subexpression sharing when the filter coefficients are optimized. Existing techniques, however, either suffer from a heavy computational overhead, or have no guarantees on the minimal hardware cost in terms of the number of adders. A recent technique capable of designing long filters optimizes filter coefficients in pre-specified subexpression spaces. The pre-specified subexpression spaces determine if a filter with fewer adders may be achieved. Unfortunately, there is no known technique that can find subexpression spaces that can guarantee the solution with the minimum number of adders in the implementation. In this paper, a tree search algorithm is proposed to update and expand the subexpression spaces dynamically, and thus, to achieve the maximum subexpression sharing during the optimization. Numerical examples show that the proposed algorithm generates filters using fewer adders than other non-optimum algorithms. On the other hand, as a consequence of its efficiency, our proposed technique is able to design longer filters than the global optimum algorithm.