Incremental gate: A method to compute minimal cost CCD realizations of MVL functions

M. H. Abd-El-Barr*, H. Choy

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

n-variable vector-valued functions that map a set of vectors of integers to a set of vectors of integers are realized using logic gates constructed using charge-coupled device (CCD) very-large-scale integration (VLSI) technology. Minimal-cost realizations of these functions are obtained through an exhaustive algorithm that considers all the circuits consisting of one gate, then all the circuits consisting of two gates, and so forth. At each step all the circuits that realize functions at a cost less than the cost of any other realizations of the same functions are recorded. Since the number of functions is exponential in the number of variables and the range of integers considered, the algorithm's time complexity is exponential in the number of variables and the range of integers. A number of pruning criteria that reduce the search space and speed up the algorithm are presented.

Original languageEnglish
Title of host publicationProceedings of The International Symposium on Multiple-Valued Logic
PublisherPubl by IEEE
Pages111-118
Number of pages8
ISBN (Print)0818626801
StatePublished - May 1992

Publication series

NameProceedings of The International Symposium on Multiple-Valued Logic
ISSN (Print)0195-623X

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

Dive into the research topics of 'Incremental gate: A method to compute minimal cost CCD realizations of MVL functions'. Together they form a unique fingerprint.

Cite this