Wyniki wyszukiwania - BazTech

1

XOR-based decomposition and its application in memory-based and reversible logic synthesis

Mazurkiewicz Tomasz

Annals of Computer Science and Information Systems

|

2023

|

Vol. 35

183--190

EN

In this research paper, we propose a novel approach to digital circuit design using XOR-based decomposition. The proposed technique utilizes XOR gates as a fundamental building block for decomposing complex Boolean functions into simpler forms, leading to more efficient and compact digital circuits. We demonstrate the effectiveness of our approach in two different contexts: memory-based logic synthesis and reversible logic synthesis. In particular, we demonstrate that the proposed technique can efficiently reduce the number of input variables, which is a crucial task when using memories in the design. Obtained results prove that the XOR-based approach can efficiently complement variable reduction and dimensionality reduction algorithms. Furthermore, we show its application in generating the XOR-AND-XOR form of a reversible function and demonstrate how to combine it with another technique, i.e., a functional decomposition for reversible logic synthesis

2

Synteza logiczna – aktualne trendy i perspektywy

Mazurkiewicz Tomasz

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2021

|

nr 3

88--92

PL

Synteza logiczna jest gałęzią nauki, która rozwija się nieprzerwanie od kilkudziesięciu lat. Pozornie można odnieść wrażenie, że ze względu na dużą dojrzałość zaproponowanych metod w zakresie tej tematyki nie dzieje się nic nowego. Jednakże ostatnie prace, publikowane również na łamach Przeglądu Telekomunikacyjnego i Wiadomości Telekomunikacyjnych, zdają się przeczyć tej tezie. W artykule przedstawiono najważniejsze – zdaniem autora – kierunki rozwoju metod syntezy logicznej. Wskazano również technologie, których rozwój w najbliższych latach najbardziej może przyczynić się do wzmożonego zainteresowania opracowaniem nowatorskich metod.

EN

Logic synthesis is a branch of science that has been developing for several decades. It is possible to get the impression that nothing new is happening in this field due to the high maturity of the already proposed methods. However, recent works, also published in this journal, seem to contradict this thesis. This article presents the most interesting directions (in the author's opinion) in the development of logic synthesis methods. Moreover, the technologies, which progress in the coming years may contribute most to the increased interest in this field, are indicated.

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

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.

5

Dekompozycja funkcjonalna w syntezie funkcji generowania indeksów

Łuba Tadeusz, Mazurkiewicz Tomasz

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2019

|

nr 1

19--25

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.