Algorytm syntezy kombinacyjnych układów odwracalnych

• Autorzy: Skorupski A. , Szyprowski M. , Kerntopf P.

Warianty tytułu

EN

Algorithm for reversible circuit synthesis

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono koncepcję nowego algorytmu syntezy układów odwracalnych. Jest on oparty na oryginalnej reprezentacji zamiany wierszy w tablicy prawdy. Dla układów o trzech wejściach i trzech wyjściach sformułowano kryteria takiego doboru bramek, aby otrzymać układ zbliżony do optymalnego. Następnie podano przykład zastosowania przedstawionego algorytmu do syntezy układów o trzech wejściach i trzech wyjściach z bramek Toffoliego.

EN

A gate or circuit is reversible if there is one-to-one correspondence between its input signals and output signals, i.e. if they implement bijective functions. Research on reversible logic circuits is motivated by advances in quantum computing, nanotechnology and low-power design. Recently, the attention has been focused on the synthesis of reversible circuits built from the NCT library of gates consisting of NOT, CNOT and Toffoli gates. This paper presents a novel algorithm for synthesis of reversible circuits. It is based on a new representation of row exchanges in the truth table. There is described how each possible row exchange determines the set of subsequent gates in a circuit, basing on the newly introduced cube of row exchanges. Next, the criteria for the choice of NCT reversible gates are formulated. For an exemplary function, the presented algorithm generates an optimal reversible circuit with 3 inputs and 3 outputs. It can also be generalized to any number of inputs and outputs.

Słowa kluczowe

PL

odwracalne układy logiczne; bramki Toffoliego

EN

reversible logic circuits; Toffoli gates

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 8
• Strony: 858--860
• Opis fizyczny: Bibliogr. 15 poz., rys., tab.

Twórcy

autor

Skorupski A.

autor

Szyprowski M.

autor

Kerntopf P.

• Wyższa Szkoła Menadżerska, ul. Kawęczyńska 36, 03-772 Warszawa,

Bibliografia

• [1] De Vos A.: Reversible Computing. Fundamentals, Quantum Computing, and Applications. Wiley-VCH, Berlin 2010.
• [2] Wille R., Drechsler R.: Towards a Design Flow for Reversible Logic. Springer, Dordrecht 2010.
• [3] Nielsen M., Chuang I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge 2000.
• [4] 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, 2010.
• [5] Kerntopf P.: Synteza odwracalnych układów logicznych, Pomiary Automatyka Kontrola, vol. 53, nr 7, 2007, pp. 78-80.
• [6] 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.
• [7] Miller D. M., Maslov D., Dueck G. W.: A transformation based algorithm for reversible logic synthesis, Proc. 40th Design Automation Conference, Anaheim, CA, USA, 2003, pp. 318-323.
• [8] Gupta P., Agrawal A., Jha N. K.: An algorithm for synthesis of reversible logic circuits, IEEE Trans. on Computer-Aided Design, 2006, vol. 25, pp. 2317-2330.
• [9] Miller D. M., Maslov D.: Spectral Techniques for Reversible Logic Synthesis, Proc. 6th Int. Symp. on Representations and Methodology of Future Computing Technology, Trier, Germany, 2003, pp. 56-62.
• [10] 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: pp. 1-28.
• [11] Kerntopf P.: A new heuristic algorithm for reversible logic circuit synthesis, Proc. 41st Design Automation Conference, San Diego, USA, 2004, pp. 834-837.
• [12] Shende V. V., Prasad A. K., Markov I. L., Hayes J. P.: Synthesis of reversible logic circuits, IEEE Trans. on Computer-Aided Design, 2003, vol. 22, no. 6, pp. 710-722.
• [13] Van Rentergem Y., De Vos A., De Keyser K.: Using group theory in reversible computing. Proc. IEEE Congress on Evolutionary Computation, Vancouver, BC, Canada, July 2006.
• [14] Yang G., Song X., Hung W. N. N., Xie F., Perkowski M. A.: Group theory based synthesis of binary reversible circuits. Proc. 3rd International Conference on Theory and Applications of Models of Computation, Lecture Notes in Computer Science, 3959, 2006, pp. 365-374.
• [15] Grosse D., Wille R., Dueck G. and Drechsler R.: Exact Multiple Control Toffoli Network Synthesis with SAT Techniques, IEEE Trans. on CAD, vol. 28, 2009, pp. 703-715.