5.3 Начальная формализация задачи синтеза уа

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

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

ГСА – это ориентированный связный граф, включающий вершины четырех типов: начальную, конечную, операторную и условную (рис. 5.2). Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет. У начальной и операторной вершин по одному выходу, у условной – два выхода, помеченных символами 1 и 0. Конечная вершина выходов не имеет.

ГСА удовлетворяет следующим условиям:

1. входы и выходы вершин соединяются друг с другом с помощью дуг, направленных всегда от выхода ко входу;

2. каждый выход соединен только с одним входом;

3. л

   53

   юбой вход соединяется, по крайней мере, с одним выходом;

4. любая вершина ГСА лежит, по крайней мере, на одном пути из начальной вершины к конечной;

5. в каждой условной вершине записывается один из элементов множества X={x₁, … , x_L} логических условий (разрешается в различных условных вершинах запись одинаковых элементов множества Х);

6. один из выходов условной вершины, помеченный “0” или “1”, может соединяться с ее входом, что недопустимо для операторной вершины; такие условные вершины будем иногда называть возвратными или ждущими;

7. в каждой операторной вершине записывается оператор (микрокоманда) Y_t – подмножество множества микроопераций Y={y_{1, …,} y_N}; допускается Y_t = 0; разрешается также запись в различных операторных вершинах одинаковых микрокоманд.

0

1

а), б) - начальная и конечная вершины; в) - операторная вершина;

г) - условная вершина.

Рис. 5.2 Графическое представление вершин ГСА.

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

Условия обязательно формулируются в виде вопроса, на который возможными ответами являются ДА или НЕТ.

Выполняемые операции каждого шага заносятся в операторные вершины ГСА, а условия перехода от одного оператора к другому - в условные вершины.

П

54

ри составлении содержательной ГСА производится ее уточнение. Для каждой элементарной операции в объекте управления выделяется исполнительный механизм (операционный автомат), аппаратно ее реализующей. Если такого соответствия достигнуть не удалось, операции подлежат разбиению на более мелкие операции с соответствующей корректировкой ГСА.

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

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