© 2001 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
Single-faced Boolean Functions and their Minimization
1 Department of Computer Science, Erik Jonsson School of Engineering and Computer Science, Box 830688, MS EC 31, University of Texas at Dallas, Richardson, TX 75083-0688, USA Email: yuke@utdallas.edu 2 Department of Computer Science, University of Saskatchewan, Saskatoon, Saskatchewan, Canada, S7N 0W0 3 Department of Electrical and Computer Engineering, Portland State University, P.O. Box 751, Portland, OR 97207-0751, USA
This paper identifies a new class of Boolean functions called single-faced functions. Single-faced functions are extensions of the related double-faced core functions which have fewer supporting variables. It is proven that single-faced functions can be simplified to their core functions with respect to Sum of Product minimization, general factored forms minimization and Ordered Binary Decision Diagram (OBDD) minimization. Even if a function $f$ is not single-faced, it must contain single-faced function restrictions if $f$ is not the odd–even parity function. Experimental results show that single-faced functions are common in benchmark circuits. The structure of OBDDs of single-faced functions is studied in detail giving insights which can lead to efficient OBDD minimization algorithms. Moreover it is proven that for symmetric functions and the newly identified complete single-faced functions, any variable ordering will lead to identical OBDDs, which implies that traditional OBDD minimization algorithms will search exhaustively for those functions. Therefore for OBDD minimization, symmetry detection is mandatory in order to avoid unnecessary permutation of variables.
Received 10 November, 2000. Revised 10 March, 2001.