Planar Decision Diagrams for Multiple-Valued Functions
Butler, Jon T.
MetadataShow full item record
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.
RightsThis 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.
Showing items related by title, author, creator and subject.
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 ...
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 ...
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 ...