Wyniki wyszukiwania - BazTech

1

Systematyczne metody dekompozycji funkcji boolowskich

Wąsicki Dariusz

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2020

|

nr 11-12

432--438

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.

2

Metody syntezy logicznej w optymalizacji sprzętowej systemów eksploracji danych

Wąsicki Dariusz, Malinowska Agnieszka

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2020

|

nr 4-5

72--79

PL

W artykule dyskutowane jest zastosowanie syntezy logicznej w celu zmniejszenia złożoności sprzętowej systemów analizy danych. Zastosowanie redukcji atrybutów zmniejsza złożoność dekompozycji. Omówiono metody dekompozycji liniowej i funkcjonalnej. Przedstawione wyniki wskazują, że metody syntezy logicznej z powodzeniem mogą być zastosowane do rozwiązywania zadań eksploracji danych, skutecznie upraszczając złożoność sprzętową systemów.

EN

The article discusses the use of logical synthesis in terms of reducing the hardware complexity of data analysis systems. The methods of linear and functional decomposition are discussed. The use of attribute reduction reduces the complexity of decomposition. The presented results indicate that logical synthesis methods can be successfully used to solve data mining tasks, effectively simplifying the hardware complexity of the systems.

3

Application of Graph Theory Algorithms in Non-disjoint Functional Decomposition of Speciﬁc Boolean Functions

Mazurkiewicz Tomasz

Journal of Telecommunications and Information Technology

|

2020

|

nr 3

67--74

EN

Functional decomposition is a technique that allows to minimize Boolean functions that cannot be optimally minimized using other methods, such as variable reduction and linear decomposition. A heuristic method for ﬁnding nondisjoint decomposition has been proposed lately. In this paper, we examine how the usage of diﬀerent graph theory techniques affects the computation time and the quality of the solution obtained. In total, six dfferent approaches were analyzed. The results presented herein prove the advantages of the proposed approaches, showing that results obtained for standard benchmark M-out-of-20 functions are better than those presented in previous publication. Results obtained for randomly generated functions prove that time complexity and scalability are signiﬁcantly better when using the heuristic graph coloring algorithm. However, quality of the solution is worse, in general.

4

Synteza generatorów indeksów metodą dekompozycji liniowej

Morawski Łukasz, Łuba Tadeusz

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2019

|

nr 10

761--771

PL

Omówiono nowy algorytm syntezy generatorów indeksów, który umożliwia przeprowadzenie procedury redukcji i dekompozycji liniowej funkcji generowania indeksów. Algorytm wykonuje obliczenia dla wszystkich odnalezionych reduktów oraz niezredukowanej funkcji i odnajduje najkorzystniejsze rozwiązania zgodnie z przyjętą strategią. Wyniki przeprowadzonych eksperymentów zostały skonfrontowane z obecnie przyjętym założeniem, w którym do procedury dekompozycji liniowej stosuje się minimalno-argumentowe reprezentacje funkcji.

EN

A new method of index generation function, which allows to perform the procedure of argument reduction and linear decomposition is discussed. This tool execute calculations for all found reducts along with non-reduced function and finds most favorable result in accordance with the adopted strategy. The results of experiments were confronted with the current assumption in which representations of functions with a minimal argument set are used for the linear decomposition procedure.

5

Realizacja sprzętowego generatora indeksów z wykorzystaniem filtru Blooma

Mazurkiewicz Tomasz

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2019

|

nr 3

61--66

PL

Funkcje generowania indeksów są wykorzystywane przede wszystkim do wyszukiwania wzorców w dużych zbiorach danych. Spowodowało to znaczny wzrost zainteresowania efektywną realizacją tych funkcji w czasach dynamicznego rozwoju technologii, takich jak np. Big Data. W literaturze przedstawiono wiele algorytmów skutecznie minimalizujących tego typu funkcje. Równocześnie zaproponowano metody ich sprzętowej realizacji. W ramach niniejszej pracy przedstawiono możliwość implementacji funkcji generowania indeksów z wykorzystaniem struktury probabilistycznej - filtru Blooma. Pokazano, że kosztem wprowadzenia niewielkiego prawdopodobieństwa otrzymania wyniku fałszywie pozytywnego, możliwa jest efektywna implementacja proponowanego rozwiązania. W tym celu przedstawiono ideę filtru Blooma z pojedynczą funkcją skrótu. Uzyskane wyniki dowodzą, że opisana struktura zapewnia mniejsze wykorzystanie pamięci od rozwiązania opisywanego w literaturze. Mimo że konieczne jest zrealizowanie dodatkowych obliczeń, w pracy pokazano, że mogą być one efektywnie zrealizowane w układach FPG A.

EN

Index generation functions are primarily used for pattern matching in large data sets. Efficient implementation of these functions is attracting significant interest due to the dynamic development of technologies such as Big Data. In the literature many algorithms were presented that efficiently minimize these functions. At the same time, methods of efficient hardware implementation have been proposed. In this paper, the possibility of implementing index generation functions using the probabilistic structure, i.e. a B loom filter, was analyzed. We show that at the cost of a small probability of a false positive result, it is possible to efficiently implement the proposed method. Furthermore, the idea of an One-Hashing Bloom filter is presented. The obtained results prove that the described structure provides lower memory usage than the structure described in the literature. Even though it requires additional computations, we prove that these operations can be efficiently implemented using FPG A devices.

6

Synteza generatorów indeksów metodami dekompozycji liniowej i funkcjonalnej

Łuba T., Mazurkiewicz T.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2018

|

nr 5

122--128

PL

Metody projektowania funkcji generowania indeksów, ze względu na ważne zastosowania (dystrybucja adresów IP, skanowanie wirusów, wykrywanie niepożądanych danych), są ostatnio przedmiotem intensywnych badań naukowych. W rezultacie powstało wiele metod syntezy takich funkcji. Celem artykułu jest przegląd tych metod, ich porównanie z metodami proponowanymi przez autorów oraz wskazanie problemów, których rozwiązanie może przyczynić się do zwiększenia skuteczności metod projektowania.

EN

Methods of designing the index generation functions have recently been subject of intensive scientific research due to important applications (distribution of IP addresses, virus scanning and undesired data detection). As a result, many methods have been developed to synthesize such functions. The aim of the article is to review these methods, compare them with the methods proposed by the authors and identify issues (problems) whose solution may contribute to the effectiveness of design methods.

7

Metody wyboru dekompozycji dla algorytmu z wykorzystaniem zbiorów niezgodności i ich wpływ na minimalizację generatorów indeksów

Mazurkiewicz T., Łuba T.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2018

|

nr 8-9

722--725, CD

PL

Minimalizacja wykorzystania pamięci wydaje się kluczowym zadaniem dla efektywnej realizacji sprzętowej funkcji generowania indeksów. W tym celu stosuje się algorytmy dekompozycji liniowej. W niniejszej pracy przedstawiono nową metodę wyboru dekompozycji dla algorytmu z bramkami XOR, wykorzystującego zbiory niezgodności. Przedstawione w artykule wyniki dla koderów m z 16 i m z 20 dowodzą skuteczności proponowanej metody.

EN

Memory minimization seems to be the main problem of effective index generation functions hardware implementation. A linear decomposition can be used to reduce memory size. In this paper a new method of decomposition selection for algorithm with EXOR gates, which uses discernibility sets, is proposed. Presented results show its effectiveness for m-out-of-16 and m-out-of-20 functions.