A transformation based algorithm for reversible logic synthesis

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.

REFERENCES

• 1: C. Bennett. Logical reversibility of computation. I.B.M. J. Res. Dev., 17:525--532, 1973.
• 2: Efficient Adder Circuits Based on a Conservative Reversible Logic Gate, Proceedings of the IEEE Computer Society Annual Symposium on VLSI, p.83, April 25-26, 2002
• 3: R. Feynman. Quantum mechanical computers. Optic News, 11:11--20, 1985.
• 4: E. Fredkin and T. Toffoli. Conservative logic. International Journal of Theoretical Physics, 21:219--253, 1982.
• 5: Kazuo Iwama , Yahiko Kambayashi , Shigeru Yamashita, Transformation rules for designing CNOT-based quantum circuits, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514026]
• 6: A. Khlopotine, M. Perkowski, and P. Kerntopf. Reversible logic synthesis by iterative compositions. International Workshop on Logic Synthesis, 2002.
• 7: E. Knill, R. Laflamme, and G. J. Milburn. A scheme for efficient quantum computation with linear optics. Nature, pages 46--52, Jan. 2001.
• 8: R. Landauer. Irreversibility and heat generation in the computing process. IBM J. Res., 5:183--191, 1961.
• 9: 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.
• 10: R. C. Merkle. Two types of mechanical reversible logic. Nanotechnology, 4:114--131, 1993.
• 11: D. M. Miller. Spectral and two-place decomposition techniques in reversible logic. In Midwest Symposium on Circuits and Systems, Aug. 2002.
• 12: 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.
• 13: A. Mishchenko and M. Perkowski. Logic synthesis of reversible wave cascades. In International Workshop on Logic Synthesis, June 2002.
• 14: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 15: M. Perkowski and et~al. A hierarchical approach to computer-aided design of quantum circuits. Preprint, 2002.
• 16: 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.
• 17: G. Schrom. Ultra-Low-Power CMOS Technology. PhD thesis, Technischen Universität Wien, June 1998.
• 18: Vivek V. Shende , Aditya K. Prasad , Igor L. Markov , John P. Hayes, Reversible logic circuit synthesis, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.353-360, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774625]
• 19: T. Toffoli. Reversible computing. Tech memo MIT/LCS/TM-151, MIT Lab for Comp. Sci, 1980.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Design, Theory

Keywords:
minimization, quantum circuits, reversible logic, templates