Метод мінімізації булевих функцій для проєктування цифрових комбінаційних схем

Abstract

Розглянуто двоетапний метод мінімізації булевих функцій для проєктування цифрових комбінаційних схем. На першому етапі здійснюють пошук простих кон’юнктермів методом побітового розбиття множини вихідних кон’юнктермів. Тавтологія не виникає, кон’юнктерми низького рангу виявляють без здійснення проміжних склеювань. На другому етапі виконується пошук мінімальної множини простих кон’юнктермів методом ланцюгового покриття таблиці простих кон’юнктермів. У циклічній частині віднаходять фрагменти ланцюгових функцій, покриття яких відбувається доволі просто. Для зменшення обчислювального навантаження в точках розгалуження ланцюгів можна прийняти рішення про входження чи вилучення відповідного простого кон’юнктерма з кінцевої множини на підставі розрахунку коефіцієнта складності в околі розгалуження. Запропонований метод є евристичним.

The article discusses a two-stage method of minimizing Boolean functions for designing digital combinational circuits. At the first stage, the search for simple conjuncterms is carried out by the method of bitwise division of the set of initial conjuncterms. At this way tautology does not appear, low-rank conjuncterms are found without intermediate gluing. At the second stage, the search for the minimal set of simple conjuncterms is performed by the method of chain coverage of the table of simple conjuncterms. In the cyclic part, fragments of chain functions are found, the coverage of which is quite simple. To reduce the computational load at branching points of chains, a decision can be made about entering or removing the corresponding simple conjuncterm from the finite set based on the calculation of the complexity factor in the vicinity of the branching. The proposed method is heuristic.