An algorithm for synthesis of reversible logic circuits

Pallav Gupta, Abhinav Agrawal, Niraj Kumar Jha

Research output: Contribution to journalArticle

286 Scopus citations

Abstract

Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25.

Original languageEnglish (US)
Article number1715418
Pages (from-to)2317-2329
Number of pages13
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume25
Issue number11
DOIs
StatePublished - Nov 1 2006

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Keywords

  • Quantum computing
  • Reversible computing
  • Reversible logic synthesis

Fingerprint Dive into the research topics of 'An algorithm for synthesis of reversible logic circuits'. Together they form a unique fingerprint.

  • Cite this