автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математическое моделирование и синтез вычислительных и управляющих логических устройств

Направахрукописи

Чебурахни Игорь Федорович

МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ И СИНТЕЗ ВЫЧИСЛИТЕЛЬНЫХ И УПРАВЛЯЮЩИХ ЛОГИЧЕСКИХУСТРОЙСТВ

Специальность:

05.13.18 -Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Москва 2004

Работа выполнена в «МАТИ» - Российском государственном технологическом университете им. К.Э. Циолковского

Официальные оппоненты:

доктор технических наук, профессор

Л.Н. АЛЕКСАНДРОВСКАЯ доктор технических наук, профессор

В.А. ДЕМЕНТЬЕВ доктор технических наук, профессор А.Б. БАРСКИЙ

Ведущая организация:

Федеральное государственное унитарное предприятие "Научно-производственный центр автоматики н приборостроения им. академика Н.А. Пилюгина"

Защита состоится 16 июня 2004 г. в _час. на заседании диссертационного совета Д 212.110.06 в «МАТИ» - Российском государственном технологическом университете им_ К.Э. Циолковского по адресу: 119111 Москва, Оршанская ул., д. 3 (аудитория '

С диссертацией можно ознакомиться в библиотеке «МАТИ» - Российском государственном технологическом университете им. К.Э. Циолковского.

Автореферат разослан « » мая 2004 г.

Ученый секретарь 'у ,

диссертационного совета У!/!/'.''^

доктор технических наук, профессор Марсова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Системы автоматического управления сложнейшими объектами и процессами, интеллектуальные пакеты прикладных программ, системы планирования вычислений, системы автоматизированного проектирования - вот далеко не полный перечень аппаратных и программных систем, без которых немыслим сейчас научно-технический прогресс. Основная черта, выделяющая эти системы из всех остальных, состоит в том, что они содержат знания о той проблемной области, в которой работают, и о своих возможностях по решению задач в ней.

Особое место в указанном списке занимают вычислительные системы, включая бортовые и другие специализированные ЦЭВМ. Взаимоотношения выше перечисленных систем с вычислительной техникой имеют две различные стороны: ЭВМ является основным инструментом исследований, включая моделирование, и будучи сами сложными системами, выступают важными объектами исследований.

В значительной мере для описания, анализа и проектирования этих систем (устройств) используется аппарат математической кибернетики, из которого в диссертации, в основном, делается акцент на: формулы алгебры логики, схемы из функциональных элементов, конечные автоматы и программы (алгоритмы). Этот математический аппарат является мощным средством для моделирования, при котором достаточно точно копируется не только функция объекта (процесса), но также и его структура, схема.

Проектирование таких систем в настоящее время характеризуется широким использованием достижений микроэлектроники. Элементной базой для синтеза вычислительных и логических управляющих устройств рассматриваемых систем являются интегральные схемы малой, средней, большой, сверхбольшой и ультрабольшой степени интеграции (МИС, СИС, БИС, СБИС, УБИС). Стремительное развитие микроэлектроники, проявляющееся в постоянном совершенствовании и в создании новых элементов базиса, содержащего микросхемы различной степени интеграции, с одной стороны, создает благоприятные предпосылки для разработки новых высокопроизводительных вычислительных и управляющих систем с высокой степенью параллелизма обработки данных, а с другой стороны, ставит ряд трудно решаемых проблем перед разработчиками этой техники.

В практике все шире применяются БИС, СБИС и УБИС, что объясняется их возможностями и технико-экономическими характеристиками. Но чтобы не принять необоснованную позицию в отношении использования этих интегральных схем в проектировании вычислительных и управляющих логических устройств, отметим мнение американского специалиста S.Muroga в монографии, посвященной проектированию БИС и СБИС: "...В некотерых— случаях при создании цифровых систем предпочтитель-

ное. НАЦИОНАЛЬНАЯ ПСЛСОТСКЛ

нее использовать схемы малой и средней степени интеграции, а не большой и сверхбольшой".

Таким образом, приходим к задачам аппаратной реализации булевых функций, т.е. к задачам синтеза функционально-логических схем в заданных базисах. Ситуацию, сложившуюся в этой области, можно охарактеризовать тем, что нет способов приемлемой трудоемкости, позволяющих оптимальным образом синтезировать каждую схему. Причиной этому является возрастающая сложность (площадь кристалла, глубина схемы, число логических элементов, суммарная длина проводников между БИС и между элементами и другие показатели качества) проектируемых систем.

Метод решения, реализующий сложность, является в некотором смысле наилучшим, наиболее экономным, наиболее простым из методов, решающих все задачи рассматриваемого класса, причем оптимизация решения на этапе организации проектирования экономит время и средства.

Быстродействие (составляющая производительности) является одной из тех важнейших характеристик, которые служат для сравнения и выбора той или иной ЭВМ. Повышение быстродействия достигается разными средствами: в отношении методов характерно появление значительного числа работ, посвященных методам синтеза и оптимизации многоуровневой комбинационной логики; для технических средств наблюдается обоснованный интерес к использованию оптических элементов, реализующих функции И, ИЛИ, НЕ-И или НЕ-ИЛИ, для синтеза комбинационных схем. При проектировании БИС невозможно скомпенсировать на более поздних этапах дефекты, которые были допущены на ранних этапах, т.е. проблему быстродействия необходимо решать на всех уровнях проектирования.

Наряду с оптимизацией решения необходимо рассматривать трудоемкость решения дискретных экстремальных задач. Трудоемкость их решения астрономически растет с размерностью этих задач, что негативно сказывается на качестве решения. Поэтому необходимо раньше вводить и тщательно изучать показатели, характеризующие качество решения.

Цель работы: создание фундаментальных основ и использование математического моделирования для решения проблемы реализации (экономной по различным показателям качества и по трудоемкости) системы булевых функций в различных базисах, состоящих из микросхем степени интеграции от малой до сверхбольшой, разработка и исследование математических моделей синтеза вычислительных и управляющих логических устройств, а также решение актуальных теоретико-прикладных задач в робототехнике (разработки управляющего автомата для циклового манипулятора) и авиационной области (обеспечения безопасности движения летательных аппаратов) на основе разработки цифровых автоматов в базисе микросхем.

Область исследования: разработка, исследование и обоснование математических моделей синтеза вычислительных и управляющих логиче-

ских устройств; разработка, обоснование и тестирование эффективных численных методов, используемых при аппаратной реализации систем булевых функций с применением ЭВМ. Достижение цели работы обеспечивается решением ряда проблем и задач.

1. Разработка и анализ оригинальных математических моделей вычислительных и управляющих логических устройств; исследование этих моделей с целью выявления в них свойств (сложности и глубины), одинаковых для классов булевых функций, используемых для оптимизации синтеза этих устройств в базисе микросхем различной степени интеграции.

2. Разработка методов декомпозиции булевых функций и соответственно для них функционалов - показателей качества (по числу подформул и глубине) декомпозиции с целью использования их при синтезе логических устройств в базисе микросхем.

3. Исследование множества булевых функций в различных базисах с целью их экономного представления и установления зависимости между сложностью булевых формул и их минимальной глубиной, необходимого для минимизации (по сложности и глубине) логических схем.

4. Разработка методов оптимального или близкого к нему (по сложности, быстродействию, а также трудоемкости) синтеза вычислительных и управляющих логических устройств в базисе микросхем различной степени интеграции на основе математического моделирования.

5. Разработка программ для ЭВМ с целью проведения машинных экспериментов, подтверждающих состоятельность и эффективность проведенных исследований, разработанных методов и алгоритмов.

6. Применение разработанных методов в решении актуальных теоретико-прикладных задач в робототехнике (разработка управляющего автомата для циклового манипулятора) и авиационной области (разработка аппаратуры для обеспечения безопасности движения летательных аппаратов) на основе проектирования цифровых конечных автоматов.

Используемые модели и методы: теория множеств, комбинаторика, отношения; теория чисел и теоретико-числовые функции; теория булевых функций; теория графов; теория конечных автоматов; теория алгоритмов и сложности; общая и математическая теория систем; схемотехника; теоретическая механика.

Научная новизна. В диссертации можно выделить два фундаментальных понятия общей теории систем - это структура (строение) и декомпозиция, благодаря которым в определенных рамках получено решение проблемы оптимальной или близкой к ней (по числу транзисторов, логических элементов, микросхем; глубине и др.) реализации булевых функций в базисе микросхем. Использовались модификации этих понятий. Благодаря этому впервые получены следующие основные результаты. 1. Разработана оригинальная многоуровневая модель математико-информационного (компьютерного) представления булевых бесповторных

и произвольных функций (на основе понятия строение таких формул, как полином Жегалкина, ДНФ, КНФ и другие) в заданном базисе, позволяющая решать все важнейшие задачи оптимизации синтеза.

2. Определены оригинальные методы параллельной и последовательной декомпозиции булевых функций на основе их строения как многошаговые процессы и соответственно для них функционалы - показатели качества (по числу подформул и глубине) декомпозиции с целью применения при оптимизации синтеза логических устройств в базисе микросхем.

3. Впервые разработаны математические модели и методы (на основе декомпозиции) многокритериального оптимального (по сложности и/или быстродействию и чувствительности к отказам типа разрыв) синтеза вычислительных и управляющих логических устройств для отдельных классов (простых, бесповторных и порожденных) булевых функций в базисе микросхем различной степени интеграции, причем значения показателей качества такого синтеза получены аналитически.

4. Впервые проведено исследование множества всех булевых функций в некоторых базисах с целью получения глубины, а также с целью установления зависимости между сложностью булевых формул и их минимальной глубиной; определен подход к разбиению множества всех булевых функций на классы функций одной глубины.

5. Для базовой модели (формул, длины равной двум) различных общих классов формул получены условия для проведения многокритериальной (по сложности и глубине-быстродействию) минимизации логических схем.

6. Разработаны оригинальные алгоритмы для моделирования параллельной декомпозиции булевой функции на основе функционалов качества, раздельной или совместной параллельной декомпозиции системы булевых функций в различных базисах, при этом впервые минимизируется число логических элементов и/или глубина схемы.

7. Разработаны впервые методы синтеза логических схем в базисе микросхем различной степени интеграции на основе структурно-функциональной декомпозиции, позволяющие в зависимости от параметров исходного описания задачи заранее оценивать качество синтеза по числу транзисторов, логических элементов, микросхем и глубине. Методы эффективны по этим показателям качества с ограниченной трудоемкостью.

8. Предложен принцип геометрического кодирования для оптимизации логического управления цикловым манипулятором, реализованного аппарат-но на основе цифрового автомата.

9. Принципиально разработан основной цифровой автомат, предназначенный для обеспечения безопасности движения в пространстве по пересекающимся или близко расположенным траекториями двух летательных аппаратов, основывающийся на новых дискретных математических моделях движения и оптимальном принципе разведения; в качестве примера в базисе микросхем синтезирован автомат моделирования движения таких

летательных аппаратов с целью принятия решения по их оптимальному разведению.

Практическая ценность и реализация результатов. Полученные в диссертации теоретические результаты ориентированы на проектирование быстродействующих вычислительных и управляющих логических устройств на основе микросхем различной степени интеграции, а также - интеллектуальных систем автоматизированного их проектирования. При этом предлагается аппарат, который позволяет заранее, не синтезируя самого устройства, давать оценку возможности синтеза для различных показателей качества в зависимости от исходных данных.

Результаты диссертации использованы при выполнении Государственного Контракта с Росавиакосмосом от 13.03.2002 г. по НИР "Целеста-2", а также в разработках научно-исследовательских институтов: ФГУП "Центральный научно-исследовательский институт машиностроения"; ЗАО "Гражданские самолеты Сухого"; при чтении учебных курсов по дисциплинам "Дискретная математика", "Схемотехника" и "Теория конечных автоматов" студентам кафедры "Кибернетика" МАТИ-РГТУ им. К.Э. Циолковского.

Апробация работы. Основные теоретические и практические результаты диссертации докладывались и обсуждались на:

Конференциях и семинарах России: Международная научно-техн. конф. "Актуальные проблемы фундаментальных наук" (СССР, Москва, МГТУ им.Н.Э.Баумана; 1991); International Aerospace Congress: Theory, Applications, Technologies "- IAC'94 ( Moscow, Russia, 1994); 1-й Межд. симпозиум "Интеллектуальные системы 94" ("IN-TELS'94") (Россия, Дагестан, г.Махачкала, 1994); 2-я Межд. научно-техн. конф. "Актуальные проблемы фундаментальных наук" (Москва, МГТУ им.Н.Э.Баумана, 1994); Межд. конф. по инженерному образованию (UNESCO, ICEE'95) (Россия, Москва, 1995); 9th International Conference "Systems for Automation of Engineering and Research (SAER '95)" (Bulgaria, Sofia, Vama, 1995); 5-й Межгосударственный семинар "Дискретная математика и ее приложения", посвященный 70-летию чл-корр. РАН СВ. Яблонского (Москва, МГУ, 1995); 2-й Межд. симпозиум "Интеллектуальные системы 96" (Россия, С-Петербург, МГТУ им.Н.Э.Баумана, 1996); Второй Межд. аэрокосмический конгресс IAC97 (Россия, Москва, 1997); Межд. конф. по инженерному образованию (UNESCO, ICEE'97) (Россия, С-Петербург, 1997); Ш Межд.конф. "Дискретные модели в теории управляющих систем" (Москва, МГУ, 1998); Межд. научно-техн. конф. МНТК-98 "Системы и комплексы автоматического управления в космонавтике и народном хозяйстве, посвященная 90-летию со дня рождения академика Н.А.Пилюгина" (Москва, 1998); 3-й Международный симпозиум "Интеллектуальные системы" (INTELS'98) (Россия, Псков, МГТУ им. Н.Э. Баумана, 1998); 6-й межгосударственный семинар "Дискретная математика и

ее приложения" (Москва, МГУ, 1998); XII Международная конференция "Проблемы теоретической кибернетики" (Нижний Новгород, 1999); IV Межд.конф. "Дискретные модели в теории управляющих систем" ( Москва, МГУ, 2000); Третий Международный аэрокосмический конгресс ]АС2000 (Россия, Москва, 2000); 1 -я Всероссийская конференция "Спектральные методы обработки информации в научных исследованиях" ("СПЕКТР - 2000") (Институт математических проблем биологии РАН, г.Пущино, 2000); VII Международный семинар "Дискретная математика и ее приложения" (Москва, МГУ, 2001); Межд. научно-техн.конф., посвященная 30-летию со дня основания МГТУ ГА "Гражданская авиация на рубеже веков" ( Москва, 2001); Межд.научной конф. " Информационные технологии в естественных науках, экономике и образовании" (Саратов -Энгельс, 2002); 5-ый Международный симпозиум "Интеллектуальные системы INTELS'2002" (Москва, МГТУ им.Н.Э.Баумана, 2002); 4-й Международный аэрокосмический конгресс IAC2003. Посвящается 100-летию авиации (Россия, Москва, 2003) и другие.

Семинары: МГУ им. М.В.Ломоносова, МГТУ им. Н.Э.Баумана, МАТИ-РГТУ им. К.Э. Циолковского.

Публикации. По теме диссертации опубликовано самостоятельно и в соавторстве свыше 60 работ, включая две монографии и 8 работ, опубликованных в центральных и зарубежных изданиях. Опубликованные материалы отражают основное содержание диссертации.

Структура и объем работы. Диссертация состоит из введения, одиннадцати глав, заключения, списка литературы (329 наименований) и трех приложений/Объем работы 323 страницы, включая 33 рисунка. Основное содержание имеет объем 296 страниц.

Достоверность полученных результатов обеспечивается применением строгих математических методов при их доказательстве и проведением всего исследования на математическом уровне строгости.

Все научные результаты, которые выносятся на защиту, получены полностью автором.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснованы актуальность синтеза вычислительных и управляющих логических устройств, выбор областей и направления исследований, приведены основные положения диссертационной работы.

В первой главе рассматриваются математические модели вычислительных и управляющих логических устройств: формулы алгебры логики (схемы из функциональных элементов), реализующие булевы функции в данном базисе; конечные автоматы, реализующие преобразования входных последовательностей в выходные; программы (алгоритмы), вычисляющие заданные формулы по исходным данным, а также проблемы, возникающие

при реализации булевых функций в различных базисах. Исследования по этим проблемам начались уже с изучения дизъюнктивных нормальных форм - ДНФ булевых функций, при этом авторами отмечаются алгоритмические трудности, возникающие при минимизации, анализе числовых характеристик булевых функций, классификации булевых функций и др. Итоги первых результатов в этой области в нашей стране подвел С.В.Яблонский, который систематизировал основные понятия и дал обзор методов минимизации, известных к тому времени. Существенным вкладом в математическую теорию ДНФ явились работы Ю.И. Журавлева, Ю.Л.Васильева, В.В. Глаголева и других математиков. Техническое направление, связанное с применением ДНФ в вычислительной и управляющей технике, развивалось под влиянием работ В.И. Шестакова, М.А. Гав-рилова, Д.А. Закревского, Д.А. Поспелова и др.

Задача минимизации, будучи частным случаем задачи синтеза дискретных управляющих систем, несет в себе характерные черты экстремальных задач и является удобной моделью для изучения трудностей, возникающих при их решении. Известное, тривиальное с классической точки зрения алгоритмическое решение (связанное с перебором), состоящее в построении конечного числа ДНФ и выборе среди них минимальной, недопустимо в связи с большим объемом вычислений.

