Common Subexpression Elimination for Digital Filters Using Genetic Algorithm
Payman Samadi, Majid Ahmadi · 2007
In this paper a new method for the elimination of common subexpressions for digital filters with canonical signed digit (CSD) coefficients is presented. In this method, the problem is converted to a simple traveling salesman problem and is solved with genetic algorithm (GA). The proposed approach finds subexpressions with 2 non-zero digits in both vertical and horizontal positions and subexpressions with 3 non-zero digits in only vertical position. Experimental results on a large number of FIR filters with CSD coefficients show a 25% and 32% saving in the number of additions for 2 and 3 non-zero digits respectively.