Planar Decision Diagrams for Multiple-Valued Functions
Loading...
Authors
Sasao, Tsutomu
Butler, Jon T.
Subjects
Ordered binary decision diagram (OBDD)
ordered multiple-valued decision diagram (OMDD)
computer-aided design
threshold function
symmetric function
dual function
ordered multiple-valued decision diagram (OMDD)
computer-aided design
threshold function
symmetric function
dual function
Advisors
Date of Issue
1996
Date
Publisher
Language
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.
Type
Article
Description
Series/Report No
Department
Electrical and Computer Engineering
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Multi. Val. Logic, 1996, Vol. 1, pp. 39-64
Distribution Statement
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.