Efficient ordered binary decision diagrams minimization based on heuristics of cover pattern processing

TitleEfficient ordered binary decision diagrams minimization based on heuristics of cover pattern processing
Publication TypeConference Paper
Year of Publication1993
AuthorsWu, Y-L, Marek-Sadowska, M
Conference NameDesign Automation, 1993, with the European Event in ASIC Design. Proceedings. [4th] European Conference on
Date Publishedfeb
KeywordsBoolean functions, cover pattern processing, directed graphs, efficient ordering heuristic, logic design, metric of dynamic binateness, minimisation of switching nets, ordered binary decision diagrams minimization, recognizing strings of patterns, two-level form specified functions
AbstractA metric of dynamic binateness for Boolean functions is introduced. Based on it and on an analogy between an ordered binary decision diagram (OBDD) of a function and the process of recognizing strings of patterns representing the function's cover, a near linear, efficient ordering heuristic for two-level form specified functions is developed. The algorithm stably achieves on average an improvement of over 600% in OBDD size in comparison to results from similar computation complexity heuristics. The results are comparable to those obtained using lexicographic order but are achieved in less CPU time
DOI10.1109/EDAC.1993.386464