Article

Synthesis of Reversible Logic

Authors:

Abhinav Agrawal,

Niraj K. JhaAuthors Info & Claims

DATE '04: Proceedings of the conference on Design, automation and test in Europe - Volume 2

Page 21384

Published: 16 February 2004 Publication History

Get Access

Abstract

A function is reversible if each input vector produces a unique output vector. Reversible functions find applications in low power design, quantum computing, and nanotechnology. Logic synthesis for reversible circuits differs substantially from traditional logic synthesis. In this paper, we present the .rst practical synthesis algorithm and tool for reversible functions with a large number of inputs. It uses positive-polarity Reed-Muller decomposition at each stage to synthesize the function as a network of Toffoli gates. The heuristic uses a priority queue based search tree and explores candidate factors at each stage in order of attractiveness. The algorithm produces near-optimal results for the examples discussed in the literature. The key contribution of the work is that the heuristic .nds very good solutions for reversible functions with a large number of inputs.

References

[1]

{1} M. Nielsen and I. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 2000.

Digital Library

Google Scholar

[2]

{2} R. C. Merkle, "Two types of mechanical reversible logic," Nanotechnology , vol. 4, pp. 114-131, 1993.

Crossref

Google Scholar

[3]

{3} C. Bennett, "Logical reversibility of computation," IBM J. Res. Dev., vol. 17, pp. 525-532, 1973.

Digital Library

Google Scholar

[4]

{4} V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes, "Reversible logic circuit synthesis," in Proc. Int. Conf. Computer-Aided Design, Nov. 2002, pp. 125-132.

Digital Library

Google Scholar

[5]

{5} D. M. Miller, D. Maslov, and G. W. Dueck, "A transformation based algorithm for reversible logic synthesis," in Proc. Design Automation Conf., June 2003, pp. 318-323.

Digital Library

Google Scholar

[6]

{6} A. Khlopotine, M. Perkowski, and P. Kerntopf, "Reversible logic synthesis by iterative compositions," in Proc. Int. Wkshp. Logic Synthesis, June 2002, pp. 261-266.

Google Scholar

[7]

{7} K. Iwama, Y. Kambayashi, and S. Yamashita, "Transformation rules for designing CNOT-based quantum circuits," in Proc. Design Automation Conf., June 2002, pp. 419-424.

Digital Library

Google Scholar

[8]

{8} A. Mishchenko and M. Perkowski, "Logic synthesis of reversible wave cascades," in Proc. Int. Wkshp. Logic Synthesis, June 2002, pp. 197- 202.

Google Scholar

[9]

{9} D. M. Miller and G. W. Dueck, "Spectral techniques for reversible logic synthesis," in Proc. 6th Int. Symp. Representations & Methodology of Future Computing Technologies, Mar. 2003.

Google Scholar

[10]

{10} N. C. S. U. Collaborative Benchmarking Laboratory, Dept. of Computer Science, North Carolina State University, "Benchmark archives at CBL." {Online}. Available: http://www.cbl.ncsu.edu/benchmarks/

Google Scholar

Cited By

View all

Deb ADas DRahaman HBhattacharya BWille RDrechsler R(2013)Reversible circuit synthesis of symmetric functions using a simple regular structureProceedings of the 5th international conference on Reversible Computation10.1007/978-3-642-38986-3_15(182-195)Online publication date: 4-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-38986-3_15
Donald JJha N(2008)Reversible logic synthesis with Fredkin and Peres gatesACM Journal on Emerging Technologies in Computing Systems10.1145/1330521.13305234:1(1-19)Online publication date: 7-Apr-2008
https://dl.acm.org/doi/10.1145/1330521.1330523
Maslov DDueck GMiller D(2007)Techniques for the synthesis of reversible Toffoli networksACM Transactions on Design Automation of Electronic Systems10.1145/1278349.127835512:4(42-es)Online publication date: 1-Sep-2007
https://dl.acm.org/doi/10.1145/1278349.1278355
Show More Cited By

Index Terms

Synthesis of Reversible Logic
1. Hardware
  1. Electronic design automation
    1. High-level and register-transfer level synthesis
  2. Integrated circuits
    1. Logic circuits

Recommendations

Fredkin/Toffoli Templates for Reversible Logic Synthesis
ICCAD '03: Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design

Reversible logic has applications in quantum computing, lowpower CMOS, nanotechnology, optical computing, and DNAcomputing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of ...
Reversible logic synthesis with Fredkin and Peres gates

Reversible logic has applications in low-power computing and quantum computing. Most reversible logic synthesis methods are tied to particular gate types, and cannot synthesize large functions. This article extends RMRLS, a reversible logic synthesis ...
A transformation based algorithm for reversible logic synthesis
DAC '03: Proceedings of the 40th annual Design Automation Conference

A digital combinational logic circuit is reversible if it maps each input pattern to a unique output pattern. Such circuits are of interest in quantum computing, optical computing, nanotechnology and low-power CMOS design. Synthesis approaches are not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DATE '04: Proceedings of the conference on Design, automation and test in Europe - Volume 2

February 2004

606 pages

ISBN:0769520855

Publisher

IEEE Computer Society

United States

Publication History

Published: 16 February 2004

Check for updates

Qualifiers

Article

Conference

DATE04

Sponsor:

SIGDA

DATE04: Design, Automation and Test in Europe 2004

February 16 - 20, 2004

Acceptance Rates

Overall Acceptance Rate 518 of 1,794 submissions, 29%

Upcoming Conference

DATE '25

Sponsor:
sigda

Design, Automation and Test in Europe

March 31 - April 2, 2025

Lyon , France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
247
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Deb ADas DRahaman HBhattacharya BWille RDrechsler R(2013)Reversible circuit synthesis of symmetric functions using a simple regular structureProceedings of the 5th international conference on Reversible Computation10.1007/978-3-642-38986-3_15(182-195)Online publication date: 4-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-38986-3_15
Donald JJha N(2008)Reversible logic synthesis with Fredkin and Peres gatesACM Journal on Emerging Technologies in Computing Systems10.1145/1330521.13305234:1(1-19)Online publication date: 7-Apr-2008
https://dl.acm.org/doi/10.1145/1330521.1330523
Maslov DDueck GMiller D(2007)Techniques for the synthesis of reversible Toffoli networksACM Transactions on Design Automation of Electronic Systems10.1145/1278349.127835512:4(42-es)Online publication date: 1-Sep-2007
https://dl.acm.org/doi/10.1145/1278349.1278355
Abdollahi APedram MGielen G(2006)Analysis and synthesis of quantum circuits by using quantum decision diagramsProceedings of the conference on Design, automation and test in Europe: Proceedings10.5555/1131481.1131569(317-322)Online publication date: 6-Mar-2006
https://dl.acm.org/doi/10.5555/1131481.1131569
De Vos AVan Rentergem YBagherzadeh NValero MRamirez A(2005)Reversible computingProceedings of the 2nd conference on Computing frontiers10.1145/1062261.1062270(35-44)Online publication date: 4-May-2005
https://dl.acm.org/doi/10.1145/1062261.1062270
Kerntopf PMalik SFix LKahng A(2004)A new heuristic algorithm for reversible logic synthesisProceedings of the 41st annual Design Automation Conference10.1145/996566.996789(834-837)Online publication date: 7-Jun-2004
https://dl.acm.org/doi/10.1145/996566.996789

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Fredkin/Toffoli Templates for Reversible Logic Synthesis

Reversible logic synthesis with Fredkin and Peres gates

A transformation based algorithm for reversible logic synthesis