Fast synthesis of reversible circuits using a sorting algorithm and optimization

Ömercan Susam, Mustafa Altun

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

This paper studies synthesis and optimization of reversible circuits composed of Toffoli gates with negative and positive control lines. The proposed synthesis algorithm performs sorting among optimal implementations of certain functions - called as essential functions - to implement any reversible Boolean function. Essential functions comprise very small amount of all functions. For example, to implement 3 bit circuits, 28 essential functions out of all 40320 functions are needed. The proposed optimization algorithm considers both reversible and quantum circuit costs. First, reversible cost is reduced by considering adjacent gate pairs. Then, inner quantum structures of the gates are investigated and quantum optimization is performed. The proposed algorithms are evaluated on benchmark circuits in comparison with the results in the literature.

Original languageEnglish
Pages (from-to)1-23
Number of pages23
JournalJournal of Multiple-Valued Logic and Soft Computing
Volume29
Issue number1-2
Publication statusPublished - 2017

Bibliographical note

Publisher Copyright:
© 2017 Old City Publishing, Inc.

Keywords

  • Algorithms
  • Design
  • Optimization
  • Reversible

Fingerprint

Dive into the research topics of 'Fast synthesis of reversible circuits using a sorting algorithm and optimization'. Together they form a unique fingerprint.

Cite this