Dekompozycja funkcjonalna w syntezie funkcji generowania indeksów

• Autorzy: Łuba Tadeusz , Mazurkiewicz Tomasz

Identyfikatory

DOI

10.15199/59.2019.1.3

Warianty tytułu

EN

Functional decomposition in the synthesis of index generation functions

• Języki publikacji: PL

Abstrakty

PL

Funkcje generowania indeksów znajdują zastosowanie w dystrybucji adresów IP, skanowaniu wirusów oraz wykrywaniu niepożądanych danych. Cechą charakterystyczną proponowanej metody jest dekompozycja funkcjonalna. Dekompozycja umożliwia kompresję danych, zachowując jednocześnie precyzję rozpoznawania wzorców. Nowością tej metody jest zastosowanie oryginalnego algorytmu uzupełniania funkcji boolowskich. Metoda zachowuje zalety dekompozycji funkcjonalnej i jest dostosowana do syntezy w strukturach z pamięciami ROM.

EN

Index Generation Functions may be useful in distribution of IP addresses, virus scanning or undesired data detection. A characteristic feature of the proposed method is using functional decomposition. Decomposition has a huge impact on data compression while maintaining the accuracy of pattern matching. The innovation of the method focuses on efficient procedure based on the Complementation of Boolean Function. Furthermore, it preserves advantages of functional decomposition and is well suited for ROM-based synthesis of Index Generation Functions.

Słowa kluczowe

PL

funkcje generowania indeksów; dekompozycja funkcjonalna; redukcja argumentów; synteza na pamięciach ROM

EN

Index Generation Functions; functional decomposition; argument reduction; ROM based synthesis

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
• Rocznik: 2019
• Tom: nr 1
• Strony: 19--25
• Opis fizyczny: Bibliogr. 21 poz., rys., tab.

Twórcy

autor

Łuba Tadeusz

• Warszawska Wyższa Szkoła Informatyki

autor

Mazurkiewicz Tomasz

• Instytut Matematyki i Kryptologii, Wydział Cybernetyki, Wojskowa Akademia Techniczna

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", Journal of Multiple-Valued Logic and Soft Computing, vol. 9, Old City Publishing, Inc., pp. 377-417, 2003.
• [4] Łuba T., T. Mazurkiewicz: "Synteza generatorów indeksów metodami dekompozycji liniowej i funkcjonalnej. Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 5, 2018.
• [5] Łuba T., G. Borowik: Synteza logiczna, Oficyna Wydawnicza PW, Warszawa 2015.
• [6] Łuba T., R. Lasocki, J. Rybnik: An Implementation of Decomposition Algorithm and its Application in Information Systems Analysis and Logic Synthesis, Rough Sets, Fuzzy Sets and Knowledge Discovery, W. Ziarko (ed.). Workshops in Computing Series. Springer Verlag, pp. 458-465, 1994.
• [7] Ł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.
• [8] Łuba T., H. Selvaraj: A general Approach to Boolean Function Decomposition and its Applications in FPGA-based Synthesis, VLSI Design, Special Issue on Decomposition in VLSI Design, vol. 3, nos. 3-4, pp. 289-300, 1995.
• [9] Łuba T.: Decomposition of Multiple-Valued Functions, 25th International Symposium on Multiple-Valued Logic (ISMVL), 1995.
• [10] Mazurkiewicz T., T. Łuba: "Redukcja liczby zmiennych do reprezentacji funkcji generowania indeksów", Przegląd Telekomunikacyjny i Wiadomości Telekomunikacyjne, nr 8-9, pp. 795-798, 2017.
• [11] Sasao T., K. Matsuura, Y. Iguchi: An Algorithm to Find Optimum Support- Reducing Decompositions for Index Generation Functions, Proceedings of the Conference on Design, Automation & Test in Europe, pp. 812-817, 2017.
• [12] Sasao T.: Memory-Based Logic Synthesis, Springer, 2011.
• [13] Sasao T.: A Reduction Method for the Number of Variables to Represent Index Generation Functions: s-Min Method, IEEE 45th International Symposium on Multiple-Valued Logic (ISMVL), pp. 164-169, 2015.
• [14] Sasao T.: Index Generation Functions, Logic Synthesis for Pattern Matching, EPFL Workshop on Logic Synthesis & Verification, Dec. 2015.
• [15] Sasao T.: Index generation functions: Minimization methods, IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL), pp. 197- 206, 2017.
• [16] 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.
• [17] logic.mimuw.edu.pl/~rses/.
• [18] idss.cs.put.poznan.pl/site/139.html.
• [19] Białas M.: Implementacja oprogramowania wspomagającego redukcję i klasyfikację danych, Praca dyplomowa, WEiTI, Ośrodek Kształcenia na Odległość, Politechnika Warszawska, Warszawa 2017.
• [20] Iwaszko T.: Dekompozycja funkcji boolowskich z zastosowaniem do syntezy eneratorów adresów, Praca dyplomowa, WEiTI, Politechnika Warszawska, Warszawa 2016.
• [21] Kowalski K.: Synteza funkcji generowania indeksów metodą redukcji i kompresji argumentów, Praca dyplomowa, WEiTI, Politechnika Warszawska, Warszawa 2017.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).