Decompositions of reversible logic circuits

• Autorzy: Szyprowski M. , Kerntopf P.

Warianty tytułu

PL

Dekompozycje odwracalnych układów logicznych

• Języki publikacji: EN

Abstrakty

EN

Results of research on decompositions of reversible circuits into blocks are presented where each block is constructed from one kind of gates. The main contribution of this paper consists in discovering that there exist more decompositions than the only one considered in the literature up to now. Moreover, it is shown that all of these decompositions correspond to circuits having different average minimal cost. This fact can be used in the future to guide heuristics in developing better algorithms for reversible logic circuit synthesis.

PL

Układ logiczny jest odwracalny, gdy liczba wejść jest równa liczbie wyjść, a funkcja realizowana przez ten układ jest wzajemnie jednoznaczna. Do tej pory tylko w jednej publikacji rozważano dekompozycję układów odwracalnych na takie bloki, z których każdy jest złożony z bramek odwracalnych jednego typu. W pracy prezentujemy znalezione przez nas trzy inne dekompozycje układów. Dzięki znalezieniu przez nas wszystkich optymalnych układów o trzech wejściach i trzech wyjściach, pokazaliśmy, że rozpatrywane przez nas nowe dekompozycje prowadzą do układów o mniejszym koszcie niż dla wcześniej rozpatrywanej dekompozycji. Zatem znalezione przez nas dekompozycje mogą mieć duże znaczenie przy konstruowaniu algorytmów syntezy odwracalnych układów logicznych generujących układy o mniejszym koszcie niż opublikowane dotąd algorytmy.

Słowa kluczowe

EN

reversible logic circuits; decompositions of reversible circuits

PL

odwracalne układy logiczne; dekompozycje układów odwracalnych

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2009
• Tom: R. 55, nr 8
• Strony: 609--611
• Opis fizyczny: bibliogr. 8 poz., rys., tab.

Twórcy

autor

Szyprowski M.

autor

Kerntopf P.

• Institute of Informatics, Faculty of Electronics and Information Techniques, Warsaw University of Technology,

Bibliografia

• [1] D. Maslov, G. W. Dueck: Improved quantum cost for n-bit Toffoli gates, IEE Electronic Letters, vol. 39, Dec. 2003, no 25, pp. 1790-1791.
• [2] V. V. Shende, A. K. Prasad, I. L. Markov, J. P. Hayes: Reversible Logic Circuit Synthesis, IEEE Trans. on CAD, vol. 22, 2003, no 6, pp. 710-722.
• [3] K. N. Patel, I. L. Markov, J. P. Hayes: Optimal synthesis of linear reversible circuits. Quantum Information and Computation, 8, 3&4 (2008), pp. 282-294.
• [4] D. Maslov: Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite neighbor quantum architectures. ArXiv:quant-ph/0703211v2 (15 Nov. 2007).
• [5] A. K. Prasad, V. V. Shende, K. N. Patel, I. L. Markov, J. P. Hayes: Data structures and algorithms for simplifying reversible circuits, ACM Journal on Emerging Technologies in Computing Systems, vol. 2, 2006, no 4, pp. 277-293.
• [6] D. Maslov, G. W. Dueck, D. M. Miller: Techniques for the synthesis of reversible Toffoli networks, ACM Transactions on Design Automation of Electronic Systems, vol. 12, Sept. 2007, no 4, article 42.
• [7] J. Zhong: A New Fault Model and Its Application in Synthesizing Toffoli Networks, PhD Thesis, University of Victoria, Victoria, Canada, 2008.
• [8] K. Iwama, Y. Kambayashi, S. Yamashita: Transformation rules for designing CNOT-based quantum circuits, Proc. Design Automation Conference, New Orleans, LA, June 2002, pp. 419-425.