МЕТОД МІНІМІЗАЦІЇ БУЛЕВИХ ФУНКЦІЙ З ВЕЛИКОЮ КІЛЬКІСТЮ ЗМІННИХ НА ОСНОВІ НАПРАВЛЕНОГО ПЕРЕБОРУ

Анотація

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