We present a graph theoretical methodology that reduces the implementation complexity of a vector multiplied by a scalar The proposed approach is called MRP (minimally redundant parallel) optimization and is presented in FIR filtering framework to obtain a low-complexity multiplierless implementation. The key idea is to expand the design space using shift inclusive differential coefficients together with computation reordering using a graph theoretic approach to obtain maximal computation sharing. The transformed architecture of a filter is obtained by solving a set cover problem of the graph. A simple algorithm based on a greedy approach is presented. The proposed approach is merged with common sub-expression elimination. The simulation results show that 70% and 16% improvement in terms of computational complexity over simple implementation (transposed direct form) and common sub-expression, respectively, when using carry, lookahead adder synthesized from Synopsys designware library in 0.25 /spl mu/m technology.
['Hunsoo Choo', 'Khurram Muhammad', 'Kaushik Roy']
MRPF: An Architectural Transformation for Synthesis of High-Performance and Low-Power Digital Filters