Two-Step Optimization Approach for the Design of Multiplierless Linear-Phase FIR Filters

Deterministic tree search algorithms for the design of multiplierless linear phase finite impulse response filters are generally time consuming. Many researches therefore focus on how to restrict the number of discrete values assigned to each coefficient during a tree search. In this paper, a two-step tree search algorithm is proposed. In the first step, a polynomial-time tree search algorithm where each coefficient is fixed to a single one discrete value is introduced. Since the synthesis of large coefficients is dominant in the hardware cost over small coefficients, in the second step optimization, the small coefficients obtained in the first step is kept unaltered and the large coefficients are further divided into several groups and the coefficients are optimized group by group alternatingly. Such a two-step search strategy maximally utilizes the limited computational resources and can achieve lower hardware cost design in a shorter design time, compared with existing algorithms.