Synteza odwracalnych układów logicznych oparta na sieciach Closa

• Autorzy: Szyprowski M.

Warianty tytułu

EN

Clos switching network based reversible circuit synthesis

• Języki publikacji: PL

Abstrakty

PL

W pracy zaprezentowany jest efektywny obliczeniowo algorytm syntezy układów odwracalnych oparty na komutacji połączeń w sieci przełączającej Closa. Zaproponowano heurystyki, które zmniejszają koszt generowanych układów. Dla układów o 3 wejściach i wyjściach podstawowa wersja algorytmu generuje układy o średnim koszcie równym 131,1% kosztu układu optymalnego, zaś pokazane heurystyki zmniejszają go do 113,7%.

EN

Synthesis of reversible Boolean functions (i.e. bijective mappings) is an emerging research area, mainly motivated by advances in quantum computing, nanotechnologies and low power design. The paper describes a computationally efficient reversible circuit synthesis algorithm. The presented synthesis algorithm decomposes the permutation realized by a reversible function into simpler permutations, which can be then directly mapped to reversible gates. The decomposition is based on the combinatorial theorems used by the Clos switching networks. In the paper analysis of the algorithm computational complexity is performed as well as some new heuristic modifications are proposed. These heuristics decrease the cost of generated circuits and reduce the required computation time. For all 3-input, 3-output reversible functions, the basic algorithm generates circuits that are 131.1% larger than the optimal one, while the introduced heuristics reduce it to 113.7%.

Słowa kluczowe

PL

odwracalne układy logiczne; synteza logiczna

EN

reversible logic circuits; logic synthesis

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2010
• Tom: R. 56, nr 7
• Strony: 735--738
• Opis fizyczny: Bibliogr. 6 poz., rys., tab., wzory

Twórcy

autor

Szyprowski M.

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

Bibliografia

• [1] de Vos A., van Rentergem Y.: “Networks for reversible logic”, Int. Workshop on Boolean Problems, Freiberg, Germany, 2008, pp. 41-47.
• [2] de Vos A., van Rentergem Y.: “Young groups for reversible computers“, Advances in Maths of Communications 2, 2008, pp. 183-200.
• [3] Borgersen R.: “Equivalence of seven major theorems in combinatorics”, http://home.cc.umanitoba.ca/~umborger/Presentations/GS-05R-1.pdf.
• [4] Maslov D., Dueck G.W.: “Improved quantum cost for n-bit Toffoli gates”, IEE Electronics Letters, vol. 39 (25), 2003, pp. 1790-1791.
• [5] 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.
• [6] Rudell R.: “Dynamic variable ordering for ordered binary decision diagrams”,. Proc. ICCAD, Nov. 1993, pp. 42-47.