Multiplierless implementation of 2-D FIR filters

In this paper, the multiplierless design of two-dimensional (2-D) FIR filters is studied. The adders that are used in place of multiplications are reduced by using the 2-D common subexpression elimination (CSE) method which is developed in this paper. This method decomposes the original filter into smaller filters and the output of each filter is scaled with an appropriate coefficient to form the original filter output. It is also shown in this paper that each step of this procedure is an NP-complete problem. Hence, 0-1 integer programming model for each step is formed. Since the solution of these models are time and memory consuming, heuristic algorithms have also been developed. The heuristic 2-D CSE method proves to be better than traditional implementations of 2-D filters in terms of adder count. Though power and performance analysis of the produced filters have not been made, it is estimated that power consumption of these filters will be low due to low interconnect density. Also, concurrent processing of data with small filters increase the overall filtering performance filter.