Planar Multiple-Valued Decision Diagrams
Abstract
In VLSI, crossings occupy space and cause delay. Therefore, there is significant benefit to planar circuits. We propose the use of planar multiple-valued decision diagrams to produce planar multiple-valued circuits. Specifically, we show conditions on: (1) threshold functions; (2) symmetric functions; and (3) monodiagrams. Our results apply to binary functions, as well. For example, we show that all two-valued monotone increasing threshold functions of up to five variables have planar binary decision diagrams.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 02, 1995
- Accession Number
- ADA605395
Entities
People
- Jon T. Butler
- Tsutomu Sasao
Organizations
- Naval Postgraduate School