A graph theoretic approach for synthesizing very low-complexity high-speed digital filters

We present computation reduction techniques which can either be used to obtain multiplierless implementation of finite impulse response (FIR) digital filters or to further improve multiplierless implementation obtained by currently used techniques. Although presented in the FIR filtering framework, these ideas are also directly applicable to any task/application which can be expressed as multiplication of vectors by scalars. The presented approach is to remove computational redundancy by reordering computation. The reordering problem is formulated using a graph in which vertices represent coefficients and edges represent resources required in a computation using the differential coefficient defined by the difference of the vertices joined by the edge. This interpretation leads to various methods for computation reduction for which simple polynomial run time algorithms are presented. It is shown that about 20% reduction in the number of add operations per coefficient can be obtained over the conventional multiplierless implementations. It is also shown that implementations requiring less than one adder per coefficient can be obtained using the presented approaches when using nonuniformly scaled coefficients quantized from infinite precision representation by simple rounding.