Czasopismo | PRZEGLĄD TELEKOMUNIKACYJNY - WIADOMOŚCI TELEKOMUNIKACYJNE | Rocznik 2020 - zeszyt 11-12

Systematyczne metody dekompozycji funkcji boolowskich

Systematic methods of Boolean function decomposition

Dariusz Wąsicki

nr katalogowy: 129454

Streszczenie

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.

Abstract

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

Keywords

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.

Jeśli masz wykupiony/przyznany dostęp - zaloguj się. Skorzystaj z naszych propozycji zakupu!

Publikacja


PRZEGLĄD TELEKOMUNIKACYJNY - WIADOMOŚCI TELEKOMUNIKACYJNE- e-publikacja (pdf) z zeszytu 2020-11-12 , nr katalogowy 129454 licencja: Osobista Produkt cyfrowy Nowość	10.00 zł

Zeszyt


PRZEGLĄD TELEKOMUNIKACYJNY - WIADOMOŚCI TELEKOMUNIKACYJNE- e-zeszyt (pdf) 2020-11-12 licencja: Osobista Produkt cyfrowy Nowość	61.00 zł

Prenumerata

PRZEGLĄD TELEKOMUNIKACYJNY - prenumerata cyfrowa
licencja: Osobista

Produkt cyfrowy
Nowość

300.00 zł

PRZEGLĄD TELEKOMUNIKACYJNY - papierowa prenumerata roczna + wysyłka
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD TELEKOMUNIKACYJNY - papierowa prenumerata roczna	348.00 zł brutto 322.22 zł netto 25.78 zł VAT (stawka VAT 8%)
PRZEGLĄD TELEKOMUNIKACYJNY - pakowanie i wysyłka	21.00 zł brutto 17.07 zł netto 3.93 zł VAT (stawka VAT 23%)

369.00 zł

PRZEGLĄD TELEKOMUNIKACYJNY - PAKIET prenumerata PLUS
licencja: Osobista

Szczegóły pakietu

Nazwa
PRZEGLĄD TELEKOMUNIKACYJNY - PAKIET prenumerata PLUS (Prenumerata papierowa + dostęp do portalu sigma-not.pl + e-prenumerata)	450.00 zł brutto 416.67 zł netto 33.33 zł VAT (stawka VAT 8%)

450.00 zł

Zeszyt

2020-11-12

Twój Koszyk

Publikacja

Zeszyt

Prenumerata

Zeszyt

Czasopisma