АКТУАЛЬНОСТЬ ПРОБЛЕМЫ. В диссертации рассматриваются методы аппаратной и программной реализации алгоритмов логического управления, которое основано на истинности и ложности входных и выходных переменных.
Основные теоретические исследования в этой области были начаты в мире с конца 30-х годов этого века. В течение многих лет признанным лидером в этом направлении в СССР был член-корреспондент АН СССР Михаил Александрович Гаврилов (1903;1979), работавший в Институте проблем управления (Институте автоматики и телемеханики) АН СССР (Москва), создавший школу по теории релейных устройств и конечных автоматов.
Автор начал заниматься исследованиями в области логического управления в научно-производственном объединении (НПО) «Аврора» (Ленинград) с середины жизни этого научного направления — с 1971 года, после окончания Ленинградского электротехнического института им. В. И. Ульянова (Ленина). Это было время расцвета теоретических исследований в этой области и широкого внедрения комплексных систем управления сложными промышленными и транспортными объектами. При этом возникало много теоретических и практических задач, в решении которых автор принимал участие. Это привело автора к активным, почти тридцатилетним исследованиям в указанной области, результатом которых является настоящая диссертация.
За эти годы элементная база систем логического управления быстро изменялась, пройдя путь от релейно-контактных элементов, микросхем малого и среднего уровней интеграции к программным логическим устройствам, а затем к большим и сверхбольшим интегральным схемам, частным случаем которых являются микропроцессоры и микроконтроллеры, которые используются в качестве вычислительного ядра в том числе и в промышленных (управляющих) компьютерах и программируемых логических контрол.
— и лерах.
При этом в настоящее время в крупных и долго существующих организациях весьма часто возникает ситуация, когда в одной и той же организации одновременно ведутся проектирование, модернизация и модификация различных поколений систем логического управления, в каждой из которых превалирует тот или иной тип элементов и устройств из указанного выше спектра.
Каждый тип элементной базы порождает свои критерии и ограничения, что, в свою очередь, приводит к постановке научных задач, решение которых позволяет выполнить выдвигаемые практикой требования.
Эти требования связаны с различными характеристиками систем логического управления, например такими, как надежность, живучесть, диагностика. Однако все эти годы научные интересы автора были связаны с другими аспектами построения систем этого класса, которые характеризуются такими терминами, как «логическое проектирование» или «логический синтез», и были посвящены разработке формализованных методов аппаратной и программной реализации алгоритмов логического управления, которые являлись актуальными на протяжении многих лет и являются актуальными в настоящее время.
Так, например, задача синтеза комбинационных схем в базисе априори заданных произвольных элементов, решаемая в настоящей работе, являлась актуальной при использовании логических элементов различной физической природы и сложности и не потеряла своей актульности в настоящее время применительно к сверх/большим интегральным схемам программируемой логики, базисом которых являются функциональные преобразователи различной сложности.
Если при построении схем ставились задачи минимизации аппаратуры (внешних выводов у настраиваемых модулей и модулей в схемах) и ее унификации, предельным случаем которой является однородность, то при программной реализации оптимизировались объем памяти и быстродействие при одних методах и «понятность» и «безошибочность» программ при других методах, что связано с большой ответственностью объектов, управляемых системами рассматриваемого класса. Последнее свойство было и остается актуальным и при построении схем любого уровня интеграции.
При разработке предлагаемых методов везде, где это было возможно, автором были получены оценки сложности предстоящих реализаций. Отметим также, что если некоторые классы схем и программ изоморфны и поэтому могут строиться одинаковыми методами, то возможность работы с целыми числами и арифметическими операциями позволяет предложить методы программной реализации алгоритмов логического управления, которые не имеют аналогов в аппаратуре.
При этом для аппаратных реализаций автором предложены методы построения только комбинационных схем, а для программных реализаций рассматривались также и автоматы с памятью. Это связано с тем, что «синхронность» программных реализаций резко упрощает построение этого класса автоматов по сравнению с построением асинхронных схем с памятью, синтез которых в настоящее время является отдельным направлением в логическом проектировании.
Специфика комбинационных схем, рассматриваемых в настоящей работе, состоит в том, что так как они в системах логического управления технологическими процессами в большинстве случаев воздействуют на инерционные исполнительные механизмы, то для них может не решаться проблема риска и не обеспечиваться высокое быстродействие. Другая особенность этих схем состоит в том, что они обычно реализуют булевы формулы с малой повторностью переменных. Такие формулы характерны также и для пометок дуг графов переходов, описывающих поведение автоматов с памятью, применяемых в системах этого класса.
В логическом проектировании кроме задач, непосредственно возникающих из потребностей практики, имеется также уже ставшая традиционной область теоретических задач, связанных с исследованиями как класса всех булевых функций, так и его подклассов. Большой интерес представляют также исследования булевых формул, являющихся одной из реализаций булевых функций, первичным заданием которых являются таблицы истинности. При этом, по мнению автора, особую важность имеют простейшие из булевых формул — бесповторные (в определенном базисе), свойства которых, как показано в настоящей работе, связаны с такими фундаментальными понятиями математики (в основном дискретной), как например эйлеровы графы, клики в графах, числа Фибоначчи и число «е». Кроме того в работ? показано, что для булевых формул (в определенных базисах) некоторые характеристики имеют линейные от числа букв оценки сложности.
ЦЕЛЬЮ ДИССЕРТАЦИОННОЙ РАБОТЫ является разработка методов аппаратной и программной реализации алгоритмов логического управления технологическими процессами, обеспечивающих повышение качества схем и программ, построенных на их основе.
ОСНОВНЫЕ ЗАДАЧИ ДИССЕРТАЦИИ, определяемые целью диссертации, состоят в следующем.
1. Исследование свойств и количественных характеристик булевых формул (БФ) (в основном бесповторных), двухместные операции в которых подчиняются сочетательному закону.
2. Разработка метода синтеза одновыходных комбинационных схем в произвольных априори заданных элементных базисах по БФ и получение оценок сложности предстоящих реализаций.
3. Разработка метода синтеза одновыходных комбинационных схем в произвольных априори заданных элементных базисах по булевым функциям (БФУ), заданным таблицами истинности (ТИ).
4. Разработка метода построения многофункциональных логических модулей (МЛМ) из функциональных элементов (элементов с односторонней проводимостью) с минимизированным числом внешних выводов.
5. Разработка МЛМ из элементов с двусторонней проводимостью и методов реализации комбинационных схем на их основе с оценками сложности предстоящих реализаций.
6. Оценка функциональных возможностей программируемых логических матриц.
ПЛМ) в классе БФ.
7. Разработка различных типов однородных структур для реализации БФ и методов реализации последних с оценками сложности предстоящих реализаций.
8. Разработка метода реализации БФ линейными бинарными графами с оценками сложности предстоящих реализаций.
9. Разработка методов реализации систем БФУ с помощью арифметических полиномов.
10. Разработка методов программной реализации автоматов с памятью.
11. Разработка технологии алгоритмизации и программирования задач логического управления.
МЕТОДЫ ИССЛЕДОВАНИЙ базируются на булевой алгебре, теории переключательных схем и конечных автоматов, комбинаторике, теории графов, теоретическом программировании и линейной алгебре.
НАУЧНАЯ НОВИЗНА РАБОТЫ состоит в полученных теоретических результатах, перечисленных в заключении.
ДОСТОВЕРНОСТЬ научных положений, выводов и практических рекомендаций подтверждается корректным обоснованием постановок задач, точной формулировкой критериев, математическим доказательством, а также результатами практического использования решений, предложенных в диссертации. Результаты, которые не доказаны, но базируются на предположениях автора, основанных на интуиции и большом числе примеров, сформулированы как гипотезы.
ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ состоит в том, что все полученные результаты могут быть использованы, а некоторые используются, на практике. Они позволяют для аппаратных реализаций сократить элементную сложность, а для программных — объем памяти и время вычислений. Однако, главное их значение состоит в повышении достоверности проектных решений принимаемых на их основе. Они делают эти решения понятными для Специалистов различных областей знаний и квалификации. Формализованное^ предлагаемых методов позволяет их автоматизировать, что для некоторых из них выполнено.
РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Результаты работы внедрены в части:
— многофункциональных логических модулей во ВНИИ «Альтаир» при создани: микросборки ЛГ83, выпускавшейся в трех модификациях (ЛГ183, ЛГ283, ЛГ383), и при создании отраслевого стандарта 0СТ5.8354−74 «Микросхемы гибридные сложные — микросборки „Пакет“. Руководство по применению», а также в НПО «Аврора» при создании унифицированных логических плат для систем управления типа «Корунд» ;
— однородных модулей из элементов с двусторонней проводимостью в НПО «Аврора» при создании унифицированных кассет логики для систем управления типа «Молибден» ;
— SWITCH-технологии в НПО «Аврора» при создании системы управления дизель-генератором ДГР-2А 500*500 для трех судов проекта 15 640 на базе аппаратуры «Selma-2» фирмы «ABB Stromberg» (Финляндия) — системы управления дизель-генератором того же типа для судна проекта 15 967 на базе аппаратуры «Selma-2» фирмы «ABB Stromberg» (Финляндия) — системы управления дизель-генератором того же типа для судна проекта 15 760 на базе аппаратуры фирмы «Norcontrol» (Норвегия) — комплексной системы управления техническими средствами пяти судов проекта 17 310 на программируемых логических контроллерах (ПЛК) «Autolog» фирмы «FF-Automation 0Y» (Финляндия) — комплекта «Авролог» для управления техническими средствами судна проекта «ПС 500» на ПЛК «Autolog» — АСУ ТП центральной подготовительной станции первичной обработки нефти «Авролог-НП1» на ПЛК «Autolog» (Северо-Ореховское месторождение) — АСУ ТП дожимной насосной станции «Авролог-НП2» на ПЛК «Autolog» (Северо-Покурское месторождение системы управления турбокомпрессорным агрегатом. «Ларина» на основе микроэвм КР 1816 ВЕ51, используемой при производстве полиэтилена в ПО.
Полимир" (Новополоцк) — транслятора «Ядро языка СИ — язык инструкций ALPro» для ПЛК «Autolog» .
Результаты работы использовались в учебном процессе в Институте повышения квалификации руководящих работников и специалистов судостроительной промышленности (Ленинград) — Ленинградском элекротехническом институте им. В. И. Ульянова (Ленина) — Ленинградском политехническом институте им. М.И. КалининаСанкт-Петербургском институте точной механику и оптики (техническом университете).
АПРОБАЦИЯ РАБОТЫ. Основные результаты диссертации докладывались на следующих основных конференциях, совещаниях и семинарах: III (Таганрог, 1972) и IV (Киев, 1975) Всесоюзных конференциях «Однородные вычислительные системы и среды» — II Всесоюзной межвузовской конференции «Алгоритмические методы проектирования цифровых систем» (Л., 1972) — Советско-Болгарском семинаре «Теория автоматов и ее приложения» (М., 1973) — V (Севастополь, 1973), VI (Л., 1982) и VII (Л., 1989) Всесоюзных научно-технических конференциях «Проблемы создания систем управления судовыми техническими средствами» — симпозиуме ИФАК «Дискретные системы» (Рига, 1974) — VI (М., 1974), IX (Ереван, 1983), X (Алма-Ата) и XI (Ташкент, 1989) Всесоюзных совещаниях по проблемам управленияIII Всесоюзном совещании «Логический синтез в дискретных однородных средах» (Рязань, 1974) — постоянно действующем семинаре «Конечные автоматы» Научного Совета по автоматизации научных исследований и проблемам кибернетики при Президиуме АН Латвийской ССР (Рига, 1975) — XVI (Челябинск, 1976), XXI (Таллин, 1981), XXXII (М., Подлипки, 1993) и XXXV (М., Челюскинская, 1996) Всесоюзных школах-семинарах по теории автоматов им. М. А. Гавриловапостоянно действующем семинаре «Теория автоматов» при НТО приборпром им. ак. С. И. Вавилова (Л., 1978, 1986) — Всесоюзном семинаре «Однородные вычислительные структуры и малые ЭВМ» (М., Звенигород, 1979) — III (Ташкент, 1984) и IV (Новосибирск, 1989).
Всесоюзных совещаниях «Методы и программы решения оптимизационных зада на графах и сетях» — школе-семинаре «Автоматизация логического проектирования» (Севастополь, 1982) — VIII Всесоюзном симпозиуме «Логическое управление» (Куйбышев, 1985) — научно-координационном совещании «Применение микропроцессорной техники в системах управления» секции «Техническая кибернетика» Минвуза СССР (Суздаль, 1986) — Всесоюзном семинаре «Логические методы построения однородных и систолических структур» (М. Звенигород, 1988) — постоянно действующем семинаре ВЦ СО АН СССР «Математическое и архитектурное обеспечение параллельных вычислений» (Новосибирск, 1989) — постоянно действующем семинаре «Теория графов» Института математики СО АН СССР (Новосибирск, 1989) — 10th IEEE International Symposium on Intelligent Control. ISIC Workshop «Architectures for Semiotic Modeling and Situation Analysis in Large Complex Systems» (Monterey, California, 1995) — International Conferens on Informatics and Control (ICI&C97) (St. Petersburg, 1997) — научно-техническом сове те НПО «Аврора» (СПб., 1998).
По теме диссертации опубликовано 114 основных работ, в том числе 2 монографии, 14 книжных изданий, 27 статей и 53 авторских свидетельства на изобретения.
Кроме того в Санкт-Петербургской издательской фирме «Наука» Российской Академии наук в работе находится монография автора «Логическое управление. Методы аппаратной и программной реализации алгоритмов» объемом 4.1,5 печатных листов, срок выпуска которой по договору — 1999 г. Монография кроме И глав, включенных практически полностью в диссертацию, содержит еще 10 глав, в которых приводятся результаты исследований автора, также относящиеся к теме диссертации, но не включенных в нее в виду большого объема. Эти главы имеют следующие наименования: реализация булевых функций схемами из мажоритарных элементовреализация булевых функций схемами из мультиплексоровиспользование мультиплексорного метода для реализации схем в различных элементных базисахпостроение многофункциональных логических модулеймодули, универсальные в классе симметрических функциймодули универсальные в классе самодвойственных функций и в «близких» к ним классахмодули, универсальные в классе всех булевых функцийметоды построения бинарных графов для автоматов без памятилогические устройства для последовательного вычисления булевых функцийнетрадиционные методы вычисления булевых функций.
СТРУКТУРА И ОБЪЕМ ДИССЕРТАЦИИ
Диссертация состоит из оглавления, введения, одиннадцати глав и заключения. Список работ, составленный по главам, содержит 356 наименований. Объем работы — 392 страниц. Она содержит 144 рисунка, 22 таблицы и 141 пример.
ВЫВОДЫ.
1. Определено количество типов бесповторных булевых формул (ББФ) в базисе И, ИЛИ, НЕ в различных классификациях.
2. Выполнено табулирование представителей PN-типов этих формул при h <= 8.
3. Определено рекуррентное соотношение для подсчета неизоморфных деревьев из двухвходовых элементов.
4. Рассмотрены покрывающие деревья и на их основе предложены модули, универсальные в указанном классе формул с простой структурой.
5. Рассмотрена PN-классификация ББФ в базисе И, ИЛИ, НЕРАВНОЗНАЧНОСТЬ, НЕ и выполнено их табулирование при h <= 4.
6. Установлено, что ББФ в базисе И, ИЛИ, НЕ, существенно зависящие от всех переменных, имеют нечетный ранг.
7. Предложены методы подсчета числа единиц при формульном задании булевой функции.
8. Определены свойства бесповторных пороговых формул и установлена их связь с числами Фибоначчи.
9. Определены отношения покрытия, при выполнении которых булева формул в форме, аналогичной разложению Шеннона, не будет содержать переменных «разложения'1 с инверсиями.
10.Предложен метод совместной реализации булевых функций, обладающий меньшей трудоемкостью по сравнению с «гарвардским» методом.
11. Получены новые соотношения для преобразования булевых функций и на примерах показана целесообразность их применения при решении ряда задач логического проектирования.
