Average path length as a paradigm for the fast evaluation of functions represented by binary decision diagrams

Abstract

International Symposium on New Paradigm VLSI Computing, Sendai, Japan, Dec. 12-14, 2002, pp.31-36. ; 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. ; This paper focuses on the average path length (APL) of BDD's for switching functions. APL is a metric for the time it takes to evaluate the function by a computer program. We derive the APL for the AND, OR, parity, carry-out, comparison, threshold symmetric, and majority functions. We also consider the average of the APL for various classes of functions, including symmetric, threshold symmetric, and majority functions. We also consider the average of the APL for various classes of functions, including symmetric, threshold symmetric, and unate cascade. For symmetric functions, we show the average APL is close to the maxium path length, n, the number of variables.