loading...
Structural Detection of Symmetries in Boolean Functions
San Jose, California October 13-October 15
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICCD.2003.12409462003 IEEE International Conference on ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Guoqiang Wang, University of California at Berkeley, CA
Andreas Kuehlmann, University of California at Berkeley, CA; Cadence Berkeley Labs, Berkeley, CA
Alberto Sangiovanni-Vincentelli, University of California at Berkeley, CA
Functional symmetries provide significant benefits for multiple tasks in synthesis and verification. Many applications require the manual specification of symmetries using special language features such as symmetric data types. Methods for automatically detecting symmetries are based on functional analysis, e.g. using BDDs, or structural methods. The latter search for circuit graph automorphisms which imply functional symmetry. In this paper we present a method for finding symmetries of Boolean functions based on a two-step approach. First, the circuit structure is modified to maximize its structural regularity and thus the number of inherent automorphisms. The next step implements a fast algorithm for detecting the automorphism generators of the circuit graph. The generators provide a compact representation of all automorphisms which in turn encode a subset of the functional symmetries. Because of its pure structural nature, our approach avoids the complexity issues inherent to methods using BDDs, yet it still works automatically and independently from the input specification format. However, the described method may not detect all functional symmetries, however, our experiments demonstrate that it can find the majority of the symmetries present in practical circuits.
Citation:
Guoqiang Wang, Andreas Kuehlmann, Alberto Sangiovanni-Vincentelli, "Structural Detection of Symmetries in Boolean Functions," iccd, pp.498, 2003 IEEE International Conference on Computer Design (ICCD'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.