Мethod for minimization of Boolean functions with a large number of variables based on directed enumeration

Abstract

The development of computer technology directly depends on the development of methods for synthesizing components of digital computer technology, therefore the automation of the process is observed in the development of microcircuits. Boolean algebra is widely used for the synthesis of circuit models, and one of the problems in this case is the dependence of the complexity of implementing a given circuit on the number of variables of the Boolean function that implements it. Based on this, it can be argued that the increase in the number of variables in the functions that require minimization requires the search for new or improvement of existing methods of minimization of Boolean functions, which will be easy to use, descriptive and have the ability to automate the implementation of the minimization process. The task of developing effective methods of minimization of Boolean functions for simulation of circuits with linear and polynomial dependence of simulation speed on the number of variables of the implemented Boolean function remains relevant. The object of research is the process of minimization of Boolean functions, which are used in the construction of circuits of digital automata. The purpose of this work is practical implementation of the method of minimization of Boolean functions based on directed enumeration when increasing the number of variables. The objective considered in this work is to develop and implement the method of minimization of Boolean functions, which will help to minimize Boolean functions based on directed enumeration, the bitness of which exceeds ten variables, as well as to increase the efficiency of search when bonding implicants with a large uncertainty in the sets of functions. Since all existing methods of minimization face the problem of cumbersome calculations when the number of variables increases, the method of directed enumeration, which is quite effective in the case of large uncertainty in the sets, has been chosen for the study. Based on the calculations, it has been determined that this method of minimization of Boolean functions is efficient and easy to use. Its main advantage is the possibility of implementation by means of computer technology, and directed enumeration as the basis can reduce the requirements for hardware and software resources of automated design systems.

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