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

An algorithm is presented 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, the author's 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 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 finite impulse response (FIR) filter designs shows that it achieves up to 8.9 dB improvement over simulated annealing and mixed integer linear programing on the normalized peak ripples of example filters.>