Табличный метод структурного синтеза конечных автоматов
Структурный синтез конечных автоматов заключается в выборе типов элементарных автоматов, в составлении возбуждения каждого элементарно автомата и функций кодированных выходов заданного автомата.
На этапе структурного синтеза выбираем также способ кодирования состояний и выходных сигналов заданного автомата через состояния и выходные сигналы элементарных автоматов, в результате чего составляют кодированные таблицы переходов и выходов.
Функции возбуждения элементарных автоматов и функции выходов получаются на основе кодированной таблицы переходов и выходов.
Рассмотрим примеры синтеза, которые позволяют сформулировать общий алгоритм структурного синтеза конечных автоматов.
Пусть необходимо синтезировать автомата Мили, заданный совмещенной таблицей переходов и выходов.
|
xj\ai |
a0 |
a1 |
a2 |
|
x1 |
a1/y1 |
a1/y2 |
a1/y2 |
|
x2 |
a2y3 |
a2/y3 |
a0/y1 |
В качестве элементарных автоматов будем использовать JK-триггера, а в качестве логических элементов – элементы И, ИЛИ, НЕ. Итак, имеем A={a0, a1, a2}; X={x1, x2}; Y={y1, y2, y3}. Здесь n=2, n+1=3; m=2, k=3.
1. Перейдем от абстрактного автомата к структурному, для чего определим количество элементов памяти R и число входных L и выходных N каналов.
R = ]log (n+1)[ = ] log 3[ = 2
L = ]log m[ = ] log 2[ = 1
R = ]log k[ = ] log 3[ = 2.
Таким образом, необходимо иметь два элементарных автомата Q1 и Q2 (т.к. R=2), один входной канал b1 и два выходных канала Z1 и Z2.
2. Закодируем состояния автомата, входные и выходные сигналы совокупностью двоичных сигналов.
|
Сост.элем.авт. Сост.задан.абстрактн.авт. |
Q1 |
Q2 |
|
a0 |
0 |
0 |
|
a1 |
0 |
1 |
|
a2 |
1 |
0 |
Таблица кодирования состояний автомата.
|
Вх.сигн.структ.авт Вх.сигн.задан.авт |
d1 |
|
X1 |
0 |
|
X2 |
1 |
Таблица кодирования входных сигналов.
предыдущая темаследующая