Implementation of low complexity FIR filters using a minimum spanning tree

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.