A polynomial-time algorithm for the design of multiplierless linear-phase FIR filters with low hardware cost

Deterministic tree search algorithm for the design of multiplierless linear phase finite impulse response filters are usually time consuming. More researches therefore focus on how to restrict the number of discrete values assigned to each coefficient during a tree search. This paper proposes a polynomial-time tree search algorithm where each coefficient is fixed to only one discrete value. Due to the short search time, multiple searches with floating passband gain become possible, and each search may produce a feasible discrete solution. In such a way, if the whole floating passband gain range is partitioned into many smaller ones, a large amount of feasible discrete solutions may be obtained. In the end, all these feasible solutions are synthesized using an multiple constant multiplication algorithm, and the one using the least number of adders is the final design results. To accelerate the search, a low hardware cost scheme which fixes some coefficient values to 0 prior to each search is proposed. With these techniques, design examples show that the proposed algorithm significantly outperforms the existing algorithms in terms of design time while the hardware cost is kept low.