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

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

Егорова Евгения Кирилловна

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

з о СЕН 2015

Москва 2015

005562694

Работа выполнена на кафедре «Прикладная математика и информационные технологии» ФГБОУ ВПО «МАТИ - Российского государственного технологического университета имени К. Э. Циолковского»

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

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

Кутепов Виталий Павлович

доктор физико-математических наук, профессор НИУ «МЭИ»

Топка Владимир Владимирович,

кандидат технических наук, с. н. с. Института проблем управления им. В. А. Трапезникова

ФГАОУ ВО «Нижегородский государственный университет им. Н.И. Лобачевского»

Защита состоится 17 сентября 2015 г. в 12:00 на заседании диссертационного совета Д 212.110.08 при ФГБОУ ВПО «МАТИ - Российский государственный технологический университет имени К. Э. Циолковского» по адресу: 121552, г. Москва, ул. Оршанская, д. 3, 612А

С диссертацией можно ознакомиться в библиотеке и на сайте ФГБОУ ВПО «МАТИ - Российский государственный технологический университет имени К. Э. Циолковского», http://www.mati.ru.

Автореферат разослан «-»—августа- 2015 г.

Ю ш^п^у®

Ученый секретарь диссертационного совета Д 212.110.0Й кандидат физико-математических наук

Научный руководитель

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

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

Мокряко» Алексей Викторович

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

Актуальность темы.

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

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

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

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

з

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

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

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

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

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

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

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

Цель работы.

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

Область исследования.

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

Достижение цели работы обеспечивается решением ряда проблем и задач.

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

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

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

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

Научная новизна.

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

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

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

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

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

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

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

Практическая ценность и реализация результатов.

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

Результаты диссертации использованы при чтении учебных курсов по дисциплинам "Дискретная математика", 'Теория программирования" и

"Информатика" студентам кафедры "Прикладная математика и информационные технологии" МАТИ - РГТУ имени К. Э. Циолковского.

Апробация работы.

Основные теоретические и практические результаты диссертации докладывались и обсуждались на XXXVII и XXXIX международных молодежных научных конференциях «Гагаринские чтения», первом форуме союзного государства вузов инженерно-технического профиля — Материалы встречи молодых учёных «Молодёжные идеи и проекты», Международной научно-технической конференции молодых ученых, аспирантов и студентов «Управление, автоматизация и окружающая среда-2012» в Севастополе и Межвузовской молодёжной научно-практической конференции «Информационные и телекоммуникационные технологии».

Также полученные в диссертации результаты обсуждались на семинарах, проводимых в МАТИ-РГТУ им. К.Э.Циолковского, ВЦ РАН им. А. А. Дородницына.

Работа выполнена при финансовой поддержке РФФИ, грант № 0901-90441 Укр Ф.

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

Публикации.

По теме диссертации опубликовано самостоятельно и в соавторстве 10 работ в том числе 2 работы в изданиях, входящих в перечень ведущих журналов и изданий, рекомендованных ВАК для публикации основных результатов диссертаций на соискания ученой степени доктора и кандидата наук. Опубликованные материалы отражают основное содержание диссер-

тации. Кроме того, автором получено свидетельство о регистрации программы для ЭВМ

Структура и объем работы. Диссертация состоит из введения, четырёх глав, заключения, списка литературы (46 наименований) и приложения. Объем работы 136 страниц, включая 16 рисунков. Основное содержание имеет объем 114 страниц.

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

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

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

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

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

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

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

Наличие в теории булевых функций трудных и недостаточно разработанных проблем по представлению булевых функций формулами отмечается и в настоящее время (Перязев H.A. Существование и сложность представлений булевых функций формулами; Винокуров С.Ф. Операторы в полиномиальных представлениях булевых функций).

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

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

