Уточнение оценок показателей сложности схем и автоматизация их эффективного применения
https://doi.org/10.17587/mau.17.75-83
Аннотация
Исследуется задача реализации произвольной булевой функции в классе формул и схем из функциональных элементов в стандартном базисе и базисе Жегалкина. Предлагается конструктивный метод синтеза формул и схем на основе рекуррентных соотношений (функциональных уравнений), сопровождаемого получением заранее аналитических верхних оценок различных показателей сложности (по числу букв; числу подформул; по числу функциональных элементов; по глубине формулы и по глубине схемы), в том числе и для схем минимальной сложности. При необходимости уточнения верхних оценок сложности предлагается вычислительный алгоритм.
Об авторах
И. Ф. Чебурахин
МАТИ - РГТУ имени К. Э. Циолковского
Россия
Россия
О. Н. Гавриш
МАТИ - РГТУ имени К. Э. Циолковского
Россия
Россия
Список литературы
1. Журавлев Ю. И. Теоретико-множественные методы в алгебре логики // Проблемы кибернетики. 1962. № 8.
2. Кудрявцев В. Б., Гасанов Э. Э., Подколзин А. С. Введение в теорию интеллектуальных систем. М.: Изд-во ф-та ВМиК МГУ, 2006. 208 стр.
3. Лупанов О. Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики. Вып. 3. М.: Физматгиз, 1960.
4. Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики. 1959. № 2.
5. Поспелов Д. А. Логические методы анализа и синтеза схем. М.: Энергия, 1974. 342 с.
6. Теряев Е. Д., Петрин К. В., Филимонов Н. Б., Филимонов А. Б. Агентные технологии в автоматизированных информационно-управляющих системах. Часть II. Агентные решения в задачах контроля и управления // Мехатроника, автоматизация, управление. 2010. № 10. С. 11-21.
7. Цурков В. И. Декомпозиция в задачах большой размерности. М.: Наука, 1981. 324 с.
8. Чебурахин И. Ф. Синтез дискретных управляющих систем и математическое моделирование: алгоритмы, программы. М.: Физматлит, 2004. 247 с.
9. Чебурахин И. Ф. Преобразования функциональных уравнений и показатели сложности булевых функций // Матер. IX Междунар. семинара "Дискретная математика и ее приложения", посвященного 75-летию со дня рождения академика О. Б. Лупанова. М.: Изд-во МГУ, 2007. С. 126-129.
10. Чебурахин И. Ф. Математические модели для интеллектуализации синтеза дискретных логических управляющих устройств на основе цифровых интегральных схем // Изв. РАН. ТиСУ. 2008. № 1. С. 68-77.
11. Чебурахин И. Ф. Сложность симметрических полиномов Жегалкина // XVII Междунар. школа-семинар "Синтез и сложность управляющих систем" им. акад. О. Б. Лупанова. Новосибирск, 2008. С. 180-185.
12. Чебурахин И. Ф. Математические модели для минимизации и автоматизации синтеза дискретных управляющих систем // Мехатроника, автоматизация, управление. 2012. № 4. С. 5-13.
Рецензия
Для цитирования:
Чебурахин И.Ф., Гавриш О.Н. Уточнение оценок показателей сложности схем и автоматизация их эффективного применения. Мехатроника, автоматизация, управление. 2016;17(2):75-83. https://doi.org/10.17587/mau.17.75-83
For citation:
Cheburakhin I.F., Gavrish O.N. Clarification of Difficulty Indexes of Digital Circuits and Automation their Efficient Application. Mekhatronika, Avtomatizatsiya, Upravlenie. 2016;17(2):75-83. (In Russ.) https://doi.org/10.17587/mau.17.75-83
Просмотров: 416
.png)
Послать статью по эл. почте 