Planar Decision Diagrams for Multiple-Valued Functions
NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING
Pagination or Media Count:
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 to produce planar multiple-valued circuits. Specifically, we show conditions on 1 threshold functions, 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 all two-valued monotone increasing threshold functions of up to five variables have planar ordered binary decision diagrams.
- Electrical and Electronic Equipment
- Numerical Mathematics
- Computer Programming and Software