Title :
A graph theoretic approach for design and synthesis of multiplierless FIR filters
Author :
Muhammad, Khurram ; Roy, Kaushik
Author_Institution :
Storage Products Group, Texas Instrum. Inc., Dallas, TX, USA
Abstract :
We present a novel approach which can be used to obtain multiplierless implementations of finite impulse response (FIR) digital filters. The main idea is to reorder filter coefficients such that an implementation based on differential coefficients requires only a few adders. We represent this problem using a graph in which vertices represent the coefficients and edges represent the resources required when the differential coefficient corresponding to the edge is used in a computation. We also present a graph model for an implementation based on second-order coefficient differences. The optimal solution to the coefficient reordering problem is the well known problem of finding the Hamiltonian path of smallest weight in this graph. We use two approaches to find the smallest weight Hamiltonian cycle; a greedy approach, and the heuristic algorithm proposed by Lin and Kernighan. The power and potential of this approach is demonstrated by presenting results for large filters (lengths up to >300) which show that, in general, for 18-bit coefficients, the total number of adders required per coefficient is less than 2. Hence, high performance and/or low power filters can be designed and synthesized using the proposed approach
Keywords :
FIR filters; circuit CAD; graph theory; heuristic programming; Hamiltonian path; adders; coefficient reordering problem; differential coefficients; filter coefficients; finite impulse response digital filters; graph model; graph theoretic approach; greedy approach; heuristic algorithm; multiplierless FIR filter design; optimal solution; second-order coefficient differences; smallest weight Hamiltonian cycle; Adders; Digital signal processing; Finite impulse response filter; Frequency response; Heuristic algorithms; Instruments; Power dissipation; Quantization; Signal processing algorithms; Signal synthesis;
Conference_Titel :
System Synthesis, 1999. Proceedings. 12th International Symposium on
Conference_Location :
San Jose, CA
Print_ISBN :
0-7695-0356-X
DOI :
10.1109/ISSS.1999.814266