Synthesis of reversible sequential elements

ABSTRACT

To construct a reversible sequential circuit, reversible sequential elements are required. This work presents novel designs of reversible sequential elements such as the D latch, JK latch, and T latch. Based on these reversible latches, we construct the designs of the corresponding flip-flops. Then we further discuss the physical implementations of our designs based on electron waveguide Y-branch switch technology. Test costs, including test generation and test application, of reversible sequential circuits with these reversible flip-flops are also discussed. Compared with previous work, the implementation cost of our new designs, including the number of gates and the number of garbage outputs, is significantly reduced. The number of gates in our designs is 47.4% of the designs in previous work on average. The number of garbage outputs in our designs is 25% of the designs in previous work on average.

REFERENCES

• 1: Bennett, C. 1973. Logical reversibility of computation. IBM J. Res. Dev. 17, 525--532.
• 2: Alexis De Vos , Yvan Van Rentergem, Reversible computing: from mathematical group theory to electronical circuit experiment, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy [doi>10.1145/1062261.1062270]
• 3: Forsberg, E. 2003. Electronic and photonic quantum devices. PhD thesis, Royal Institute of Technology.
• 4: Forsberg, E. 2004. Reversible logic based on electron waveguide Y-branch switches. Nanotechn. 15, 4, 298--302.
• 5: Erik Forsberg, The electron waveguide y-branch switch: a review and arguments for its use as a base for reversible logic, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy [doi>10.1145/1062261.1062328]
• 6: Fredkin, E. and Toffoli, T. 1982. Conservative logic. Int. J. Theoret. Phys. 21, 219--253.
• 7: John P. Hayes , Ilia Polian , Bernd Becker, Testing for Missing-Gate Faults in Reversible Circuits, Proceedings of the 13th Asian Test Symposium, p.100-105, November 15-17, 2004 [doi>10.1109/ATS.2004.84]
• 8: Pawel Kerntopf, A new heuristic algorithm for reversible logic synthesis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996789]
• 9: Knill, E., Laflamme, R., and Milburn, G. J. 2001. A scheme for efficient quantum computation with linear optics.Nature, 46--52.
• 10: Landauer, R. 1961. Irreversibility and heat generation in the computational process. IBM J. Res. Dev. 5, 183--191.
• 11: M. Morris Mano, Computer engineering hardware design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 12: Maslov, D. and Dueck, G. W. 2003. Garbage in reversible design of multiple output functions. In Proceedings of 6th International Symposium on Representations and Methodology of Future Computing Technologies. 162--170.
• 13: Merkle, R. C. 1993. Two types of mechanical reversible logic. Nanotech. 4, 114--131.
• 14: Merkle, R. C. and Drexler, K. 1996. Helical logic. Nanotech. 7, 325--339.
• 15: Miller, D. M. 2002. Spectral and two-place decomposition techniques in reversible logic. In Proceedings of the IEEE Midwest Symposium on Circuits and Systems (MWCAS). II493--II496.
• 16: 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]
• 17: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 18: Palm, T., Thylen, L., Nilsson, O., and Svensson, C. 1993. Quantum interference devices and field-effect transistors: A switch energy comparison. J. Appl. Phys 74, 687--694.
• 19: Ketan N. Patel , John P. Hayes , Igor L. Markov, Fault Testing for Reversible Circuits, Proceedings of the 21st IEEE VLSI Test Symposium, p.410, April 27-May 01, 2003
• 20: Perkowski, M., Jozwiak, L., Mishchenko, A., Al-Rabadi, A., Coppola, A., Buller, A., Song, X., Khan, M., Yanushkevich, S., Shmerko, V. P., and Chrzanowska-Jeske, M. 2001. A general decomposition for reversible logic. In Proceedings of Reed-Muller Workshop. 119--138.
• 21: Picton, P. 1996. Multi-valued sequential logic design using Fredkin gates. Multiple-Val. Logic J. 1, 241--251.
• 22: Rice, J. E. 2006. A new look at reversible memory elements. In Proceedings of the IEEE International Symposium on Circuits and Systems.
• 23: Schrom, G. 1998. Ultra-low-power CMOS technology. PhD thesis, Technischen Universitat Wien.
• 24: Shahin, N. 2005. Testing Reversible Circuits. University of Southern California Press, Los Angeles, CA.
• 25: Thapliyal, H. and Srinivas, M. B. 2005. A beginning in the reversible logic synthesis of sequential circuits. In Proceedings of Military and Aerospace Programmable Logic Devices International Conference.
• 26: Toffoli, T. 1980. Reversible computing. Tech rep. MIT/LCS/TM-151, MIT Lab for Computer Science.
• 27: T. W. Williams , K. P. Parker, Design for Testability A Survey, IEEE Transactions on Computers, v.31 n.1, p.2-15, January 1982 [doi>10.1109/TC.1982.1675879]
• 28: M. J. Y. Williams , J. B. Angell, Enhancing Testability of Large-Scale Integrated Circuits via Test Points and Additional Logic, IEEE Transactions on Computers, v.22 n.1, p.46-60, January 1973 [doi>10.1109/T-C.1973.223600]
• 29: Guowu Yang , Xiaoyu Song , William N. N. Hung , Marek A. Perkowski, Fast synthesis of exact minimal reversible circuits using group theory, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120777]
• 30: Zhirnov, V. V., Cavin, R. K., Hutchby, J. A., and Bourianoff, G. I. 2003. Limits to binary logic switch scaling---A Gedanken model. In Proceedings of the IEEE, 1934--1939.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Sequential circuits

General Terms:
Design

Keywords:
Reversible logic, sequential circuits, sequential elements