Planar Decision Diagrams for Multiple-Valued Functions
Abstract
In VLSI, crossings of interconnect occupy space and cause delay. Therefore, there is significant benefit to planar circuits. We propose the use of planar multiple-valued decision diagrams for produce planar multiple-valued circuits. Specifically, we show conditions on 1) threshold funtions, 2) symmetric functions, and 3) monotone increasing functions that produce planar diagrams. Our results apply to binary functions, as well. For example, we show that two-valued monotone increasing threshold functions of up to five variables have planar ordered binary decision diagrams.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Tools for binary decision diagram analysis
Ang, Kwee Hua (Monterey, California. Naval Postgraduate School, 1995-03);The Binary Decision Diagram (BDD) is a very useful representation in the design and verification of switching functions. This is due to to its compactness, where size is measured by the number of nodes. In the implementation ... -
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 ... -
On the average path length in decision diagrams of multiple-valued functions
Sasao, T.; Butler, Jon T. (2003-05);We consider the path length in decision diagrams for multiple-valued functions. This is an important measure of a decision diagram, since this models the time needed to evaluate the function. We consider the path length ...