Circuit-based evaluation ot the arithmetic transform of boolean functions
2002 (English)Conference paper (Other academic)
In this paper we present a fast algorithm for evaluating the arithmetic transform of a Boolean function based on its circuit representation. The arithmetic transform has multiple applications in CAD, including the computation of signal probabilities and switching activities of circuit nets and the mapping of Boolean functions onto probabilistic hash values. Previous algorithms forevaluating the arithmetic transform required an orthogonal, non redundant representation of the function to be transformed in formof a disjoint function cover or a single BDD. We present a new algorithmt hat partitions the evaluation based on the dominator relationsof the circuit graph. Similar to the application of cut-pointsin combinational equivalence checking, the dominators are used to progressively simplify intermediate evaluation steps. As a result,the presented algorithm can handle larger circuits than previously possible. An extensive set of experiments on benchmark and industrialcircuits demonstrate the effectiveness of our approach.
Place, publisher, year, edition, pages
IdentifiersURN: urn:nbn:se:kth:diva-6853OAI: oai:DiVA.org:kth-6853DiVA: diva2:11677
11th IEEE/ACM International Workshop on Logic & Synthesis, June 4-7, 2002, New Orleans, Louisiana, USA
QC 201102152007-03-012007-03-012011-02-15Bibliographically approved