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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on signal processing 2002-08, Vol.50 (8), p.1935-1941
Main Authors: Li, Dongning, Lim, Yong Ching, Lian, Yong, Song, Jianjian
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Algorithms
Applied sciences
Complexity
Costs
Design methodology
Detection, estimation, filtering, equalization, prediction
Digital filters
Exact sciences and technology
Finite impulse response filter
Finite wordlength effects
FIR filters
Gain
Information, signal and communications theory
Large scale integration
Polynomials
Proposals
Signal and communications theory
Signal processing
Signal processing algorithms
Signal, noise
Studies
Sums
Telecommunications and information theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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/sup /spl infin// 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.
ISSN:1053-587X
1941-0476
DOI:10.1109/TSP.2002.800385