Contention resolution algorithm for common subexpression elimination in digital filter design

• Main Authors: Xu, Fei, Chang, Chip Hong, Jong, Ching Chuen
• Other Authors: School of Electrical and Electronic Engineering
• Format: Article
• Language: English
• Published: 2009
• Subjects: DRNTU::Engineering::Electrical and electronic engineering
• Online Access: https://hdl.handle.net/10356/91438; http://hdl.handle.net/10220/6025
• Institution: Nanyang Technological University

In this paper, a new algorithm, called contention resolution algorithm for weight-two subexpressions (CRA-2), based on an ingenious graph synthesis approach has been developed for the common subexpression elimination of the multiplication block of digital filter structures. CRA-2 provides a leeway to break away from the local minimum and the flexibility of varying optimization options through a new admissibility graph. It manages two-bit common subexpressions and aims at achieving the minimal logic depth as the primary goal. The performances of our proposed algorithm are analyzed and evaluated based on benchmarked finite-impulse-response filters and randomly generated data. It is demonstrated that CRA-2 achieves the shortest logic depth with significant reduction in the number of logic operators compared with other reported algorithms.