Построение отмеченной граф-схемы алгоритма

Для разметки граф-схемы алгоритма каждой совокупности микроопераций, находящихся в операторных вершинах, ставятся в соответствие управляющие микрокоманды (МК) Y₁…Y_n. Эти МК являются выходными сигналами УА и обеспечивают выполнение требуемых действий в соответствии со списком микроопераций (МО) ОА. Совокупность МО для каждой операторной вершины образуют микрокоманды, список которых представлен в таблице 4. Каждой условной вершине содержательной ГСА ставится в соответствие один из входных сигналов управляющего автомата X₁…X_m [1].

Таблица 4 – Список микрокоманд

Далее в полном соответствии с правилами разметки содержательной ГСА (см. ниже) строится отмеченная ГСА.

Предварительно в каждой условной вершине проставляются символы из множества входных сигналов УА – Х₁, Х₂, …, Х_М (таблица 5). Во всех операторных вершинах ГСА проставляют символы из множества выходных сигналов УА – У₁, У₂, …, У_N (таблица 5.1). Удобно в каждой операторной вершине ГСА вслед за символом МК указать в скобках набор МО, образующих каждую МК.

Таблица 5 – Список входных сигналов для УА

Разметка ГСА в соответствии с моделью Мили, выполняется по следующим правилам:

1. Вход вершины, следующей за начальной, и вход конечной вершины отмечаются символом начального состояния автомата а₀.

2. Входы всех вершин, следующих за операторными, отмечаются символами а₁, …, а_К.

3. Если вход вершины отмечается, то только одним символом.

4. Входы различных вершин за исключением конечной отмечаются различными символами.

Разметка ГСА в соответствии с моделью Мура, выполняется по следующим правилам:

1. Символом начального состояния автомата а₀ отмечаются начальная и конечная вершины.

2. Различные операторные вершины отмечаются различными символами а₁, …, а_К.

Рис 21. Отмеченная ГСА для алгоритма умножения

Все операторные вершины должны быть отмечены, то есть каждой МК, отдельно представленной в ГСА ставится в соответствие отдельное состояние автомата Мура.

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

Получается ГСА, размеченная для модели Мили символами a₀..a₈ , для модели Мура символами b₀..b₁₃.