- •Воронежский государственный технический университет
- •Практикум по теории автрматов:
- •1 Цели и особенности курсового проектирования
- •1.1 Основные цели курсового проектирования
- •4 Оформление расчетно – пояснительной записки
- •5.3 Начальная формализация задачи синтеза уа
- •5.4 Переход к абстрактному автоматному описанию уа
- •6.1 Выбор типа элементов памяти.
- •6.2 Структурное кодирование входных, выходных сигналов и состояний автомата
- •6.3 Детализация блока памяти
- •6.4 Составление расширенной структурной таблицы переходов и выходов
- •6.5 Канонический синтез логического преобразователя
- •Воробьев н.И. Проектирование электронных устройств: Учебное пособие. – м.: Высш. Шк., 1989. – 223 с.
- •Учебное издание
- •394026 Воронеж, Московский просп.,14
5.3 Начальная формализация задачи синтеза уа
Задача разработки (синтеза) управляющего автомата может быть поставлена перед разработчиком в различных вариантах. Это может быть словесное описание функционирования устройства, различного рода таблицы, временные диаграммы, циклограммы, ориентированные графы и т.п., определяющие последовательность и условия выполнения тех или иных операций по реализации алгоритма функционирования устройства.
Для применения общепринятых методов синтеза исходную постановку задачи необходимо формализовать, т.е. привести ее к каноническим формам описания управляющих автоматов. Обычно при проектировании используется методика синтеза микропрограммных управляющих автоматов, основанная на использовании граф-схем алгоритмов (ГСА).
ГСА – это ориентированный связный граф, включающий вершины четырех типов: начальную, конечную, операторную и условную (рис. 5.2). Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет. У начальной и операторной вершин по одному выходу, у условной – два выхода, помеченных символами 1 и 0. Конечная вершина выходов не имеет.
ГСА удовлетворяет следующим условиям:
входы и выходы вершин соединяются друг с другом с помощью дуг, направленных всегда от выхода ко входу;
каждый выход соединен только с одним входом;
л
53
юбой вход соединяется, по крайней мере, с одним выходом;любая вершина ГСА лежит, по крайней мере, на одном пути из начальной вершины к конечной;
в каждой условной вершине записывается один из элементов множества X={x1, … , xL} логических условий (разрешается в различных условных вершинах запись одинаковых элементов множества Х);
один из выходов условной вершины, помеченный “0” или “1”, может соединяться с ее входом, что недопустимо для операторной вершины; такие условные вершины будем иногда называть возвратными или ждущими;
в каждой операторной вершине записывается оператор (микрокоманда) Yt – подмножество множества микроопераций Y={y1, …, yN}; допускается Yt = 0; разрешается также запись в различных операторных вершинах одинаковых микрокоманд.
0 1
а), б) - начальная и конечная вершины; в) - операторная вершина;
г) - условная вершина.
Рис. 5.2 Графическое представление вершин ГСА.
На первом этапе формализации алгоритм функционирования УА разбивается на ряд шагов, выполняемых последовательно во времени. В процессе такого разбиения выделяются все операции (действия) по выполнению алгоритма, а также условия выполнения этих операций на каждом конкретном шаге.
Условия обязательно формулируются в виде вопроса, на который возможными ответами являются ДА или НЕТ.
Выполняемые операции каждого шага заносятся в операторные вершины ГСА, а условия перехода от одного оператора к другому - в условные вершины.
П
54
Кроме того проверяется возможность одновременного совмещения нескольких операций на некоторых шагах алгоритма, а также объединение нескольких мелких операций в более крупную при наличии соответствующего исполнительного механизма в объекте управления.
ГСА относится к начальным языкам описания алгоритма функционирования управляющего автомата. Характерной особенностью начальных языков является то, что они не позволяют в явном виде задать функцию переходов. Поэтому для дальнейшего синтеза управляющего автомата необходим переход от начального языка описания работы автомата (т.е. от ГСА) к какому – либо автоматному языку описания, например, к таблицам переходов и выходов.