Efficient algorithms for common subexpression elimination in digital filter design

A contention resolution algorithm (CRA) is proposed for the common subexpression elimination of the multiplier block of the digital filter structure. CRA synthesizes common subexpressions of any Hamming weight to achieve an overall minimization with the emphasis that every logic depth increment must be accompanied by a reduction in logic complexity. A new data structure, called the admissibility graph is introduced to represent succinctly a set of coefficients; the admissible subexpressions are progressively labeled on the graph as either precedence or contention edges (or paths). The performance of CRA is evaluated based on benchmarked circuits and randomly generated coefficients. It is demonstrated that our algorithm outperforms several distinguished algorithms in both the logic depth and logic complexity.