Systematyczne metody dekompozycji funkcji boolowskich

• Autorzy: Wąsicki Dariusz

Identyfikatory

DOI

10.15199/59.2020.11-12.3

Warianty tytułu

EN

Systematic methods of Boolean function decomposition

• Języki publikacji: PL

Abstrakty

PL

Ze względu na ważne zastosowania (dystrybucja adresów iP, skanowanie wirusów i wykrywanie niepożądanych danych) metody projektowania funkcji generowania indeksów są ostatnio przedmiotem intensywnych badań naukowych. większość proponowanych algorytmów oparta jest na metodach heurystycznych umożliwiających znalezienie lokalnie optymalnego rozwiązania. W artykule dyskutowane są systematyczne metody rozłącznych oraz nierozłącznych dekompozycji, funkcjonalnej i liniowej, stosowanych w generatorach indeksów. Ich wykorzystanie umożliwia znalezienie globalnie najlepszego rozwiązania. Zastosowanie pojęcia r-przydatności znacznie poprawia efektywność proponowanych algorytmów dekompozycji.

EN

Due to important applications (iP address distribution, virus scanning, and unwanted data detection), index generation function design methods have recently been the subject of intense research. Most of the proposed algorithms are based on heuristic methods allowing to find a locally optimal solution. The article discusses systematic methods of disjoint and nondisjoint functional and linear decomposition used in index generators. Their use makes it possible to find the best global solution. The use of the r-admissibility concept significantly improves the efficiency of the proposed decomposition algorithms.

Słowa kluczowe

PL

funkcja generowania indeksów; dekompozycja liniowa; dekompozycja funkcjonalna; dekompozycja rozłączna; dekompozycja nierozłączna; r-przydatność

EN

index generation functions; linear decomposition; functional decomposition; disjoint decomposition; nondisjoint decomposition; r-admissibility

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2020
• Tom: nr 11-12
• Strony: 432--438
• Opis fizyczny: Bibliogr. 16 poz., rys., tab.

Twórcy

autor

Wąsicki Dariusz

• Szkoła Doktorska Wojskowej Akdemii Technicznej

Bibliografia

• [1] Borowik G., T. Łuba: Fast Algorithm of Attribute Reduction Based on the complementation of Boolean Function, ch. 2, pp. 25-41, Springer International Publishing, 2014.
• [2] Borowik G., T. Łuba, K. Poźniak: „New Trends in Logic Synthesis for Both Digital Designing and Data Processing”, SPIE, Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments, 100314U, 9/2015.
• [3] Brzozowski J. A., T. Łuba: „Decomposition of Boolean Functions Specified by Cubes”, in Journal of Multiple-Valued Logic and Soft Computing, Vol. 9, Old City Publishing Inc., Philadelphia, 377-417, 2003.
• [4] Mańkowski M., T. Łuba, C. Jankowski: „Evaluation of Decision Table Decomposition Using Dynamic Programming Classifiers”, The 24th International Workshop on Concurrency, Specification and Programming, Sept. 2015.
• [5] Mazurkiewicz T., T. Łuba: „Redukcja liczby zmiennych do reprezentacji funkcji generowania indeksów”, Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 8-9, s. 795-798, 2017
• [6] Mazurkiewicz T., T. Łuba: „Metody wyboru dekompozycji dla algorytmu z wykorzystaniem zbiorów niezgodności i ich wpływ na minimalizację generatorów indeksów”, Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 8-9, s. 722-725, 2018
• [7] Łuba T., G. Borowik: Synteza logiczna, Oficyna Wydawnicza PW, Warszawa 2015.
• [8] Łuba T., K. Poźniak, B. Zbierzchowski: „Redukcja i kompresja zmiennych w syntezie funkcji generowania indeksów”, Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 10, 2016.
• [9] Łuba T., J. Rybnik: „Algorithmic Approach to Discernibility Function with Respect to Attributes and Objects Reduction”, Foundations of Computing and Decision Sciences, Vol. 18, No. 3-4, 241–258, 1993.
• [10] Łuba T., T. Mazurkiewicz: „Dekompozycja funkcjonalna w syntezie funkcji generowania indeksów”, Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 1, 2019.
• [11] Sasao T.: „Index generation functions: Minimization methods”, IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL), pp. 197-206, 2017.
• [12] Sasao T.: „Index generation functions: Recent developments”, International Symposium on Multiple-Valued Logic (ISMVL-2011), Tuusula, Finland, May 2011.
• [13] Sasao T.: „Linear decomposition of index generation functions”, 17th Asia and South Pacific Design Automation Conference (DAC), pp. 781–788, 2012.
• [14] Sasao T.: Memory-Based Logic Synthesis, Springer New York Dordrecht Heidelberg London, 2011.
• [15] Sasao T., I. Fumishi, Y. Iguchi: „On an exact minimization of variables for incompletely specified index generation functions using SAT”, Note on Multiple-Valued Logic in Japan, pp. 1-8, 2015.
• [16] Simovici D.A., Zimand M., Pletea D.: „Several remarks on index generation functions”, International Symposium on Multiple-Valued Logic (ISMVL-2012), Victoria, Canada, May 2012.

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).