Preview

Мехатроника, автоматизация, управление

Расширенный поиск

Уточнение оценок показателей сложности схем и автоматизация их эффективного применения

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

Просмотров: 16


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1684-6427 (Print)
ISSN 2619-1253 (Online)