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

This paper presents a polynomial-time algorithm for designing digital filters with coefficients expressible as sums of signed power-of-two (SPT) terms. Our proposal is based on an observation that under certain circumstances, the realization cost of a filter with SPT coefficients depends only on the total number of SPT terms, regardless of how the terms distribute among the coefficients. Therefore, the number of SPT terms for each coefficient is not necessarily limited to a fixed number. Instead, they should be allowed to vary subject to a given number of total SPT terms for the filter. This provides the possibility of finding a better set of coefficients. Our algorithm starts with initializing all the quantized coefficient values to zero. It chooses one SPT term at a time and allocates it to the currently most deserving coefficient to minimize the L^∞ distance between the SPT coefficients and their corresponding infinite wordlength values. This process of allocating the SPT terms is repeated until the total number of SPT terms for the filter is equal to a prescribed number. For each filter gain, the time complexity is a second-order polynomial in the number of coefficients to be optimized and is a first-order polynomial in the filter wordlength