I2CRA: contention resolution algorithm for intra- and inter-coefficient common subexpression elimination

Effective common subexpression extraction has become an eminent means to eliminate redundant computations in multiple constant multiplication problems. Prevailing common subexpression elimination (CSE) algorithms use horizontal common subexpressions predominantly due to the symmetry of linear phase FIR filters. This paper presents a new contention resolution algorithm (CRA), called the I²CRA that exploits both the intra- and inter-coefficient redundancy to reduce the logic depth and logic complexity further. Unlike the statistical based CSE, I²CRA allows a selected common subexpressions to be freed in case of conflicts. By endowing the basic CRA with the prowess to handle common subexpressions in both dimensions in a comprehensive manner, the essentiality of vertical and oblique common subexpressions has been manifested.