Detection of symmetry of Boolean functions represented by ROBDDs
- 30 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Addresses the problem of the detection of symmetries of Boolean functions. To know these symmetries may be important in several stages of logic design, e.g. in logic optimization, in logic synthesis, and in technology mapping. Reduced ordered binary decision diagrams (ROBDDs) play an important role in these tools. Using this representation form for Boolean functions there is a simple symmetry test by checking if certain cofactor functions are equivalent, i.e. if their ROBDD representations are the same. Unfortunately, this procedure may be very time and storage consuming because of the necessary cofactor computations. The approach presented in this paper uses preprocessing methods to find as many asymmetric pairs of variables as possible to avoid cofactor computations at the end. For that, special properties of the ROBDD structure as well as properties of Boolean functions are used. Experimental results on a large number of benchmarks show that this is a very efficient approach.Keywords
This publication has 8 references indexed in Scilit:
- Boolean matching using binary decision diagrams with applications to logic synthesis and verificationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Permutation and phase independent Boolean comparisonPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Verifying equivalence of functions with unknown input correspondencePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Efficient implementation of a BDD packagePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Technology mapping using Boolean matching and don't care setsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Multilevel logic synthesis of symmetric switching functionsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1991
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- Detection of symmetries in combinatorial functions by spectral meansIEE Journal on Electronic Circuits and Systems, 1977