Title :
On the relation between disjunctive decomposition and ROBDD variable ordering
Author :
Dubrova, E.V. ; Miller, D.M. ; Muzio, J.C.
Author_Institution :
Dept. of Comput. Sci., Victoria Univ., BC, Canada
Abstract :
The relation between disjunctive decomposition of functions and a variable ordering minimizing the size of a ROBDD (Reduced Ordered Binary Decision Diagram) is considered. We show that a best ordering for a function with a disjunctive decomposition cannot always be directly determined from the best orderings for the component functions. We also demonstrate that keeping the variables from a bound set of the function adjacent does not always guarantee obtaining the ROBDD for the function with a minimal number of nodes
Keywords :
Boolean functions; circuit diagrams; directed graphs; logic design; Boolean functions; ROBDD; Reduced Ordered Binary Decision Diagram; component functions; directed graphs; disjunctive decomposition; functions; logic design; variable ordering; Boolean functions; Computer science; Councils; Data structures; Microelectronics; Testing; Upper bound; Very large scale integration;
Conference_Titel :
Communications, Computers and Signal Processing, 1997. 10 Years PACRIM 1987-1997 - Networking the Pacific Rim. 1997 IEEE Pacific Rim Conference on
Conference_Location :
Victoria, BC
Print_ISBN :
0-7803-3905-3
DOI :
10.1109/PACRIM.1997.620353
