Polynomial-time algorithm for designing digital filters with power-of-two coefficients

Abstract

This paper presents an algorithm for designing digital filters with coefficients expressible as sums of signed power-of-two (SPT) terms. For each filter gain, the time complexity of the algorithm is a second-order polynomial in the filter order and is a first-order polynomial in the filter wordlength. Unlike conventional methods where each coefficient is allocated a fixed number of SPT terms, our method allows the number of SPT terms for each coefficient to vary subject to the number of SPT terms for the entire filter. This provides us with the possibility of finding a better filter without increasing the number of adders, which determines the realization cost for a given filter length. Application of the algorithm to FIR filter designs shows that it achieves up to 8.9 dB improvement over simulated annealing and mixed integer linear programming on the normalized peak ripples of example filters.