Fredkin/Toffoli Templates for Reversible Logic Synthesis

ABSTRACT

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 Toffoli and Fredkin gates with no back-tracking and minimal look-ahead. Next we apply transformations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for atemplate is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformationthat reduces the gate count can be applied. In this paper weshow that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not needto be specified-they can match a Toffoli or a Fredkin gate.We formalize this by introducing the box gate. All templateswith less than six gates are enumerated and classified. Wesynthesize all three input, three output reversible functionsand compare our results to those obtained previously.

REFERENCES

• 1: [1] G. W. Dueck and D. Maslov. Reversible function synthesis with minimum garbage outputs. In 6th International Symposium on Representations and Methodology of Future Computing Technologies, pages 154-161, March 2003.
• 2: [2] G. W. Dueck, D. Maslov, and D. M. Miller. Transformation-based synthesis of networks of toffoli/fredkin gates. In IEEE Canadian Conference on Electrical and Computer Engineering, Montreal, Canada, May 2003.
• 3: [3] E. Fredkin and T. Toffoli. Conservative logic. International Journal of Theoretical Physics, 21:219-253, 1982.
• 4: 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]
• 5: [5] 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.
• 6: D. Michael Miller , Dmitri Maslov , Gerhard W. Dueck, A transformation based algorithm for reversible logic synthesis, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775915]
• 7: [7] A. Mishchenko and M. Perkowski. Logic synthesis of reversible wave cascades. In International Workshop on Logic Synthesis, June 2002.
• 8: 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]
• 9: [9] T. Toffoli. Reversible computing. Tech memo MIT/LCS/TM-151, MIT Lab for Comp. Sci, 1980.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Logic arrays

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Gate arrays

General Terms:
Algorithms, Design, Theory