A New Subexpression Elimination Algorithm Using Zero-Dominant Set

A new common sub expression elimination (CSE) algorithm is proposed for realizing finite impulse response (FIR) filters or other dot product operations. In the proposed algorithm, filter coefficients are represented using redundant number representations from the zero-dominant set (ZDS). The ZDS is generated to add importance on the zero symbol positions in a representation while minimizing the Hamming weight. The ZDS contains all minimum Hamming weight redundant representations plus some other representations taken from the large set of all of the redundant representations for a given word length. A heuristic horizontal sub expression elimination algorithm is proposed to resolve the overlapped patterns in the representations of the coefficients. The algorithm achieved a better sub expression elimination compared to Hartley's CSD method and to other proposed algorithms that do not resolve overlapping patterns.