TY - JOUR

T1 - An algorithm for synthesis of reversible logic circuits

AU - Gupta, Pallav

AU - Agrawal, Abhinav

AU - Jha, Niraj K.

N1 - Funding Information:
Manuscript received May 3, 2004; revised December 16, 2004, May 31, 2005, and November 7, 2005. This work was supported by the National Science Foundation under Grant CCF-0429745. This paper was recommended by Associate Editor S. Nowick. P. Gupta and N. K. Jha are with the Department of Electrical Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: pgupta@ princeton.edu; [email protected]). A. Agrawal is with McKinsey and Company, New York, NY 10022 USA. Digital Object Identifier 10.1109/TCAD.2006.871622

PY - 2006/11

Y1 - 2006/11

N2 - 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.

AB - 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.

KW - Quantum computing

KW - Reversible computing

KW - Reversible logic synthesis

UR - http://www.scopus.com/inward/record.url?scp=33750588847&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33750588847&partnerID=8YFLogxK

U2 - 10.1109/TCAD.2006.871622

DO - 10.1109/TCAD.2006.871622

M3 - Article

AN - SCOPUS:33750588847

SN - 0278-0070

VL - 25

SP - 2317

EP - 2329

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 11

M1 - 1715418

ER -