Porównanie efektywności heurystycznych miar złożoności odwracalnych funkcji boolowskich

• Autorzy: Szyprowski M. , Kerntopf P.

Warianty tytułu

EN

Comparison of Heuristic Complexity Measure Quality for Reversible Boolean Functions

• Języki publikacji: PL

Abstrakty

PL

Funkcja boolowska jest nazywana odwracalną, gdy jest wzajemnie jednoznaczna. W literaturze zaproponowano kilka heurystyk służących do syntezy odwracalnych układów logicznych, jednak do tej pory nie znaleziono rozwiązania, które dawałoby zadowalające wyniki. Przy pracach nad ulepszaniem tych algorytmów potrzebne jest dobre kryterium oceny jakości poszczególnych heurystyk. W pracy pokazano jak wykorzystać bazę optymalnych układów odwracalnych do oceny działania heurystyk oraz przedstawiono wyniki obliczeń pozwalających na porównanie ich efektywności.

EN

A Boolean logic function is reversible if it is a bijective mapping. Synthesis of such functions is motivated by advances in quantum computing, nanotechnologies and low power design. Several heuristic synthesis algorithms has been proposed, but so far none of them produces circuits of good quality in acceptable time. All of them are based on exploration of the search tree guided by a complexity measure function. Search for better algorithms is important and for this aim a good evaluation criterion of a heuristic complexity measure quality is needed. In this article the comparison of reversible function complexity measures known from the literature is made. Their accuracy is checked on the library of the optimal circuits of 3 inputs/outputs. The results are presented in Table 1. The numeric factor Q is introduced on the basis of calculating the probability of taking a wrong way in the search tree by a synthesis algorithm for every reversible function. This factor was calculated for five heuristic complexity measures and shown in Table 2. According to it the Reed-Muller spectrum based complexity measure gives best synthesis results, however there is still a lot of space for improvements.

Słowa kluczowe

PL

odwracalne układy logiczne; miary złożoności funkcji odwracalnych

EN

reversible logic circuits; reversible function complexity measure

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2009
• Tom: R. 55, nr 8
• Strony: 581--583
• Opis fizyczny: Bibliogr. 5 poz., tab., wzory

Twórcy

autor

Szyprowski M.

autor

Kerntopf P.

• Instytut Informatyki, Wydział Elektroniki i Technik Informacyjnych, Politechnika Warszawska,

Bibliografia

• [1] G. W. Dueck, D. Maslov: Reversible Function Synthesis with Minimum Garbage Outputs, Proceedings of the 6th International Symposium on Representations and Methodology of Future Computing Technology, Trier, Germany, March 2003, pp. 154-161.
• [2] P. Gupta, A. Agrawal, N. K. Jha: An Algorithm for Synthesis of Reversible Logic Circuits, IEEE Transactions on Computer-Aided Design, 25, November 2006, pp. 2317-2330.
• [3] P. Kerntopf: A New Heuristic Algorithm for Reversible Logic Synthesis, Proceedings of te 41st Design Automation Conference, San Diego, CA, June 2004, pp. 834-837.
• [4] 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, no 4, September 2007, article 42, pp. 1-28.
• [5] D. M. Miller, D. Maslov: Spectral Techniques for Reversible Logic Synthesis, Proceedings of the 6th International Symposium on Representations and Methodology of Future Computing Technology, Trier, Germany, March 2003, pp. 56-62.