ИНЖЕНЕРНЫЕ МЕТОДЫ СИНТЕЗА ДИСКРЕТНЫХ АВТОМАТОВ

— совокупность приемов и правил, используемых в инженерной практике при логическом синтезе схем дискретной автоматики, телемеханики и вычислительной техники с учетом реальных физических ограничений на элементы и структуру схемы. Эти приемы и правила можно разбить на три группы: задание работы будущего устр-ва и абстрактный синтез, блочный синтез и структурный синтез с учетом реальных ограничений.

Языки задания работы устройства. Классические способы задания в виде автоматных таблиц или таблиц истинности при проектировании сложных устр-в неприменимы из-за своей громоздкости. Поэтому в инженерной практике для задания закона функционирования будущего устр-ва используют спец. сжатые способы записи. Наиболее распространены язык секвенций, язык логических схем алгоритмов и язык технологич. графов. Задание на языке секвенций представляет собой совокупность выражений вида Р В левой и правой частях этих выражений указаны переменные или их отрицания, разделенные запятыми или объединенные знаками конъюнкций. Каждая запись вида Р имеет следующий смысл: если в объекте происходит изменение сигналов, обращающее хотя бы одно из выражений в левой части секвенции в единицу, то происходит соответствующее изменение всех сигналов, указанных в правой части секвенции. Напр., означает, что когда принимает значение, условно сопоставляемое с 1, или принимает значение, условно сопоставляемое с 0, а — с 1, то принимает значение значение 0. Задание на языке логич. схем алгоритмов представляет собой, по существу, совокупность микропрограмм, которые должны быть реализованы устр-вом, и информацию о порядке выполнения этих микропрограмм в зависимости от внеш. условий. Задание в виде технологич. графа представляет собой графич. изображение процесса проверки допустимости того или иного технологич. режима и процесса смены этих режимов. Напр., задается пара технологич. графов, соответствующих процессам пуска и остановки гидроагрегата, и граф проверок допустимости пуска или остановки. Такие инженерные языки задания работы устр-в требуют разработки спец. методов перехода от них к явному выражению ф-ций перехода и выхода автомата или к таблице истинности ф-ций. В связи с внедрением автоматизации проектирования с помощью ЭВМ возникла необходимость в создании спец. языков проектирования. Примерами языков такого типа могут служить ЛЯПА С, АЛОС и АЛГОРИТМ.

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

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

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

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

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

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

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

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

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

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

Наконец, на этапе инженерного синтеза решается круг проблем, связанных с повышением надежности получаемой схемы. Кроме выбора системы элементов, удовлетворяющей требованиям надежности, предъявляемым к синтезируемому автомату, можно еще повысить надежность автомата за счет структурной избыточности. Методы введения структурной избыточности могут быть весьма разнообразны: резервирование всего автомата или части его, мажорирование наиболее «опасных» частей логич. преобразователя или памяти, добавление обходных цепей в логич. схеме и т. д. Существует много методов внесения структурной избыточности на основе анализа и преобразования апалитич. выражений для ф-ций переходов и выходов автомата. Однако до последнего времени эти методы носили частный характер и накладывали существенные ограничения на характер сбоев, допускаемых в схеме: независимость сбоев в отдельных элементах, фиксированный характер отказов, симметричный характер сбоев типа 0—1 и 1—0.

См. также Автоматизация проектирования ЦВМ.

Лит.: Лазарев В. Г., Пийль Е. И. Синтез асинхронных конечных автоматов. М., 1964 [библиогр. с. 252—257]; Якубайтис Э. А. Асинхронные логические автоматы. Рига, 1906; Рабинович 3. Л. Элементарные операции в вычислительных машинах. К., 1966 [библиогр. с. 299—301]; Поспелов Д. А. Логические методы анализа и синтеза схем. М., 1968 [библиогр. с. 324—328].

Д. А. Поспелов.