Complexity Analysis of the Cost-Table Approach to the Design of Multiple-Valued Logic Circuits

Abstract

We analyze the computational complexity of the cost-table approach to designing multiple valued logic circuits that is applicable to I(2)L, CCD's, current-mode CMOS, and RTD's. We show that this approach is NP-complete. An efficient algorithm is shown for finding the exact minimal realization of a given function by a given cost-table.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 08, 1995
Accession Number
ADA605390

Entities

People

  • Jon T. Butler
  • Kriss A. Schueller

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Human Systems
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Circuits
  • Computational Complexity
  • Engineering
  • Heuristic Methods
  • Information Operations
  • Logic
  • Logic Gates
  • Mathematics
  • Military Research
  • Numbers
  • Polynomials
  • Real Numbers
  • Two Dimensional

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Integrated Circuit Design and Technology.