Design and Implementation of OBDD Variable Ordering/ Reordering Methods

点击翻译按钮获取中文摘要

This research is on the design and implementation of ordered binary decision diagram (OBDD) variable ordering and reordering methods. The work explores the use of memory-efficient data structures, called Decision Diagrams (DD), to describe the behavior of Boolean functions. Being developed is a methodology for finding an ordering of the Boolean function variables so that the DD has minimal size. This research exploits the use of conditional probabilities for the purposes of variable ordering and dynamic reordering. Efficient techniques for computation of the spectrum of a Boolean function using its OBDD representation as input are being used. Software is being developed to manipulate OBDDs as well as compute the probability values.