Implementation of low complexity FIR filters using a minimum spanning tree
2004 (English)In: Proceedings of the 12th IEEE Mediterranean Electrotechnical Conference, 2004. MELECON 2004, Volume 1, IEEE , 2004, 261-264 p.Conference paper (Other academic)
In this paper we propose a method for implementation of multiple constant multiplications, as used in, for example, FIR filters. The method is shifted difference coefficient method where the differences are selected using a minimum spanning tree. By finding a minimum spanning tree of an undirected graph, corresponding to the coefficients, an implementation of a multiple constant multiplication block with low arithmetic complexity is obtained. There are algorithms that find a minimum spanning tree in polynomial time, making the proposed method computational efficient. We also propose that the differences are computed on odd coefficients only. This reduces the number of adders in an implementation further, compared to other difference coefficient methods. Several stages of differences, i.e., a set of differences is used to compute a new set of higher order differences, may also be used. We show that the proposed method give optimal, or close to optimal, results with respect to the number of additions required for a number of FIR filter implementations.
Place, publisher, year, edition, pages
IEEE , 2004. 261-264 p.
Implementation FIR filters
Engineering and Technology
IdentifiersURN: urn:nbn:se:liu:diva-23672DOI: 10.1109/MELCON.2004.1346826Local ID: 3167ISBN: 0-7803-8271-4OAI: oai:DiVA.org:liu-23672DiVA: diva2:243987
The 12th IEEE Mediterranean Electrotechnical Conference, 2004, May 12-15, 2004, Dubrovnik, Croatia