D. Michael Miller
ABSTRACT
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 well developed for reversible circuits even for small numbers of inputs and outputs.In this paper, a transformation based algorithm for the synthesis of such a reversible circuit in terms of n × n Toffoli gates is presented. Initially, a circuit is constructed by a single pass through the specification with minimal look-ahead and no back-tracking. Reduction rules are then applied by simple template matching. The method produces near-optimal results for 3-input circuits and also produces very good results for larger problems.
- C. Bennett. Logical reversibility of computation. I.B.M. J. Res. Dev., 17:525--532, 1973.Google Scholar
Digital Library
- J. W. Bruce, M. A. Thornton, L. Shivakumaraiah, P. S. Kokate, and X. Li. Effiient adder circuits based on a conservative reversible logic gate. In IEEE Symposium on VLSI, pages 83--88, April 2002. Google ScholarDigital Library
- R. Feynman. Quantum mechanical computers. Optic News, 11:11--20, 1985.Google ScholarCross Ref
- E. Fredkin and T. Toffoli. Conservative logic. International Journal of Theoretical Physics, 21:219--253, 1982.Google ScholarCross Ref
- K. Iwama, Y. Kambayashi, and S. Yamashita. Transformation rules for designing cnot-based quantum circuits. In Proceedings of the Design Automation Conference, New Orleans, Louisiana, USA, June 10-14 2002. Google ScholarDigital Library
- A. Khlopotine, M. Perkowski, and P. Kerntopf. Reversible logic synthesis by iterative compositions. International Workshop on Logic Synthesis, 2002.Google Scholar
- E. Knill, R. Laflamme, and G. J. Milburn. A scheme for efficient quantum computation with linear optics. Nature, pages 46--52, Jan. 2001.Google Scholar
- R. Landauer. Irreversibility and heat generation in the computing process. IBM J. Res., 5:183--191, 1961.Google ScholarDigital Library
- D. Maslov and G. W. Dueck. Garbage in reversible design of multiple output functions. In 6th International Symposium on Representations and Methodology of Future Computing Technologies, pages 162--170, March 2003.Google Scholar
- R. C. Merkle. Two types of mechanical reversible logic. Nanotechnology, 4:114--131, 1993.Google ScholarCross Ref
- D. M. Miller. Spectral and two-place decomposition techniques in reversible logic. In Midwest Symposium on Circuits and Systems, Aug. 2002.Google ScholarCross Ref
- D. M. Miller and G. W. Dueck. Spectral techniques for reversible logic synthesis. In 6th International Symposium on Representations and Methodology of Future Computing Technologies, March 2003.Google Scholar
- A. Mishchenko and M. Perkowski. Logic synthesis of reversible wave cascades. In International Workshop on Logic Synthesis, June 2002.Google Scholar
- M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google ScholarDigital Library
- M. Perkowski and et~al. A hierarchical approach to computer-aided design of quantum circuits. Preprint, 2002.Google Scholar
- M. Perkowski, P. Kerntopf, A. Buller, M. Chrzanowska-Jeske, A. Mishchenko, X. Song, A. Al-Rabadi, L. Joswiak, A. Coppola, and B. Massey. Regularity and symmetry as a base for efficient realization of reversible logic circuits. In International Workshop on Logic Synthesis, 2001.Google Scholar
- G. Schrom. Ultra-Low-Power CMOS Technology. PhD thesis, Technischen Universität Wien, June 1998.Google Scholar
- V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes. Reversible logic circuit synthesis. In ICCAD, pages 125--132, San Jose, California, USA, Nov 10-14 2002. Google ScholarDigital Library
- T. Toffoli. Reversible computing. Tech memo MIT/LCS/TM-151, MIT Lab for Comp. Sci, 1980.Google Scholar
Index Terms
- A transformation based algorithm for reversible logic synthesis
Recommendations
Novel designs of nanometric parity preserving reversible compressor
Reversible logic is a new field of study that has applications in optical information processing, low power CMOS design, DNA computing, bioinformatics, and nanotechnology. Low power consumption is a basic issue in VLSI circuits today. To prevent the ...
Pairwise decomposition of toffoli gates in a quantum circuit
GLSVLSI '08: Proceedings of the 18th ACM Great Lakes symposium on VLSIQuantum circuit synthesis is the procedure of automatically generating quantum circuits to represent specified functions. A common gate in quantum circuits is the reversible Toffoli gate, a type of generalized controlled NOT operation. There are ...
Design of reversible logic based full adder in current-mode logic circuits
AbstractDemand of Very Large Scale Integration (VLSI) circuits with very high speed and low power are increased due to communication system's transmission speed increase. During computation, heat is dissipated by a traditional binary logic or logic ...
Comments