Average path length of binary decision diagrams

Download
Author
Sasao, Tsutomu
Matsuura, Munehiro
Butler, Jon T.
Date
2005-09Metadata
Show full item recordAbstract
The 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.
Description
IEEE Transactions on Computers, Vol. 54, No.9, pp.1041-1053, Sept. 2005.
This 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.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Characteristics of the binary decision diagrams of Boolean Bent Functions
Schafer, Neil Brendan. (Monterey, California: Naval Postgraduate School, 2009-09);Boolean bent functions have desirable cryptographic properties in that they have maximum nonlinearity, which hardens a cryptographic function against linear cryptanalysis attacks. Furthermore, bent functions are extremely ... -
Minimization of SOPs for bi-decomposable functions and non-orthodox/orthodox functions
Ulker, Birol (Monterey, Calif. Naval Postgraduate School, 2002-03);A logical function f is AND bi-decomposable if it can be written as f x1, x2)= h1 (x1) h2(x2), where x1 and x2 are disjoint. Such functions are important because they can be efficiently implemented. Also many benchmark ... -
An analysis of bent function properties using the transeunt triangle and the SRC-6 reconfigurable computer
Shafer, Jennifer L. (Monterey, California: Naval Postgraduate School, 2009-09);Linear attacks against cryptosystems can be defeated when combiner functions are composed of highly nonlinear Boolean functions. The highest nonlinearity Boolean functions, or bent functions, are not common- especially ...