The Transforming Method Between Two Reversible Functions

• Autorzy: Skorupski Andrzej , Gracki Krzysztof

Identyfikatory

DOI

10.24425/123562

• Języki publikacji: EN

Abstrakty

EN

This paper presents an original method of designing some special reversible circuits. This method is intended for the most popular gate set with three types of gates CNT (Control, NOT and Toffoli). The presented algorithm is based on two types of cascades with these reversible gates. The problem of transformation between two reversible functions is solved. This method allows to find optimal reversible circuits. The paper is organized as follows. Section 1 and 2 recalls basic concepts of reversible logic. Especially the two types of cascades of reversible function are presented. In Section 3 there is introduced a problem of analysis of the cascades. Section 4 describes the method of synthesis of the optimal cascade for transformation of the given reversible function into another one.

Słowa kluczowe

EN

reversible logic; reversible circuits; reversible gate; CNT set of the gates

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: International Journal of Electronics and Telecommunications
• Rocznik: 2019
• Tom: Vol. 65, No. 1
• Strony: 33--38
• Opis fizyczny: Bibliogr. 22 poz., tab., wykr.

Twórcy

autor

Skorupski Andrzej

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

autor

Gracki Krzysztof

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

Bibliografia

• [1] R. Landauer, Irreversibility and heat generation in the computing process. IBM Journal of Research and Development , 5(3):183–191, July 1961.
• [2] M. Nielsen, I. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, 2000.
• [3] B. Desoete, A. De Vos, M. Sibinski, T. Widerski, Feynman’s reversible gates implemented in silicon, 6th International Conference MIXDES, pages 496–502, 1999.
• [4] M. Veldhorst, C. H. Yang, J. C. C. Hwang, W. Huang, J. P. Dehollain, J. T. Muhonen, S. Simmons, A. Laucht, F. E. Hudson, K. M. Itoh, A. Morello, A. S. Dzurak, A two-qubit logic gate in silicon, Nature, 526, 410–414, October 2015
• [5] P. Picton, Opoelectronic, multivalued, conservative logic, International Journal of Optical Computing, 2:19–29, 1991.
• [6] R. C. Merkle, K. E. Drexler, Helical logic, Nanotechnology, 7:325–339, 1996.
• [7] E. Fredkin T. Toffoli. Conservative logic. International Journal of Theoretical Physics, 21:219–253, 1982.
• [8] R. Feynman. Quantum mechanical computers. Optic News, 11:11–20, 1985.
• [9] T. Toffoli. Reversible computing. Tech memo MIT/LCS/TM-151, MIT Lab for Comp. Sci, 1980.
• [10] P. Kerntopf, Maximally efficient binary and multi-valued reversible gates, International Workshop on Post-Binary ULSI Systems, pp. 55–58, Warsaw, Poland, May 2001.
• [11] K. Iwama, Y. Kambayashi, S. Yamashita, Transformation rules for designing CNOT-based quantum circuits, Design Automation Conference, New Orleans, Louisiana, USA, June 10-14 2002.
• [12] D. M. Miller, D. Maslov, W. Dueck, A transformation based algorithm for reversible logic synthesis, Proceedings of the Design Automation Conference, pages 318–323, June 2003.
• [13] K. Fazel, M. A. Thornton, J. E. Rice, ESOP-based Toffoli Gate Cascade Generation, Proc. IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, pp. 206 –209, 2007.
• [14] M. H. A. Khan, M. A. Perkowski, Multi-output ESOP Synthesis with Cascades of New Reversible Gate Family, Proc Int. Symp. On Representations and Methodology of Future Comp. Technology, pp.43-55,2003.
• [15] R. Wille, R. Drechsler, BDD-based synthesis of reversible logic for large functions, Design Automation Conf. , pp. 270–275, 2009.
• [16] M. Hawash, M. Perkowski, N. Alhagi, Synthesis of Reversible Circuits with No Ancilla Bits for Large Reversible Functions, Proc. ISMVL, 2010, p. 1-7.
• [17] D. Wang, S. Sun, H. Chen, Matrix-based algorithm for 4-qubit reversible logic circuits synthesis, Energy Procedia, vol. 13, pp. 365-371, 2011.
• [18] O. Golubitsky, 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.
• [19] A. Khlopotine, M. Perkowski, P. Kerntopf, Reversible logic synthesis by iterative compositions, International Workshop on Logic Synthesis, 2002.
• [20] M. Soeken, N. Abdessaied, G. De Micheli, Enumeration of reversible functions and its application to circuit complexity, Conference on Reversible Computation, 2016, 255–270.
• [21] P. Gupta, A. Agrawal, N. K. Jha. An algorithm for synthesis of reversible logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 25, pp. 2317-2330, 2006.
• [22] P. Kerntopf. A new heuristic algorithm for reversible logic synthesis. ACM/IEEE DAC, pages 834-837, 2004.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).