Наличие в теории булевых функций трудных и недостаточно разработанных проблем по представлению булевых функций формулами отмечается и в настоящее время (Перязев Н.А. Существование и сложность представлений булевых функций формулами // Автореферат дисс. на со-иск. ученой степени д.ф.-м.н. Иркутск, 1998. 24 с,- Винокуров С.Ф. Операторы в полиномиальных представлениях булевых функций // Автореферат дисс. на соиск. ученой степени д.ф.-м.н. Иркутск. 2001. 27 с).

В классической постановке задача синтеза схемы из функциональных (логических) элементов означает получение схемы, содержащей минимальное число элементов из заданного базиса (Д.А. Поспелов). Дальнейшее развитие теории структурного синтеза привело к постановке неклассических задач синтеза с дополнительными ограничениями на структуру получаемой схемы (А.П. Горяшко). Основной проблемой синтеза является получение оптимальной в определенном заранее смысле схемы из класса схем, задаваемых системой ограничений. По своей математической природе задача оптимального структурного синтеза является целочисленной задачей математического программирования, характеризующейся невозможностью получения решения гарантированного качества за приемлемое время, когда размерность задачи не является малой или число ограничений велико. Поэтому точное решение задачи структурного синтеза практически недоступно.

В связи с этим разрабатываются различные подходы к разработке алгоритмов синтеза, заметно отличающихся по трудоемкости от переборных.

в том числе асимптотический подход, основывающийся на функции Шеннона. Здесь О.Б. Лупанов первым разработал метод и получил асимптотическую оценку числа элементов схемы, реализующей булеву функцию. Затем развивая метод, асимптотическую оценку для глубины схемы получил А.Б. Угольников. Зависимость между минимальными значениями глубины и сложности эквивалентных формул изучалась В.М. Храпченко и САЛожкиным, при этом они получили важные неравенства. С.А. Ложкиным получена также уточненная верхняя оценка для глубины булевой функции,

В главе изложен аппарат, применяемый к исследованию надежности монотонной системы в зависимости от надежности ее элементов, а также сформулированы задачи исследования.

Во второй главе определяются экстремальные методы декомпози-цин, применяемые при синтезе логических схем, и их показатели качества. Пусть А={.*/,.- множество булевых переменных, /(X) - булева функция, зависящая от п переменных (обозначаемая иногда Пусть

С = {go = 0, g¡ = 1, ggj¡Пt^^} - функционально полная система булевых функций (возможно, она избыточна). Считаем, что каждой базисной функции сопоставлено неотрицательное число /, - ее "вес".

Определим методы параллельной ("от аргументов") и последовательной ("от функции") декомпозиции и один их частный и важный случай. Тривиальной декомпозицией булевой функции /(X) в базисе С7 назовем представление ее в виде равной функции, т.е.

множество констант (это означает введение фиктивных переменных). Первым шагом последовательной декомпозиции функции /(X) в базисе б называется представление ее в суперпозицию функцийу},...,/* и gl, причем

/(Х) = 8,(Х,и гиС),г,=/,(Х2).....2к=Гк(Хм), (2-1)

где ; С - множество констант; внешняя функция суперпозиции gf еб;//...../( - остаточные функции.

Первым шагом параллельной декомпозиции функции /(X) в базисе О называется представление ее в суперпозицию функций gl и /}, причем

Г(Х) = /,(Х2и{т,}). :,=ё1(Х,^С). (2.2)

где X = X/ иХ2; С - множество к о н с т а^н6^?;в //еш н я я , остаточная функция суперпозиции. Обозначаем через /,£) число букв формулы /, которые при декомпозиции используются в записи формулы g. Под шагом последовательной или параллельной декомпозиции функции / в базисе б (в частности, и для тривиальной декомпозиции) будем подразумевать: 1) выбор функции gl еб; 2) преобразование функции /(X) в суперпозицию (2.1) или (2.2). Если базис О избыточен, то имеется несколько альтернатив выбора базисной функции В общем случае, для выбранной функции преобразование (применение конструктивной опе-

ю

рации) функции f(X) в суперпозицию функций можно выполнять многими способами (способы разъясняются в п. 5 ). С целью минимизации

сложности и глубины суперпозиционной формулы F для первого шага декомпозиции функции f(X) в ы б и р а и такой с п о аи^ОДд л я

которых достигается максимум функции f,g, ), т.е. решается задача

ma.xL'K(f,gj,Wj), g^G,Wj&W. (2.3)

Можно сказать, что это и есть сама сложность в решении рассматриваемых задач, но это не так. Условие (2.3) рассматривается для различных классов булевых функций и в конкретных случаях принимает простой вид (исключая перебор). Оно применяется на каждом шаге декомпозиции функции/ или остаточных функций и на структурном уровне отсекает значительное множество способов декомпозиции, существенно уменьшая объем вычислений и играя важную роль для минимизации обоих показателей сложности декомпозиции.

Прпменяя шаги декомпозиции к остаточным функциям, выполняем полную s-шаговую декомпозицию функции f(X) в базисе G. получая формулу F. Результат (качество) декомпозиции оценивается в терминах функционалов: сложности число подформул в формуле глубины Depf(f,g,w)- глубина формулы F; lp(f,g,w) - сумма (или произведение) весов I, базисных функций g„ входящих в формулу F, где 8 = (Si,'—Sij еС, и w — {wlt.....wf. е!Г. Для этих показателей

будем использовать еще обозначения Lf- И Depr или их варианты. Глубина функции над базисом понимается как минимальная глубина формулы среди всех формул, реализующих функцию.

На основании определения полной декомпозиции получаем следовательно, возникает задача: для данных (или

G) из выделенных классов определить наименьшее s или, по крайней мере, выразить через исходные данные.

В третьей главе определяется математико-информационное многоуровневое описание булевых функций и формул, играющее важнейшую роль при их упорядочивании, классификации булевых функций по классам функций одной сложности и при оптимизации синтеза цифровых схем. Основу математико-информационного описания булевых функций составляет строение формул типа монотонной ДНФ flX)-KiV ...\/Кт или полинома Жегалкина /(X)=Ki@...@Km , где К, - монотонная элементарная конъюнкция ранга г, И т - длина формулы f, определяемое как вектор рангов /•=(/-/,...; г,,,).' Тогда первый уровень описания булевой формулы/есть строение г и список букв формулы. Аналогично определяется строение г конъюнктивной нормальной формы (КНФ) булевой функции f и других формул этого типа. Строением формулы /, представляющей функцию из класса & (v, ©• или назовем число ее аргументов, т.е. число п

(строение - вектор рангов вырождается в число). Формулу f строения r=(ri,...,r„J назовем канонической, если Г/...>гш. Базисную формулу g всегда считаем канонической. В полное математико-информационное описание булевой формулы (другие уровни) входят специальные матрицы, учитывающие при необходимости отрицание и повторяемость переменных.. Заметим, что для функционалов качества Lp (f G) и Deppif, G) основную роль играет строение формулы.

Пусть векторы рангов бесповторных формул fug одного типа есть соответственно г = (rt.....r„J и q = (qi,...,qm). Вектору меньшей длины приписываем справа такое число нулей, чтобы их длины стали равными (формулы не меняются). На множестве канонических бесповторных формул введем определения. Считаем, что формулы (функции) / и g имеют одно и то же строение, если г, = q, ; формула (функци/)не сложнее (проще) формулы (функции) g, если г, < q, (г, < q, хотя бы для одного i при равенстве при остальных) i = 1, ..., т . Аналогично вводятся отношения не проще и сложнее, а также несравнимы. Возможно сравнение формул с повторением переменных. Иногда полезно сравнивать формулы, представляющие одну функцию в разных базисах на основе соответст-вуюших строений.

Лемма 3.1. Схема S, реализующая функцию f реализует каждую функцию h, которая не сложнее функции f {на входы возможна подача const).

С целью расширения класса функций, реализуемых одновременно с данной функцией /(на основе леммы 3.1), вводятся понятия порождающей и порожденной (не сложнее) формулы. В зависимости от длины формулы подсчитывается мощность таких классов

Для проведения декомпозиции аналитически введем конструктивные операции над формулами. Они используются для приведения данной формулы f к одному строению с базисной формулой g (при декомпозиции): перестановка элементарных конъюнкций (дизъюнкций) в формуле, а в ней переменных; замена подформулы новой переменной; переименование и отождествление в формуле переменных; подстановка в формуле вместо переменных констант; вынесение общих множителей за скобки и обратные им операции.

В четвертой главе для методов параллельной и последовательной декомпозиции на основе строения функции из простых классов

разработаны алгоритмы декомпозиции, позволяющие для этих классов функций минимизировать (по сложности и глубине) синтез логических схем. Декомпозицию функции на основе строения назовем структурно-функциональной декомпозицией. Пусть функции fug задаются формулами j[X)=.Xt-...-x„, п>2, и g = g<n ) = ■=tt-...-tn-, п'>2. Используя (2.2) и условие (2.3) оптимизации, получим алгоритм параллельной декомпозиции функции f в базисе G—{I,g}. Если

п < п', то этот случай относится к тривиальной (ояношаговой) декомпозиции. Если п>п', то выполнение шагов полной 8-шаговой параллельной декомпозиции представим в виде рекуррентной процедуры для /-го шага:

(4.1)

где Х0 = X = {х,.....х„ }, /0 = f, X, - п'- условие оптимизации, .т„4.,= ¿{X,' )

и для 5-го шага остается подфункция Х!_!), где 2 < < п\

На уровне теоретико-множественных понятий (4.1) дает рекуррентную процедуру вычитания и объединения множеств

с начальными условиями Хо - X, X/ ={х:/,....хп-}, п >н', и условием (2.3)

.V, \Х( =л'. 1 = 1......ч-1.

(4.3)

(4.4)

и выполняемой до тех пор, пока не будет получено неравенство

Далее выполняется шаг - тривиальная декомпозиция.

Рассматривая алгебраические вопросы, получаем процедуру (4.5) (изоморфную (4.2)) относительно мощности рассматриваемых множеств

Соотношения (4.5) позволяют установить для 5 - числа подформул в получаемой формуле Ж арифметический эквивалент "деления с остатком" в множестве натуральных чисел, т.е.

с тем лишь отличием, что здесь допускается "остатку" быть на

единицу больше "делителя" (п'—1), что соответствует условию (4.4). Из уравнения (4.6) находим 5, т.е. выражение для функционала сложности параллельной декомпозиции,

Г" П (4.7)

где М наименьшее целое, не меньшее числа х.

В алгоритме (4.2) на каждом шаге вычитается множество максимальной мощности (алгоритм является градиентным) и, следовательно, таких шагов, т.е. 8, будет минимально, которое находится при решении уравнения (4.6), из чего следует теорема.

Теорема 4.1. При параллельной декомпозиции функции f=f в ба-

зисе (?-{1, g1" *} минимальная сложность L имеет вид

'п-1'

п'-1

(4.8)

Функционал для глубины суперпозиционной формулы F определяется на основе следующих взаимосвязанных теорем.

Теорема 4 2. Если / = /<"', % = п > 2, и п = (п/, кеЫ,то

При доказательстве используется индукция по к,

дерево формулы Р . Теорема 4.3. Если < п <(п')к ,к е N. то существует парал-

лельная декомпозиция функции / = в базисе С^^}, такая что минимальная глубина формулы /% равна числу к.

Доказательство основывается на разбиении числа п на слагаемые, из которых первое, большее по значению, соответствует теореме 4.2, и аналогичном разбиении (по мощности) множества переменных в формуле.

Теорема 4.4. Минимальная глубина суперпозиционной формулы Г в базисе й = ¿п )}, п'^2, получаемая при параллельной декомпозиции

функции / = /<п> (п>2), есть

ОерГ(Г,в.*КТ'= Г^«] (4-9)

Доказательство. Но теореме 4.3 параллельная декомпозиция функции / в базисе С существует и Оерр(/.,£?> - к. Для получения выраже-

ния для функционала Оерр(/)т\п решаем двойное неравенство (п')к~' < п < (п'/, к € Л', относительно к.

Аналогично определяются алгоритм последовательной декомпозиции и соответствующие выражения для функционалов качества:

Lf(n,n',w)™med ~DepF(n,n'.w),

послед 'шах

п-1 п'-1

(4.10)

Из результатов (4.8)-(4.10) следует, что параллельная декомпозиция функции/ предпочтительнее по сравнению с последовательной декомпозицией в отношении глубины Depr суперпозиционной формулы F.

Особо отметим, что (в данной главе и последующих главах) функционалы L и Dep качества декомпозиции (синтеза схемы) выражаются через параметры исходного описания функции и базиса.

В пятой главе разрабатывается метод параллельной структурно-функциональной декомпозиции произвольной булевой функции /, задаваемой полиномом Жегалкина (ДНФ, КНФ или др.) строения г в базисе

состоящем из одной соответствующей функции предоставляющий средства, которые позволяет заранее, не проводя самой

декомпозиции, давать оценку результата предстоящей декомпозиции для различных показателей качества (сложности и глубины) в зависимости от исходных данных г и q. С этой целью на основе определения (2.2), сравнения формул / И g, конструктивных операций над f предлагается алгоритм Ana одного шага параллельной декомпозиции/ в базисе g.

Из того, что каждый шаг (кроме последнего) декомпозиции преобразует функцию (на основе строения) в суперпозицию двух функций того же класса и они проще исходной, следует теорема.

Теорема 5.1. Полная структурно-функциональная параллельная декомпозиция функции f в базисе С, проводимая по алгорипъиу Аца> выполняется (существует) всегда.

Для получения выражений для функционалов качества рассмотрим следующие два случая. Если /< т < т', то по алгоритму Апа "выравниваем" строение формулы f так, чтобы получить внешнюю функцию суперпозиции не сложнее базисной функции g. Функционалы имеют вид:

LF(f.g,w)=l + I i = 1

Ri-1 qrl

DepF(f,g,w) = l + max{ \log,h R,"]} при 1 < / < IV.-<?г- + /, если n>qj,

m,

(5.1)

(5.2)

ГДе Л/-

I- если г/ ^<7,- -

Если т>т (для случая базовым является предыдущий), то, разбивая формулу / на подформулы длиной т и последняя может быть меньшей длины, получаем число предыдущих случаев, для которых будут иметь двойную индексацию - номер случая и номер элементарной конъюнкции. Суммируя действия, получим выражения для функционалов качества:

Lr(f.g. ») =

т-1 т' — I

sn т' + 11 i=Ij=l

Rij-l

qrl

(5.3)

Оеру&g. м>)= \lcig,,,. /и]+ шах

К, ЛЛ) (5 4)

при 1 </ <а0, /<у <т',

\г(1-1)т'+]-Ч]+1' если 1-(1-1)т' + ]>Чу где Ц = | J если , . < .

Эти функционалы (имеются и другие)"%сУь'/&р"Ьфме'т.ические (изоморфные) аналоги шагов структурно-функциональной декомпозиции.

В функционалах (5.1) - (5.4) за счет подходящих перестановок элементарных конъюнкций в формуле f можно уменьшать только последние слагаемые, минимизируя функционалы.

Теорема 5 2. Пусть f формула строения г и длиной т; г/ - способ упорядочивания элементарных конъюнкций, доставляющий минимальное

значение показателю сложности ¿р декомпозиции функции / в соответствующем базисе С=^0=0, g^=!, g}. где строение g есть д и длина

равна т, т е Ьр = Lp(g,w')шя, к Ьр — ], g, у)") - значение

сложности дчя любого способа w" декомпозиции Тогда сложности Ьр

и Ьр могут различаться от 0 до т — 1, т.е. 0<Ьр — Ьр <т—1.

, Доказательство. Левая часть неравенства выполняется по определению, а для правой части на основе (5.1) получаем

711

н 1 т « - К, -I д,-1 т Л,'-/

ьГ -Ьр = X -X Я,-'

I 7 = '

I*, -т

1=1_

_

4,-1

<т-1 +

~ I*,

Ч,~1

яг

= т-1 +

— т — 1.

д,-1

Ошибка от неудачного упорядочивания элементарных конъюнкций в формуле для формулы может давать "лишние" подформулы, что в общем случае влечет увеличение глубины.

Полезно заметить, что двойственные формулы имеют одинаковое строение и, сл., имеют равные значения показателя качестваЬр(и Оерр).

Теперь сформулируем методику для решения задачи минимизации рассматриваемых показателей качества декомпозиции на основе (5.1)-(5.4).

Бхли т < т\ то, проводя анализ перестановок п(К) )=■ К/ элементарных

конъюнкций в формуле / с целью сокращения их числа, учитывая строение гид соответственно формул f И g, получаем возможность с меньшей (по сравнению с перебором) трудоемкостью получить требуемую перестановку для последующего выполнения декомпозиции. Предложенную методику можно отнести к прямым методам решения поставленных задач, при этом она, тем не менее, может потребовать большого объема вычислений для отдельных условий. Если т > т', то эта методика обобщается.

Возможен другой путь решения. Для одного случая (длина формул т=ш'=2) проведено исследование математической модели для задачи минимизации, в результате которого получена таблица с условиями (линейными неравенствами), позволяющая с одним объемом вычислений, практически не зависящим от числа переменных, получать требуемую перестановку (как и для вышеизложенной методики) с минимальными значениями сложности и глубины. Эти условия иллюстрируются, геометрически на плоскости с помощью областей минимизации сложности и глубины формулы F (схемы S). Например, для бесповторной формулы / строения ^{I'iS':) и базисной формулы g строения q=(iji;qi) рассмотрим один случай изб:

Li >L2 при дополнительном условии (p-I)(qi -l)+qi <rt <p(qt -l)+q2 и Li=L2 при дополнительном условии p(qt -l)+q: <ri <p(qi-l)+qt, peN.

В шестой главе решается проблема о глубине произвольной булевой функции в стандартном базисе и ее получении. Решение позволит проводить оптимизацию (по быстродействию) логических схем с ограниченной трудоемкостью.

Пусть бесповторная функция (формула) /"' имеет строение г=(г/,...?•„,). Тогда е? сложность Lh{f)~rt +...+ гт~п . "Для данной функции безразлично, в каком базисе из определять ее глубину,

так как основную роль теперь играет строение г. Поэтому будем говорить о формуле строения г, рассматриваемой над различными множествами логических операций (микросхемы содержат логические элементы, реализующие эти функции). Принципиальным является случай т = 2, для которого справедлива теорема 6.1 (для любого типа формул f строения г).

Теорема 6.1. При деколтозш^ш формулы f 'Строения r^frt.T^), где

Г/ > г-, > 0. п - г( +»ч. в базисе G показатель Lr(f. G) — п-1 it минимальная глубина суперпозиционной формулы F есть

\\l0S2 н] + 7. ест [/о?: rt"j = /1].

ее ш {log 2 >11 < I log2 "1

Dr(f.G)mm =

log 2 n j

(6.1)

Доказательство. Применяя вышеприведенные результаты для показателя иа, в), получаем Ьг (/.в) = (г, -1) + (г, -1) +1 = г, +г2-1 = п-1.

Если < г, <п< 2*, т.е. \1о%2 г,] = [7о£2 п~\ = л, то глубина

= тах{Оер(К,);Эер(К2)}+1 = Оер(К, ) + ! = \logj я] + /.

< г, < 2S~' <п ¿2s, то глубина получается аналогично, т.е. DepF(f.g.w)-[log2rl~\+1 = (s~ IJ +1 = [log2n"\ Других случаев нет.

Теорема 6.2. При декомпозиции формулы f строения г =^(rt;r2;r3), где I) > г, >г3 > 0, п = rt + г2 + г} и и > 3, в базисе G минимальная глубина суперпозиционной формулы F есть DepF(f<n>)mm =

(6.2)

[log2 и] +1. если {log2 и] = [log2 rf \ v

v [log2 n"] = [log2 >'/"1+ I = [log2 r2] + /,

f/og? и"|, если [log2 «1 = [log2 /'/"] + / = |"/ogj> /j>] + 2 v v [log2 и] = [log2 n1 + 2 = [log2 r2~\ + 2.

Лемма 6 1. Dep(Kj ®(K2®K3))< Dep((K} ®K2)®K3).

Теорема 6.2 и лемма 6.1 доказываются аналогично теореме 6.1.

Далее глубина бесповторных формул произвольной доступной длины вычисляется на основе разбиения на слагаемые отдельных значений числа переменных и = 2s.

Теорема 6 3. Если формула f зависит от п-2s, s = 2, 3,..., переменных, имеет строение г = (г,,..., гт), где г; &{2SГ..Л1 },' = Л .... т, и п- г) + ... + гт, то минимальная глубина суперпозиционной формулы F. представляющей функцию /, в базисе G равна [log2n\=s.

Доказывается индукцией по i, причем она справедлива для числа п переменных,удовлетворяющего двойному неравенству 2s~l <n<2s.

Теорема б 4. При декомпозиции формулы f<n> строения г-(r{; г2;...гт), где г, >г2 >...>гт >0 и п = г} +Г7+...+гт, в соответствующем базисе G достижимые нижняя и верхняя оценки для минимальной глубины суперпозиционной формулы F есть соответственно [logи [log2n\+l, т.е. [¡og2n\<DepF(fln>, G)m„ <[log2n~\+J.

Заметим, что случаи т-1, 2 и 3 полностью исследованы ранее и согласуются с утверждением. Пусть для числа переменных п выполняются

неравенства 2s~'<n<2s. Из того, что для случая т~1 глубина

Depr(f<nKG)mn = [log2 и], а увеличение длины формулы (т >/) не может ее уменьшить, следует нижняя оценка глубины в утверждении.

Пусть для рангов г, выполняются неравенства 2S' 2S', i = 1. 2, ..., те, s>si>s:„.>5„,. Для формулы /'" сопоставим формулу f("' строения г =(rh...,rm), где п-7,+...+7т и г, = 2*', i = I, 2, .... т. Формула f,n> находится в отношении несложнее с формулой f1"'. Представляя г; = г, + Л,, i- 1,2.....т, где 0 < Д, < 25', получаем 7f<2-rl,

п<2-п и Dep(f<n>, G)mu, <Dep(f<"1, G) = \log2n']<\log7n'\+l, что и требовалось доказать.

Теорема 6 5. При декомпозиции формулы /н> строения г= = (rt;r2;...rm), где г, >г, >. ,>rm >0, п = rt + r2+..,+rm, т>2 и п>4,в базисе G минимальная глубина суперпозиционной формулы F есть

flog,n"]+/, ее tu [log-, и] = [~log2r/~(v

vf log_,n~]-1 = flog, ;■/"] = ["log, r, ] v

v p og,«] = flog^r, ] + У = [log, r2 ] + 2 = [log, r, 1+2 & m = 4,

(6-3)

flog,«] если flogin"l-2 = flog2/-/"]=flogi?r,"| &(m = jvm = 4)v

vf'log_,n]=riog2r/1+/ = flog,^l+2 = riog_,/J]+5 & m = 4,

иначе или или flog;/?~|+7.

Доказательство основывается на результатах теорем 6.1, 6.2 и 64 и проводится аналогично доказательству теоремы 6.1.

Из этих теорем следует, что минимальное значение глубины (одно из двух) для остальных случаев можно продолжать получать, но уже практического интереса, наверно, это не будет составлять, так как даст бесконечный процесс - число случаев и большую трудоемкость. Для получения конечного числа случаев и сокращения трудоемкости введем понятие кода глубины бесповторной функции.

Кодом (вектором) глубины формулы (полинома Жегапкина, ДНФ, КНФ и др.) /'" строения r = (r,;r2;...rmJ при ее параллельной декомпозиции в двухместном базисе G={&, Ф, v} называется вектор d-(di, d2,...,dj, где dl=\log2r,\ i = l,...,m.

Пусть /'Л - функция строения r = (r,;r2;...rm), где г\ >г2 >...>гт>0,

n = rj + r2+...+rm и 2S~} <n<2s, s~3,4..... G={&, ©, vj - базис. To-

гда имеют место следующие теоремы, причем для т- 2, 3 исследуемые вопросы выяснены и далее считаем, что т > 3.

Теорема б. б. Если кодом глубины формулы/"' строения г (т= s) является вектор d с компонентами d, = s - i, i= /,..., m, то минимальная глубина суперпозиционной формулы F есть s и число п переменных такой формулы удовлетворяет неравенствам 2i'1 + s-l<n<2s -1 (s>3).

Доказывается индукцией по s (s > 5).

Теорема б 7. Если для формулы /"' строения r-(rt; г2 ;...гт), с числом переменных, удовлетворяющим неравенствам <п<2$ и равенству п - >'] + ¡"2 +...+/",„, и длиной т~2', i=0,1,..., s, кодом глубины является векторd=(dj.....dj, то Depr(f<n>.G)mm =s = [7og_iM~}

Действительно, пусть d/-...=dm=d. Тогда 2,l~' < r} < 2'1 ,j = 1,2,...,m, и n = r, +... + r„,<m-2'1 = 2'*A. Отсюда d = s-i и DepF( f1"',G )nm < <\log:m~\+ \log21)1= / + 5 - / = s. С другой стороны, Depr( f('",G)тш > s, что и завершает доказательство.

Теперь установим связь сложности формулы с ее глуби ной. Пусть

fied = -К/® ®К2@...@Кт - полином Жегалкина строения r=(V/.....г

где п = I) +;•,+.„ + гт, и f("J =К[® ...@Кт- произвольный полином Жегалкина строения г -(г/.....r„J, причем п <п и ЬБ(/'"') = г, + ... + /-,„. Тогда

справедлива теорема.

Теорема 6 8. Минимальная глубина суперпозиционной формулы F,

полу чаемая на основе декомпозиции функции строения r=0'i. ■■■,>',J в базисе G={&, Ф, 1), удовлетворяет двойному неравенству

% \hg,(LB(f<">)){ <Depf(f(n>,G)mm < \hg2(LB(f""))\+1. (6'4) Используя результаты теоремы 6.4 для глубины бесповторной формулы

\log:(Le( f£>))] <DepF(fg>,G)mm < \log2(LB(f£>J)}+l и имеющуюся связь в условии между параметрами Ls(/?!!,) = " =ri + r2 + ---rm=Ls(f<n)) <'n<n) и показателями

DePF(f£n-GLn = DepF(r, G)mm = Dep, (/"". G)mm, получаем требуемые неравенства (6.4).

Для других типов формул вопрос минимальной глубины решается аналогично только по отношению к заданной формуле. Например, если fn)

- минимальная ДНФ строения r=fri, г?, ...,г„,), то глубина функции (.минимальная глубина формулы) /"' на основе минимальной ДНФ удовлетворяет (6.4), иначе, если она (ДНФ) не минимизирована полностью в силу ее сложности, то верхняя оценка глубины уже может быть минимальной (совпадать с глубиной функции и может быть больше), но в любом случае она минимальна по отношению к сложности заданной формулы и к формуле F (если можно так говорить), т.е. она получена для любой конкретной формулы. Для немонотонных ДНФ строения г=(г/, п, ...,гш) с учетом функции отрицания оценки (6.4) увеличиваются на 1. Таким образом, если булева функция задана ДНФ, то ее строение и сложность позволяют получить либо точное значение для минимальной глубины функции (на основе решения задачи минимизации), либо ее верхнюю оценку. Это обстоятельство усиливает интерес к задаче минимизации булевых функций в классе ДНФ и предъявляет высокие требования к алгоритмам минимизации. При использовании математического моделирования в такие алгоритмы можно вставлять блок, анализирующий сложность получаемой ДНФ и принимающий решение о прекращении работы алгоритма в случае достижения минимальной глубины, если при этом отсутствуют требования к минимизации по другим критериям. Это означает, что такие алгоритмы параллельно уменьшат трудоемкость решения задачи.

Верхнюю оценку (6.4) глубины булевой функции, полученную для стандартного базиса G, используем теперь для получения верхней оценки глубины функции для произвольного базиса G"p. Из того, что определенным образом присваивая константы переменным базисных функций из G"p, всегда можно получить соответствующий стандартный базис G, следует сохранение верхней оценки (6.4) для глубины. При этом не будет выполняться принцип оптимизации декомпозиции [2.3]. Если же он соблюдается, то в силу свойств монотонности функции приближения с избытком и логарифмической функции это не может вызвать увеличение показателей сложности по числу подформул и глубине, т.е.

Для каждого конкретного базиса G"" оценку (6.5) можно уточнять. Особо отметим, что здесь (и ранее) получены оценки показателей качества декомпозиции, выраженные через параметры исходного описания функции

jfn/

Рассмотрим вопросы глубины некоторых симметрических булевых функций /"', задаваемых элементарными симметрическими полиномами (монотонными ДНФ или полиномами Жегалкина) строения г = (г/, ..., г,„), причем 1 < Г/ = ...=/•„, < п (г/ и п>2 - несвязанные параметры, п и т • связанные параметры). Считая, что /• = /•/, введем следующее обозначение:/'" для таких полиномов, их сумма есть симметри-

ческий полином, т.е. они образуют алгебры с соответствующими операциями. Число элементарных симметрических полиномов f" равно и (г = =1,2,..., п); длина соответствующих формул равна т = Сгп ; сложность

, г I п!

Lb{f'r)~ >'гСп = -:-. для которой имеет место асимптотиче-

(г-1)!(п-г)!

ское равенство Lb{f"r) ~ п /(/• - 1)1

Формула Depr(f"r,G)=[log2r>f/og,m~\={!og:r]+f/og:C;l, !</<«, для. глубины раздельной декомпозиции в классе ДНФ доставляет минимальное значение глубине каждой функции из этого класса. Заметим, что полученные здесь значения минимальной глубины совпадают со значениями, полученными на основе (6.4).

... .. Нижняя достижимая оценка глубины элементарного симметрического полиномаfnjr равна Depr(f"r, G)~[log:н!, а верхняя достижимая оценка получается на основе анализа полученных выше результатов, т.е. max {\log7г~\+ Гlog2 C^l}. Причем доказывается, что точка 5 = [я/2J

1<г<п

ИЛИ является точкой максимума (или одной из них) функции

D(n,r)-\log2r\+\log2 СЛ, п>3,1<><п, и для случая п - четное и г=п /2 получено следующее асимптотическое равенство: Depdf'" ,G) = DepF(f:rr ,G)=llog2r~} + [log2 Cr2r~\~ 2r = п.

Отметим, что в теоремах 6.1-6.8 минимальные результаты достигаются на основе структурно-функциональной параллельной декомпозиции. Эти теоремы также позволяют получать классы функций одной глубины за счет использования конструктивных операций над строением функции, включая различные интерпретации строения формулы. Полученные в главе результаты играют важнейшую роль для разработки интеллектуальных программ оптимального синтеза логических схем.

В седьмой главе рассматривается синтез схем S из функциональных элементов, выполняемый на основе структурно-функциональной декомпозиции. Пусть имеется базис

G*', состоящий из функциональных элементов (ФЭ) g,, j =/, 2.....к. Для ФЭ базиса и представляющей его функции используем одно обозначение gr Функция g, ,j = 1. 2, .... к, характеризуется определенным "весом" /,, который для ФЭ интерпретируется или как время прохождения сигнала (задержка) /,, или как вероятность р, безотказной работы в течение времени Т (отказ ФЭ означает разрыв в цепи), или как число транзисторов в нем. Теперь для заданной системы булевых

функций Д.х/......*„), | = 1..... к , требуется получить представляющую ее

схему S из ФЭ базиса С1". Следующие понятия вводятся для одной функции fixt.....х„), не содержащей фиктивных переменных и аналогично переносятся на системы функций. В качестве показателей качества схемы S из ФЭ базиса реализующей функцию/, используем: Ls( f,g,w) - число

ФЭ - сложность схемы 51, где набор, состоящий из ФЭ, а лу - набор, состоящий из способов построения схемы (эти способы связаны с преобразованием функции и одинаково обозначаются); Оер$(- глубина схемы 5, определяемая как число ФЭ в самой длинной цепочке, ведущей от входов к выходу схемы, а длина цепочки - число ФЭ в ней; Р$() -

показатель надежности схемы 1™р(/) или 1тр- число транзисторов в схеме 5. По практическим соображениям, считаем, что схема 5 тем лучше, чем меньше значение ее показателей сложности

и и больше Р5(/,%,уч), т.е. М/.8.™)->ш«,

Оер5(/,£,\*)->тш, 1%р( Р$(/,тах, ё е С, \veJV'.

Для схем без ветвления выполняются равенства =

Выполняя синтез схемы 5 без ветвления на основе структурно-функциональной декомпозиции, получим минимальные значения или верхние оценки для ее показателей. Для классов функций &, V, ф или <->, зависящих от п переменных, получаем, что минимальные значения показателей качества схемы 5 равны соответствующим показателям суперпозиционной формулы Р. т.е.

парса. mm

П-1

п-1

(7.1)

(7.2)

Если функции fug задаются формулами соответственно строения г и q, то показатели качества синтеза требуемых схем определяются при помощи функционалов (5.1)-(5.4) на основе математического моделирования. Получаемые значения являются верхними достижимыми оценками для числа ФЭ и глубины схемы: Ls( f,g,v/)<Lf(f,g.vt) и Deps(f,g,w)<DepF(f.g.w)- При этом, используя метод совместной параллельной декомпозиции для синтеза схемы с ветвлением, оценка для числа ФЭ может быть уменьшена. Считаем, что с выходов инверторов всегда возможно ветвление, поэтому их число в схеме не более числа я, глубина увеличивается на 1. Для двухместного базиса С'" иминимизиро-ванной функции глубины схемы получены точнее, а именно,

Верхняя оценка глубины справедлива для произвольного базиса G"p.

Исследования по минимизации числа транзисторов (диодов), содержащихся в схеме S, можно проводить в разных направлениях: проводя исследование базиса из ФЭ и выдавая рекомендации проектировщикам микросхем относительно состава библиотечных элементов; изучая различные

формы представления булевых функций; выбирая методы и способы преобразования - декомпозиции для указанного синтеза. Рассмотрим некоторые из них.

При синтезе схемы Я для функции/ из классов &, V, © и <-» в базисе о"""" „„„„„ ™„„„„2ТОрОВ подучим минимальное значение (¿т_ )„„„=/„ • —- , где вес 1„ - число транзисторов в базисном эле-

п—1

менте и для всех трех показателей качества синтеза достигается минимум. Для этих классов функций предложена математическая модель представления функции /большой размерности при помощи нескольких базисных функций меньших размерностей с соответствующими весами, позволяющая выбирать представление с минимальной суммой весов базисных функций.

Заметим, что минимизация схемы по сложности Ду в базисе одного универсального элемента приводит к уменьшению в ней числа транзисторов, но в базисе из нескольких элементов такой зависимости может не быть. Здесь полезную роль играет исключение повторяемости переменных.

Для двухместного базиса где базисные элементы и gv имеют соответственно веса (число транзисторов) и . Тогда схема Я имеет вес

Если I/, (/) = п и, например, < !у, то /& -(л - 1) < б) < /„ (и - 1).

Надежность схемы 5 (без резервирования) для классов функций &, V, ф или при условии, что все каналы передачи сигналов абсолютно надежны, отказы могут происходить только в ФЭ 2, , независимо друг от друга и от положения в схеме, определим как вероятность безотказной работы схемы реализующей булеву функцию!/, на основе теории монотонных систем (./V - число ФЭ в схеме 5):

получаемая на основе структурно-функциональной декомпозиции, при некоторых условиях (входящих в аксиомы 1-5 эквивалентных преобразований) приводится к структурному виду (комбинации последовательных и параллельных структур). Тогда вероятность Рх (конкретно Рпа и Р„а ) условно безотказной работы такой схемы 5 получаем, используя теоремы и формулы теории вероятностей. Структурная схема 5 характеризуется: степенью "параллелизма" как разность Р, — Рл, называемой показателем параллелизма схемы 5; степенью "линейности" как разность

- Рх ), называемой показателем (степенью) "линейности" схемы 5, которая характеризует ее чувствительность к отказам типа разрыв.

Теорема 7.1. Пусть функции/=/"' и ' принадлежит одному из классов &, V, ф и о и п = (п'/; g - обозначение ФЭ (и соответствующей функции) с вероятностью безотказной работы р7. Тогда вероятность Р™ра''( f,%.Уi) условно безотказной работы схемы 5 из ФЭ g равна Рь т.е. Р™ра1(= , причем Рк вычисляется при помощи

Р1=р/1-(1-Р1.,)"'1 (7.6)

где РI = р, и 1-2.....к. Доказывается утверждение индукцией по к.

В восьмой главе рассматриваются оптимизирующие логико-комбинаторные преобразования, включающие в себя последовательно применяемые действия к каждой булевой функции над различными базисами на основе математико-информационного описания: удаление фиктивных переменных; минимизацию булевой функции, включая приведение ее к скобочным формулам или к системе формул; доопределение частичной булевой функции.

При моделировании: декомпозиции на основе функционалов (5.1)-(5.4) применяется алгоритм, сокращающий число перестановок элементарных конъюнкций; совместной декомпозиции в произвольном базисе применяется алгоритм, проводящий лексикографический анализ формул и функций с целью минимизации Ь?. Другие алгоритмы также основываются на такой технологии, являясь, как и эти, алгоритмами градиентного типа.

Для произвольной булевой формулы строения в двухместном базисе предлагается эвристический целенаправленный алгоритм получения минимальной глубины, обобщающий результат леммы 6.1.

Результаты главы в конечном итоге применяются для минимизации значений показателей и Эер<, логической схемы 5. Этой же цели служит следующая теорема, но уже для различных базисов и схем без ветвления.

Теорема 8.1. Пусть булева функция / имеет строе^^ев базисе (?/, представляя формулу р/, и /2> в базисе С?, представляя формулу Р2, причем <7/ с С7= {&, V, ©, 1} и С (?= {&, V, ©, 1} . Если представление f в базисе б/ не сложнеепредставления / в базисе (т.е. г" <г">), то реализация функции / в базисах логических элементов (с получением схем 5/ и соответствующих базисам С/ и С?;, характеризуется следующими неравенствами относительно значений показателей качества: для формул (/, С,)< ЬГ: (/, в;) и йерп (/, в,)< йеру, (/, в2) и

длясхем и Оер^(/.в,) < Оер5:(/,С2).

Доказательство, Пусть г(,) < г(2). Тогда при помощи конструктивных операций на основе структурно-параллельной декомпозиции в базисе (/; выполним приведение формулы Р2 (в базисе С;) к одному строению с формулой При этом используется некоторое количество

базисных формул (логических элементов) и создаются начальные уровни глубины формулы Рз (схемы 5:). Дальнейшая реализация функции / в соответствующих базисах для формул одинакового строения и одного строения базисных ф>нкций имеет одинаковый результат, что подтверждает справедливость теоремы.

Эти алгоритмы и теорема являются основой решения задачи синтеза логических схем в следующей, девятой главе, в которой рассматриваются примеры цифровых микросхем и проводится анализ их математических моделей на основе полного математико-информационное описания функций, представляющих эти микросхемы.

Базовый метод синтеза сетей из микросхем разделяется условно на этап предварительной структурно-функциональной параллельной декомпозиции исходных формул в заданном базисе, представляющем логические элементы (включающий совместную декомпозицию), и получения искомой сети (ее описание в элементах микросхем с учетом нумерации входов-выходов и возможного ветвления выходов). Минимизация по числу элементов схемы достигается также с помощью различных представлений булевой функции, например, задания ее скобочной формулой. Для системы булевых формул ее совместной реализации по

алгоритму удовлетворяет неравенству

Для раздельной и совместной, включая ветвление выходов, реализации булевой функции в базисе микросхем (произвольного функционального базиса имеет место следующая цепочка неравенств и равенств для сложности 1/т и ¿х: £/{/, С) £ С"р) = Спр ),мМ > С "р ) где Ьг(/, С'р) определяется при помощи функционалов (5.1) и (5.3). Более того, используемый подход (в том числе математико-информационное описание формул) позволяет произвольный базис характеризовать системой числовых параметров

максимальное число переменных соответствующих функций или максимальный ранг элементарной конъюнкции соответствующей формулы, т.е.

1& =тах{/^,"|),...,/^"*>,д{1).....<71(/')}. Для двух таких систем и естественным образом, как для векторов, вводится отношение предшествования. Если для базисов Сг// и (/'' соответствующие системы Я) и Иг находятся в отношении предшествования < , то для показателей качества синтеза схем выполняются неравенства ¿5{/, С1"' ) < Ь\{/, ) и Ь^/, С'2' ) < ¿¡{ /, (г1' ). Таким образом, для совокупности базисов получаем семейство оценок качества синтеза логических схем Б.

Из теоремы 6.8 следует, что минимальная глубина схемы без ветвлений 5 (на основе минимальной ДНФ и др.), реализующей функцию f в соответствующем базисе удовлетворяет двойному неравенству

При реализации системы ДНФ /, длиной т,, / = I, 2, .., р, над множеством X ={.Т/, хх,,} в базисе ПЛМ(1, где 5-число входов, Г-

выходов, q-промежуточных шин, могут быть различные случаи. Рассмотрим методику реализации одного из нескольких основных случаев.

Пусть п> 5, р < / и т, < д . На основе математике-информационного описания булевых функций и, дополнительно к этому, таблиц п.3.1 получаем покрытие множества X, т.е. А=Л/ иХ; и ...и Хр , где переменные множества X,, г =1, 2,...,р, являются аргументами функции

Если шах|А",|< 5, то при помощи математико-информационного описания системы функций получено покрытие множества X с наименьшим числом объединяемых множеств. Это число дает первые ПЛМ. Для тех же Х^ для которых выполняется неравенство \Х] I > 5 ,7 =1, 2, ... , получаем дополнительное число Г|^¡1/Л, /=1, 2,... , ПЛМ. Эти ПЛМ, представляемые как вершины графа, все вместе составят нижний уровень дерева суперпозиционной формулы Р. При этом получается параллельная декомпозиция системы булевых функций на более простые системы функций.

Приводится пример реализации симметрических функций в базисе ПЛМ - ППЛМ 556РТ1 (16, 8,48) и элементов МИС (серии К155 ЛИ1 -2И, К155 ЛЛ1 - 2ИЛИ). Отмечаются случаи, когда эффективнее в отношении быстродействия тот или другой базис - вариант реализации.

Дается описание некоторых программ для моделирования оптимального или близкого к нему синтеза микросхем, разработанных на основе алгоритмов глав 4, 5, 7 и 8 при участии и под руководством диссертанта: декомпозиции функции на основе перестановок; приближенной минимизации ДНФ,* привидения их и полиномов Жегалкина к скобочному виду; синтеза комбинационных автоматов; декомпозиции булевой функции в двухместном базисе (минимизация глубины).

Приводятся результаты вычислительного эксперимента. В десятой главе рассматривается синтез управления цикловым манипулятором на основе принципа геометрического кодирования

Манипулятор рассматривается как механическая голономная система материальных точек в инерциальной системе отсчета Оху: с координатами х,,у, и г,, I = 1,2,...,к, которые выражаются на основе связей через независимые обобщенные координаты ...,д„ и время 1 Для каждого момента времени ? между возможными положениями системы (звеньев манипулятора) и точками некоторой области в п-мерном координатном пространстве устанавливается взаимно-однозначное соответствие, которое определенным образом нумеруется (кодируется). Это правило нумерации точек назовем принципом геометрического кодирования.

На основе математической модели циклового манипулятора как инициального конечного автомата Мура (Хц, Ym , Qm , фм, у/ц , и регулятора как инициального конечного автомата Мили (Хц . Yr , Qr , <рц, Щ , g*ft), а также принципа геометрического кодирования разработан алгоритм управления манипулятором, который реализуется аппаратно в базисе СИС и программно (причем допускает программирование не только на специализированных роботоориентированных языках, а на широко распространенных языках Алгол, Фортран, Pascal, Си, Assembler и др., давая независимость в выборе ЭВМ для управления). Результаты работы могут быть использованы при разработке математического обеспечения управления адаптивным роботом.

В одиннадцатой главе для обеспечения безопасности полета летательных аппаратов рассматриваются принципы для оптимального разведения двух летательных аппаратов (ЛА), выполняющих движение навстречу по пересекающимся или близко расположенным траекториям со скоростями v"' и v'2>. Если эти векторы коллинеарные, то каждый ЛА поворачивает вправо, иначе направление для пространственного разворота каждым JLA (с одинаково определенной системой координат) определяется на основе векторного произведения v(l>xvu>. При этом разработаны основные дискретные математические модели для различных возможных ситуаций, позволяющие получать оптимальное разведение в пространстве двух ЛА, а также рекомендована общая структура управляющего цифрового автомата, реализуемого в базисе микросхем различной степени интеграции. Приводится пример одного структурного автомата, позволяющего моделировать движение двух таких ЛА с целью принятия решения по их оптимальному разведению.

Приложение П.1 содержит описание свойств функции [V], используемых при получении оценок показателей качества синтеза схем.

Приложение П.2 содержит тексты программ, представленных в гл.9.

Приложение П.? содержит акты о внедрении результатов работы.

ЗАКЛЮЧЕНИЕ

В диссертации разработаны фундаментальные основы и использованы математическое моделирование, численные методы и комплексы программ для решения научных и технических проблем реализации системы булевых функций в базисах микросхем различной степени интеграции (экономной по различным показателям качества и за приемлемое время), получены и исследованы математические модели синтеза вычислительных и управляющих логических устройств, имеющие важное прикладное значение.

Основные научные результаты работы, выносимые на защиту

1. Разработаны оригинальные математические модели (объектов и процесса логического синтеза) и проведен их анализ с целью получения оптимального или близкого к нему (по сложности, быстродействию, надежности) синтеза вычислительных и управляющих логических устройств в базисе микросхем различной степени интеграции.

1.1.Разработана оригинальная многоуровневая модель математико-информационного (компьютерного) представления булевых бесповторных и произвольных функций (на основе понятия строение таких формул, как полином Жегалкина, ДНФ, КНФ и другие) в заданном базисе, позволяющая решать все необходимые задачи оптимизации синтеза.

1.2. Определены методы параллельной и последовательной декомпозиции на множестве всех булевых функций на основе их строения как многошаговые процессы и соответственно для них функционалы - показатели качества (по числу подформул и глубине) декомпозиции с целью применения при оптимизации синтеза логических устройств в базисе микросхем. Метод параллельной декомпозиции позволяет распараллеливать вычисления, в том числе булевы уже на внутрикристальном уровне.

2. Разработаны оригинальные математические модели и методы (на основе декомпозиции) многокритериального оптимального (по сложности и/или быстродействию и другим показателям) синтеза вычислительных и управляющих логических устройств для отдельных классов (простых, бесповторных и порожденных) булевых функций в базисе микросхем различной степени интеграции, причем значения показателей качества такого синтеза получены аналитически.

2.1. Исследовано влияние методов параллельной и последовательной декомпозиции для классов булевых функций на результаты синтеза логических схем, получаемые на основе декомпозиции, в отношении показателей - функционалов сложности (методы одинаково минимизируют число элементов в схеме), глубины (метод параллельной декомпозиции минимизирует глубину схемы, а метод последовательной декомпозиции максими-

зирует ее) и надежности (метод параллельной декомпозиции распараллеливает вычисления в схеме, делает ее менее чувствительной к отказам типа разрыв, а метод последовательной декомпозиции делает ее более чувствительной к таким отказам). Причем оптимизация функционалов качества проводится аналитически, экстремум достигается на классах булевых функций, в ряде случаев подсчитывается мощность этих классов.

2.2. Проведено исследование множества всех булевых функций в некоторых базисах с целью их экономного компьютерного представления, включая минимизацию по сложности и глубине (приведены примеры такого представления), а также с целью установления зависимости между сложностью булевых формул (с повторением и без повторения переменных) и их минимальной глубиной; определен подход к получению разбиения множества булевых функций на классы функций одной глубины и получены некоторые классы такого разбиения; предложен подход к определению глубины скобочных формул.

2.3. Предложена совокупность оригинальных математических моделей декомпозиции, позволяющая решать различные задачи оптимизации синтеза логических схем (дополнительно к сформулированным достижимым показателям качества возможно включение показателя - суммарной длины проводников между логическими элементами и других). Для базовой модели (формул, длины равной двум) получены условия для проведения многокритериальной (по сложности и глубине) минимизации логических схем.

3. Разработаны методы многокритериальной оптимизации (по сложности, быстродействию и другим показателям) синтеза вычислительных и управляющих логических устройств для произвольных булевых функций в базисе микросхем различной степени интеграции на основе математического моделирования.

3.1. Разработаны алгоритмы для моделирования параллельной декомпозиции булевой функции на основе функционалов качества, раздельной или совместной параллельной декомпозиции системы булевых функций в различных базисах, при этом минимизируется число логических элементов и/или глубина схемы.

3.2. Разработаны методы синтеза логических схем в базисе микросхем различной степени интеграции на основе структурно-функциональной декомпозиции, позволяющие в зависимости от параметров исходного описания задачи заранее оценивать качество синтеза по числу транзисторов, логических элементов, микросхем и глубине. Методы эффективны по этим показателям качества с ограниченной трудоемкостью.

3.3. На основе рекомендованных методов и алгоритмов разработаны программы для ЭВМ, позволяющие моделировать различные преобразования булевых формул (такие как минимизация, экономное доопределение частичных булевых функций, параллельная декомпозиция с многокрите-

риальной минимизацией показателей качества - по числу подформул и глубине, а также для приведения формул к скобочному виду). Вычислительные эксперименты подтвердили состоятельность и эффективность проведенных исследований, разработанных методов и алгоритмов.

4. Предложено решение актуальных теоретико-прикладных задач в робототехнике и авиационной области на основе логики и методов структурно-функциональной декомпозиции.

4.1. Предложен принцип геометрического кодирования для оптимизации логического управления цикловым манипулятором. Разработан алгоритм, использующий модели теории конечных автоматов и реализованный аппаратно, такого управления цикловым манипулятором.

4.2. Принципиально разработан основной цифровой автомат (определена иерархическая структура), предназначенный для обеспечения безопасности движения в пространстве по пересекающимся или близко расположенным траекториями двух летательных аппаратов, основывающийся на новых дискретных математических моделях движения и оптимальном принципе разведения; в качестве примера в базисе микросхем синтезирован автомат моделирования движения таких летательных аппаратов.

Основные результаты диссертации отражены в следующих работах

Монографии

1. Чебурахин И.Ф. Синтез логических схем и программ управления на основе структурно-функциональной декомпозиции. Москва: МГТУ им.Н.Э.Баумана. 172 с. Деп. в ВИНИТИ 07.07.93, № 1884-В93.

2. Чебурахин И.Ф. Синтез дискретных управляющих систем и математическое моделирование: теория, алгоритмы, программы. Москва. Физмат-лит. 2003. 264 с.

Статьи, доклады и тезисы докладов

3. Чебурахин И.Ф. Синтез схем из функциональных элементов. 4.1. Некоторые вопросы декомпозиции булевых функций. Москва: МГТУ им.Н.Э.Баумана. 13 с. Деп. в ВИНИТИ 14.01.85, N 373-85. Р.Ж. Техн. кибернетика, N 4, 1985.

4. Чебурахин И.Ф. Сложность декомпозиции булевых функций, алгоритмы. 4.2. Москва: МГТУ им.Н.Э.Баумана. 18 с. Деп. в ВИНИТИ 14.01.85, N 374-85. Р.Ж. Техн. кибернетика, N 4,1985.

5. Чебурахин И.Ф. Синтез схем из функциональных элементов. Ч.З. Основные принципы, пакет программ. Москва: МГТУ им.Н.Э.Баумаиа. 20 с. Деп. в ВИНИТИ 14.01.85, N 375-85. Р.Ж. Техн. кибернетика, N 4, 1985

6. Чебурахин И.Ф. Принцип геометрического кодирования и логическое управление адаптивным роботом. Москва: МГТУ им.Н.Э.Баумана. 16 с. Деп. в ВИНИТИ 11.02.87, N 992 - В.

1. „Чебурахин И.Ф. Оптимизация программ управления для логических контроллеров // Межд. сб. "Вычислительная техника. Системы. Управление". Москва - София. МЦНиТИ, 1989, вып. 1, С. 56 - 64.

8. Чебурахни И.Ф. Автоматизированная разработка оптимальных программ управления для логических контроллеров // Сб. "Автоматизация проектирования систем программно-логического управления", вып. 2. М: Машиностроение, 1990. С. 151 -196.

9. Чебурахин И.Ф. Надежность комбинационных схем // Сб. "Труды МГТУ им.Н.Э.Баумана. № 544". М: Изд-во МГТУ, 1990. С. 114 -126.

10. Чебурахин И. Ф. Проектирование оптимальных комбинационных схем // Научно-техн. сборник РКТ, серия 5, вып. 2,1991. С. 84 - 90.

11. Чебурахин И. Ф. Проблемы декомпозиции булевых функций и ее применений // Сб. докл. Межд. научно-техн. конф. "Актуальные проблемы фундаментальных наук" (СССР, Москва, 28 октября-3 ноября 1991 г.), том

2, Изд-во МГТУ им.Н.Э.Баумана. 1991. С.76.

12. Чебурахин И.Ф. Проблемы аппаратной и программной реализации булевых функций. М: МГТУ им.Н.Э.Баумана. 28 с. Деп. в ВИНИТИ 8.01.92, N 69.В92.Р.Ж. Математика, N 4,1992.

13. Cheburakhin I.F. The computer-aided design of optimal logical circuits and control programs // Abstracts International Aerospace Congress: Theory, Applications, Technologies IAC'94. August 15-19,1994, Moscow,Russia. P.445.

14. Чебурахин И. Ф. Точные оценки показателей качества параллельной обработки данных, получаемых с помощью структурной декомпозиции // Сб. 1-го Межд. Симпозиума "Интеллектуальные системы 94" ("INTELS'94") (22-27 июня 1994г. Россия, Дагестан, г.Махачкала). М.: Изд-во МГТУ, 1994. С. 147-151.

15. Чебурахин И.Ф. Точные, оценки сложности структурно-функциональной декомпозиции // Труды 2-й Межд. научно-технической конференции "Актуальные проблемы фундаментальных наук", том 1, часть 2, МГТУ им.Н.Э.Баумана, М.: Техносфера-информ, 1994. Стр. С-53 - С-56.

16. Cheburakhin I.F. The computer-aided design of optimal logical circuits and control programs // International Aerospace Congress: Theory, Applications, Technologies - IAC'94. August 1 5-19,1 994, Proceedings, Volume 2, Moscow, Russia. Publisher: STC "Petrovka",1995. P. 214-216.

17. Cheburakhin I.F. The Logical Control: Tasks and Estimates // Proceedings of the 9th International Conference "Systems for Automation of Engineering and Research"(SAER '95) and DECUS NUG Seminar '95, Sofia, 1995. P.85-89.

18. Чебурахин И.Ф. Функционалы качества для интеллектуальных САПР СБИС // Сб. материалов и сообщений 2-го Международного симпозиума "Интеллектуальные системы 96" (Россия, С-Петербург, 1996 г.). Т.2. М.: Изд-во ПАИМС. С.227-230.

19. Чебурахин И.Ф. Автоматизированное проектирование оптимальных логических схем // Тезисы докладов 2-го Международного аэрокосмического

гоконгресса 1АС97. Москва, Россия, 1997. Moscow, Russia. Publisher: STC "Petrovka", 1997. C.57.

20. Чебурахни И. Ф. Автоматизированное проектирование оптимальных логических схем // Труды 2-го Международного аэрокосмического конгресса IAC97. Том 1. Москва, Россия, 1997. Moscow, Russia. Publisher: STC "Petrovka", 1999. P. 1-68 -1-70.

21 . Чебурахин И.Ф. Некоторые показатели качества логических схем и программ // Труды III Межд.конф. "Дискретные модели в теории управляющих систем" (22-27 июня 1998г.). Москва: Диалог-МГУ, 1998. С.117-121. 22. Чебурахин И.Ф. Вопросы надежности некоторых параллельных дискретных устройств // Тез. Докл. Межд. научно-технической конф. МНТК-98 "Системы и комплексы автоматического управления в космонавтике и народном хозяйстве, посвященной 90-летию со дня рождения академика Н.А.Пилюгина", Москва, 18-21 мая 1998г. Москва: НПЦ АП, 1998. С. 12. 23.Чебурахин И.Ф. Функционалы качества для синтеза параллельных алгоритмов // Сб. докл. на 3-м Международном симпозиуме "Интеллектуальные системы" (INTELS'98) Россия, г. Псков, ЗОиюня - 4 июля 1998 г. М.: 00 0 ТВК. СЛ 92-194.

24.Чебурахин И.Ф. Показатели сложности, быстродействия и надежности некоторых дискретных устройств // Сб.докл. Межд. научно-технической конференции МНТК-98 "Системы и комплексы автоматического управления в космическом и народном хозяйстве", посвященной 90-летию со дня рождения академика Н.А.Пилюгина. М.: ГОНТИ-6. 1999, С. 124-128

25. Чебурахин И.Ф. Задачи автоматизации и оптимизации аппаратной и программной реализации булевых функций // Информационные технологии. 1999, №2. С. 28-34.

26. Чебурахин И.Ф. О показателях качества декомпозиции для некоторых классов булевых функций // Проблемы теоретической кибернетики. Тезисы докладов XII Международной конференции (Нижний Новгород, 17-22.05.1999г.) 4.2. М.: Изд-во механико-матем.ф-та МГУ, 1999.С.243.

27. Чебурахин И.Ф. О сложности и глубине схем из функциональных элементов // Труды IV Межд.конф. "Дискретные модели в теории управляющих систем"( 19-25 июня 2000г.). М.: "МАКС Пресс". 2000. С. 133-134.

28. Чебурахин И.Ф. Разработка компонентов автоматики для летательных аппаратов на основе логических методов // Тез.докл. "3-й Международный аэрокосмический конгресс IAC2000". Москва, Россия, 23-27 августа 2000. Изд-во СИП РИА, 2000. С.57.

28. Чебурахин И.Ф. Разработка компонентов автоматики для летательных аппаратов на основе логических методов // Докл. "3-й Международный аэрокосмический конгресс IAC2000". Москва, Россия, 23-27 августа 2000 г. (ISBN 5-89354-064-6 -электронный вид, издание 2003 г.). С.57.

29. Бородовский В Н., Чебурахин И.Ф. Система безопасности полетов летательных аппаратов. Тез.докл. "Третий Международный аэрокосмический

зз

конгресс 1АС2000". Москва, Россия, 23-27 августа 2000. Изд-во СИП РИА, 2000. С. 62-63.

30. Чебурахин И Ф. Аналитические методы в автоматизированном синтезе дискретных управляющих систем // Докл.: 1-я Всероссийская конференция "Спектральные методы обработки информации в научных исследованиях» ("СПЕКТР - 2000"), Институт математических проблем биологии РАН, 2428 октября 2000 г.Пущино. М.: 2000. ИМПБ РАН. С. 40-44.

31. Чгбурахин И.Ф. О некоторых классах булевых функций одной глубины // Материалы VII Международного семинара "Дискретная математика и ее приложения" (29.01-02.02 2001 г.). 4.1. Изд-во центра прикладных исследований при механико-математическом фак-те МГУ. М.: 2001. С.83-86.

32. Чебурахин И.Ф. Структурный синтез функциональных схем на основе математического моделирования // Тез.докл Международн.научно-техн. конф., посвященной 30-летию со дня основания МГТУ ГА "Гражданская авиация на рубеже веков" (30-31 мая 2001 г.). М.: 2001. С.266-267.

33. Чебурахин И.Ф. Математические средства аппаратной реализации булевых функций на основе структурно-функциональной декомпозиции // Информационные технологии. 2002, № I. С. 36 - 41.

34. Чебурахин И.Ф. Анализ и выбор оптимальных решений для автоматизированной системы синтеза функциональных схем // Труды Межд.научной конф. "Информационные технологии в естественных науках, экономике и образовании (16-21 апреля 2002 г. Саратов - Энгельс)". Саратов - Энгельс. 2002. С.419 - 421.

35. Чебурахин И Ф. Логическое управление: задачи, алгоритмы, показатели качества. М.: Изд.центр МАТИ-РГТУ им. К.Э. Циолковского. 2003. 200 с.

36. Чебурахин И.Ф. Методы декомпозиции булевых функций: алгоритмы, показатели качества, приложения // Изв. РАН. ТиСУ. №5. 2003. С.56 - 61.

37. Чебурахин И.Ф. Логическое управление цикловым манипулятором // Мехатроника, управление, автоматизация. № 4. 2004. С. 9-14.

38. Чебурахин И.Ф. Синтез быстродействующих дискретных логических устройств на основе структурно-функциональной декомпозиции // Изв. РАН. ТиСУ. №4. 2004. С.62 - 67.

чрормгп 60 х 84 '/,<,. Усл. печ. л. 1. Уч. изд. л. 0.7. Печать на ризографе. Тираж 100 экз. Заказ № 75

Ти1Ю1рафия Издательского центра МАТИ 109240. Москва. Берниковская наб.. 14.

H2Î04

Список обозначений.

Введение.

Часть 1. Основные математические модели цифровых интегральных схем.

Глава 1. Вычислительные и управляющие логические устройства: основные понятия, определения, задачи

1.1. Основные модели.

1.1.1. Булевы функции.

1.1.2. Конечные автоматы. Схемы из функциональных элементов и управляющие программы.

1.2. Декомпозиция и минимизация булевых функций

1.3. Монотонные системы и надежность.

1.4. Базисы.

1.5. Общие вопросы синтеза дискретных логических устройств.

1.6. Методы синтеза схем из функциональных элементов

1.7. Постановка задач.

Глава 2. Методы многошаговой декомпозиции булевых функций. Функционалы качества.

2.1. Основные модели.

2.2. Методы декомпозиции булевых функций.

2.3. Основные функционалы качества. Оптимизация.

Глава 3. Булевы функции и их математико-информационные модели.

3.1. Формулы, их строение и компьютерное представление

3.2. Отношения на множестве канонических формул. Разбиение множества формул на классы эквивалентности. Упорядочивание формул.

3.3. Конструктивные операции над формулами.

3.4. Порождающие и порожденные формулы.

3.5. Точные оценки мощности некоторых подклассов бесповторных формул, порожденных данной.

Часть 2. Многокритериальная оптимизация синтеза цифровых интегральных схем. Аналитическое решение.

Глава 4. Структурно-функциональная декомпозиция в классах функций &, v, ® и

4.1. Параллельная декомпозиция. Функционалы качества

4.2. Последовательная декомпозиция. Функционалы качества

4.3. Анализ показателей качества параллельной и последовательной декомпозиции

Глава 5. Структурно-функциональная параллельная декомпозиция в классах полиномов Жегалкина, ДНФ и КНФ.

5.1. Моделирование одного шага декомпозиции произвольной булевой функции.

5.2. Функционалы качества.

5.3 Принцип двойственности и декомпозиция.

5.4. Минимизация числа функций отрицания в классе ДНФ.

5.5. Способы декомпозиции. Математическая модель декомпозиции одной функции.

5.6. Исследование математической модели (базовый случай). Области минимизации показателей качества декомпозиции.

Глава 6. Анализ глубины произвольных булевых функций в стандартных базисах на основе параллельной декомпозиции

6.1. Конструктивные операции над строением булевой формулы.

6.2. Зависимость между значениями сложности и минимальной глубины бесповторной булевой формулы

6.3. Минимальная глубина бесповторной формулы и разбиения числа ее переменных на положительные целые слагаемые.

6.4. Продолжение исследования минимальной глубины бесповторной булевой формулы.

6.5. Основная зависимость минимальной глубины произвольной булевой формулы от ее сложности

6.6. Глубина некоторых симметрических функций.

6.7. Верхние оценки показателей качества декомпозиции в произвольном базисе.

Глава 7. Синтез схем из функциональных элементов и управляющих программ на основе структурнофункциональной декомпозиции.

7.1. Минимизация схем по сложности и глубине.

7.2. Минимизация числа транзисторов и времени задержки схем и числа команд в управляющих программах

7.3. Надежность схем из функциональных элементов. Математические модели.

Часть 3. Многокритериальная оптимизация синтеза цифровых интегральных схем на основе математического моделирования.

Глава 8. Моделирование структурно-функциональной параллельной декомпозиции системы булевых функций. Алгоритмы.

8.1. Оптимизирующие логико-комбинаторные преобразования.

8.1.1. Удаление фиктивных переменных.

8.1.2. Минимизация булевых функций. Скобочные формулы 177 # 8.1.3. Частичные булевы функции.

8.2. Моделирование декомпозиции произвольной булевой функции на основе функционалов качества.

8.3. Моделирование совместной декомпозиции систем булевых функций в базисе общего вида. Минимизация сложности.

8.4. Моделирование декомпозиции булевой функции в двухместном базисе. Минимизация глубины.

8.5. Анализ глубины схемы в различных базисах.

Глава 9. Математическое моделирование синтеза в базисе микросхем.

9.1. Математические модели микросхем.

9.2. Минимизация числа логических элементов.

9.3. Минимизация глубины схемы.

9.4. Синтез комбинационных автоматов в базисе ПЛМ

9.5. Методика программной реализации алгоритмов логического управления.

9.6. Описание программ.

9.7. Результаты вычислительного эксперимента.

Актуальность темы. Системы автоматического управления сложнейшими объектами и процессами, интеллектуальные пакеты прикладных программ, системы планирования вычислений, системы автоматизированного проектирования, экспертные системы - вот далеко не полный перечень аппаратных и программных систем, без которых немыслим сейчас научно-технический прогресс. Для всех таких и многих остальных систем общим является то, что они содержат или используют дискретные устройства обработки информации и управления (вычислительные и управляющие, логические устройства). Основная черта, выделяющая эти системы из остальных, состоит в том, что они содержат знания о проблемной области, в которой работают, и о своих возможностях по решению задач в ней [89].

Особое место в указанном списке занимают вычислительные системы. Взаимоотношения выше перечисленных систем с вычислительной техникой имеют две различные стороны: ЭВМ является основным инструментом исследований, включая моделирование, и будучи сами сложными системами выступают важными объектами исследований, при этом обязательно рассматриваются вопросы организации управления вычислительным процессом [52-55].

В значительной мере для описания, анализа и проектирования этих систем (устройств) используется аппарат математической кибернетики [26, 53-55, 116, 184, 196], из которого в диссертации, в основном, делается акцент на: формулы алгебры логики, реализующие булевы функции в данном базисе; схемы из функциональных элементов, реализующие системы булевых функций в данном базисе; конечные автоматы, реализующие преобразования входных последовательностей в выходные; программы (алгоритмы), вычисляющие заданные формулы по исходным данным. Поэтому этот математический аппарат является мощным средством для моделирования, при котором достаточно точно копируется не только функция объекта (процесса), но также и его структура, схема.

Заметим, что проектирование (аппаратное и программное) устройств обработки информации и систем логического управления в настоящее время характеризуется широким использованием достижений микроэлектроники. Элементной базой синтеза являются интегральные схемы малой, средней, большой, сверхбольшой и ультрабольшой степени интеграции (МИС, СИС, БИС, СБИС, УБИС). Тенденция к увеличению степени интеграции микросхем, сохраняющаяся в микроэлектронике, привела к созданию уже ультрабольших интегральных схем [3, 6, 16, 17, 24, 26, 64, 65, 81, 88, 98-100, 118, 137, 138, 140,141,184, 189,215-219, 291,293].

Создалась парадоксальная ситуация. Стремительное развитие микроэлектроники, проявляющееся в постоянном совершенствовании и в создании новых элементов базиса, содержащего микросхемы различной степени интеграции и различные микропроцессорные средства, с одной стороны, создает благоприятные предпосылки для разработки новых высокопроизводительных ЭВМ, вычислительных и управляющих систем с высокой степенью параллелизма обработки данных, а с другой стороны, ставит ряд трудно решаемых проблем перед разработчиками этой техники в отношении рационального использования всех имеющихся возможностей этого базиса [3, 16, 24, 26, 61, 63-65, 80, 88, 98, 99, 118, 127, 144, 154, 198, 213, 215, 216, 217, 291]. Алгоритмы функционирования управляющих устройств (алгоритмы логического управления - АЛУ) реализуются также программно на основе программируемых логических контроллеров [7,116, 117,137,138,140,141, 247, 284, 285].

В практике все шире применяются БИС, СБИС и УБИС. Это объясняется их возможностями и технико-экономическими характеристиками.

Но чтобы не принять необоснованную позицию в отношении использования БИС и других интегральных схем, в проектировании вычислительной и управляющей техники, обратимся к рекомендациям американского специалиста S.Muroga в монографии, посвященной проектированию БИС и СБИС, [144]: ".B некоторых случаях при создании цифровых систем предпочтительнее использовать схемы малой и средней степени интеграции, а не большой и сверхбольшой. Решение об использовании МИС, СИС или БИС принимается с учетом многих факторов. Благодаря гибкости и другим свойствам МИС и дискретных устройств потребность в них вряд ли исчезнет. Использование программируемых логических матриц (ПЛМ) существенно уменьшает время разработки благодаря применению процедуры минимизации, которая поддается автоматизации и может быть осуществлена с помощью САПР. Упрощается в этом случае и топологическая схема, что связано с регулярной структурой ПЛМ. В противоположность этому при логическом проектировании на основе нерегулярных логических схем временные затраты больше, но характеристики ИС, изготовленных подобным образом, лучше, а размеры кристалла меньше. При логическом проектировании в каждом случае необходимо сравнивать различные подходы к проектированию, оценивая, что мы выигрываем и что теряем".

Чтобы спроектировать эффективную интегральную схему, разработчик должен продумать широкий спектр вопросов - от исходного алгоритма работы интегральной схемы до ее топологии на кристалле [328], т.е. получить решение ряда задач аппаратной реализации булевых функций (синтеза логических схем). Ситуацию, сложившуюся в этой области, можно охарактеризовать следующим образом: "Нет способов приемлемой трудоемкости, позволяющих оптимальным образом реализовать каждую схему"[292]. Причиной этому является возрастающая сложность проектируемых систем.

Отметим еще мнение авторов монографии [292]: ". В практике разработки АСУ наметилась эволюция традиционных методов проектирования, постепенно, по мере усложнения систем, адаптирующаяся к новым особенностям задач и возможностям используемой дискретной техники.

На смену эволюционному подходу к проектированию должен прийти более прогрессивный, учитывающий новое качество - сложность проектируемых систем".

Вначале уточним, что мы понимаем под термином "сложность" с тем, чтобы получить возможность измерять или сравнивать сложности различных классов систем (объектов, процессов) [292]. Сложность задачи может характеризоваться размерностью - числом переменных, необходимых для описания функционирования системы. Сложность функционирования системы определяется минимальным временем, минимальной памятью или предельными значениями других характеристик. Задачи проектирования порождают и другие показатели сложности: уменьшение площади кристалла; уменьшение глубины схемы; уменьшение суммарной длины проводников между БИС и в них между элементами и числа пересечений этих проводников; увеличение плотности упаковки элементов в больших интегральных схемах; повышение надежности схем и др. При логическом проектировании комбинационных схем под сложностью схемы понимают минимальное число элементов заданного базиса, позволяющее реализовать любую булеву функцию [120-123]. Для логического проектирования БИС можно минимизировать сложность проектированного устройства при заданном быстродействии или минимизировать время выполнения операций при заданной сложности [118], а также число транзисторов в схеме [91, 189]. При программной реализации булевых функций, как правило, минимизируются показатели сложности программ: время их работы и память [69-71, 109-112].

Метод решения, реализующий сложность, является в некотором смысле наилучшим, наиболее экономным, наиболее простым из методов, решающих все задачи рассматриваемого класса [292].

Оценивание тех или иных показателей сложности, компонент вектора сложности класса систем (или класса задач), зависит от огромного числа факторов, с которыми каким-либо образом связаны исследуемые сложные системы. Это представляет собой необозримую задачу. Еще сложнее обстоит дело с проектированием. Вряд ли можно рассчитывать на разработку универсальных методов проектирования достаточно широких классов систем, об оптимизации уже не говорят [292].

В то же время "идея оптимизации, стремление к оптимальным, а не к любым допустимым решениям глубоко пронизывают современное проектирование. . Оптимизация решения на этапе организации проектирования экономит время и средства "[292].

Быстродействие (составляющая производительности) является одной из тех важнейших характеристик, которые служат для сравнения и выбора той или иной ЭВМ. Повышение быстродействия достигается разными средствами. Если рассматривать методы и алгоритмы, то последнее время характеризуется значительным числом работ, посвященных методам синтеза и оптимизации многоуровневой комбинационной логики [59, 61, 64, 65, 328]. Если рассматривать технические средства, то, например, наблюдается повышенный и обоснованный интерес к использованию оптических элементов, реализующих функции И, ИЛИ, НЕ-И или НЕ-ИЛИ, для синтеза комбинационных схем [329].

При проектировании СБИС невозможно скомпенсировать на более поздних этапах все дефекты, которые были допущены на ранних этапах.

При этом проблему быстродействия необходимо учитывать и решать на всех уровнях и этапах проектирования" [328].

Трудоемкость решения экстремальных задач различных классов часто оценивается минимальным числом операций, необходимых для решения с заданной точностью любой задачи класса. Теория сложности, основанная на подобных оценках, носит название машиннозависимой. Машин-нонезависимую оценку трудоемкости решения экстремальных задач непрерывных классов получают в терминах информационной сложности. Классы дискретных экстремальных задач разделяют по вычислительной сложности на две группы: с полиномиальной и с экспоненциальной сложностью. Можно ожидать, что рассматриваемые задачи характеризуются экспоненциальной сложностью. Трудоемкость их решения астрономически растет с размерностью (числом переменных) этих задач, что, в свою очередь, негативно сказывается на качестве решения. Поэтому необходимо раньше вводить и тщательно изучать различные показатели, характеризующие качество решения.

В подтверждение этому в [118] отмечается, что функциональная избыточность современных базисов и большая размерность практических задач в большинстве случаев не позволяет получить точное решение одно-критериальной задачи за приемлемое время даже на высокопроизводительных ЭВМ.

Тем не менее, целью разработчиков больших интегральных схем является создание эффективных методов синтеза схем как наиболее экономных (в смысле, определяемом выбранным показателем сложности) методов, гарантирующих требуемое качество решения любой задачи класса. Построение методов эффективного синтеза класса систем предполагает умение вычислять или оценивать сложность соответствующего класса задач. Оценка сложности класса задач или систем трудоемкая работа, сохраняющая свою актуальность в настоящее время [292].

12

Цель работы. Оптимальная (по различным показателям качества и по трудоемкости) реализация систем булевых функций в разных базисах представляет собой несомненно актуальную проблему, решение которой теснейшим образом связано с синтезом вычислительных и управляющих логических устройств в базисах микросхем различной степени интеграции и, можно сказать, обобщая другие приложения, прямо или косвенно положительно влияет на успехи в научно-производственной человеческой деятельности. Решение проблемы связывается с проведением исследований в следующих направлениях, определяющих тематические рамки диссертации.

- Разработка математических моделей для компьютерного представления булевых функций и на их основе различных преобразований, включая декомпозицию в разных базисах.

- Создание математических моделей, которые позволили бы, не синтезируя самой булевой формулы (или схемы из логических элементов), дать оценку возможности синтеза для различных показателей качества в зависимости от исходных данных.

- Исследование множества всех булевых функций с целью их экономного представления в различных базисах, включая минимизацию по сложности и глубине, а также установление зависимости между сложностью булевых формул (с повторением и без повторения переменных) и их минимальной глубиной.

- Разработка методов многокритериальной оптимизации (по сложности, по быстродействию и другим показателям качества; с ограниченной трудоемкостью) синтеза вычислительных и управляющих логических устройств в базисе микросхем на основе математического моделирования и проведение вычислительных экспериментов.

Научная новизна. Стержневую роль в диссертации играет разработка математических моделей для различных объектов и процессов, начи

13 нающаяся с представления исходных данных в виде определенных структур, на основе которых определяются операции и проводятся все исследования, и завершающаяся на этапе синтеза устройств.

В диссертации можно выделить два фундаментальных понятия общей теории систем - это структура (строение) и декомпозиция [88, 136], благодаря которым в определенных рамках получено решение проблемы оптимальной или близкой к ней (по числу транзисторов, логических элементов, микросхем; глубине и др.) реализации булевых функций в базисе микросхем. Использовались эти понятия по-новому. В диссертации строение это основа математико-информационного (многоуровневого) описания булевой формулы (и бесповторной функции); многоуровневое описание булевых формул, предполагающее использование всех или определенных уровней для решения той или иной поставленной задачи, является новым [232, 252, 279]. Например, для нахождения глубины бесповторной булевой функции в двухместном базисе (конъюнкция и сложение по модулю два) достаточно знать ее строение [279, 280].

Методы синтеза схем на основе функциональной декомпозиции известны [16, 26-28, 39, 55, 70, 159, 164]. Отличие их (и других) от методов, предлагаемых в диссертации, состоит в подходе к самой декомпозиции и отсутствием достаточной степени (уровней) формализации функций. Как следствие, в них вопросы оптимизации качества по сложности (числу базисных элементов), глубине и другим показателям качества схем для вычислительных и управляющих логических систем остаются открытыми.

В диссертации определен принципиально иной подход к декомпозиции, т.е. декомпозиция есть явный многошаговый процесс преобразования функции (в суперпозицию функций) в заданном базисе и выполняемая она на основе строения функции или формулы становится структурно-функциональной декомпозицией. Таким образом, результат декомпозиции зависит от конкретной функции, базиса и способа преобразования. Это

14 позволило для основных показателей сложности - числа подформул и глубины - определить функционалы (показатели качества декомпозиции) для каждой конкретной булевой функции из множества всех булевых функций (зависящих от любого конечного числа переменных), на множестве базисов и способов декомпозиции (вариантов преобразований). Из других методов, характеризующихся получением оценок, являются асимптотические методы [8-13, 120-123, 210-212]. Однако данный подход к получению оценок сложности отличается от подходов, характеризующихся получением асимптотических оценок уже тем, что в них функционалы качества используют функцию Шеннона и определяются они не для конкретной функции, а для множества всех функций от п переменных. Особо отметим, что для методов, развиваемых в диссертации, функционалы качества определяются для каждой конкретной функции, но результат (минимальный или близкий к нему, аналитически или на основе математического моделирования) получается для отдельных классов функций. При этом в основу данного подхода заложены различные модели декомпозиции булевых функций, которые можно сравнивать и выбирать требуемую модель на основе значений их показателей качества.

Перечислим по главам полученные впервые и освещенные в диссертации научные результаты.

Выводы

Для обеспечения безопасности полета летательных и космических аппаратов в главе :

- разработаны и сформулированы общие принципы для оптимального разведения в пространстве двух летательных аппаратов;

- разработаны основные дискретные математические модели (для различных возможных ситуаций), позволяющие получать оптимальное разведение в пространстве двух летательных аппаратов, выполняющих движение навстречу по пересекающимся или близко расположенным траекториям;

- рекомендована общая структура управляющего цифрового автомата, реализуемого в базисе микросхем различной степени интеграции.

Рис. 11.15. Общая схема арифметического устройства для моделирования движения JIA

-1 -L

МО — g1 н — h — m — o(t) P ~

Q -v —

I +

1Г я Ж

Tga

-p + q v„ -h- * r.+H

4 r.+H

Ущ". r. + H h-V„ r.+H xz{t + h)

V .т ч X

X 1

V-m-TgG J

V^-m-Tga г, +Я p-Q

Sin

Sin у/

-P + Q)Sinw

Cos

Cosy

Cos

Cosy

P-Q)Cosv

V*'Vm-m-Tgi7 r3 + Я w-Tgg K + H

Z ■ Sin I//-Cosy

Z-Cosy/ Cosy

4L

V!g(t + h)

4i

P - Q) ■ Cos ty + Z Sim// Cosy n + H

-P + Q) ■ Sin 1// + Z- Cosy/- Cosy +

Ущ -m-Tga г3 + Я

P-QDCosip + ZSiny/Cosy

-P + Q)-Sini// + Z- Cos у ■ Cos у + r, + H

V^ -m-Tga r, + H

P-Q)- Cos t// + Z- Sin ц/ - Cosy

-P + Q)-Siniff + Z- Cosy- Cosy

Z-Cosy

Рис.11.16. Структурно-логическая схема арифметического устройства для моделирования движения ЛА

268

ЗАКЛЮЧЕНИЕ

Настоящая диссертационная работа подытоживает многолетние исследования автора в отношении экономной по многим показателям реализации системы булевых функций в различных базисах с ограниченной трудоемкостью, поднятых в его кандидатской диссертации [246]. Объектом диссертационного исследования являются дискретные устройства обработки информации и управления, получаемые на основе микросхем различной степени интеграции, а предметом - математические модели этих устройств, обеспечивающие их синтез, характеризуемый оптимальными или близкими к ним значениями показателей сложности (качества).

Разработанные алгоритмы и методы в совокупности с результатами проведенных исследований создают теоретико-методологические основы решения проблемы - оптимальной реализации системы булевых функций в различных базисах микросхем с ограниченной трудоемкостью.

Основные научные результаты и выводы работы : 1. Разработаны основные математические модели и проведен их анализ с целью применения результатов для оптимального или близкого к нему (по сложности, глубине, надежности) синтеза вычислительных и управляющих логических устройств в базисе микросхем различной степени интеграции. 1.1. Разработана новая многоуровневая модель компьютерного представления булевых произвольных и бесповторных функций (на основе их строения) в заданном базисе, позволяющая:

- задавать булевы функции;

- разбивать множество функций (формул) на классы эквивалентности;

- упорядочивать множество формул;

- автоматизировать и распараллеливать процесс вычисления булевых формул;

- использовать математико-информациоииое описание формул для выполнения различных преобразований, включая минимизацию и декомпозицию;

- определять порождающие и порожденные функции и подсчитывается их число.

1.2. Разработаны экстремальные методы параллельной и последовательной (частично использовался) декомпозиции булевых функций (в общем виде и на основе понятия строение таких формул, как полином Жегалкина, ДНФ, КНФ и др.) как многошаговый процесс; получены решения задач минимизации функционалов качества (по числу подформул и глубине получаемой суперпозиционной формулы) декомпозиции, которые для некоторых классов булевых функций доставляют минимальные значения, а для остальных классов и некоторых стандартных базисов позволяют получать минимальные значения на основе математического моделирования; выполнено сравнение методов по сложности и глубине, которое показало преимущество метода параллельной декомпозиции перед методом последовательной декомпозиции в отношении глубины (не больше) получаемой суперпозиционной формулы при совпадении результатов в отношении числа подформул; метод параллельной декомпозиции для отдельных классов булевых функций, зависящих от любого конечного числа переменных, характеризуется получением минимальных значений числа подформул и/или глубины получаемой суперпозиционной формулы (получены условия для проведения многокритериальной минимизации).

1.3. Проведено исследование множества всех булевых функций с целью их экономного представления в некоторых базисах, включая минимизацию по сложности и глубине, а также с целью установления зависимости между сложностью булевых формул (с повторением и без повторения переменных) и их минимальной глубиной; определен подход к получению разбиения множества булевых функций на классы функций одной глубины и получены некоторые классы такого разбиения; предложен подход к получению глубины скобочных формул.

2. Разработаны методы анализа и синтеза вычислительных и управляющих логических устройств в базисе микросхем различной степени интеграции на основе математического моделирования, которые позволяют оптимизировать устройства по быстродействию (глубине), по числу транзисторов, логических элементов, микросхем и по различным показателям надежности (с ограниченной трудоемкостью).

2.1. Разработаны алгоритмы для моделирования процессов совместной декомпозиции системы булевых функций (с минимизацией числа функций в системе суперпозиций) и раздельной декомпозиции булевой функции в двухместном базисе (с минимизацией глубины), а также - для приведения формул к скобочному виду.

2.2. Разработаны методы синтеза сетей из микросхем, включая БИС (БМК, ПЛМ), на основе декомпозиции, позволяющие в зависимости от параметров исходного описания задачи заранее оценивать качество синтеза по числу транзисторов, логических элементов, микросхем и глубине (эффективным по этим показателям качества) с ограниченной трудоемкостью.

2.3. Проведено исследование методов синтеза сетей в отношении возможностей их оптимизации по различным показателям надежности; получено, что метод синтеза на основе последовательной декомпозиции по сравнению с методом - параллельной декомпозиции является более чувствительным к отказам типа разрыв.

3. Разработаны программы для ЭВМ на основе рекомендованных методов и алгоритмов, позволяющие моделировать различные преобразования булевых формул (такие как минимизация, экономное доопределение частичных булевых функций, параллельная декомпозиция с многокритериальной минимизацией показателей качества - по числу подформул и глубине); разработана методика моделирования: совместной параллельной декомпозиции системы булевых функций с минимизацией числа функций в системе суперпозиций; параллельной декомпозиции булевой функции в двухместном базисе с минимизацией глубины. Проведение вычислительных экспериментов подтвердило состоятельность и эффективность проведенных исследований, разработанных методов и алгоритмов.

4. Решены актуальные теоретико-прикладные задачи анализа и синтеза . (разработаны: управляющий автомат для адаптивного робота, принцип разведения и математические модели для обеспечения безопасности движения летательных аппаратов) на основе методологии структурно-функциональной декомпозиции.

4.1. Предложен принцип геометрического кодирования для логического управления адаптивным роботом. Разработаны алгоритмы, использующие модели теории конечных автоматов и реализованные аппаратно и программно, такого управления роботом.

4.2. Разработаны основные дискретные математические модели для обеспечения безопасности полета летательных аппаратов и предложен оптимальный принцип (по их разведению); определена иерархическая структура цифровго автомата для разведения в пространстве двух летательных аппаратов, летящих по пересекающимся или близко расположенным траекториям.

Итак, в работе изложен метод синтеза формул (и схем) из функциональных элементов, который для различных классов булевых функций позволяет строить формулы (схемы), оптимальные или близкие к ним по критериям: по сложности и/или глубине. Метод параллельной декомпозиции позволяет проводить совместную декомпозицию системы булевых функций, оптимизируя формулы (схемы) на этапе логического проектирования. Этот метод допускает варианты для оптимизации на последующих этапах синтеза и применим для базисных элементов широкого диапазона, а также при программной реализации булевых функций на логических контроллерах [5,131, 38, 60,101].

В практике решения различных вычислительных задач, например решения дифференциальных уравнений, возникает необходимость в уменьшении объема вычислений или распараллеливании вычислений [36, 46 - 49, 51, 75 -78, 83, 93 - 95, 129, 132]. Из отмеченных выше свойств параллельной декомпозиции следует, что она с успехом может применяться при решении таких задач [235].

1. Абалакин И.В., Жохова А.В., Четверушкин Б.Н. Разностные схемы на основе кинетического расщепления вектора потока // Математическое моделирование. Т. 12, № 4, 2000. с.73-82.

2. Абалакин И.В., Антонов А.Н. и др. Использование кинетически согласованных разностных схем для расчета характеристик шума сверхзвуковых турбулентных струй // Математическое моделирование. Т. 13, № 10, 2001. с.56-76.

3. Автоматизированное проектирование СБИС на базовых кристаллах / Петренко А.И., Лошаков В.Н. и др. М.: Радио и связь, 1988.

4. Авгуль Л.Б., Супрун В.П. Декомпозиция булевых функций на основе полиномиального разложения // Изв. АН СССР. Техн. киберн. 1989. № 3.

5. Акритас А. Основы компьютерной алгебры с приложениями. Москва. Мир. 1994.

6. Алексенко А.Г., Шагурин И.И. Микросхемотехника. М.: Радио и связь, 1982. 414 с.

7. Амбарцумян А.А., Малевич А.Н. и др. Структура системы автоматизированного проектирования логического управления, реализуемого на программируемых контроллерах (система ФОРУМ-М). В кн.: Проектирование логического управления. - М.: Наука, 1984.

8. Андреев А.Е. Об одном методе получения нижних оценок сложности индивидуальности монотонных функций // Докл. АН СССР. 1985. - Т. 282. - № 5.

9. Андреев А.Е. О минимизации булевых функций. ДАН СССР. 1984.- Т. 274, № 2.

10. Андреев А.Е. О сложности монотонных функций. т. 283, N 2, с. 265 -269. ДАН СССР, 1984, т. 277, № 3, с. 521 - 525.

11. Андреев А.Е. О синтезе самокорректирующихся схем. ДАН СССР. -1984. - Т. 277, № 3, с. 521 - 525.

12. Андреев А.Е. Математический сборник, 1985, т. 127 (169), № 6, с. 147 -172.

13. Андреев А.Е. О синтезе вентильных схем. 1985. т. 282, № 5,1985.

14. Анишин Н.С. Микропроцессорная реализация аналитических функциональных преобразований // Межвуз. сб.: Организация вычислительных структур и процессов. Вып. 11. Проектирование функционально-ориентированных систем. Л.: Изд-во ЛГУ, 1990.

15. Арбиб М.А. Алгебраическая теория автоматов, языков и полугупп. М.: Статистика. 1975.

16. Артюхов В.JI., Копейкин Г.А., Шалыто А.А. Настраиваемые модули для управляющих устройств. Л.: Энергоиздат, 1981.

17. Артюхов А.А., Викеитьев Л.Ф., Аляев Б.А. Автоматизация синтеза судовых комбинационных схем из настраиваемых модулей. Л.: 1985.

18. Байхельт Ф., Франкен П. Надежность и техническое обслуживание. Математический подход. -// Пер. с немецк. М.: Радио и связь, 1988.

19. Басманов А.С., Широков Ю.Ф. Микропроцессоры и однокристальные микро-ЭВМ: номенклатура и функциональные возможности. / Под ред. В.Г.Домрачева. М.: Энергоатомиздат, 1988.

20. Баранов С.И., Журавина Л.Н., Кожина В.Б., Левин И.С., Межин Н.Н., Песчанский В.А. Система автоматизации логического проектирования дискретных устройств. В сб.: Автоматизация проектирования / под. общ. ред. В.А.Трапезникова. - М.: Машиностроение, 1986.

21. Баранов С.И., Синеев В.Н., Янцен Н.Я. Синтез автоматов с матричной структурой // Межвуз. сб.: Организация вычислительных структур и процессов. вып. 11. - Проектирование функционально-ориентированных систем.- Л.: изд-во ЛГУ, 1990.

22. Барлоу Р., Прошан Ф. Статистическая теория надежности и испытания на безотказность.- М.: Наука, 1984.

23. Беляев Ю.К., Богатырев В.А. Надежность технических систем : Справочник. Под ред. Ушакова И.А. М.: Радио и связь. 608 с.

24. Берски Д. Лазерное программирование позволяет быстро разрабатывать матрицы на 18 ООО вентилей. Электроника, № 17/18 (879), 1992.

25. Берски Д. Булева верификация как способ ускоренного сравнения нового и старого вариантов логической схемы. / Электроника, № 15, 1991.

26. Бибило П.Н., Енин С.В. Синтез комбинационных схем методами функциональной декомпозиции. Минск: Наука и техника, 1987.

27. Бибило П.Н. Декомпозиция булевых функций (обзор) // В кн.: Проектирование устройств логического управления. М.: Наука, 1983.

28. Бибило П.Н. Декомпозиция булевых функций на основе решения логических уравнений. I // Изв. РАН. ТиСУ. 2002. №4.

29. Бородовский В.Н., Чебурахин И.Ф. Тенденции и проблемы подготовки бакалавров технических наук по кафедре Кибернетика И Тез. докл. Межд. конф. по инженерному образованию (UNESCO, ICEE'95), май 23-25,1995, Москва, Россия. Стр.

30. Бородовский В.Н., Чебурахин И.Ф. Тенденции и проблемы подготовки инженеров по кафедре Кибернетика II Тез. докл. Межд. конф. по инженерному образованию (UNESCO, ICEE'97), июнь 10-12, 1997, С-Петербург, Россия.

31. Бородовский В.Н., Чебурахин И.Ф. Система безопасности полетов летательных аппаратов // Тез.докл. «Третий Международный аэрокосмический конгресс 1АС2000». Москва, Россия, 23-27 августа 2000 г. стр.

32. Бохман Д., Постхоф X. Двоичные динамические системы. Москва, Энергоатомиздат, 1986. 401 с.

33. Бутаков Е.А., Волынский М.Б., Новоселов В.Г. Диагностика программируемых логических матриц. М.: Радио и связь, 1991. - 158 с.

34. Бухгольц Н.Н. Основной курс теоретической механики. Ч. 1 и 2. Москва. Наука. 1966. 799 с.

35. Валицкас А.И. Алгоритм деления булевых функций в задачах много уровневого логического синтеза // Автометрия. -1991. № 5. - с. 119 - 123.

36. Василевский А.М., Кропотник , Тихонов В.В. Оптическая электроника. JL: Энергоатомиздат, 1990. - 176 с.

37. Ватанабэ Э. Отказоустойчивые ВС // BIT (Jap), 1987. v. 19, p. 12011216.

38. Ващенко В.П. // Докл. АН СССР. 1979. Т. 247, № 1. с. 15-18.

39. Вентцель Е.С. Теория вероятностей. Москва, Наука, 1969. 576 с.

40. Винокуров С.Ф. Операторы в полиномиальных представлениях булевых функций // Автореферат дисс.на соискание ученой степени д.ф.-м.н. Иркутск. 2001. 27 с.

41. Воеводин В.В. Математические модели и методы в параллельных процессорах. М.: Наука, 1986. - 296 с.

42. Воклер И.Э. Алгоритм формульной декомпозиции булевых функций в бесповторных базисах // Механизация и автоматизация управления. 1976. №1.

43. Гавриленко П.П. Простой универсальный контроллер с микропрограммным управлением. / Сб.: Микропроцессорные средства обработки информации в системах управления и связи. Под ред. И.Е.Соловейчика.-М.: Радио и связь, 1988. С. 37 41.

44. Гаврилов М.А. Теория релейно-контактных схем. Москва. Изд-во АН СССР. 1950 г. 304 с.

45. Гаврилов М.А. Декомпозиция комбинационных автоматов. В кн.: Избр. тр. Теория релейных устройств и конечных автоматов. М.: Наука, 1983.

46. Гаврилов М.А., Девятков В.В., Пупырев Е.И. Логическое проектирование дискретных автоматов. М.: Наука, 1977.

47. Гаврилов М.А., Девятков В.В. ДАСП диалоговая автоматизированная система проектирования дискретных управляющих устройств общепромышленного назначения // В кн.: Дискретные системы, т. 3. Рига: Зинатне, 1974.

48. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. Москва. Наука. 1992. 406 с.

49. Гантмахер Ф.Р. Лекции по аналитической механике. Москва. Наука. 1966. 300 с.

50. Гашков С.Б. Сложнореализуемые булевы функции и трудновычислимые действительные числа. Том 3 вып.1. 1991г. «Дискретная математика».

51. Гессель М., Согомонян Е.С. Построение самотестируемых самопроверяемых комбинационных устройств со слабонезависимыми выходами //АиТ, N8, 1992.

52. Глушков В.М., Молчанов И.Н. О некоторых проблемах решения задач на ЭВМ с параллельной организацией вычислений. Кибернетика, 1981, N 4, с. 82-88.

53. Глушков В.М. Кибернетика, вычислительная техника, информатика. Избранные труды в трех томах. Том 1. Математические вопросы кибернетики. Киев. Наукова думка. 1990. 260 с.

54. Глушков В.М. Кибернетика, вычислительная техника, информатика. Избранные труды в трех томах. Том 2. ЭВМ техническая база кибернетики. Киев. Наукова думка. 1990. 221 с.

55. Глушков В.М. Кибернетика, вычислительная техника, информатика. Избранные труды в трех томах. Том 3. Кибернетика и ее применение в народном хозяйстве. Киев. Наукова думка. 1990. 265 с.

56. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. 2-е изд. М.: Наука, 1987.

57. Гнеденко Б.В. Курс теории вероятностей. Москва, Наука, 1969. 400 с.

58. Головкин Б.А. Параллельные вычислительные системы. М.: Наука. 1980. 520 с.

59. Горбатов В.А. Синтез логических схем в произвольном базисе. В кн.: Теория дискретных автоматов. Рига: Зинатне, 1967.

60. Горбатов В.А. Фундаментальные основы дискретной математики. Москва. Наука. Физматлит. 1999.

61. Горбатов В.А., Кафаров В.В., Павлов П.Г. Логическое управление технологическими процессами. М.: Энергия, 1978.

62. Горовой В.Р. Синтез релейных структур методом замены выходных функций // АиТ. 1967. № 1.

63. Горяшко А.П. Логические схемы и реальные ограничения: методы синтеза, оценки сложности. М.: Энергоатомиздат, 1982. 184 с.

64. Гош Д. Европейская конференция по ИС 1991 г. перспективный взгляд на технологию будущего. Электроника, № 17 (869), 1991.

65. Гош Д. Глобальные перспективы технологии производства электронных компонентов и ИС // Электроника, № 17 (869), 1991.

66. Давиташвили Т.Д., Елизарова Т.Г., Криадо Ф. и др. О сходимости кинетически-согласованных разностных схем для одномерных уравнений газовой динамики // Математическое моделирование. Т. 13, № 4, 2001.

67. Дуйсекулов А.Е., Елизарова Т.Г. Использование многопроцессорных вычислительных систем для реализации кинетически-согласованных разностных схем газовой динамики // Математическое моделирование. Т. 2, №7,1990. с.140-148.

68. Девенпорт Дж., Сирэ И., Турнье Э. Компьютерная алгебра. Москва. Мир. 1991.

69. Девятков В.В., Чичковский А.Б. УСЛОВИЕ-82 язык для описания работы дискретных управляющих устройств // В кн.: Абстрактная и структурная теория релейных устройств. М.: Наука, 1984.

70. Девятков В.В. Стековая программная реализация алгоритмов логического управления // В кн.: Проектирование устройств логического управления. М.: Наука, 1984.

71. Девятков В.В. Программная реализация управляющих алгоритмов // В кн.: Автоматизированное проектирование дискретных управляющих устройств. М.: Наука, 1980.

72. Девятков В.В. Алгебраический метод автоматизации логического проектирования структур дискретных управляющих систем по описанию на языках различного уровня // Дисс. . докт. техн. наук. М., 1979.

73. Дичюнас В. Сравнение мощности некоторых классов логических схем //Математическая логика и ее применение, вып. 4. Вильнюс, 1985.

74. Дмитриев А.А., Зенкевич С.Л. Логическое управление адаптивным ро-бототехническим комплексом // Изв. АН СССР. Техническая кибернетика. 1986. № 3.

75. Ершов А.П. Теоретическое программирование. М.: Наука, 1984.

76. Журавлев Ю.И. Алгоритм построения минимальных дизъюнктивных нормальных форм для функций алгебры логики // В кн.: Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974

77. Журавлев Ю.И. Теоретико-множественные методы в алгебре логики // Проблемы кибернетики. 1962. №8.

78. Задыхайло И.В., Зеленский С.Д. Механизм синхронизации в языках параллельного программирования // Изв. АН СССР. Техн. кибер. 1985, № 5.

79. Закревский А.Д. Логический синтез каскадных схем. М.: Наука, 1981.

80. Закревский А.Д. Автоматизация логического синтеза дискретных устройств//Кибернетика. 1975, №4. С. 100-108.

81. Закревский А.Д. К теории параллельных алгоритмов логического управления // Изв. АН СССР. Техн. кибернетика. 1989, № 5. с. 179 -191.

82. Иванов А.Г. Распознавание вхождения слов в реальное время на конечных многоголовных автоматах // Вопросы кибернетики. Сложность вычислений и прикладная математическая логика. Под ред. Адяна С.И. Вып. 134. М., 1988. с. 72 103.

83. Ильвовский А.В. Методика и средства построения генераторов программ для программируемых контроллеров. В кн. Управление сложными техническими системами. М., 1987.

84. Ильин В.П., Фет Я.И. Параллельный процессор для решения задач математической физики. Новосибирск, 1979.36 с. ( Препринт ВЦ СО АН СССР: № 217).

85. Ильин В.П., Фет Я.И. Параллельный процессор для решения разностных уравнений Пуассона // Изв. АН СССР. Техн. кибернетика, 1979, № 5, с. 200 204.

86. Ильин В.П., Фет Я.И. Распараллеливание неявных сеточных методов на универсальном матричном процессоре // М.: 1982. 16 с. ( Препринт ОБМАН СССР: №27).

87. Ильин В.П., Фет Я.И. Семейство параллельных процессоров для задач математической физики // В кн.: Вычислительные процессы и системы. Вып. 1. М.: Наука, 1983, с. 81 99.

88. Интеллектуальные системы автоматизированного проектирования больших и сверхбольших интегральных микросхем // В.А.Мищенко, JI.M. Городецкий, Л.И.Гурский и др.; Под ред. В.А.Мищенко. М.:Радио и связь, 1988. 272 с.

89. Кандрашина Е.Ю., Литвинцева Л.В., Поспелов Д.А. Представление знаний о времени и пространстве в интеллектуальных системах. М.: Наука. 1989. 328 с.

90. Карпова Н.А. Минимальные схемы из замыкающих контактов для монотонных функций пяти переменных // Проблемы кибернетики. 1973. Вып. 26.

91. Касим-Заде О.М. О сложности реализации булевых функций в одной модели электронных схем // Математические вопросы кибернетики. Под ред. С.В. Яблонского. Вып. 2. Москва. Наука. 1989. С. 145 160.

92. Карцев М.А., Брик В.А. Вычислительные системы и синхронная арифметика. М.: Радио и связь, 1981. 360 с.

93. Квиттнер П. Задачи. Программы. Вычисления. Результаты. Москва, Мир, 1980.

94. Киносита К., Асада К., Карацу О. Логическое проектирование СБИС. М.: Мир, 1988.

95. Коган А.Ю. Дизъюнктивные нормальные формы булевых функций с малым числом нулей. Каталог функций с четырьмя нулями // ВЦ АН СССР, 1986, 18 с.

96. Козлов Б.И., Ушаков И.А. Справочник по расчету надежности. М.: Сов. радио, 1975. 472 с.

97. Коломейко В.В. Выполнение базовых вычислительных процедур в специализированных ЭВМ микроцессорах//Кибернетика, 1990. №4. с. 117-120.

98. Компьютеры на СБИС, т.1, 2 / Мотоока Т., Томита С. и др. М.: Мир,1988.

99. Конструирование аппаратуры на БИС и СБИС. Борисов В.Ф, Боченков Ю.И. и др. Под ред. Высоцкого Б.Ф. и Сретенского В.Н. М.: Радио и связь.1989.

100. Коневцев В.А., Казаченко А.П., Бабаянц А.В. Разработка математического обеспечения автоматических систем управления. В сб.: Автоматизация проектирования / Под общ. ред. В.А.Трапезникова. М.: Машиностроение, 1986.

101. Конкоран Э. Тенденция развития вычислительной техники. СуперЭВМ: архитектура и возможности // Мир науки, том 35, № 3, 1991.

102. Коновалов А.Н., Бугров А.Н., Блинов В.Д. Алгоритмы распараллеливания сеточных задач // В кн.: Актуальные проблемы вычислительной и прикладной математики. Новосибирск: Наука, 1983, с. 95 99.

103. Котов В.Е. Формальные модели параллельных вычислений. Новосибирск, 1979. 56 с. Препринт ВЦ СО АН СССР: № 165.

104. Кричевский Р.Е. Лезвие Оккама и частичные булевы функции // Оптимизация. 1990. №48. С. 88-95.

105. Кроль В.М., Таненгольц Л.И. Логическое исчисление для решения задач в сильно структурированных предметных областях //АиТ,1988, № 2, с. 127 136.

106. Крылов А.В., Федоров И.В. Оценка сложности логических систем промышленной автоматики // В кн.: Измерение эффективности и качества в больших системах. М.: МДИТП им.Ф.Э.Дзержинского, 1980.

107. Кузнецов О.П. О программной реализации логических функций и автоматов//АиТ. 1977. №7,9.

108. Кузнецов Б.П., Шалыто А.А. Система преобразований некоторых форм представления булевых функций // АиТ. 1985. №11.

109. Кузнецов О.П., Шипилина Л.Б. Методы синтеза автоматов, описанных на языке ЯРУС. ИФАК. 1974.

110. Кузьмин В.А. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ //В кн.: Методы дискретного анализа в теории кодов и схем. Новосибирск, 1977, вып. 29.

111. Кук Д., Бейз Г. Компьютерная математика. Москва. Наука. 1990.

112. Кучеров А.Б., Николаев Е.С. Параллельные алгоритмы итерационных методов с факторизованным оператором для решения эллиптических краевых задач // Дифференциальные уравнения, 1984, 20, № 7, с. 1230 -1237.

113. Кучеров А.Б., Николаев Е.С. Параллельные и конвейерные алгоритмы попеременно-треугольного итерационного метода. В кн.: Разностные методы математической физики // М.: Изд-во МГУ, 1984, с. 66-83.

114. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов // М.: Энергия, 1978.

115. Лихонинский B.C. Программный метод расчета логических функций, заданных в КНФ // Приборы и системы управления, № 8, 1988, с. 14.

116. Логическое проектирование БИС // Под ред. В.А.Мишенко. М.: Радио и связь, 1984.

117. Ложкин С.А. О связи между глубиной и сложностью эквивалентных формул и о глубине монотонных функций алгебры логики // Проблемы кибернетики. Вып. 38. М.: Наука. Гл.ред.физ.-мат.лит. 1981.

118. Лупанов О.Б. О сложности реализации функций алгебры логики формулами // Проблемы кибернетики, № 3, М.: Наука, 1960.

119. Лупанов О.Б. О схемах из функциональных элементов с задержками // Проблемы кибернетики, вып. 23, М.: Наука, 1970.

120. Лупанов О.Б. Об одном подходе к синтезу управляющих систем -принципе локального кодирования // В кн.: Проблемы кибернетики. Вып. 14. М.: Наука, 1965.

121. Лупанов О.Б. Асимптотические оценки сложности управляющих систем // М.: Изд-во МГУ, 1984.

122. Лурье А.И. Аналитическая механика. Москва. Физматгиз. 1961.

123. Максимов В.И. Интеграция видов избыточности в отказоустойчивых системах управления // Принципы обеспечения отказоустойчивости многопроцессорных вычислительных систем / Сб. тр. ИПУ, М.: 1987. с. 74 -80.

124. Малиньяк JI. Пакет логического моделирования, сочетающий высокие быстродействие и точность с большими предельными возможностями // Электроника , № 15 (867), 1991.

125. Малиньяк JL Логическая эмуляция эффективный инструмент параллельного проектирования цифровых устройств и систем // Электроника, 1992, № 15/16.

126. Малиньяк Л. На пути к параллельному проектированию // Электроника. 1993. №1-2.

127. Малюгин В.Д. Реализация булевых функций арифметическими полиномами // АиТ. 1982. № 4.

128. Марков А.А. О вычислении функций алгебры логики системами формул ограниченной сложности// Дискретная математика, 1992, том 4, вып. 4.

129. Марковский А.В. Шипилина Л.Б. О машинной реализации операций со скобочными булевыми выражениями. Сб. Алгоритмические исследования в комбинаторике. М.: Наука. 1978. с. 172-183.

130. Марчук Г.И., Ильин В.П. Параллельные вычисления в сеточных методах решения задач математической физики// Новосибирск, 1979. 23 с. Препринт ВЦ СО АН СССР: N 220.

131. Математическая логика в программировании. Москва, Мир, 1991.

132. Медведев А.И. Общий метод оценки надежности невосстанавливае-мых систем.// Надежность и контроль качества. 1988. N2. с. 21 -26.

133. Медведев B.C., Лесков А.Г., Ющенко А.С. Системы управления ма-нипуляционных роботов. Москва. Наука. 1978.

134. Месарович М., Такахара Я. Общая теория систем: математические основы. Москва. Мир. 1978. 311 с.

135. Мещеряков В.М. и др. Комплект БИС К1804 в процессорах и контроллерах. М.: Радио и связь, 1990. 256 с.

136. Микропроцессорные средства диспетчеризации, автоматики и телемеханики Микро-ДАТ // М.Д. Гаранович и др. М.: ЦНИИТЭИ приборостроения, 1984, вып.5.

137. Миренков Н.Н. Параллельное программирование для многомодульных вычислительных систем. М.: Радио и связь, 1989, 320 с.

138. Мишель Ж., Лоржо К., Эспьо Б. Программируемые контроллеры. М.: Машиностроение, 1986.

139. Мишель Ж. Программируемые контроллеры: архитектура и применение. Москва. Машиностроение. 1992. 320 с.

140. Моисеев Н.Н. Математические задачи системного анализа. Москва. Наука. 1981.487 с.

141. Мюллер Д.Е., Препарата Ф.П. Перестроение арифметических выражений для параллельного вычисления // В кн.: Кибернетический сборник. Вып. 16. М.: Мир, 1979, с. 5 22.

142. Мурога С. Системное проектирование сверхбольших интегральных схем. Книги 1 и 2. М.: Мир, 1985.

143. Надежность и эффективность в технике: Справочник. Т. 2. Математические методы в теории надежности и эффективности / Под ред. Гнеденко Б.В. М.: Машиностроение, 1987.

144. Надежность и эффективность в технике. Т. 5. Проектный анализ надежности. Под ред. Петрушева В.И., Рембезы А.И. М.: Машиностроение, 1988.

145. Накано Э. Введение в робототехнику. М.: Мир. 1988.

146. Нгуэн Ким Ань. О некоторых характеристиках алгоритмов минимизации булевых функций // ДАН СССР. 1983. Т. 267, № 5.

147. Некоторые основополагающие вопросы управления качеством ПО. Экспесс-информация, сер. И. Автоматизир. системы управления. Выпуск 3. 1992.

148. Нечипорук Э.И. О реализации дизъюнкции и конъюнкции в некоторых монотонных базисах // Проблемы кибернетики, вып. 23, М.: Наука, 1970.

149. Нигматуллин Р.Г. Два класса доказательств нижних оценок сложности // Докл.АН СССР. 1987. Т. 294. №2.

150. Нигматуллин Р.Г. Сложность универсальных функций и нижние оценки сложности // Изв. вузов. Математика. 1984. №11.

151. Новиков С.В. Анализ методов синтеза сетей из программируемых логических матриц// УСиМ, 1984, № 3, с. 24 28.

152. Нурлыбаев А.Н. Об упрощении булевых функций с множеством нулей специального вида. «Дискретная математика». Том 3 вып.1. 1991г.

153. Обозрение зарубежной прессы. Компьютер ПРЕСС. № 10, 1991.

154. Основы построения автоматизированной системы проектирования автоматов (АСПУМА)/ Дьяченко В.Ф., Лазарев В.Г., Пийль Е.И. и др. В кн.: Дискретные системы. Т. 3. Рига: Зинатне, 1974.

155. Офман Ю. Об алгоритмической сложности дискретных функций // Докл. АН СССР, 1962, 145, с. 48-51.

156. Пантюшин С.В., В.М Назаретов, О.В. Тягунов, А.В. Кульба, В.И. Ситников, В.П. Гайдуков. Моделирование робототехнических систем и гибких автоматизированных производств. Под ред. Макарова И.М. Москва. Высшая школа. 1986.

157. Пархоменко П.П. Синтез структуры релейных устройств методом замены входных переменных//АиТ. 1967. №1.

158. Перязев Н.А. Существование и сложность представлений булевых функций формулами // Автореферат дисс.на соискание ученой степени д.ф.-м.н. Иркутск, 1998. 24 с.

159. Поддерюгина Н.В. Об одной задаче программирования арифметических выражений, связанной с параллельными вычислениями// М.: 1982. 28 с. (Препринт ИПМ АН СССР: № 40)

160. Попов Е.П., Зенкевич СЛ. Системы очувствления и адаптивные промышленные роботы // Сб. АМиРС. Под ред. Попова Е.П. Москва. Машиностроение. 1985.

161. Поспелов Д.А. Введение в теорию вычислительных систем. М.: Советское радио, 1972.

162. Поспелов Д.А. Логические методы анализа и синтеза схем. М.: Энергия, 1974.

163. Поспелов Д.А. Ситуационное управление. Теория и практика. Москва, Наука, 1986.

164. Поспелов Г.С., Поспелов Д.А. Искусственный интеллект // Вестник АН СССР, 1975, № 10.

165. Прангишвили И.В., Стецюра Г.Г. Микропроцессорные системы // М.: Наука, 1980.

166. Прангишвили И.В. Микропроцессоры и локальные сети микро-ЭВМ в распределенных системах управления. М.: Энергоатомиздат,1985.

167. Прангишвили И.В., Абрамова Н.А., Бабичева Е.В.,Игнатущенко В.В. Микроэлектроника и однородные структуры для построения логических и вычислительных устройств // М.: Наука, 1967.

168. Проблемы безопасности полетов. ВИНИТИ. № 4. 1999 г.

169. Проведение научно-исследовательских работ в области техники обеспечения надежности // Экспесс-информация, cep.II. Автоматизир. системы управления. Выпуск 3. 1992.

170. Пупырев Е.И. Интерпретирующие программы реализации булевых функций и автоматов // АиТ. 1982. № 1.

171. Пупырев Е.И., Чебурахин И.Ф., Четверикова И.В. Пакет программ проектирования и моделирования логики БИС // Тез. докл. Всес. конф. "Современные проблемы информатики, вычислительной техники и автоматизации". М., 1988.

172. Пятницкий А.А., Швеин А.А. Применение языков высокого уровня в проектировании аппаратных средств на основе программируемой логики // Технические и программные средства высокопроизводительных комплексов СМ ЭВМ. М., 1987.

173. Разборов А.А. Нижние оценки размера схем ограниченной глубины в полном базисе, содержащем функцию логического сложения // Мат. заметки, 1987, т. 41, № 4, с. 598 607.

174. Разборов А.А. Формулы ограниченной глубины в базисе {&, + } и некоторые комбинаторные задачи // Вопросы кибернетики. Сложность вычислений и прикладная математическая логика. Под ред. Адяна С.И. -Вып. 134.-М., 1988.

175. Райншке К., Ушаков И.А. Оценка надежности систем с использованием графов // Под ред. проф. И.А.Ушакова. М.: Радио и связь, 1988. 209 с.

176. Редькин Н.П. Доказательство минимальности некоторых схем из функциональных элементов // Проблемы кибернетики, вып. 23, М.: Наука, 1970.

177. Риордан Дж. Введение в комбинаторный анализ. М.: Изд-во иностр. литер., 1963.

178. Робинсон Дж. Машинно-ориентированная логика, основанная на принципе резолюции. В кн.: Киберн. сб., вып. 7. М.: Мир, 1970, с. 194 -218.

179. Рубинов В.И., Шалыто А.А. Построение граф-схем бинарных программ для систем булевых функций, заданных таблицами истинности // АиВТ.1988, № 1.

180. Савельев А.Я. Прикладная теория цифровых автоматов. М.: Высшая школа. 1987. 272.

181. Самарский А.А. Введение в численные методы. Москва. Наука. 1982. 272 с.

182. Самарский А.А., Гулин А.В. Устойчивость разностных схем. М.: Наука, 1973.

183. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.

184. Сапоженко А.А., Чухров И.Н. Минимизация булевых функций в классе дизъюнктивных нормальных форм // В кн.: Итоги науки и техники. Теория вероятностей. Математическая статистика. Техническая кибернетика. Т. 25. М.: ВИНИТИ, 1987.

185. Сапоженко А.А., Ложкин С.А. Методы логического проектирования и оценки сложности схем на дополняющих МОП-транзисторах// Микроэлектроника. 1983. Т. 12, вып. 1. С. 42 47.

186. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. Киев, Наукова Думка, 1988.

187. Сергиенко И.В., Червак Ю.Ю., Гренджа В.И. Распараллеливание в лексикографических алгоритмах дискретной оптимизации // Кибернетика, 1984, N 5 с. 82 85.

188. Синтез асинхронных автоматов на ЭВМ / Под ред. А.Д. Закревского. -Минск: Наука и техника,1975.

189. Синтез комбинационных схем на ЭВМ / Закревский А.Д., Канторович Е.Б., Поттосин Ю.В. и др. В кн.: Теория релейных устройств, Тр. XYI Всес. школы-семинара / Челябинский политехнический институт. Сб. тр. N 186. Челябинск: ЧПИ,1976.

190. Система программ для логического синтеза ЦВМ и ее практическое использование / Астопас Ф.Ф., Беляускас Б.Б., Жинтелис Г.Б. и др. В кн.: Вычислительная техника. Т. 3 / Каунасский политехнический институт. Сб. научн. тр. Каунас: КПИ, 1972.

191. Скотт П. Промышленные роботы переворот в производстве. Москва. Экономика. 1987.

192. Смирнов А.Д. Архитектура вычислительных систем. М.: Наука. 1990. 319 с.

193. Справочник. Надежность технических систем. Под ред. И.А.Ушакова. М.: Радио и связь, 1985.

194. Справочник по надежности, т. 2. // Под ред. Б.Е.Бердичевского. М.: Мир, 1970.

195. Справочник. Применение интегральных микросхем в электронной вычислительной технике // Данилов Р.В., Ельцов С.А., Иванов Ю.П. и др.: Под общ. ред. Б.Н.Файзулаева, Б.В.Тарабрина. М.: Радио и связь, 1987.

196. Степановская И.А., Ускач М.А. Представление булевых функций многофункциональными логическими элементами // АиТ. 1973. N 4. С. 26 -31.

197. Структура оптимального по быстродействию закона управления для нескольких рук роботов, манипулирующих общим объектом // Системыавтоматического управления и техническая кибернетика. Экспресс-информация N 10. М.: 1992.

198. Супрун В.П. Дизъюнктивно-конъюнктивное разложение с фиксированными булевыми функциями // АВТ, N 1, 1986.

199. Супрун В.П. Табличный метод полиномиального разложения булевых функций // Кибернетика, N 1, 1987, с. 116 -117.

200. Сычев А.Н. Построение комбинационных устройств методами линеаризации // АВТ, N 4,1986.

201. Субоч Н.Н. Проблемы кибернетики, вып. 17. М.: Наука,

202. Тарг С.М. Краткий курс теоретической механики. Москва. Наука. 1974. 478 с.

203. Тихонов А.Н., Самарский А.А. Уравнения математической физики. М.: Наука, 1972.

204. Трахтенброт Б.А., Бардзинь Я.М. Конечные автоматы. Поведение и синтез. М.: Наука, 1970.

205. Токхейм Р. Основы цифровой электроники. М.: Мир, 1988. 383с.

206. Уваров С.И. Вычисление арифметических выражений на многопроцессорной вычислительной системе с общим потоком команд // В кн.: Многопроцессорные вычислительные системы с общим потоком команд. Сб. трудов, вып. 19. М.: ИПУ, 1978, с. 67 78.

207. Угольников А.Б. О реализации монотонных функций схемами из функциональных элементов // Проблемы кибернетики. М.: Наука, 1976, вып. 31.

208. Угольников А.Б. О реализации функций из замкнутых классов схемами из функциональных элементов // Математические вопросы кибернетики. Вып. 1. М.: Наука, 1988.

209. Угольников А.Б. Глубина формул в неполных базисах // Математические вопросы кибернетики. Под ред. С.В.Яблонского. Вып. 1. М.: Наука. Гл.ред.физико-матем.лит. 1988.

210. Ульман Дж.Д. Вычислительные аспекты СБИС. М.: Радио и связь, 1990, 480 с.

211. Ушаков И.А. Построение высоконадежных систем // Серия: Математика, кибернетика. М.: Знание. 1974. 64 с.

212. Файзулаев Б.Н. Теория матричных БИС и СБИС ЭВМ // В кн.: Электронная вычислительная техника. Сб. статей под ред. В.В. Пржиялков-ского, вып. 1. М.: Радио и связь, 1987.

213. Фазулаев Б.Н., Шагурин И.И. и др. Быстродействующие матричные БИС и СБИС. Теория и проектирование. М.: Радио и связь. 1989.

214. Ферри Д., Эйкерс JI., Гринич Э. Электроника ультрабольших интегральных схем: Пер. с англ. М.: Мир, 1991. 327 с.

215. Фридман А., Менок П. Теория и проектирование переключательных схем. М.: Мир, 1978.

216. Фрир Дж. Построение вычислительных систем на базе перспективных микропроцессоров: Пер. с англ. М.: Мир, 1990. 413 с.

217. Фролов А.Б. Модели и методы технической диагностики. Сер. Математика, кибернетика. №4. Москва. Знание, 1990. 48 с.

218. Функционально ориентированные процессоры / Водяхо А.И., Смолов В.Б., Плюснин В.У., Пузанов Д.В. Под ред. Смолова В.Б. JL: Машиностроение. Ленингр. отд-ние, 1988. 224 с.

219. Халилов А.И. Распараллеливание арифметических выражений методом последовательного углубления // Программирование, 1979, N 2, с. 34 -40.

220. Хасин Л.С. Оценки сложности реализации монотонных симметрических функций формулами в базисе &, v, // ДАН СССР, 189, N 4, 1969, с.752 755.

221. Храпченко В.М. Об асимптотической оценке времени сложения параллельного сумматора // Проблемы кибернетики. Вып. М.: Наука, 1967, с. 107 122.

222. Храпченко В.М. О соотношении между сложностью и глубиной формул // Методы дискретного анализа в синтезе управляющих систем, вып. 32, Новосибирск, 1978, с. 76-94.

223. Хоггер К. Введение в логическое программирование. Москва, Мир, 1988.

224. Цвиркун А.Д. Основы синтеза структуры сложных систем. М.: Наука, 1982.

225. Цирлин Б.С. Обзор эквивалентных проблем реализации схем в базисе И-НЕ, не зависящих от скорости // Изв. АН СССР. Техн. кибернетика. -1986.-№2.

226. Цирлин Б.С. Обзор эквивалентных проблем реализации схем в базисе И-НЕ, не зависящих от скорости // Изв. АН СССР Техн. кибернетика, 1986, №2.

227. Цифровые следящие системы для управления движением роботов. Охоцимский Д.Е. и др. // Сб. Роботизация сборочных процессов. Под ред. Д.Е.Охоцимского. М.: Наука. 1985.

228. Чарп С. Современные средства обучения с использованием вычислительных машин // Мир науки, том 35, № 3,1991.

229. Чебурахин И.Ф. Синтез схем из функциональных элементов. 4.1. Некоторые вопросы декомпозиции булевых функций. Москва: МГТУ им.Н.Э.Баумана. 13 с. Деп. в ВИНИТИ 14.01.85, № 373-85. Р.Ж. Техн. кибернетика, № 4, 1985.

230. Чебурахин И.Ф. Основные принципы минимальной декомпозиции булевых функций в базисе И, ИЛИ, НЕ. Москва: МГТУ им.Н.Э.Баумана. Деп. в ВИНИТИ 05.04.85, № 2348-85. Р.Ж. Техн. кибернетика, N 8,1985.

231. Чебурахин И.Ф. Сложность декомпозиции булевых функций. Аналитическое решение задачи. Москва: МГТУ им.Н.Э.Баумана. Деп. в ВИНИТИ 05.04.85, № 2349-85. Р.Ж. Техн. кибернетика, № 8, 1985.

232. Чебурахин И.Ф. Некоторые вопросы минимальной декомпозиции булевых функций в базисе И, ИЛИ. Москва: МГТУ им.Н.Э.Баумана. Деп. в ВИНИТИ 16.07.85, № 5117-85. Р.Ж. Математика, № 10, 1985.

233. Чебурахин И.Ф. Алгебраический метод декомпозиции булевых функций в заданном классе функций. Москва: МГТУ им.Н.Э.Баумана. Деп. в ВИНИТИ 03.01.86, № 103-В. Р.Ж. Математика, № 5, 1986.

234. Чебурахин И.Ф. Преобразование программ логического управления и использование машинной графики // Сб. тез. докл. 4-го научно-технического семинара "Математическое обеспечение систем с машинной графикой", Устинов, 1986.

235. Чебурахин И.Ф. Принцип геометрического кодирования и логическое управление адаптивным роботом. Москва: МГТУ им.Н.Э.Баумана. 16 с. Деп. в ВИНИТИ 11.02.87, № 992 В.

236. Чебурахин И.Ф. Алгебраические преобразование булевых функций, их сложность и применение. Москва: МГТУ им.Н.Э.Баумана. 20 с. Деп. в ВИНИТИ 11.02.87, №993 -В.

237. Чебурахин И.Ф. Об оценивании сложности декомпозиции технических систем // Сб. "Труды МВТУ № 473". М.: 1987. С. 69 76.

238. Чебурахин И.Ф. Об одной математической модели декомпозиции булевых функций. Москва: МГТУ им.Н.Э.Баумана. Деп. в ВИНИТИ 19.05.87, № 3532-В87.19 с. Р.Ж. Математика, № 8, 1987.

239. Чебурахин И.Ф. Автоматизированная подготовка программ логического управления методом декомпозиции // Тез. докл. "Всес. конф. по автоматизации проектирования систем планирования и управления", Звенигород, окт., 1987 г. с. 132 134, М., 1987.

240. Чебурахин И.Ф. Оптимизация программ, вычисляющих формулы алгебры логики. Москва: МГТУ им.НЭ.Баумана. Деп. в ВИНИТИ 04.05.89, № 2853-В89. 47 с. Р.Ж. Математика, № 8, 1989.

241. Чебурахин И.Ф. Оптимизация программ управления для логических контроллеров // Межд. сб. "Вычислительная техника. Системы. Управление" Москва София. МЦНиТИ, 1989, вып. 1, с. 56 - 64.

242. Чебурахин И.Ф. Автоматизация проектирования оптимальных структур и программ логического управления методом конструктивного выравнивания. Дисс. . канд. техн. наук. М., 1990. 256 с.

243. Чебурахин И.Ф. Автоматизированная разработка оптимальных программ управления для логических контроллеров // Сб. "Автоматизация проектирования систем программно-логического управления", вып. 2. М.: Машиностроение, 1990. С. 151 -195.

244. Чебурахин И.Ф. Надежность комбинационных схем // Сб. "Труды МГТУ № 544". М.: Издательство МГТУ, 1990. С. 114 126.

245. Чебурахин И.Ф. Проектирование оптимальных комбинационных схем //Научно-техн. сборник РКТ, серия 5, вып. 2, 1991. с. 84-90.

246. Чебурахин И.Ф. Проблемы декомпозиции булевых функций и ее применений // Сб. докл. Межд. научно-техн. конф. "Актуальные проблемы фундаментальных наук" (СССР, Москва, 28 октября- 3 ноября), том 2, изд-во МГТУ, 1991, с.76.

247. Чебурахин И.Ф. Проблемы аппаратной и программной реализации булевых функций. Москва: МГТУ им.Н.Э.Баумана. 28 с. Деп. в ВИНИТИ 8.01.92, № 69.В92.Р.Ж. Математика, № 4, 1992.

248. Чебурахин И.Ф. Синтез логических схем и программ управления на основе структурно-функциональной декомпозиции. Москва: МГТУ им.Н.Э.Баумана. 172 с. Деп. в ВИНИТИ 07.07.93, N 1884-В93. Р.Ж. Математика, 40, М., 1993.

249. Cheburakhin I.F. The computer-aided design of optimal logical circuits and control programs // Abstracts International Aerospace Congress: Theory, Applications, Technologies IAC'94. -August 15-19, 1994, Moscow, Russia. -p. 445.

250. Cheburakhin I.F. The Logical Control: Tasks and Estimates. Proceedings of the 9th International Conference "Systems for Automation of Engineering and Research" (SAER'95) and DECUS NUG Seminar'95, Sofia, 1995. P. 8589.

251. Чебурахин И.Ф. Структурно-функциональная декомпозиция, методы и оценки // Сб. докл. 5-го межгосударственного семинара "Дискретная математика и ее приложения", посвященного 70-ю чл-корр. РАН С.В. Яблонского. Москва. 1995. (в печати)

252. Чебурахин И.Ф. Функционалы качества для интеллектуальных САПР СБИС // Сб. материалов и сообщений 2-го Международного симпозиума "Интеллектуальные системы 96". Россия, Санкт-Петербург, 1996.

253. Чебурахин И.Ф. Некоторые вопросы дискретной математики. Мето-дич. указан, по курсам "Теория конечных автоматов" и "Схемотехника". МГАТУ. 1996. 30 с.

254. Чебурахин И.Ф. Автоматизированное проектирование оптимальных логических схем // Тезисы докладов на 2-м Международном аэрокосмическом конгрессе IAC97. Москва, Россия, 1997. Moscow, Russia. Publisher: STC Tetrovka',1997.

255. Чебурахин И.Ф. Автоматизированное проектирование оптимальных логических схем // Доклады 2-го Международного аэрокосмического конгресса IAC97. Том 1. Москва, Россия, 1997. Moscow, Russia. Publisher: STC 'Petrovka', 1999.

256. Чебурахин И.Ф. Некоторые показатели качества логических схем и программ // Труды III Межд.конф. 'Дискретные модели в теории управляющих систем* (22 27 июня 1998г.). Москва. Диалог - МГУ. 1998. С.117 -121.

257. Чебурахин И.Ф. Функционалы качества для синтеза параллельных алгоритмов // Сб. докл. на 3-м Международном симпозиуме 'Интеллектуальные системы' (INTELS'98), Россия г. Псков, ЗОиюня - 4 июля 1998 г.

258. Чебурахин И.Ф. Оптимальный метод декомпозиции в одном подклассе Булевых функций // Доклад : 6-й межгосударственный семинар 'Дискретная математика и ее приложения', 2-6 февраля 1998 г., МГУ им. М.В.Ломоносова (в печати).

259. Чебурахин И.Ф. Задачи автоматизации и оптимизации аппаратной и программной реализации булевых функций. // Информационные технологии, 1999, № 2, С. 28 34.

260. Чебурахин И.Ф. О сложности и глубине схем из функциональных элементов // Труды IV Межд.конф. «Дискретные модели в теории управляющих систем» (19-25 июня 2000г.).Москва. «МАКС Пресс». 2000. С. 133-134.

261. Чебурахин И.Ф. Разработка компонентов автоматики для летательных аппаратов на основе логических методов // Тез.докл. «Третий Международный аэрокосмический конгресс 1АС2000». Москва, Россия, 23-27 августа 2000 г.

262. Чебурахин И.Ф. Математические средства аппаратной реализации булевых функций на основе структурно-функциональной декомпозиции // Информационные технологии, 2002, № 1, С. 36 41.

263. Чебурахин И.Ф., Хорхордин В.И., Степанов B.C. Автоматизированная система синтеза функциональных схем // Труды 5-го Международного симпозиума «Интеллектуальные системы INTELS 2002». М.: МГТУ им.Н.Э.Баумана, 2002. С.З57-359.

264. Чебурахин И.Ф. Разработка компонентов автоматики для летательных аппаратов на основе логических методов // Труды «Третий Международный аэрокосмический конгресс 1АС2000». Москва, Россия, 23-27 августа 2000 г. (электронный вид, издано 2003 г.). С.78-83.

265. Чебурахин И.Ф. Синтез дискретных управляющих систем и математическое моделирование: теория, алгоритмы, программы. Москва. Физ-матлит. 2003. 264 с.

266. Чебурахин И.Ф. Логическое управление: задачи, алгоритмы, показатели качества. Москва. Изд.центр МАТИ-РГТУ им.К.Э.Циолковского. 2003. 200 с.

267. Чебурахин И.Ф. Методы декомпозиции булевых функций: алгоритмы, показатели качества, приложения // Изв. РАН. ТиСУ. 2003. №5. с. 5661.

268. Чистов В.П. Автоматизация логико-компилятивного проектирования дискретных систем // В сб.: Автоматизация проектирования / под. общ. ред. В.А.Трапезникова. М.: Машиностроение, 1986.

269. Чичковский А.Б., Чебурахин И.Ф. Система проектирования логических контроллеров с языка высокого уровня на персональной ЭВМ // Тез. докл. Межд. научно-техн. конф. "Проблемы автоматизированного проектирования в машиностроении". М., 1988.

270. Чичковский А.Б. // Сб. "Автоматизация проектирования систем программно-логического управления", вып. 2. М.: Машиностроение, 1990. С. 151 -196.

271. Шахинпур М. Курс робототехники. Москва. Мир. 1990.

272. Шеннон К. Работы по теории информации и кибернетики. М.: Иностр. лит., 1963.

273. Шоломов J1.A. Основы теории дискретных логических и вычислительных устройств. М.: Наука, 1980.

274. ЭВМ начинает видеть. Экспесс-информация, сер. 2, САУ. Вып.2. 1992.

275. Эйрис Р. Проектирование СБИС, метод кремниевой компиляции. Под ред. Б.Н.Наумова и Е.Г.Ойхмана. Москва. Наука, 1988. 455 с.

276. Юдин Д.Б., Горяшко А.П., Немировский А.С. Математические методы оптимизации устройств и алгоритмов АСУ / Под ред. Ю.В.Асафьева, В .А. Шабалина. М.: Радио и связь, 1982. 288 с.

277. Юдицкий С.А., Тагаевская А.А., Ефремова Т.К. Проектирование дискретных устройств автоматики. М.: Машиностроение, 1980. Юдицкий С.А., Мачергут В.З. Логическое управление дискретными процессами. М.: Машиностроение, 1987.

278. Яблонский С.В. Об алгоритмических трудностях синтеза минимальных контактных схем // Проблемы кибернетики, № 2. М.: ГФ-М лит., 1959.

279. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.

280. Яковлев М.Ф. О решении систем уравнений с частными производными на многопроцессорном вычислительном комплексе // Кибернетика, № 4, с. 112-114.

281. Яненко Н.Н., Коновалов А.Н., Бугров А.Н., Шустов Г.В. Об организации параллельных вычислений и "распараллеливание" прогонки //Числ. методы мех. сплошн. среды, 1978,9, № 7, с. 139 146.

282. Abhyankar S. Absolute minimal expressions of Boolean functions. IRE Transaction on Electronic Computers, vol. EC-8,1959,1 1.

283. Aerospace America. 1990. Vol. 28, 1 8. P. 42,43

284. Berman C.L., Trevillyan L.N. Global flow optimization in automatic logic dising//IEEE Trans. Comput. Aid. Des. Integr. Circuits & Syst. 1991. 10, '5.

285. Chen H.Y., Kang S.M. A new circuit optimization technique for high performance CMOS circuits // IEEE Trans. Comput. Aid. Des. Integr. Cicuits and Syst. 1991. 10, 15. P. 670-677.

286. Chen Y. On the structure of the minimum time control law for multiple robot arms handling a common object. / IEEE Trans. Automat. Contr. 1991, 36 l2, p. 230-233.

287. Cheng Kwang-Ting, Agrawal Vishwani D. Methods for synthesizing testable sequential circuits//AT and T Techn. J. 1991. 70, 1 1. P. 64-86.

288. Devidson E.C. An algorithm for NAND decomposition under network contrains. IEEE Trans., December 1969,vol. C-18.

289. Diamantaras K.I., Jha Niraj K. A new transition count method for testing of logic circuits// IEEE Trans. Comput. Aid. Des. Integr. Circuits and Syst. 1991. 10, l3. P. 407-410.

290. Durand Y. Logic synthesis based on unification & rewriting rules // Des. Methodol. VLSI Comput. Arch.: Proc. IFIP Work Conf., Pisa, 19-21 Sept., 1988. Amsterdamets. 1989.

291. Grassman W., Tremblay J.P. Logic and Discrete Mathematics/ A Computer Scince Perspective Englewood Cliffs (N.J.): Ptentice Hall, 1995. 650 p.

292. Kim Bo-Gwan, Dietmeyer D.L. Mulilevel logic synthesis jf symmetric switching function // IEEE Trans. Comput. Aid. Des. Integr. Circuits & Syst. 1991. 10,4.

293. LeeC.Y Representation of switching function by binary dicision program. Bell System Techn. J., 1959, 38, p. 985 999.

294. Mehlhorn K. Acta Informtics. 1979, vol. 12.

295. Muroga S. Logic Design and Switching Theory. Johnwiley, 1979.

296. Mc Coll W.F. The maximum depth of monotone formulae. Information processing letters, 1978,v. 7,1 2, p. 65.

297. Niessen-Gillhaus U., Scheneeweis W. A practical comparison of several algorithms for reliability calculations // Reliability Engineering & Sistem Safety, 1991,31, 1 3,p. 309 319.

298. On covering distant minterms by the camp algorithm. / Biwas Nripendra N. // IEEE Trans. Comput. Aid Des. Integr. Circuits and Syst. 1990. 9, 1 7, p. 786 - 789.

299. Paterson M.S. Theoret. Comput. Sci., 1975, vol. 1.

300. Rawles J.W. DOD adopts application specific ICs. Defense Electronics, 1990,22, 1 11, p. 39-41.

301. Rowe J. New building blocks for future architectures // Defense Electronics.-1990. 22, 1 11. P. 31-34.

302. Schneider P.R., Detmeyer D.L. An algorithm for synthesis of multiple output combinational logic. IEEE Trans., Februery 1968, vol. C-17,1 2.

303. Science and Technologu in Japan, 1991, v. 10, N 38, UII, p.43.

304. Simonis H., Le Provost T. Circuit verification in CHIP: bech-mark result. //Formal VLSI. IFIP WG 10.2/ WG 10.5 Int.Workshop Appl. FormalMeth. Correct VLSI Des., Houthalen, 13 16 Nov., 1989. Amsterdam etc., 1990. P. 125 - 129.

305. Software Engineering Notes. 1991. Vol.16, 1 2. P.23-30.

306. Software Engineering Jounal. 1990. Vol.5,1 6. P.319-330.

307. Word PLC market to hit $ 5.5 billion mark by 1996 / Emerson Amy //I and CS. 64, 1 1. P. 70-71.

308. Tai S.C., Du M.W., Lee R.C.T. Atransformational approach to synthesizing combinational circuits // IEEE Trans. Comput. Aid. Des. Integr. Circuits & Syst. 1991. 10,'3.

309. Theyse A.P. Functions: a new tool for the analisis and synthesis of binary programs. IEEE Trans. Computers, 1981,12.

310. Valiant L.G Proc. 15-th ACM Symp. Teory Сотр., 1983.

311. VLSI Electronics Microstructure Science. V. 14. VLSI Design. Edited by Norman G. Einspruch. College of Engineering University of Miami Coral Gables, Florida. ACADEMIC PRESS, INC. 1986. 256 p.

312. Dictionary of Computing. Oxford University Press. Market House Books Ltd., 1986. 560 p.