PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

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

Identyfikatory
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.
Czasopismo
Rocznik
Strony
33--43
Opis fizyczny
Bibliogr. 18 poz.
Twórcy
autor
  • Politechnika Warszawska, Instytut Informatyki
autor
  • Politechnika Warszawska, Instytut Informatyki
autor
  • 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
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-3352c80e-7583-4903-9fa1-a0c010186acd
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.