В связи с этим разрабатываются различные подходы к разработке алгоритмов синтеза, заметно отличающихся по трудоемкости от переборных, в том числе асимптотический подход, основывающийся на функции Шеннона. Здесь О.Б. Лупанов первым разработал метод и получил асимптотическую оценку числа элементов схемы, реализующей булеву функцию. Затем развивая метод, асимптотическую оценку для глубины схемы получил А.Б. Угольников. Зависимость между минимальными значениями глубины и сложности эквивалентных формул изучалась В.М. Храпченко и С.АЛожкиным, при этом они получили важные неравенства. С.А. Ложкиным получена также уточненная верхняя оценка для глубины булевой функции. Несмотря на имеющиеся успехи в области синтеза схем, однако, в целом, в теории булевых функций нет полных ответов на следующие вопросы. Как использование скобочных формул, математических моделей, улучшают качество проектируемых схем из ФЭ? Как ветвление выходов ФЭ позволяет минимизировать их число в схеме? Как зависит трудоемкость синтеза от результатов минимизации перечисленных выше показателей (как они связаны)? С помощью каких средств можно уменьшить трудоемкость синтеза и др.? В научной литературе приводятся и исследуются примеры, когда одна функция в некотором базисе имеет меньшие значения показателей сложности по сравнению с другим базисом, другая же функция, наоборот. Для таких задач интересны ответы на вопросы: во сколько раз или как может измениться сложность функции при переходе из одного базиса в другой (и наоборот). Имеющихся ответов на все эти вопросы в из-

вестных публикациях недостаточно. В одной из своих работ C.B. Яблонским было сказано: «Асимптотические оценки важны не только с точки зрения понимания сложности получаемых схем, но и как способ оценки качества алгоритмов синтеза». Однако при построении схем для конкретных функций асимптотически наилучшие методы синтеза часто не дают хороших результатов. Тем не менее, поиск минимальных решений может быть успешным, но искать его следует на основе классификации множества булевых функций, совершенствования методов декомпозиции с привлечением понятия строение-структура. Поэтому в качестве математических моделей, для большей части рассматриваемых задач, выбирались все БФ, а также - симметрические булевы функции и их представления в классе формул и — схем из ФЭ. Отмстим, что синтезируемые схемы применяются при проектировании различных дискретных логических устройств для вычислительной и управляющей техники.

В главе также рассматриваются: математико-информационное описание булевых функций; меры сложности представления функции / формулой F или схемой S из ФЭ. Определяем декомпозицию как многошаговый процесс: параллельная ("от аргументов"); последовательная ("от функции") декомпозиции. Под шагом (первым) последовательной или параллельной декомпозиции функции f в базисе G подразумеваем: 1) выбор базисной функции g, eG; 2) преобразование функции f(X) в соответствующую суперпозицию функций. Применяя шаги декомпозиции к остаточным функциям, выполняем полную s-шаговую декомпозицию функции f(X) в базисе G, получая формулу F. Результат (качество) декомпозиции оценивается в терминах функционалов В качестве меры сложности представления функции формулой F или схемой S из функциональных элементов (ФЭ) определяем соответствующие показатели (дискретные функционалы): Lb(f, G) - суммарное число вхождений символов переменных в формулу F; Lf{f, G)- число базисных подформул в F; L^J, G)- число

ФЭ в схеме S; Перт (J, G) - глубина F; Depb<f, G) - глубина S, определяемая как наибольшее число ФЭ в цепочке, среди всех цепочек, соединяющих вход с выходом. Заканчивается глава постановкой задачи.

Во второй главе уточняется и дополняется новыми эквивалентпо-стями математический аппарат для синтеза дискретных логических устройств обработки информации и управления. Этот аппарат включает описаиие булевых переменных X={xi,...,x„}, функций /п) и формул F*n>, а также функционально полные системы функций G - базисы. Также важную положительную роль здесь играют функциональные уравнения - комбинаторные преобразования (на основе рекуррентных соотношений).

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

