Title :
K-disjointness paradigm with application to symmetry detection for incompletely specified functions
Author :
Wang, Kuo-Hua ; Chen, Jia-Hung
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Fu Jen Catholic Univ., Hsinchuang, China
Abstract :
In this paper, we propose a K-disjointness paradigm that can effectively search all pairs of minterms with Hamming distance K between two Boolean functions. By this paradigm, we correlate it with symmetry detection problem and propose an efficient symmetry detection algorithm for Boolean functions. Our algorithm can not only handle completely specified functions but also incompletely specified functions. Experimental results on a set of MCNC and ISCAS benchmarking circuits show that our algorithm is indeed very effective and efficient for detecting symmetries of large Boolean functions.
Keywords :
Boolean functions; algorithm theory; Boolean functions; Hamming distance; ISCAS benchmarking circuits; K-disjointness paradigm; MCNC benchmarking circuits; incompletely specified functions; symmetry detection algorithm; symmetry detection problem; Application software; Boolean functions; Circuits; Computer science; Data structures; Detection algorithms; Hamming distance; Logic; Pain;
Conference_Titel :
Design Automation Conference, 2005. Proceedings of the ASP-DAC 2005. Asia and South Pacific
Print_ISBN :
0-7803-8736-8
DOI :
10.1109/ASPDAC.2005.1466507
