Сучкова Л.И. Абстрактный и структурный синтез автоматов
Подождите немного. Документ загружается.
111
граммы.
- особый вид условной вершины - ждущая - имеет множество
входов, 2 выхода, 1 из которых заведен на вход. При попада-
нии в ждущую вершину выход из нее возможен только при
выполнении условия Х.
Граф микропрограммы состоит из совокупности пере-
численных вершин и дуг, соединяющих выходы одних вер-
шин с входами других.
ГСА на
рисунке 7.2 слева называется содержательной,
т.к. внутри вершин записаны в явном виде микрооперации и
логические условия. Если же каждую микрооперацию обо-
значить символами Yi, a логические условия через Xi, то по-
лучится так называемая кодированная ГСА, расположенная
на рисунке 7.2 справа.
Рисунок 7.2 Содержательная и кодированная ГСА
Различные микрооперации выполняются операционны-
112
ми элементами (ОЭ), которые являются составными частями
основного ОА. Под операционным элементом понимают уст-
ройство, реализующее одну из следующих функций или их
произвольную комбинацию: хранение слова информации,
выполнение некоторых микроопераций, в результате кото-
рых вычисляется новое значение слова С, вычисление логи-
ческого условия, зависящего от слова С. Для построения ОА
ОЭ
соединяются между собой с помощью цепей передачи
слов информации от выходов одних элементов к входам дру-
гих. В зависимости от выполняемых микроопераций ОЭ де-
лятся на разновидности: шина, регистр, счетчик, сумматор,
схема сравнения, дешифратор, шифратор и т.д.
Для различных содержательных ГСА, имеющих одина-
ковую кодированную ГСА, ОА будут различны,
но УА будет
одним и тем же. Синтез ОА будет рассмотрен в курсе схемо-
техники.
Рассмотрим синтез только УА для кодированной ГСА.
Конечный автомат, интерпретирующий микропро-
грамму работы дискретного устройства, называется
микропрограммным автоматом. Одну и ту же ГСА можно
интерпретировать как автоматом Мили, так и автоматом Му-
ра.
Абстрактный синтез
микропрограммного автомата по
ГСА осуществляется в два этапа:
1. Получение отмеченной ГСА.
2. Построение графа автомата или таблиц переходов и
выходов.
7.2 Синтез автомата Мили по ГСА
На этапе получения отмеченной ГСА входы вершин,
следующих за операторными, отмечают символами a
1
, a
2
,..
по следующим правилам:
1) символом а
1
отмечают вход вершины, следующей
за
начальной, а также вход конечной вершины;
113
2) входы всех вершин следующих за операторными,
должны быть отмечены;
3) входы различных вершин, за исключением конечной,
отмечаются различными символами;
4) если вход вершины отмечается, то только одним сим-
волом.
Для проведения отметок потребуется конечное число
символов а
1
,...,a
m
. Результатом первого этапа является отме-
ченная ГСА, которая служит основой для второго этапа
- пе-
рехода к графу или таблицам переходов-выходов. Пример
ГСА, отмеченной для автомата Мили, представлен на рис.
7.3.
114
Рисунок 7.3 - ГСА, отмеченная для автомата Мили
На втором этапе из отмеченной ГСА строят граф авто-
мата или таблицы переходов-выходов. Для этого полагают,
что в автомате будет столько состояний, сколько символов a
i
понадобилось при отметке ГСА.
На плоскости отмечаем все состояния автомата a
i
. Для
каждого из состояний a
i
определяем по
отмеченной ГСА все
115
пути, ведущие в другие состояния и проходящие обязатель-
но только через одну операторную вершину. Например, из
состояния а
1
(рис. 7.3) есть переход в состояние a
2
(путь про-
ходит через операторную вершину y
1
y
2
) и в состояние a
4
(путь проходит через вершину y
3
y
4
). Перехода из a
1
в a
3
нет, так как
на этом пути нет ни одной операторной верши-
ны. Будем считать, что автомат осуществляет переход, на-
пример, из a
1
в a
2
при условии x
1
= 0 или x
1
(см.ГСА) и вы-
рабатывает на этом переходе выходные сигналы у
1
у
2
(то,
что записано в проходимой операторной вершине ГСА). Зна-
чение условий
х
2
, х
3
, х
4
на этом переходе не оказывает
влияния на автомат. Исключение составляет только путь, ве-
дущий в конечную вершину, он может не содержать ни од-
ной операторной вершины (например, переход из а
6
в а
1
),
т.е. не сопровождается выработкой выходных сигналов.
Отмечаем на графе все указанные пути
для всех состоя-
ний в виде дуг, которым приписываем условия перехода и
выходной сигнал, вырабатываемый на этом переходе. Полу-
чим граф автомата Мили (рисунок 7.4.).
На этом графе переходам типа а
3
→a
4
, a
5
→ a
1
припи-
сывается условие перехода 1, т.к. эти переходы являются
безусловными и выполняются всегда, когда автомат
попадает
в состояние а
3
(или а
5
).
На основании отмеченной ГСА или графа автомата
можно построить таблицу переходов-выходов. Для микро-
программных автоматов таблица переходов-выходов строит-
ся в виде списка, и различаются прямая и обратная таблицы.
116
Рисунок 7.4
Для данного автомата прямая таблица представлена в
таблице 7.1, обратная - в таблице 7.2.
Таблица 7.1 - Прямая таблица переходов-выходов автомата
Мили
a
m
a
5
X Y
a
1
a
2
a
4
x
1
x
1
y
1
y
2
y
3
y
4
a
2
a
2
a
5
a
6
x
3
x
2
x
3
x
3
x
2
y
1
y
2
y
2
y
3
y
4
a
3
a
4
1 y
3
y
4
a
4
a
1
a
3
x
2
x
2
y
2
y
1
y
4
a
5
a
1
1 y
2
a
6
a
1
a
2
x
4
x
4
-
y
1
y
2
117
Таблица 7.2 - Обратная таблица переходов-выходов автомата
Мили
a
m
a
5
X Y
a
4
a
5
a
6
a
1
x
2
1
x
4
y
2
y
2
-
a
1
a
2
a
6
a
2
x
1
x
3
x
2
x
4
y
1
y
2
y
1
y
2
y
1
y
2
a
4
a
3
x
2
y
1
y
4
a
1
a
3
a
4
x
1
1
y
3
y
4
y
3
y
4
a
2
a
5
x
3
y
2
y
3
a
2
a
6
x
3
x
2
y
4
В приведенных таблицах a
m
- исходное состояние, a
S
-
состояние перехода, Х - условие (входной сигнал), обеспечи-
вающий переход из состояния a
m
в состояние a
s
, Y - выход-
ной сигнал, вырабатываемый автоматом при переходе из a
m
в
a
S
.
7.3 Синтез автомата Мура по ГСА
Для автомата Мура на этапе получения отмеченной ГСА
разметка производится согласно следующим правилам:
1) символом а
1
отмечается начальная и конечная вер-
шины;
2) различные операторные вершины отмечаются раз-
личными символами;
3) все операторные вершины должны быть отмечены;
118
Пример ГСА, отмеченной для автомата Мура, представ-
лен на рисунке 7.5.
Рисунок 7.5 - ГСА, размеченная для автомата Мура
Граф автомата Мура, соответствующий отмеченной
ГСА, представлен на рисунке 7.6. Построение его аналогично
построению графа для автомата Мили.
119
Таблицы переходов-выходов автомата Мура представ-
лены в таблице 7.3 (прямая) и 7.4 (обратная). Обычно для
автомата Мура в таблице переходов-выходов дополнитель-
ный столбец для выходных сигналов не используется, и вы-
ходной сигнал записывается в столбце, где указывается ис-
ходное состояние a
m
или состояния перехода a
S
.
Рисунок 7.6 - Граф автомата Мура
Таблица 7.3 - Прямая таблица переходов автомата Мура
a
m
(Y) a
S
X
a
1
(--)
a
2
a
3
x
1
x
1
a
2
(y
1
y
2
)
a
2
a
5
a
6
x
3
x
2
x
3
x
3
x
2
120
a
3
(y
3
y
4
) a
4
a
7
x
2
x
2
a
4
(y
1
y
4
) a
3
1
a
5
(y
2
y
3
) a
7
1
a
6
(y
4
) a
1
a
2
x
4
x
4
a
7
(y
2
) a
1
1
Таблица 7.4 - Обратная таблица переходов автомата Му-
ра
a
m
a
S
(Y) X
a
6
a
7
a
1
(-)
x
4
1
a
1
a
2
a
6
a
2
(y
1
y
2
)
x
1
x
3
x
2
x
4
a
1
a
4
a
3
(y
3
y
4
) x
1
1
a
3
a
4
(y
1
y
4
) x
2
a
2
a
5
(y
2
y
3
) x
3
a
2
a
6
(y
4
) x
3
x
2
a
3
a
5
a
7
(y
2
) x
2
1
Получением графа или таблиц переходов-выходов за-
канчивается этап абстрактного синтеза микропрограммного
автомата.