| Title | Efficient ordered binary decision diagrams minimization based on heuristics of cover pattern processing |
| Publication Type | Conference Paper |
| Year of Publication | 1993 |
| Authors | Wu, Y-L, Marek-Sadowska, M |
| Conference Name | Design Automation, 1993, with the European Event in ASIC Design. Proceedings. [4th] European Conference on |
| Date Published | feb |
| Keywords | Boolean 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 |
| Abstract | A 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 |
| DOI | 10.1109/EDAC.1993.386464 |
