Show simple item record

dc.contributor.authorSasao, Tsutomu
dc.contributor.authorMatsuura, Munehiro
dc.contributor.authorButler, Jon T.
dc.dateSeptember 2005
dc.date.accessioned2013-09-03T22:32:59Z
dc.date.available2013-09-03T22:32:59Z
dc.date.issued2005-09
dc.identifier.citationJ. T. Butler, T. Sasao, and M. Matsuura, “Average path length of binary decision diagrams" IEEE Transactions on Computers, Vol. 54, No.9, pp.1041-1053, Sept. 2005.
dc.identifier.urihttp://hdl.handle.net/10945/35827
dc.descriptionIEEE Transactions on Computers, Vol. 54, No.9, pp.1041-1053, Sept. 2005.en_US
dc.descriptionThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.en_US
dc.description.abstractThe traditional problem in binary decision diagrams (BDDs) has been to minimize the number of nodes since this reduces the memory needed to store the BDD. Recently, a new problem has emerged: minimizing the average path length (APL). APL is a measure of the time needed to evaluate the function by applying a sequence of variable values. It is of special significance when BDDs are used in simulation and design verification. A main result of this paper is that the APL for benchmark functions is typically much smaller than for random functions. That is, for the set of all functions, we show that the average APL is close to the maximum path length, whereas benchmark functions show a remarkably small APL. Surprisingly, however, typical functions do not achieve the absolute maximum APL. We show that the parity functions are unique in having that distinction. We show that the APL of a BDD can vary considerably with variable ordering. We derive the APL for various functions, including the AND, OR, threshold, Achilles’ heel, and certain arithmetic functions. We show that the unate cascade functions uniquely achieve the absolute minimum APL.en_US
dc.titleAverage path length of binary decision diagramsen_US
dc.typeArticleen_US
dc.contributor.departmentDepartment of Electric and Computer Engineering
dc.subject.authorBinary decision diagramsen_US
dc.subject.authorBDDen_US
dc.subject.authoraverage path lengthen_US
dc.subject.authorAPLen_US
dc.subject.authorworst-case path lengthen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record