Planar Decision Diagrams for Multiple-Valued Functions

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1996
Accession Number
ADA608075

Entities

People

  • Jon T. Butler
  • Tsutomu Sasao

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Circuits
  • Computer Science
  • Computer-Aided Design
  • Computers
  • Crossings
  • Education
  • Electronics
  • Elimination
  • Engineering
  • Information Operations
  • Integrated Circuits
  • Monotone Functions
  • Networks
  • Switching
  • Terminals

Readers

  • Graph Algorithms and Convex Optimization.
  • Integrated Circuit Design and Technology.
  • Statistical inference.

Technology Areas

  • Space