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, CCDs, current-mode CMOS, and RTDs. 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
Feb 01, 1997
Accession Number
ADA605388

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
  • Computer Science
  • Computers
  • Coverings
  • Electronic Mail
  • Engineering
  • Heuristic Methods
  • Information Operations
  • Logic
  • Logic Gates
  • Mathematics
  • Numbers
  • Polynomials
  • Real Numbers

Readers

  • Integrated Circuit Design and Technology.
  • Operations Research
  • Rocket Propulsion.