Complexity Reduction of Digital Filters Using Shift Inclusive Differential Coefficients

We present a graph theoretical methodology that reduces the implementation complexity of the multiplication of a constant vector and a scalar. The complexity of implementation is defined as the required amount of computations like additions. The proposed approach is called minimally redundant parallel (MRP) optimization and is mainly presented in a finite impluse response (FIR) filtering framework to obtain a low-complexity multiplierless implementation. The key idea is to expand the design space using shift inclusive differential coefficients (SIDCs) together with computation reordering using a graph theoretic approach to obtain maximal computation sharing. The problem is formulated using a graph in which vertices and edges represent coefficients and computational cost (number of resources). The multiplierless solution is obtained by solving a set cover problem on the vertices in the graph. A simple polynomial run time algorithm based on a greedy approach is presented. The proposed approach is compared with common-subexpression elimination to show slightly better results and is combined with it for further reduction of complexity. Simulation results show that 50–60% complexity reduction is achieved by only applying the MRP algorithm, and 70% complexity reduction is obtainable by combining it with common-subexpression elimination under a delay constraint of two or three.