Здесь же определяется математико-информационное описание булевых функций и формул, играющее важнейшую роль при их упорядочивании, классификации булевых функций по классам функций одной сложности и при оптимизации синтеза цифровых схем. Основу математико-информационного описания булевых функций составляет строение формул типа монотонной ДНФ J{X)=Kiv ...vÀ'„, (в базисе Gf) или полинома Жегалкина_ДХ)=/ОФ...©ЛТ„ (в базисе Оз), где АГ, - монотонная элементарная конъюнкция ранга пит- длина формулы F, определяемое как вектор

рангов г=(п..... г„). Тогда первый уровень описания булевой формулы /

есть строение г и список букв формулы. Другой уровень - представление полинома Жегалкина при помощи матрицы. Аналогично определяется строение г конъюнктивной нормальной формы (КНФ) булевой функции / и других формул этого типа. Строением формулы / , представляющей функцию из класса & (v, © или <->), назовем число ее аргументов, т.е.

число п (строение - вектор рангов вырождается в число). Формулу F строения r=(rt,...,rm) назовем канонической, если о >г?> ...>г,„. Базисную формулу g всегда считаем канонической. В полное математико-информационное описание булевой формулы (другие уровни) входят специальные матрицы, учитывающие при необходимости отрицание и повторяемость переменных. Заметим, что для функционалов качества Lh{f, G) и Deprif, G) основную роль играет строение формулы.

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

Получим значение показателя сложности произвольной булевой функции на основе ФУ (базовый случай). Применим метод ФУ для реализации произвольной булевой функции s Я/"' в базисе G3 формулы F") и получения при этом верхней оценки сложности Lf.

Булева функция зависит от переменных из множества X={xi,... xt, ...,х„} и задается полином Жегалкина Fn) = Ki © ... ФАГ/ © ... © Кш, где Kj - монотонная элементарная конъюнкция ранга г, , причем о >... > /•, >...>rm 1< i < т. Такой полином Жегалкина называется каноническим, его элементарные конъюнкции расположены в соответствии с порядком ">". Вектор г = (г/,..., г/ ,..., гт) задает строение полинома Жегалкина. При этом определяем еще векторр = (p,,p2,...,pi,...p„) повторяемости перемен-

ных из множества X в формуле то есть переменная х,, 1< / < п, повторяется в формуле /г(") число р, раз.

Находимр, =тах(р],р2,...,р,,...р„), 1< / < п. Тогда ФУ имеет вид

F„{^"l) (1)

где нижние индексы 0 и 1 — номера соответствующих остаточных функций, рассматриваемых на одном множестве X' = Х\ { дг,).

Применяя к Р0{"','> и ФУ (1) и так далее, получим . Каждое применение ФУ (1) порождает не более двух базисных функций из Оз и не более двух остаточных функций и Используя последовательно ФУ (1) и суммируя значения сложности £/г, выводим верхнюю оценку сложности для общего случая. Итак, при реализации произвольной булевой функции /е Р2 "1 в базисе отличной от константы, уточнена верхняя оценка показателя сложности

С3) = (5/4)-2"—2. (2)

Погрешность получаемой оценки (2) может быть большой (см. пример 1 и табл. 2). Поэтому предлагается следующий Алгоритм вычисления оценки ¿/г. Рассмотрим кратко структуру и функционирование разработанного алгоритма, позволяющего численно получать верхнюю оценку или минимальное значение сложности на основе ФУ (4) в базисе Gj.

Пример 1 начало. Функция задается полиномом Жегалкина: = XI -х2 Хз -Х4@Х1 Х2 -Х&Х1 -х6®х7, строения г = (4,3,2, 1). Представить её в классе скобочных формул, минимизируя показатель сложности

Составим табл. 1 повторяемости переменных х,, /е (1. 2, 3, 4, 5, 6, 7}, в формуле

Таблица 1.

Х) X) X2 Хз XI Хз Хб X7 Х8 Хд

рр> 1 2 3 1 1 1 1 - -

рр 1 3 2 1 2 1 1 1 4

Выполним эквивалентные преобразования формулы в соответствии с ФУ

р{1) = ХгХ2 Хз -Х4 ©Х2-Хз-Хз@ Х3-Х6®Х7 = = Хз-(ХгХ2-Х4 ®Х2-Х5® Хб ) = = Хз-(Х1(Х/-Х4®Х1)®Хб )®х? = = Хб ) ®х7 =

Таким образом выполнена декомпозиция функции в базисе Сз и получена бесповторная скобочная формула И^р, минимальной сложностью = 6. При этом однозначно определен порядок вычисления формулы

Замечание 1. На основе примера 1 можно строить счетные классы булевых формул определенного строения, характеризуемых минимальной сложностью представления (доказываемой методом математической индукции). В качестве простого ближайшего примера предлагается функция/9', задаваемая полиномом Жегалкина ГЛ9\ строения г = (5, 4, 3, 2, 1), то есть

= Х2 -Хз Х4 -х,-х?® х2 Хз Х;Х9®Х2 -ХгХд®Х8-Х9@Х,=

= Х9-(Х2-(ХЗ-(Х4-Х5®Х6)®Х7)®Х8) ®Х1 (3)

Минимальное значение показателя 8. Для наглядности и удоб-

ства сравнения представим результаты в одной табл. 2.

Таблица 2

iV и - число переменных /*°-ТИП полинома ¿ДУ7"")- сложность по числу букв irti1"') Сложность по числу базисных функций !*(!***) = =(5/4)2"-2

1 2 3 4 5

1 7 F4(7) 140 66 158

2 7 F2(7) 42 26 158

3 7 /7(7) 10 6 - min 158

4 9 f( 9) 15 8 - min 638

Аналитически и из табл. 2 следует, что при возрастании п значения показателей Х^"') и ¿к^"')»« булевых функций также увеличиваются (столбцы 1 - 4), но прогнозируемые оценки сложности увеличиваются быстрее (столбец 5).

Конец примера 1.

В третьей главе (продолжение) исследования продолжаются для получения (и минимизации) показателей сложности выражений с ЭСП Же-галкина, например, И^® Р^т\

Пусть | X | = п, Р^, т<п, / < я, у < т. Вначале на основе ФУ получаем

рР71'1^)

откуда выводим ФУпк для показателя сложности ¿б и оцениваем его

/}(т)} = 1+ £ • а +] - сгд - .

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

¿/.<^(П)Ф < 1+ г ■ СА +7 -с/;, - - . (4)

Для одного ЭСП оценка (4) имеет вид

< 1+ г • а - С£\.

Пример 2. Приведём оценку ¿Е (^й), полученную методом алгеб-

раическом декомпозиции.

Рис. 1.

На рис. 1 представлены четыре оценки:

(^1с3)=^п3-п2+|п-3,

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

Как видно получено улучшении оценки на порядок.

В четвертой главе вычислительный метод синтеза формул и схем -метод алгебраической декомпозиции применяется для автоматизации получения оценок любой функции в базисе Жегалкина. В результате формализации метода, использованного в предыдущей главе, был разработан алгоритм, позволяющий это сделать. Также в главе рассматриваются особенности реализации данного алгоритма на практике и возникающие при этом особые случаи. В результате работы алгоритма происходит не только вычисление оценок произвольной булевой функции, но и ее минимизация, для методов параллельной и последовательной декомпозиции на основе строения функции из простых классов (&, V, © или <-») разработаны алгоритмы декомпозиции, позволяющие для этих классов функций минимизировать (по сложности и глубине) синтез логических схем. Декомпозицию функции / в базисе О на основе строения назовем структурно-функциональной декомпозицией.

Вычислительный метод получения верхних оценок сложности.

Погрешность получаемой оценки (3) может быть большой (см. пример 1 и табл. 2). Поэтому предлагается следующий вычислительный метод получешм оценки £/■• на основе оригинального матричного представления

полинома Жегалкина. Метод отличается от известных и позволяет численно получать верхнюю оценку или минимальное значение сложности /-/ на основе ФУ (2) в базисе

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

алгоритма синтеза формулы и соответствующей схемы 5).

Пусть Х= {х/, дг„} - множество булевых переменных. Произ-

вольная булева функциязадается полиномом Жегалкина

№ = К,®...в)К@... @К„ в базисе С3 ={&, ©, 0,1}, где п - число переменных, т - длина полинома Жегалкина,

А!) - монотонная элементарная конъюнкция ранга г„ 1<Л<т, г=(г/,... г,, ..., г„,) - вектор рангов полинома Жегалкина, упорядочивается для алгоритма один "!" раз отношением " > ". При дальнейших преобразованиях этот порядок сохраняется, позволяя уменьшать трудоемкость. Получаем /■/>...> п> ...> гт.

Матричная модель полинома Жегалкина и ее свойства (достаточность для вычисления, преобразований и др.).

С целью рационального представления булевой функции предлагается следующая новая модель для полинома Жегалкина Р-п] = АО®...ФА',©... ©А"т, где К, - монотонная элементарная конъюнкция ранга п, 1< ( < т. Полином Я"' представляется при помощи матрицы (А'у) размером т х п, включаемой в табл. 3 с числом строк {т+1) и - столбцов (л+1). Определяется матрица и таблица следующим образом (будем их так называть). После заполнения матрицы (АГу) размером т х п в табл. 3 с числом строк (/»+1) и числом столбцов («+!) подсчитать по формулам числовые

характеристики полинома: векторы рангов г и повторяемости р переменных, а также - исходная сложность полинома.

Элемент матрицы К^ = I, если (х1е {К,}, /<у"< п), 1< << т, иначе Кц = 0 (/< /'< т, /<у'< и), где под символом {А.',} понимаем множество переменных, образующих элементарные конъюнкции К^

В столбец (/< ;'< да, /г-н/) вычислить и записать ранг

П =П,„^ , ,/< /< /л,

г-1

элементарной конъюнкции К,.

В строку (т+1, /<у < л) вычислить и записать число д повторений переменной лгу, /< у < я, в (исходной или текущей) формуле Я-"', подсчитывая

PJ =Рт+1.) = ]>Х„

Л =■

и получая вектор р=(р1,...,р^...р„) повторяемости переменных из множе-спваХ={х1,... х^ ...,х„) в формуле Я"1, [переменнаяЛ;, 1 <у <я, повторяется в формуле число р] раз].

т

Вычислить ¿и = X/, - число букв в формуле /=1

Определить максимальную компоненту pj вектора р и ее индекс у, то есть р^ак:=тах(р1,..., р^...р„), I < у < п, и у - индекс максимально повторяющейся переменной ху. Итак, у = ]тах максимально повторяющаяся переменная дгу повторяется ру раз (в случае нескольких одинаковых индексов выбираем один любой из них).

Множество {К, \ 1< / < т} элементарных конъюнкций полинома Я"' разбиваем на два подмножества Яо и Я/: первое подмножество, ЭК которого содержат переменную Хр обозначаем как Я'(/■"'= _Г0); второе подмножество, ЭК которого не содержат переменную обозначаем как Я" (Я" = Я/). При выполнении перестановок в полиномах /•"= Р0 и Я" Я/ сохра-

пять порядок "> " по рангам элементарных конъюнкций. В множестве элементарных конъюнкций выносим переменную X] за скобки, для остатка сохраняя обозначение /<"'.

Записываем полиномы Р'и Я" и их числовые характеристики (аналогично предыдущему и сохраняя порядок "> ") в табл. 3. ¡1 = 1, 2, ... - начало и продолжение записи функций F'и Р'\ номер последней записанной функции в табл. 3;

¡2= 1, 2, ...- начало и продолжение чтения табл. 3; номер последней прочитанной функции.

Проверка условия: Ь> Ь.

Выбрать из табл. 3 очередную подформулу и записать ее в табл. подформул.

Таблица 3. Декомпозиция полиномов и запись результатов (1-я и 2-я строки и т.д.).

п' или п" т' или т " Полиномы Жегалкина БЬ ли Р" Выводимые результаты Ьг

1 2 3 4

1 п'\=п-1 ГП Р;тах Г' Ь/Л-1

2 п":=п'. т"\= т -т' Р" ¿г:= 1

3 ...

На каждом шаге получать две (или одну) такие строки (остаточные формулы - полиномы Р'п Я") с результатами.

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

ЗАКЛЮЧЕНИЕ

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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

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

3). Получена аналитическая оценка сложности линейной комбинации симметрических полиномов Жегалкина через сложность самих этих полиномов Жегалкина.

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

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

5). Гос. регистрация программы для ЭВМ: Гос. регистрация программы «Минимизация сложности представления произвольной булевой функции/"' (и переменных) в классе формул». Свидетельство о гос. регистрации программы для ЭВМ № 2012616794. Заявка поступила 04.05.2012. Зарегистрировано в Реестре программ для ЭВМ 30.07.2012.

Список опубликованных работ.

1. Гурченков А. А., Егорова Е. К. Автоматизация задачи определения сложности булевой функции // Инженерный журнал: наука и инновации. 2014, № 5(29), С. 10-21.

2. Гурченков А. А., Егорова Е. К. Особенности автоматизации синтеза булевых функций // Инженерный журнал: наука и инновации. 2013, № 12(24), С. 53-61.

3. Егорова Е. К. Алгоритм минимизации сложности представления произвольной булевой функции // М.: МАТИ, статья на XXXIX международной молодежной научной конференции «Гагаринские чтения», апрель 2013, стр. 56-57.

4. Егорова Е. К. Программный комплекс минимизации сложности представления произвольной булевой функции в классе формул // М.: МАТИ, статья на XXXVII международной молодежной научной конференции «Гагаринские чтения», т. 5, 2012, С. 56-58.

5. Егорова Е. К. Сложность представления симметрических булевых функций в классе полиномов Жегалкина // М.: МАТИ, статья на XXXVII международной молодежной научной конференции «Гагаринские чтения», т. 5, 2011, С. 88-90.

6. Егорова Е. К. Показатели качества реализации симметрических полиномов Жегалкина степени п-2 // Труды межвузовской молодежной научно-практической конференции «Информационные и телекоммуникационные технологии». М.: МАТИ, 2009, С. 30-46.

7. Егорова Е. К., Мокряков А. В. Минимизация сложности представления произвольной булевой функции в классе формул программным методом // Минск: I Форум союзного государства вузов инженерно-технического профиля - Материалы встречи молодых ученых «Молодёжные вдеи и проекты», 2012, С. 7-8.

8. Егорова Е. К., Чебурахин И. Ф. Автоматизация и оптимизация синтеза дискретных устройств обработки информации и управления // Севастополь: СевНГУ, статья на Международной научно-технической конференции молодых ученых, аспирантов и студентов «Управление, автоматизация и окружающая среда-2012», 2012, с. 15-18.

9. Егорова Е. К., Чебурахин И. Ф. Автоматизация конструирования определенных счетных классов булевых функций и минимизация их сложности // «Мехатроника, автоматизация, управление», 2014, № 8, с. 3-9. (№ 1270 в перечне рецензируемых журналов, в котором должны быть опубликованы основные результаты диссертаций на соискание учёной степени кандидата наук).

Ю.Егорова Е. К., Чебурахин И. Ф. О минимизации сложности и автоматизации эффективного представления булевых функций в классах формул и схем // Изв. РАН. ТиСУ. 2013, № 3, С. 121-129. (№ 963 в перечне рецензируемых журналов, в котором должны быть опубликованы основные результаты диссертаций на соискание учёной степени кандидата паук).

П.Егорова Е. К., Чебурахин И. Ф. ПРОГРАММА ДЛЯ ЭВМ Минимизация сложности представления произвольной булевой функ-ции/^ (п переменных) в классе формул. Версия 1.0 // Официальный бюллетень «Программы для ЭВМ. Базы данных. Топологии интегральных микросхем», регистрационный № 2012616794 от 30 июля 2012.

Подписано в печать:

17.07.2015

Заказ № 10891 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru