Структурный синтез конечных автоматов заключается в выборе типов элементарных автоматов, в составлении функции возбуждения каждого элементарного автомата и функций кодированных выходов заданного автомата. На этапе структурного синтеза выбираем также способ кодирования состояний и выходных сигналов заданного автомата через состояния и выходные сигналы элементарных автоматов, в результате чего составляют кодированные таблицы переходов и выходов. Функции возбуждения элементарных автоматов и функции выходов получаются на основе кодированной таблицы переходов и выходов. Рассмотрим примеры синтеза, которые позволяют сформулировать общий алгоритм структурного синтеза конечных автоматов.
Пример. Пусть необходимо синтезировать автомата Мили, заданный совмещенной таблицей переходов и выходов:
xj\ai | a0 | a1 | a2 |
x1 | a1/y1 | a1/y2 | a1/y2 |
x2 | a2/y3 | a2/y3 | a0/y1 |
В качестве элементарных автоматов будем использовать JK-триггера, а в качестве логических элементов – элементы И, ИЛИ, НЕ. Итак, имеем
A ={ a 0, a 1, a 2}; X ={ x 1, x 2}; Y ={ y 1, y 2, y 3}. Здесь n=2, n +1=3; m =2, k =3.
|
|
1. Перейдем от абстрактного автомата к структурному, для чего определим количество элементов памяти R и число входных L и выходных N каналов.
R = ] log2(n+1) [ = 2 |
L = ] log2 m [ = 1 |
N = ] log2 k [ = 2 |
Таким образом, необходимо иметь два элементарных автомата Q 1 и Q 2 (так как R =2), один входной канал O1 и два выходных канала Z 1 и Z 2.
2. Закодируем состояния автомата, входные и выходные сигналы совокупностью двоичных сигналов.
Таблицы | ||||||||||||||||||||||||||||||||
кодирования | ||||||||||||||||||||||||||||||||
состояний | входных | выходных | ||||||||||||||||||||||||||||||
автомата | сигналов | сигналов | ||||||||||||||||||||||||||||||
|
|
|
Поскольку автомат имеет три состояния, то комбинация состояний элементарных автоматов 11 не используется и является запрещенной (автомат в это состояние никогда не попадет). Здесь и в дальнейшем будем использовать естественное кодирование, когда наборы значений двоичных переменных расписываются в порядке возрастания их номеров. С учетом кодирования перерисуем совмещенную таблицу переходов и выходов абстрактного автомата.
Перерисованная совмещенная таблица переходов и выходов
xj\ai | |||
01/00 | 01/01 | 01/01 | |
10/10 | 10/10 | 00/00 |
В таблицах кодирования выходные каналы Z 1 и Z 2 называются физическими выходами автомата.
3. Пользуясь таблицами кодирования, можно на основе заданных переходов и выходов построить кодированные таблицы переходов и выходов. Кодированная таблица переходов определяет зависимость состояний
Q i(t +1) элементарных автоматов в момент времени (t +1) от значения входного сигнала и внутренних состояний автоматов в предшествующий момент времени t. То есть:
|
|
Qi(t+1)=fi[Q1(t), Q2(t),…,QR(t),O1(t),…, OL(t)]
В кодированной таблице выходов – выходные сигналы Z l(t) определяются в зависимости от значения входных сигналов и внутренних состояний в момент времени t. То есть:
Zl(t)=fi[Q1(t),Q2(t),…,QR(t),O1(t),…,OL(t)]
Кодированная таблица переходов и выходов (совмещенная) имеет следующий вид:
(t) | (t+1) | |||||
o1 | Q1 | Q2 | Z1 | Z2 | Q1 | Q2 |
- | - | - | - | |||
- | - | - | - |
В нашем случае:
Zl(t) = fi1[Q1(t), Q2(t), O 1(t)], Z2(t) = fi2[Q1(t), Q2(t), O 1(t)]
Эти функции являются переключательными, поскольку значения функции и ее аргументов определены в один и тот же момент времени t.
4. Основная задача, решаемая в процессе структурного синтеза – построение таблицы функций возбуждения элементарных автоматов, которая определяет значения сигналов на входах элементарных автоматов, необходимые для обеспечения переходов автомата из одного состояния в другое. При построении этой таблицы используется матрица переходов выбранных элементарных автоматов, в нашем случае JK -триггера:
J | K | Q(t) | Q(t+1) |
b1 | |||
b2 | |||
b3 | |||
b4 |
С помощью матрицы переходов заполняются столбцы таблицы функций возбуждения. В строках этой таблицы записываются значения J и K, обеспечивающие нужный переход.
Таблица функций возбуждения:
(t) | (t+1) | |||||||
o1 | Q1 | Q2 | J1 | K1 | J2 | K2 | Q1 | Q2 |
b | b | |||||||
b | b | |||||||
b | b | |||||||
- | - | - | - | - | - | |||
b | b | |||||||
b | b | |||||||
b | b | |||||||
- | - | - | - | - | - |
Таким образом, получим значения входных сигналов J и K элементарных автоматов, которые зависят как от значения входного сигнала, так и от состояния автомата в тот же момент времени, что и Q i.
Поскольку функции возбуждения J (t) и K (t) определенны в тот же момент времени, что и их аргументы Q 1(t), Q 2(t) и O1(t), то эти функции являются переключательными. В результате мы получим систему переключательных функций Z 1(t), Z 2(t), J 1(t), K 1(t), J 2(t) и K 2(t) заданных в виде таблиц их истинности.
5. Следующий этап –синтез комбинационной части конечных автоматов. На этом этапе по полученным переключательным функциям синтезируются комбинационные схемы. Очевидно, задача комбинационного синтеза конечных автоматов полностью совпадает с задачей синтеза логических схем. Обычно полученные переключательные функции минимизируют и представляют в булевом базисе, а переход к заданному базису осуществляют после.
В нашем случае мы имеем шесть переключательных функций трёх аргументов, для каждой из которых построим диаграмму Вейча.