Разметка содержательной граф-схемы алгоритма

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

Предварительно в каждой условной вершине проставляются символы из множества входных сигналов УА - х₁, х₂,...,х_М, каждый из которых эквивалентен одному из осведомительных сигналов ОА. Во всех операторных вершинах ГСА проставляют символы из множества выходных сигналов управляющего автомата - у₁, у₂,..., у_N, эквивалентных одной из МК, поступающих в ОА в соответствующие такты машинного времени. Удобно в каждой операторной вершине ГСА вслед за символом МК указать в скобках набор МО, образующих каждую МК. Допускается запись одинаковых символов X_i и Y_j в различных условных и операторных вершинах.

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

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

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

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

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

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

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

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

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

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

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