МЕТОД МИНИМИЗАЦИИ СИСТЕМЫ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ
Аннотация
Рассматривается задача минимизации системы дизъюнктивных нормальных форм (ДНФ) произвольного вида, заданной в матричной форме. Критерием минимизации является общее число различных элементарных конъюнкций в получаемой системе ДНФ. Предлагается оригинальный способ сведения данной задачи к задаче о кратчайшем покрытии, основанный на простой операции пересечения множеств. Приводятся результаты испытаний компьютерной программы.
Об авторах
Ю. В. Поттосин
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Н. Р. Торопов
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Е. А. Шестаков
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Список литературы
1. Глушков, В.М. Синтез цифровых автоматов / В.М. Глушков. – М.: ГИФМЛ, 1962. – 476 с.
2. Закревский, А.Д. Логический синтез каскадных схем / А.Д. Закревский. – М.: Наука, 1981. – 416 с.
3. Шестаков, Е.А. Декомпозиция системы полностью определенных булевых функций по покрытию аргументов / Е.А. Шестаков // Автоматика и вычислительная техника. – 1994. – № 1. – С. 12–20.
4. Brzozowski, J.A. Decomposition of Boolean functions specified by cubes. Research Report CS-97-01 / J.A. Brzozowski, J.J. Lou. – Waterloo, ON, Canada: Department of Computer Science, University of Waterloo, 1997. – 36 p.
5. Поттосин, Ю.В. Декомпозиция систем полностью определенных булевых функций по их заданию в виде компактных таблиц / Ю.В. Поттосин, Е.А. Шестаков // Информатика. – 2004. – № 2. – С. 35–44.
6. Поттосин, Ю.В. Поиск существенных аргументов системы полностью определенных булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Методы логического проектирования.– Минск: ОИПИ НАН Беларуси, 2003. – Вып. 2. – С. 69–78.
7. Поттосин, Ю.В. Ортогонализация системы полностью определенных булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 2000. – Вып. 5.– С. 107–115.
8. Фридман, А. Теория и проектирование переключательных схем / А. Фридман, П. Менон. – М.: Мир, 1978. – 580 с.
9. Миллер, Р. Теория переключательных схем. Т. I / Р. Миллер. – М.: Наука, 1970. – 416 с.
10. Yang, S. Logic Synthesis and Optimization Benchmarks. User Guide: Version 3.0. Technical Report / S. Yang. – Microelectronics of North Carolina, 1991. – 43 p.
11. Романов, В.И. Программные средства для решения логико-комбинаторных задач / В.И. Романов // Информатика. – 2005. – № 4 (8). – С. 114–123.
12. Торопов, Н. Р. Минимизация систем булевых функций в классе ДНФ / Н. Р. Торопов // Логическое проектирование. – Минск: Ин-т техн. кибернетики НАН Беларуси, 1999. – Вып. 4. – С. 4–19.
13. Закревский, А.Д. Основы логического проектирования: в 3 кн. Кн. 2. Оптимизация в булевом пространстве / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – Минск: ОИПИ НАН Беларуси, 2004. – 240 с.
Рецензия
Для цитирования:
Поттосин Ю.В., Торопов Н.Р., Шестаков Е.А. МЕТОД МИНИМИЗАЦИИ СИСТЕМЫ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ. Информатика. 2008;(2(18)):102-110.
Просмотров: 479
Послать статью по эл. почте 