Heurystyczny algorytm syntezy quasi-optymalnych układów odwracalnych

• Autorzy: Skorupski, A. , Gracki, K. , Pawłowski, M. , Kerntopf, P.

Warianty tytułu

EN

Heuristic algorithm of quasi-optimal reversible circuits synthesis

• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono nową metodę syntezy układów odwracalnych. Polega ona na stopniowym porządkowaniu bitów w kolejnych kolumnach części wyjściowej tablicy prawdy odwracalnej funkcji boolowskiej, aż do momentu zrównania części wyjściowej tablicy z jej częścią wejściową. Długość szacunkowej sekwencji bramek, która uporządkowałaby bity we wszystkich kolumnach wyjściowych, stanowi kryterium wyboru bramki w każdym kroku iteracji proponowanego algorytmu. Dla ponad 80% funkcji odwracalnych trzech zmiennych algorytm ten generuje układy optymalne.

EN

In this paper a new method of reversible circuits synthesis is presented. The method is based on iterative ordering of bits in subsequent output columns of the truth table of a reversible function until the output part of the truth table becomes identical with the input part. The length of the estimated shortest sequence which would guarantee the proper order of bits in all output columns is a criterion for choosing a gate at each step of the proposed algorithm. For over 80% of 3-variable reversible functions the algorithm generates optimal circuits.

Słowa kluczowe

PL

zrównoważone funkcje boolowskie; funkcje odwracalne; bramki odwracalne; układy odwracalne; synteza układów logicznych

EN

balanced Boolean function; reversible functions; reversible gates; reversible circuits; logic circuit synthesis

• Czasopismo: Studia Informatica
• Rocznik: 2014
• Tom: Vol. 35, nr 4
• Strony: 33--43
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Skorupski, A.

• Politechnika Warszawska, Instytut Informatyki,

autor

Gracki, K.,

autor

Pawłowski, M.

• Politechnika Warszawska, Instytut Informatyki,

autor

Kerntopf, P.

• Uniwersytet Łódzki, Zakład Informatyki Stosowanej,

Bibliografia

• 1. Golubitsky O. , Maslov D.: A study of optimal 4-bit reversible Toffoli circuits and their synthesis. IEEE Trans. on Computers,61, (2012), p. 1341÷1353.
• 2. Kerntopf P.: Some remarks on reversible logic synthesis. Proc. 8thInternational Work-shop on Applications of the Reed-Muller Expansion in Circuit Design and Representations and Methodology of Future Computing Technology, Oslo, Norway, May 2007, p. 51÷57.
• 3. Landauer R.: Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5, 183 (1961).
• 4. Maslov D., Dueck G.W., Miller D. M.: Techniques for the synthesis of reversible Toffoli networks, ACM Transactions on Design Automation of Electronic Systems, 12, 4 (Sept. 2007), article 42: p. 1÷28.
• 5. Miller D. M., Maslov D., Dueck G. W.: A transformation based algorithm for reversible logic synthesis. Proc. Design Automation Conference, Anaheim, CA, June 2003, p. 318÷323.
• 6. Mishchenko A., Perkowski M.: Logic synthesis of reversible wave cascades. Proc. 11thIEEE/ACM International Workshop on Logic Synthesis, New Orleans, LA, USA, June 2002, p. 197÷202.
• 7. Patel K.N., Markov I.L., Hayes J.P.: Optimal synthesis of linear reversible circuits. Quantum Information and Computation, 8, 3&4 (2008), p. 282÷294.
• 8. Prasad A.K., Shende V.V., Patel K.N., Markov I.L., Hayes J.P.: Data structures and algorithms for simplifying reversible circuits, ACM Journal on Emerging Technologies in Computing Systems, 2, 4 (2006), p. 277÷93.
• 9. Shende V.V., Prasad A.K., Markov I.L., Hayes J.P.: Reversible logic circuit synthesis. IEEE Trans. on CAD, 22, 6 (2003), p. 710÷22.
• 10. Skorupski A., Gracki K., Pawłowski M., Kerntopf P.: Synteza układów odwracalnych metodąróżnicową. Pomiary Automatyka Kontrola, 2013, nr 8, p.784÷786.
• 11. Szyprowski M., Kerntopf P.: Reducing quantum cost in reversible Toffoli circuits. Proc. 10thReed-Muller Workshop, Tuusula, Finland, May 2011, p. 127÷136; poprawiona wersja: http://arxiv.org/abs/1105.5831 42 A. Skorupski, K. Gracki, M. Pawłowski, P. Kerntopf
• 12. Van Rentergem Y., De Vos A.: Synthesis and optimization of reversible circuits. Proc. 8thInternational Workshop on Applications of the Reed-Muller Expansion in Circuit Design and Representations and Methodology of Future Computing Technology, Oslo, Norway, May 2007, p. 67÷65.
• 13. Van Rentergem Y., De Vos A., De Keyser K.: Six synthesis methods for reversible logic. Open Systems and Information Dynamics, 14, 1 (2007), p. 91÷116.
• 14. Wille R., Grosse D.: Fast exact Toffoli network synthesis of reversible logic, Proc. In-ternational Conference on CAD, San Jose, CA, USA, Nov. 2007, p. 60÷64.
• 15. Wille R., Le H.M., Dueck G.W., Grosse D.: Quantified synthesis of reversible logic, Proc. Design, Automation and Test in Europe Conference, Munich, Germany, March 2008.
• 16. Yang G., Song X., Hung W.N.N., Perkowski M.A.: Fast synthesis of exact minimal reversible circuits using group theory. Proc. 10thAsia and South Pacific Design Automation Conference, Shanghai, China, 2005, p. 1002÷1005.
• 17. Yang G., Xie F., Song X., Hung W.N.N., Perkowski, M.: A constructive algorithm for reversible logic synthesis. Proc. IEEE Congress on Evolutionary Computation, Van-couver, BC, Canada, July 2006, p. 2416÷2421.
• 18. Yang G., Song X., Hung W.N.N., Xie F., Perkowski M.A.: Group theory based synthesis of binary reversible circuits. Proc. 3rdInternational Conference on Theory and Applications of Models of Computation, Lecture Notes in Computer Science, 3959, 2006, p. 365÷374