Graphical Method of Reversible Circuits Synthesis

• Autorzy: Skorupski A.

Identyfikatory

DOI

10.1515/eletel-2017-0031

• Języki publikacji: EN

Abstrakty

EN

This paper presents a new approach to designing reversible circuits. Reversible circuits can decrease energy dissipation theoretically to zero. This feature is a base to build quantum computers. The main problem of reversible logic is designing optimal reversible circuits i.e. circuits with minimal gates number implementing the given reversible function. There are many types of reversible gates. Most popular library is a set of three types of gates so called CNT (Control, NOT and Toffoli). The method presented in this paper is based only on the Toffoli gates. A graphical representation of the reversible function called s-maps is introduced in the paper. This representation allows to find optimal reversible circuits. The paper is organized as follows. Section 1 recalls basic concepts of reversible logic. In Section 2 a graphical representation of the reversible functions is presented. Section 3 describes the algorithm whereby all optimal solutions of the given function could be obtained.

Słowa kluczowe

EN

reversible logic; reversible circuits; reversible gates; Toffoli gates

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2017
• Tom: Vol. 63, No. 3
• Strony: 235--240
• Opis fizyczny: Bibliogr. 13 poz., rys., tab.

Twórcy

autor

Skorupski A.

• Institute of Computer Science, Warsaw University of Technology, Poland

Bibliografia

• [1] De Vos, “Reversible Computing. Fundamentals, Quantum Computing, and Applications”, Wiley-VCH, Berlin 2010.
• [2] R. Landauer, “Irreversibility and heat generation in the computing process”, IBM Journal of Research and Development,” vol. 5, 1961, pp. 183-191.
• [3] O. Golubitsky and D. Maslov, “A study of optimal 4-bit reversible Toffoli circuits and their synthesis,” IEEE Transactions on Computers, vol. 61, no. 9, 2012,. pp. 1341-1353.
• [4] E. Forsberg, “Reversible Logic Based on Electron Waveguide Y-branch Switches”, Nanotechnology, March 2004, vol. 15, no. 4
• [5] R. Marx, A. F. Fahmy, John M. Myers, W. Bermel, and S. J. Glaser, “Approaching five-bit NMR quantum computing”, Phys. Rev. A 62, June 2000
• [6] C. Monroe, J. Bollinger, “Atomic physics in ion traps”, Physics World, March 1997
• [7] R. Akter, N. Islam, S. Waheed, “Implementation of Reversible Logic Gate in Quantum Dot Cellular Automata”, International Journal of Computer Applications, Volume 109, No. 1, January 2015
• [8] H. Deutsch, G. K. Brennen, P. S. Jessen, “Quantum computing with neutral atoms in an optical lattice”, Special Issue on Physical Implementations of Quantum Computing –Fortschritte der Physik 48, 2000
• [9] T. Toffoli, J. W. d. Bakker, J. v. Leeuwen, “Reversible computing: MIT LCS TM-151”, 1980.
• [10] Y. Zheng, C. Huang, “A novel Toffoli network synthesis algorithm for reversible logic,” IEEE ASP-DAC, Yokohama, January 2009.
• [11] I. M. Tsai S. Y. Kuo, “An algorithm for minimum space quantum boolean circuits construction”, J. Circuit Syst. Comp., vol. 15, pp. 719-738, October 2006.
• [12] M. Saeedi, M. Sedighi, M. S. Zamani, “A novel synthesis algorithm for reversible circuits”, IEEE/ACM ICCAD, California, USA, November 2007.
• [13] Y. Yang, H. Chen, S. Kuo, G. Zeng, Y. Chou, “A Novel Efficient Optimal Reversible Circuit Synthesis Algorithm”, IEEE International Conference on Systems, Man and Cybernetics, Hong Kong, 2015. pp. 68-73.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).