Synteza układów odwracalnych metodą różnicową

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

Warianty tytułu

EN

Difference method of reversible circuits synthesis

• Języki publikacji: PL

Abstrakty

PL

W niniejszej pracy przedstawiony jest prosty algorytm projektowania układów odwracalnych. Proponowany algorytm polega na wyznaczeniu dla danej funkcji zbioru bramek (nazywanego zbiorem bramek pierwszych), które mogą znajdować się na początku układu kaskadowego realizującego zadaną funkcję. Po wyznaczeniu takiego zbioru można wybrać jeden z jego elementów, a następnie powtórzyć algorytm dla tzw. funkcji resz-towej. Postępuje się tak, aż do momentu, gdy funkcja resztowa stanie się funkcją identycznościową. Liczba iteracji algorytmu jest równa liczbie bramek projektowanej kaskady.

EN

Research on reversible logic circuits is motivated by advances in quantum computing, nanotechnology and low-power design. Im-plementation of such functions is realized by special gates. These gates always form a cascade circuit. Minimization of such circuits is a very difficult problem. In this paper a novel concept of synthesis of reversible logic is presented. For simplicity, the method is described for three variables only but it is scalable for more variables. The proposed method is based on XOR function applied to input and output sides of the truth table of a function to be synthesized. The result of applying XOR function indicates bits in the truth table which have to be changed by reversible gates. Due to this property the number of analyzed gates is small. We present the comparison of three variants of the difference method. Each of them leads to different numbers of 3-variable functions for which exact optimal circuits have been found.

Słowa kluczowe

PL

odwracalne układy logiczne; projektowanie układów

EN

reversible logic circuits; circuit synthesis

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2013
• Tom: R. 59, nr 8
• Strony: 784--786
• Opis fizyczny: Bibliogr. 5 poz., rys., tab., wzory

Twórcy

autor

Skorupski A.

• Wyższa Szkoła Menadżerska, Wydział Informatyki Stosowanej i Technik Bezpieczeństwa, ul. Kawęczyńska 36, 03-772 Warszawa

autor

Pawłowski M.

• Politechnika Warszawska, Wydział Elektroniki i Technik Informacyjnych, ul. Nowowiejska 15/19, 00-665 Warszawa

autor

Gracki K.

• Politechnika Warszawska, Wydział Elektroniki i Technik Informacyjnych, ul. Nowowiejska 15/19, 00-665 Warszawa

autor

Kerntopf P.

• Politechnika Warszawska, Wydział Elektroniki i Technik Informacyjnych, ul. Nowowiejska 15/19, 00-665 Warszawa
• Uniwersytet Łódzki, Wydział Fizyki i Informatyki Stosowanej, ul. Pomorska 149/153, 90-236 Łódź

Bibliografia

• [1] De Vos A.: Reversible Computing. Fundamentals, Quantum Computing and Applications, Wiley-VCH, Berlin 2010.
• [2] Saeedi M., Markov I. L.: Synthesis and optimization of reversible circuits – a survey, ACM Computing Surveys, 2013, także w: arXiv:1110.2574.
• [3] Skorupski A., Szyprowski M., Kerntopf P.: Algorytm syntezy kombinacyjnych układów odwracalnych, Pomiary Automatyka Kontrola, vol. 57, nr 8, 2011, ss. 858-860.
• [4] Szyprowski M., Kerntopf P.: Metody konstrukcji optymalnych układów odwracalnych, Pomiary Automatyka Kontrola, vol. 58, nr 7, 2012, ss. 647-649.
• [5] Kerntopf P.: Some remarks on reversible logic synthesis, Proc. - 8th International Reed-Muller Workshop, 2007, ss. 51-57.