Accession Number:

ADA608075

Title:

Planar Decision Diagrams for Multiple-Valued Functions

Descriptive Note:

Journal article

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF ELECTRICAL AND COMPUTER ENGINEERING

Personal Author(s):

Report Date:

1996-01-01

Pagination or Media Count:

0.0

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 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.

Subject Categories:

  • Electrical and Electronic Equipment
  • Numerical Mathematics
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE