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

шэлектрогехпртбор

Аяадешл науп СССР

Ордена Ленина Институт проблей управления (азто!гатзш! и теле1гех£н:пш)

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

ЧЕЕФАХИН Игорь Федорович

УДК 681.513:681.325.66:519.713 АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ ОППЕШШЬК СГЕШУР И ПР0ГРАШ1 ЛОГИЧЕСКОГО УПРАВЛЕНИЯ МЕТОДОМ КОНСТКПГПВНОГО ВЫРАВНИВАНИЯ

зециадьиоегь C5.I3.I2 - Систены автошггязнровышого

проектирования

Автореферат

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

Цосква - 1530

Работа выполнена в ордена Ленива -Институте проблем управления (автоматики и телемеханики).

Научный руководитель - доктор технических наук, профессс!

Девятков В.В

Официальные оппоненты - доктор технических наук, профессс

Лазарев В.Г.

доктор технических наук, старший научный сотрудник Артюхов В.Л.

Ведущее предприятие - ВНИПИ САУ.

8ащита состоится и Л_ 1990г. в_чао.

на заседании Специализированного совета № к (К002.68.01) Института проблем управления (автоматики и телемеханики). Теле фон Совета: 534-95-29.

Адреа Института: косква, 117342, Профсоюзная ул., 65.

С диссертацией можно ознакомиться в библиотеке Института.

Автореферат разослан 11_" | 1990г.

Ученый секретарь Специализированного совета .

к.т.н. ''у...' * Ф.Ф.Пащенко

дУ '-

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

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

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

БМК характеризуются как большим числом различных типов логических элементов, так и большим числом самих элементов,'и ' их применение для синтеза оптимальных^по числу элементов) бхем отличается повышенной трудоемкость»! по сравнению с использование1.« простейших элементных базисов. Путь эволюции традиционных методов синтеза - постепенного адаптирования к новым особенностям реальных задач - где-то исчерпал свои возмо-

- г -

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

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

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

Научная новизна. В результате проведенных научных исследований, анализа АЛУ и теучических средств (Ш1К и БЫК) разработан комплекс формализованных моделей, методов, алгоритмов и программ, обеспечиваю^!! процесс анализа, преобразования и программной и аппаратной реализации формул на основе их строения. Применение предложенного комплекса моделей, методов и алгоритмов обеспечивает: синтез оптимальных или близких к ним (ьо числу команд и времени) программ для реальных ПЛК посредством предложенных методов функциональной декомпозиции и трансформации на основе использования минимизации ДНФ и приведения ца_к скобочному виду,-разработанной классификации формул по типам с целью их минимальной (по. числу команд и времени) реализации й рекомендованных для этого преобразований,

гоч11В«: оценок слоености (по числу команд и времени) прогрета, вычисляемых по числовым параметрам исходных формул; синтез оптимальных или близких к шш (по числу элементов) логических схем посредством разработанного метода функциональной декомпозиции и на основе точных оценок сложности (!ю числу формул) декомпозиции формул, вычисляемых по числовым параметрам исходных формул, условий минимальной декомпозиции (исключающих перебор) для выделенного подкласса монотонных бесповторных ДНФ, зависящих от любого конечного числа переменных, вида /«= К, V Кг » где К1 м - элементарные конъюнкции.

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

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

Внедрение. Результаты работы внедрены на предприятиях и организациях: ИПУ АН СССР (в составе АМПЛУА), ЦКБ.(г.Новгород), НИИ ЧАСПРОМ (г.Москва), КАМАЬ (г. Набережные Челны), Тяжстанкогидропресс (в составе АМПЛУА), а также используются в учебной процессе ЫПУ им. Н.Э.Баумана.

Апробация работы. Основные результаты диссертационной работы докладывались и обсуждались на зкспе^ ных семинарах Института проблей управления АН СССР (1984), на ХХХП конференции молодых ученых и специалистов Института проблем управления (1986), на 4-м научно-технической семинаре "Математическое обеспечение систем с машинной графикой" (Суздаль, 1986), Ка Всесоюзной конференции "Автоматизация проектирования систем планирования и управления" (Звенигород, 1987), на Международной конференции "Проблемы автоматизированного проектирования в машиностроении" (Сосква, 1983), на Всесоюзной конференции "Современные проблемы информатики, вычислительной техники и автоматизации" (Москва, 1988).

Связь диссертации с планом научных работ. Проведенные автором исследования выполнены в соответствии с планами по заданию 6.6 "Развитие САПР комплексов программно-логического "управления дискретными и дискретно-непрерывными объектами и процессами на базе использования микропроцессорных средств" проблемы E.2.I САПР КП НТП СЭВ (номер гос. регистрации -01.88.0 001254).

Публикации. По теме диссертации автором опубликовано 12 печатных' работ.

Структура и объем работы.- Диссертация состоит из введения шести глав, заключения, списка литературы из % наименований и приложения Объем диссертации - 26?. маыпгописные страницы, в том числе 169 страниц основного текста.

- 5 -

ССДЕИШШ РАБОТЫ

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

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

" АЛУ основную дола составляют булевы вычисления, но имеются и несложные арифметические. Булевы вычисления всь чане задаются с помощью формул.

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

Е работах С.У. 1.ее пгкведен анализ программ, вычисляющих булевы функции, определено понятие бинарной программы, в которой в отличие от операторной программы используется команда условного перехода и - присвоений значения; отмечено преимущество бинарных программ по сравнению с операторными ч отношении времени выч;«ления булевой функции /(Х,,..., Ха) , г;«' - булзвы переменные, а для числа коынд

1>кт(£п) в бинарной программе даны шшняя и верхннч оценки. По числу команд бинагше и операторше программы асимптотически

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

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

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

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

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

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

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

Важной частью аппаратной и частично программной реализации булзвых формул является их декомпозиция. Поэтому на основе проведенного анализа для аппаратной и частично программной реализации формул выделяется этап предварительной функциональной декомпозиции формул,' на основе понятия "близости" формул и их сравнения. Для этого предлагается использовать понятие "строение" ДНФ, определяемое по ее числовым параметрам. При этом применяется расширенное понятие базиса. Это для аппаратной реализации - набор формул или набор логических элементов и/или некоторых схем, собранных из них; для программной - набор формул или набор команд и/или подпрограмм, ви'шсляюр некоторые формулы, но может быть и программа, генерируадая требуемые подпрограммы по параметрам реализуемых формул.

Из булэвых формул в диссертации рассматриваютзя ДНФ и' скобочные формулы в базисе , в которых отрицаний может относиться как к отдельной подформуле, так и к самой 4-ормуле, и применяются следующие обозначения: - число букв в

ДН* 4 сксоочной формуле / ; ~ длина ДНО / ;

- число операция конъюнкция в формуле / ; -

число операций дизъюнкциг в формуле / .

Во второй глазе дано описание математических средств, используемых для аппаратной и программной реализации формул на основе функциональной декомпозиции для достаточно широкого мабора ¿зхнических средств СБМК, СКС, ПЛК).

Ванную часть реализации бу.-хвых формул составляет метод

декомпозиции дизъюнктивных нормальных форм (ДНФ), в которой

т

основную роль играет строение ДНФ. Если = У К\ ,

где К{ , 1-1,..., т - элем «тарная конъюнкция (Сд) ранга , - ДНФ, то ее строение удтегатически будем отокдествл-'ть с так называемым Гектором рангов ... • Для чис-

ла переменных с отрицанием в ЭК , ** ДНФ 4

применяется веьхор инверсий Л. . Повторение переменны^ в прямом и инверсном виде учитывается с пшощ>ю двух матриц б = ' где — . И С^(се$) , где

Б = ..., П , в которых первая строка отмечаем повто--реьне переменных в прямом вида, а вторая - в инверсном виде, Причем число ^ , показывает сколько

переменны:, ^'-й ЭК встречается в предыдущих ЭК - €г/ - О) , а число , 5показывает сколько раз перемен-

ная Х$ встречается во г зх ЭК. Векторы г и 5. , матрицы Б

и С , список букв ,...,х(г/ х2, , . .....%

получаемый из записи ДНФ { (для Ху* I есть номер ЭК, а ^ есхь но1/."р буквы в этой. ЭК) составляют ыатематико-ин-фс мац и с нное описе...ие ДНФ { , используемое ниже для раз р. .о-тки алгории в (различных преобразований и •тинимизапш ДНФ) и программ вычисления ДНФ, которое аналогично определяется для

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

Пусть вектору рангов ДНФ -?=У К{ и «О**/ К[ будут

зоответственно ■■■\Гп) и ;. где

/Л=тах . Будем говорить, что: две ДНФ 4 и £

;шеют одно и то яе строение, если ? ДНФ 4 ив слож-

нее ДН® 0, , если ; 1*1,...,Ж . Отношение "иметь

эдно и то кв строение" есть отношение эквивалентности, а отношение "не слозу.эе" есть отношение частичного порядка» которые используются в рсолизчции ДНФ на основе функциональной де-

композщй v.

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

у-{(К) . Для агтдкатизации конструктивных операций, примоияо?:ых при , яомйознлии, игшмизации и других преобразований формул, важную рель играет их ыат0матико-1ш$оркш..;;онное описание. Метод, использующий конструктивные операции л мате-матико-информационное описание формул, будем называть методом

- 10 -

конструктивного выравнивания (ЫКВ).

Устанавливая соответствие между логическими и арифметическими операциями (базиса 1} с базисом {*,-+,-} лц )» можно использовать определенное выше ыатематико-инфорыационное описание для рациональных выражений. При этом к ним будут применимы основные конструктивные операции и некоторые результаты, полученные для булевых формул..

В третьей главе дано описание методов.конструктивного выравнивания. В ЫКВ, применяемом для. декомпозиции булевых формул, важную роль играет алгоритм одного шага декомпозиции "сверху" ДНФ (А1). Обоснованием его является следующее утверждение: если две монотонные ДНФ / и ^ имеют одно то ае строение и ДНФ £ без повторения переменных, то декомпозиция ДНО ^ в базисе одкошаговая и ее сложность

Пусть Ш) - монотонная ДНФ с вектором рангов Г и длиной ик\{\=гп , а базис йг1, .. где £, -сеоповюрная монотонная каноническая ДНФ с вектором рангов Ц [%>у2.) ' длиной Тогда, используя конструктивные операции, выполнение алгоритма А1 заключается сначала в выравнивании ДКФ / по длине, а затем по ЭК.

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

Декомпозиция произвольной ДНФ / и базисе Сд , считая, что векторы отрицаний ДКФ / к -енулезые, выполняется в два этапа: на первом - ДНФ / выравшззаетач по длине и по воем ЭК; на второе - в ЭК полученной внеаней ДНО выполняется перестановка переменных так , чтобы ниншшзировать число ин-

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

В классе монотонных ДН4 алгоритм А1 позволил получить для сех качественно различных случаез 1-3 точные оценки слоанос-и декомпозиции "сверху"; вычисляемые заранее по числовым па-аметрам исходной ДН© и базисной бесповторной ДНФ. Полученные ценки слоаности декомпозиции могут быть использованы для про-, зволыюй ДНФ без учета инверторов, а дополнительно выполняет-я минимизация числа инверторов. Для формулируемых ниае оце-ок слоаности считаем, что /Ш - монотонная ДНФ с вектором ангов Р , дл юй иь;({)-т и 1X1=К , а £(Т) - ыоно-онная бесповто^ .шя каноническая ДНФ с вектором рангов Ц, ,

линой = и /г/=«'.

Случай I. М=т'=/, I причем Г,=п и

ли /п>/, т>1, = г 1,...,т и /'Г,..., гп' •

огда сложность минимальной декомпозиции П - 1

I

Нил

П'-1

(I)

де ] - наименьшее целое, не меньшее числа X . Случай 2. ^ . Сложность декомпозиции

т

1=1

(2)

де

Случай

^ = к 8сли

' I 0, если .

3. / , . Сложность декомпозиции

Ц-1 + [ 0 т.-1

Чг* 1= 1 ¡и'-1

н

1-1 «'-♦

где при I , 2 = 1,т'- <

X.. = / ~ % +1• если > 9"/ ,

^ * Р. 0СЛИ

и при ¿»А/, т-ч)

р =е.-1г(с-№-<П "Г1' если

ЧН/ ^ I О, если

Разработанной ЫКВ, применяемый для декомпозиции монотонных бесповторных ДНФ ^(х,,...,Хп) в базисе ^=/¿/=2/^, =: эг, V х2} позволяет выполнить декомпозицию с минимальной сложностью, т.е.

Если для ДНО / и ^ выполняется , то, выполняя

т-1 Г

базисных ДНФ ^ и приводя новую

склеивание

т 1 1

ДНФ н к каноническому воду с > , получим,

что для монотонкой бесповторной ДНФ ' различными способами декомпог>Щии теперь будут перестановки ЭК ДНФ / . Для всех этих способов декомпозиции (считая ^ *^ при , чис-

ло перестановок ЭК с П + ГЦ ПР1! * V Р^110 гп' \ 1:на" че - меньше) по формулам (1)-(3), подсчитывая слокность декомпозиции (это составляет математическую модель декомпозиции) и выбирая из них наименьшую, получы* минимальную деком' позицию в'классе монотонных бесповторных ДНФ.

- 13 -

Если два монотонные бесповторные ДНФ / и £ одной длиг ны ™ то слоаности декомпозщии ДНФ* / в базисе £

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

0*1

На основе анализа математической модели для случая, когда ДНФ и зависит от любого конечного числа аргумен-

тов, а базисная ДНФ (мояет быть /и'>2 ) и

Ф1' случено два конкурирующих между собой способа декомпозиции, задаваемые следующими подстановками:

[к; кЛ А/

, I -Т-й способ, ^ I - 2-й способ,

соответственно со сложностью и ¿-2 • Причем для всех различных распределений мехду собой чисел (рангов) и получено, возмозьно, еще при некоторых'дополнительных условиях, что или , или , или > / , . Например, при таком распределении рангов Цг^1 осли |(т- -*) с Л, ^ /и -/) + ,

± и.(4,-1) + ж,л И/

или

то , если

то , если

( -'0 •+ ^г ^ * м (ч, -<) + ъ,, 1(п-1)(4,-1) и+ , ж,«.*/«/,

ю .

Полученные результаты применяются для минимальной декомпозиции ДНФ с повторением переменных или, что то яс самое, - бесповгерной скобочной формулы {-('.^КД&К^ , где /Г*, 1*1,1,1 -ЭК.

В Ш5, ярииеняемом для минимизации ДНФ и приведения их по

запросу к скобочному виду, применяются свойства дизъюнкции и п,

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

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

- 15 -

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

Синтез программ методом трансформации (11КВ) основывается на использовании базиса, состоящего из некоторых команд и специальных программ, которые для отдельных типов формул по их математико-ипфориационному описанию последовательно генерирует фрагменты требуемых программ для ПЛК.

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

и^ЛЛ-и^Ы*), (5)

скобочную формулу / с числом пар (открывающих и закрывающих) СКОбОК кос

иыМ-иМ + ЫЯ + ^М*1- (б)

Синтез программ методом декомпозиции (1ШВ) основывается на использовании базиса, состоящего из некоторых команд и (базисных) подпрограмм, вычисляющих определенные формулы одного (с различны:.!« щ 1 ел о в ьилихара к т е р и ст I: ка и:) и различных типов. Этим подпрограммам соответствуют базисные формулы (функционально полный базис), которые они вычисляют. Тогда синтез программ методом декс1..позкц:;и состоит в то:.:, что первоначально (после

определения типа формулы и возможного ее преобразования) выполняется декомпозиция формул по их иатематико-информационно-му описанию в функционально полном базисе, а затем производится замена полученных формул на вычисляющие их базисные" подпрограммы. Получаемую при этом сложность программы по числу команд (аналогично получается сложность программы по времени ее выполнения) рассмотрим на примере языка релейно-контактных схем для базиса - { £, = х? S xfl, £2 = ос,67 v х?} . тогда сложности базисных подпрограмм, вычисляющих функции и , по числу команд будут LKa»f£,)=3, LKCM (£¿) - Ч , а сложность декомпозиции ДНФ / в базисе &<р (или, что то se самое, в базисе, состоящем из подпрограмм) будет

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

LG(i)и И)-Ч. (7)

« Дя« произвольного базиса &<р слошюсхь синтезируемой программы будет получаться аналогично с использованием формул слог;;;ости декомпозиции (1)43) и учетом соответствующей сложности базисных подпрограмм.

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

распределении их вычисления между несколькими ПЛК.

С целью оптимизации синтеза программ для ПЛК выделены типы бесновторнах булевых ф-рмул и систем формул (вклп';ая и от-

- 17 -

(ельнуи формулу) с повторяющимися подформулами, для которых шределены условия, вырааенные через числовые параметры фор-¡ул, -'/или рекомендованы или нет их преобразования (по прави-гу Моргана, приведения к ДНО, скобочной формуле» сис-дмв фор-1ул) для оптимальной реализации. Это получено на основе срав-йния слояностеп (по числу команд и времени) синтезируемых фограмм, вычисляющих булеву функцию (систему функций) по ра-¡личшш ее аналитическим прел давлениям. Из всех изученных :лучаев (по выделению типов формул) рассмотрим в качестве при-¡ера случай с повторением 5 переменных (букв) в ^ ""«{ ДН© / сложностью иБ(1) . Для нее используем преобразование в жобочную формулу 4Ск » а обозначая выражение в скосках но-¡ой переменной X , - а систему более простых ДНО X • ¡алчности программ, вычисляющих булеву функцию по этгч трем :пособам задания, по числу команд будут для:

дм <

скобочной формулы {Ск -

с::стемы ДНФ / , X - ' П -st.

)ткуда следует, что предпочтительнее по числу команд являет-:я программа вычисления:

исходной ДНО / , если $t-S-Z<0i

скобочной формулы -{Ск или системы 1 » если

Если -5-2 - о , то число команд во всех программах шшаково и выбирается та из них, время выполнения которой шньше.

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

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

Пятая глава посвящена решению задачи синтеза оптимальКшх логических-схем. Логические элементы, из которых строятся эти схемы, входах' в состав СШ и БМК. Синтез подразделяется на два этапа. На предварительную функциональную декомпозицию исходных формул в базисе, описывающем заданиые логические элементы, и затем непосредственно аппаратная реализация полученных формул, т.е. построение схемы с учетом повторяющихся формул (сопоставление формулам соответствующих логических элементов). Сформулированный подход позволяет потнее учитывать основ ныэ особенности реальных и перспективных БШ я "разгружает" сам синтез. При этом эффективно для синтеза схем'используются полученные результаты по декомпозиции и минимизации формул. Так, в классе монотонных бесповторных ДНФ синтез схем в двухвходово1 базисе { $,V} минимален, точные оценки сложности декомпозиции являются одновременно и точными оценками сложности (по числу логических элементов) синтезируемой схемы при раздельной реализации формул. Они позволяют заранее оценивать сложность (по числу элементов) схемы, выраженную через число. вые параметры реализуемых формул, для слоаяых алгоритмов уп-рввлениА распределять их вычисление между несколькими БКК и оптимизировать (по числу элементов) проектируемую сквму на основе перестановок ЭК с различными рангами. Другими средствами для -оптимизации проеха-ируе&ой схшы .являются все основные зк-вивалентности, используемые в эвристическом методе минимизации ДНФ и приведения их к скобочному виду к применяемая методика минимальной декомпозиции в подклассе монотонныхЛНФ вида

{**K1vKí , где - ЭК, зависящих от любого конеч-

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

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

В шестой главе дано описание пакетов программ подготовки оптимальных АЛУ для ПЛК (пакет МЛАФ) и автоматизированного синтеза логически схем (пакет ДЕКА) на основе МКВ (методов декомпозиции формул, минимизации ДНФ и приведения их к скобочному виду, программной и аппаратной реализации булевых формул).

Пакет МЛАФ позволяет решать две задачи. Одна задача это трансляция логической части АЛУ из одной внутримашшшой формы представления в виде древовидных списковых структур, в другую - в виде специальных массивов, и обратно. Другая задача состоит в том, что по описании полученного АЛУ в виде специальных массызов, адекватному исходному описанию АЛУ на проблемно-ориентированном языке УСЛОЗИВ-82, на основе алгоритма 3.5.1 выполняется минимизация входящих в него булевых формул и по результатам классификации формул, представлений в 4-й

главе, оня приводятся к виду ДНФ или скобочной формулы, оптимальному для дальнейшей реализации нь ПЛК. При этом число букв в ЕНФ не солее 100, ее длина не более 13 и число аргументов но более 30.

'Пакет ДЕКА, используя описание АЛУ в виде специальных массивов, позволяет на основе алгоритма 5.3.1 синтезировать оптимальные или близкие к ним (цо числу элементов) логические схемы в базисе БМК или СИС. Ограничения на слолность (по числу элементов) получаемой схемы практически зависят от ОЗУ ЭВМ.

Все проц.аммы обоих шкетов написаны на языке С^ртран-4 и содержат по пакетам общее число программных предлог::лий: 2975 (МЛАФ) и 1275 (ДЕКА).

Приведены примеры, показывающие эффективность разработанных методов и алгоритмов написанных на их основе пакетов программ

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

ОСНОВ ШЛИ РЕсУЛЬТАТАЫИ РАЕОТЫ являются;

I. Комплекс методов преобразования и реализации формул (методы конструктивного выравнивания), включающие:

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

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

методы аппараиюй реализации формул (на основа декомпозиции "сверху"), учитывающие особенности Б1.1К и С1/С.

- 21 -

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

3. Оценки слоаностй реализации формул, вычисляемые по их шсловым параметрам, позволяющие без синтеза подсчитывать чи-■Ло команд и их время выполнения и число логических элементов I проектируемых программах и структурах, включая:

точные оценки сложности декомпозиции "сверху" в класса мо-ютонных ДНФ;

точные оценки числа инверторов при декоипоэиции "сверху"' ! классе бесповторных ДНФ (и методика их минимизации);

точные оценки сложности программы.по числу команд и време-ш выполнения;

верхние оценки сложности (по числу элементов) яри совмест-юй аппаратной реалячации формул.

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

димонотонных ДНФ 4- Ki VКt с повторением переменных, изгоняющие синтезировать оптимальные программы (по числу команд и зремени) и логические схемы (по числу элементов) позыпеьной сложности.

5. Пакеты прикладных программ:

приближенной минимизации ДНФ и приведения их к скобочному виду методами конструктивного выравнивания (тисло переменных не более 30, букв не более 100, длина ДНФ не более 13);

- 22 -

подготовки оптимальных алгоритмов логического управления методами конструктивного выравнивания для реализации их на ПЖ; синтеза оптимальных или близких к шш (по числу элементов) логических схем в бесповторном базисе методами кокструк тивного выравнивания (ограничения на сложность синтезируемой схемы нависят в основном от еыкости ОЗУ ЭВМ).

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

Список основных публикаций автора по теме диссертации:

1. Чебурахин M.S. Синтез схем из функциональных элементов Ч. I. Некоторые вопросы декомпозиции булевых функций. - Деп. в ВИНИТИ 14.01.85, » 373-85. - 13 с.

2. Чебурахин И.З. Синтез "схем из функциональных элементоЕ Ч. П. Сложность декомпозиции булевых функций, алгоритмы. -Деп. в ВИНИТИ 14.01.85, » 374-85. - 20 с.

3. Чебупахии И.Ф. Синтез схем и& функциональных элементо! Ч. Ш. Основные принципы, пакет программ. - Дуп. в ВИНИТИ

14.01.85, & 375-85. - 21 с. »

4. Чебурахин И.О. Основные принципы минимальной декомпозиции булевых функций в базисе "И", "ИДИ", "НЕ". - Деп. в ВИШИ, 5.04.86, »2348-85. - 25 с

5." Чебурахин И.Ф. Сложность декомпозиции булевых функций. Аналитическое решение задачи. - Деп. в ВИНИТИ 5.04.85, J? 23' 85. - 19 с.

6. Чебурахин И.О. Некоторые вопросы минимальной декомпозиции булевых функций в базисе "И", "ИЛИ", - Деп. в ВИНИТИ 15.07.85,«? 5117-85. - 25 с.

7; Чебурахни И.О. Алгебраический метод декомпозиции буле-ызс функций в заданном массе функций. - Деп. в ВИНИТИ .01.6&, I? ЮЗ-В. - 25 с.

8. Чебурахин Н.Э. Преобразование программ логического уп-авления и использование машинной графики. - Сб. тез. докл. -го Научно-технического семинара "Математическое обеспечено систем с машинной графикой". Устинов, 1586. - С. 38-40.

9. Чебурахни И.О. Автоматизированная подготовка программ огического управления методом декомпозиции. - Сб. тез. докл. сесоюзной конференции "Автоматизация проектирования систем лакирования и управления". М., 1987. - С. 132-134.

10. Чебурахин И.О. Об оценивании'сложности декомпозиции ехнических систем. - В сб.: Труды МВТУ, I? 473. П., 1987. -

69-76.

11. Пушрев Е.И., Чебурахин И.А., Четверикова И.В. Пакет рограмм проектирования и моделирования логики БИС. - Тез. .окл. Всес. конф. "Современные проблеш информатики, вычис-лтельноЯ техники и автоматизации". М., 1988. - С. 87-88.

12. Чичковский A.B., Чебурахин И.Ф. Система программировали логических контроллеров с языка высокого уровня на персо-[альной ЭВМ. -Тез. докл. Мевд.конф. "Проблемы автоматизирован-юго проектирования в машиностроении". М., 1988. - С. 13-14.

Личный вклад автора в совместные работы

В [II ] автором разработана методика декомпозиции систем ¡улевых формул, по которой написан пакет программ синтеза югических схем в базисе БИС. В [l2] разработана кдассифика- ■ (ия формул по типам на основе их числовых параметров и пов-

А.

'оряемости переменных с целью оптимальной реализации каждого 13 типов з реальных системах команд ПЛК и разработана мето-[ика использования этой классификации.