The Algorithm for Reversible Circuits Synthesis

• Autorzy: Skorupski Andrzej , Gracki Krzysztof

Identyfikatory

DOI

10.24425/ijet.2020.131875

• Języki publikacji: EN

Abstrakty

EN

In this paper the new synthesis method for reversible networks is proposed. The method is suitable to generate optimal circuits. The examples will be shown for three variables reversible functions but the method is scalable to larger number of variables. The algorithm could be easily implemented with high speed execution and without big consuming storage software. Section 1 contains general concepts about the reversible functions. In Section 2 there are presented various descriptions of reversible functions. One of them is the description using partitions. In Section 3 there are introduced the cascade of the reversible gates as the target of the synthesis algorithm. In order to achieve this target the definitions of the rest and remain functions will be helpful. Section 4 contains the proposed algorithm. There is introduced a classification of minterms distribution for a given function. To select the successive gates in the cascade the condition of the improvement the minterms distribution must be fulfilled. Section 4 describes the algorithm how to improve the minterms distributions in order to find the optimal cascade. Section 5 shows the one example of this algorithm.

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: 2020
• Tom: Vol. 66, No. 2
• Strony: 281--286
• Opis fizyczny: Bibliogr. 17 poz., rys., tab.

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] V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes. Reversible logic circuit synthesis. In IEEE/ACM International Conference on Computer Aided Design (ICCAD), pages 353–360, 2002. November 10–14, San Jose, CA, USA, ACM.
• [2] C.H. Bennett, Logical Reversibility of Computation, IBM Journal Research and Development, Nov. 1973.
• [3] R. Landauer. Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 5: 183–191, 1961.
• [4] A. De Vos, B. Raa, L. Storme, Generating the group of reversible logic gates, J. Phys. A: Math. Gen. 35 (2002), 7063–7078.
• [5] 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.
• [6] D. M. Miller, D. Maslov, G. W. Dueck, A transformation based algorithm for reversible logic synthesis, in: Design Automation Conf., 2003, pp. 318–323.
• [7] P. Kerntopf, A new heuristic algorithm for reversible logic synthesis, Design Automation Conf., 2004, pp. 834–837.
• [8] C. Bandyopadhyay, H. Rahaman, R. Drechsler, “A Cube Pairing Approach for Synthesis of ESOP-Based Reversible Circuit,” Proceedings of the IEEE International Symposium on Multiple-Valued Logic, pp. 109-114, May 19-21, 2014.
• [9] C. S. Cheng, A. K. Singh, “Heuristic Synthesis of Reversible Logic - A Comparative Study”, Advances in Electrical and Electronic Engineering, vol. 12, no. 3, pp. 210-225, September 2014.
• [10] M. Krishna, An. Chattopadhyay, “Efficient Reversible Logic Synthesis via Isomorphic Subgraph Matching”, Proceedings of the IEEE International Symposium on Multiple-Valued Logic, pp. 103-108, May 19-21, 2014.
• [11] C.-C. Lin, N. K. Jha, “RMDDS: Reed-Muller Decision Diagram Synthesis of Reversible Logic Circuits”, ACM Journal on Emerging Technologies in Computing Systems, vol. 10, no. 2, pp. 14:1–14:25, February 2014.
• [12] S. J. Roy, K. Datta, C. Bandyopadhyay, H. Rahaman, “A Transformation Based Heuristic Synthesis Approach for Reversible Circuits”, Proceedings of the International Conference on Advances in Electrical Engineering, pp. 1-5, January 2014.
• [13] E. Schönborn, K. Datta, R. Wille, I. Sengupta, H. Rahaman, R. Drechsler: “BDD-based Synthesis for All-optical Mach-Zehnder Interferometer Circuits”, International Conference on VLSI Design, 2015.
• [14] A. Skorupski, Graphical Method of Reversible Circuits Synthesis, IJET, Vol. 63, No 3, 2017.
• [15] E. F. Fredkin, T. Toffoli, Conservative logic, International Journal of Theoretical Physics 21 (1982), pp. 219–253.
• [16] P. Gupta, A. Agrawal, N. Jha, An algorithm for synthesis of reversible logic circuits, IEEE Trans. on CAD 25 (2006), pp. 2317–2330.
• [17] D. M. Miller, D. Maslov, G. W. Dueck, A transformation based algorithm for reversible logic synthesis, in: Design Automation Conf., 2003, pp. 318–323.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).