A novel low-complexity method for parallel multiplierless implementation of digital FIR filters

We present a computation reduction method which can be used to obtain a low-complexity parallel multiplierless implementation of digital FIR filters, exploring the use of shift inclusive differential (SED) coefficients and common subexpression elimination (CSE). We introduce a new directed multigraph to represent the design space greatly expanded by the use of SED coefficients. A graph-theoretic algorithm is then employed to explore the greatly expanded design space efficiently. Further, we propose a novel CSE method applied to the design space represented by the graph, which recursively eliminates 2-bit subexpressions with a steepest descent approach for subexpression selection. Compared with a conventional multiplierless implementation, up to 75% reduction in terms of number of additions has been achieved. In comparison to a recently reported CSE method based on available data, our approach achieves an improvement of up to 19%.