Особенности автоматизации синтеза булевых функций
Авторы: Гурченков А.А., Егорова Е.К.
Опубликовано в выпуске: #12(24)/2013
DOI: 10.18698/2308-6033-2013-12-1167
Раздел: Прикладная математика
Изложен оригинальный подход к автоматическому синтезу дискретных устройств в базисе микросхем. Методические установки этого подхода основываются на математическом и информационном описаниях булевых функций и их структурно-функциональной декомпозиции. Параллельная и последовательная декомпозиции по сложности (числу подформул) характеризуются одинаковым качеством, но по глубине лучшим качеством (меньшим или равным значением) обладает первая, поэтому для синтеза схем применена параллельная декомпозиция. В частности, предложен вычислительный метод для нахождения оценок сложности реализации произвольных булевых функций в базисе Жегалкина на основе параллельной декомпозиции. Метод позволяет оценить возможность минимизации числа транзисторов и времени задержки схемы. Для алгоритма рассмотрены несколько особых случаев с примерами. На основе этих особенностей внесены дополнения в алгоритм, в результате чего алгоритм стал универсальным.
Литература
[1] Поспелов Д.А. Логические методы анализа и синтеза схем. Москва, Энергия, 1974, 342 с.
[2] Чебурахин И.Ф. Синтез дискретных управляющих систем и математическое моделирование: алгоритмы, программы. Москва, Физматлит, 2004, 247 с.
[3] Чебурахин И.Ф. Математические модели для интеллектуализации синтеза дискретных логических управляющих устройств на основе цифровых интегральных схем. Известия РАН. Теория и системы управления, 2008, № 1, с. 68-77
[4] Чебурахин И.Ф., Цурков В.И. Синтез дискретных логических устройств обработки информации на основе теории агентов. Мехатроника, автоматизация, управление, 2011, № 3, с. 27-34
[5] Егорова Е.К., Чебурахин И.Ф. О минимизации сложности и автоматизации эффективного представления булевых функций в классах формул и схем. Известия РАН. Теория и системы управления, 2013, № 3, с. 121-129
[6] Чебурахин И.Ф. Преобразования функциональных уравнений и показатели сложности булевых функций. Матер. IX Междунар. семинара "Дискретная математика и ее приложения". Москва, Изд-во МГУ, 2007, с. 126-129
[7] Чебурахин И.Ф. Сложность симметрических полиномов Жегалкина. Тр. XVII Междунар. школы-семинара "Синтез и сложность управляющих систем" им. акад. О.Б. Лупанова. Новосибирск, 2008, с. 180-185
[8] Кудрявцев В.Б., Гасанов Э.Э., Подколзин А.С. Введение в теорию интеллектуальных систем. Москва, Изд-во МГУ, 2006, 208 с.
[9] Цурков В.И. Декомпозиция в задачах большой размерности. Москва, Наука, 1981, 324 с.
[10] Чебурахин И.Ф. Математические модели для минимизации и автоматизации синтеза дискретных управляющих систем. Мехатроника, автоматизация, управление, 2012, № 4, с. 5-13