Мінімізація системи логікових функцій методом паралельного розчеплення кон'юнктермів

Abstract

A new heuristic minimization method of logic functions of n variables has been suggested. It is based on the parallel splitting of conjuncterms and differs from the known methods for it is simpler in implementation due to less computational complexity. One disadvantage of the classical method of minimization by Quine-McCluskey method and its modifications is the formation at the stage of finding prime conjuncterms some set equal conjuncterms of different ranks, whose number increases rapidly with n increasing. Such negative phenomenon as tautology of conjuncterms mainly occurs in the methods that employ adjacency and absorption laws for the formation conjuncterms lower ranks with the pairs of adjacent conjuncterms. Accordingly, to obtain the reduced SOP of a given function, it is necessary to identify and reduce excessive conjuncterms and that requires certain procedural means and time-consuming. Heuristic minimization method, based on the parallel splitting conjuncterms of a given function is devoid of tautology problem. However, this method despite its other advantages, including the formalization of simple operations and procedures that enable them to automate your computer, requires a certain time for the procedure of stepwise (sequential) splitting. In addition, this paper considers only the case of minimization of one complete (fully defined) function, which limits the scope of its practical application. This work is devoted to the development of the mentioned minimization method of logic functions and is based on a new approach – parallel splitting of conjuncterms with just one matrix splitting of conjuncterms and performance in this matrix covering procedure as one function and of full and partial (incomplete specified) functions system. The theorem on the formation in a matrix of parallel splitting with not more than 2n-1 of conjuncterms 1-rank, no more than 2n-2 of conjuncterms 2-rank, ..., not more than two of conjuncterms (n-1)-rank has been proved. The time for obtaining the searched result is reduced and the way of procedure implementation is simplified due to the suggested approach. Advantages of the method are shown by the examples taken from publications of well-known authors which illustrate their methods of minimization of full and partial (incomplete specified) logic functions system. Запропоновано новий євристичний метод мінімізації логікових функцій від n змінних на основі паралельного розчеплення кон’юнктермів, що відрізняється від відомих методів простішою реалізацією за рахунок меншої обчислювальної складності. Переваги методу проілюстровано на прикладах мінімізації системи повних і неповних (недовизначених) функцій.