Sekwencyjne odwracalne układy logiczne

• Autorzy: Zagniński P. , Kerntopf P.

Warianty tytułu

EN

Sequential reversible logic circuits

• Języki publikacji: PL

Abstrakty

PL

Układy odwracalne realizują wzajemnie jednoznaczne odwzorowania sygnałów wejściowych na sygnały wyjściowe, tj. nie prowadzące do straty informacji. Badania nad tymi układami prowadzone są bardzo intensywnie. Początkowo zajmowano się głównie syntezą kombinacyjnych układów, dopiero w ostatnich latach liczba publikacji na temat sekwencyjnych układów wzrosła. W pracy przedstawiono układy odwracalnych zatrzasków, które zaproponowano w literaturze, i sformułowano otwarte problemy w tej dziedzinie.

EN

Reversible computations stretch the limits of the classical computa-tions, bounded otherwise by energy loss. They are also the basis for the emerging quantum technologies. Though such designs have succeeded since they are logically equivalent with classical designs, there is still much room for improvement. Reversible logic circuit synthesis received much attention in the past decade from the computer science community due to its, as yet unrivaled, potential to satisfy the requirements for power efficient computations. The initial focus has been given to the combinational logic circuits, as the foundation of a general theory for the reversible circuit synthesis. Recently, more attention is given to sequential circuits as they form the basis of the well known state-based processing of the traditional computers. The research in this field started in 1980 with the pioneering work of Toffoli [3], followed only in 1996 by Picton [7]. Next publications by Chuang and Wang [8], and Rice [9] appeared in the last decade, followed by some very recent publications, e.g. Banerjee and Pathak [10]. This paper gives an overview of the current advances in the field of the sequential reversible logic presenting latches, the most common sequential circuits, and open problems.

Słowa kluczowe

PL

sekwencyjne układy odwracalne; zatrzaski odwracalne

EN

sequential reversible circuits; reversible latches

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 7
• Strony: 678--680
• Opis fizyczny: Bibliogr. 18 poz., rys., tab.

Twórcy

autor

Zagniński P.

autor

Kerntopf P.

• Politechnika Warszawska, Wydział Elektroniki, Instytut Informatyki, ul. Nowowiejska 15/19, 00-665 Warszawa,

Bibliografia

• [1] Landauer R.: Irreversibility and heat generation in the computing process, IBM J. Res. & Dev., vol. 5, 1961, pp. 183-191.
• [2] Bennett C. H.: Logical reversibility of computation, IBM J. Res. & Dev., vol. 17, 1973, pp. 525-532.
• [3] Toffoli T.: Reversible computing, Tech. Memo MIT/LCS/TM-151, MIT Laboratory for Computer Science, 1980.
• [4] Fredkin E. F., Toffoli T.: Conservative logic. International Journal of Theoretical Physics, vol. 21, 1982, pp 219-253.
• [5] Grover L. K.: A fast quantum mechanical algorithm for database search, Proc. of the 28th Annual ACM Symposium on the Theory of Computing, May 1996, pp. 212-219.
• [6] Shor P.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. on Computing, vol. 26, 1997, pp. 1484-1509.
• [7] Picton P.: Multi-valued sequential logic design using Fredkin gates, Multiple-Valued Logic J., vol. 1, 1996, pp. 241-251.
• [8] Chuang M., Wang C.: Synthesis of Reversible Sequential Elements, Proc. of the ASPDAC, Yokohama, Japan, January 2007, pp. 420-425.
• [9] Rice J. E.: An introduction to reversible latches, Computer Journal, vol. 51, 2008, pp. 700-709.
• [10] Banerjee A., Pathak A.: New designs of reversible sequential devices, arXiv:0908.1620v1 [quant-ph], 12 August 2009.
• [11] Kerntopf P.: Synteza odwracalnych układów logicznych, Pomiary-Automatyka-Kontrola, vol. 53, nr 7, 2007, pp. 78-80.
• [12] Szyprowski M., Kerntopf P.: Porównanie efektywności heurystycznych miar złożoności odwracalnych funkcji boolowskich, Pomiary-Automatyka-Kontrola, vol. 55, nr 8, 2009, pp. 581-583.
• [13] Barenco A., Bennett C. H., Cleve R., DiVincenzo D. P., Margolus N., Shor P., Sleator T., Smolin J. A., Weinfurter H.: Elementary Gates for Quantum Computation, Phys. Rev. A, vol. 52, 1995, pp. 3457-3467.
• [14] Grosse D., Wille R., Dueck G. W. and Drechsler R.: Exact Multiple Control Toffoli Network Synthesis with SAT Techniques, IEEE Trans. on CAD, vol. 28, 2009, pp. 703-715.
• [15] Wille R., Saeedi M., Drechsler R.: Synthesis of Reversible Functions Beyond Gate Count and Quantum Cost , International Workshop on Logic Synthesis (IWLS), Berkeley, USA, July-Aug. 2009, pp. 43-49.
• [16] Forsberg E.: Reversible logic based on electron waveguide Y-branch switches, Nanotechnology, vol. 15, 2004, pp. 298-302.
• [17] Thapliyal H., Ranganathan N.: Testable Reversible Latches for Molecular QCA, Proc. 8th IEEE Int. Conf. on Nanotechnology (NANO), Arlington, TX, USA, Aug. 2008, pp. 699-702.
• [18] Axelsen H. B., Glück R., De Vos A., Thomsen M. K.: MicroPower: Towards low-power microprocessors with reversible computing, http://ercim-news.ercim.eu/en79/special-theme/micropower-towards-low-power-microprocessors-with-reversible-computing