МЕТОД МИНИМИЗАЦИИ СИСТЕМЫ НЕ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ
Аннотация
Рассматривается задача минимизации системы не полностью определенных булевых функций в классе дизъюнктивных нормальных форм (ДНФ) при задании исходной системы функций в интервальной форме. Критерием минимизации является общее число различных элементарных конъюнкций в получаемой системе ДНФ. Предлагается метод решения данной задачи, который представляет собой обобщение предложенного авторами ранее метода минимизации системы полностью определенных булевых функций. В основе метода лежит оригинальный способ сведения данной задачи к задаче о кратчайшем покрытии, использующий простую операцию пересечения множеств. Приводятся результаты испытаний компьютерной программы, реализующей предлагаемый метод.
Об авторах
Ю. В. Поттосин
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Н. Р. Торопов
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Е. А. Шестаков
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Список литературы
1. Поттосин, Ю.В. Метод минимизации системы полностью определенных булевых функций / Ю.В. Поттосин, Н.Р. Торопов, Е.А. Шестаков // Информатика. – 2008. – № 2 (18). – С. 102–110.
2. Торопов, Н.Р. Минимизация систем булевых функций в классе ДНФ / Н. Р. Торопов // Логическое проектирование. – Минск : Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 4–19.
3. Шестаков, Е.А. Декомпозиция системы полностью определенных булевых функций по покрытию аргументов / Е.А. Шестаков // Автоматика и вычислительная техника. – 1994. – № 1. – С. 12–20.
4. Фридман, А. Теория и проектирование переключательных схем / А. Фридман, П. Менон. – М. : Мир, 1978. – 580 с.
5. Закревский, А.Д. Логический синтез каскадных схем / А.Д. Закревский. – М. : Наука, 1981. – 416 с.
6. Закревский, А.Д. Логические основы проектирования дискретных устройств / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.
7. Yang, S. Logic Synthesis and Optimization Benchmarks. User Guide: Version 3.0 / S. Yang. – Technical Report, Microelectronics of North Carolina. – USA, 1991. – 43 p.
Рецензия
Для цитирования:
Поттосин Ю.В., Торопов Н.Р., Шестаков Е.А. МЕТОД МИНИМИЗАЦИИ СИСТЕМЫ НЕ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ. Информатика. 2009;(3(23)):16-26.
Просмотров: 877
Послать статью по эл. почте 