Common Subexpression Elimination for Digital Filters Using Genetic Algorithm

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.