Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: non-disjoint decomposition

Sortuj według:

Ogranicz wyniki do:

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

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.