Пример канонического метода структурного синтеза автомата
Выполним структурный синтез частичного автомата А, заданного своими таблицами переходов и выходов (табл. 23 и 24.).
1. Выберем в качестве элементов памяти D-триггер.
2. Закодируем входные, выходные сигналы и внутренние состояния автомата. Количество входных абстрактных сигналов F = 3, следовательно количество входных структурных сигналов L= ]log2F [ = ]log23[ = 2, т.е. х1, х2.
Количество выходных абстрактных сигналов G = 4, следовательно количество выходных структурных сигналов N =]log2G[ = ]log24[ = 2, т.е. у1, у2. Количество внутренних состояний абстрактного автомата M = 4, следовательно количество двоичных элементов памяти (триггеров) R = ] log2M [ = ]log24[ = 2.
|
|
x1 |
x2 |
|
|
y1 |
y2 |
|
|
Q1 |
Q2 |
|
|
z1 |
0 |
0 |
|
w1 |
0 |
0 |
|
a1 |
0 |
0 |
|
|
z2 |
0 |
1 |
|
w2 |
0 |
1 |
|
a2 |
0 |
1 |
|
|
z3 |
1 |
1 |
|
w3 |
1 |
1 |
|
a3 |
1 |
1 |
|
|
|
|
w4 |
1 |
0 |
|
a4 |
1 |
0 |
|
Кодирование, в общем случае, осуществляется произвольно. Поэтому, например, каждому из сигналов zi можно поставить в соответствие любую двухразрядную комбинацию х1, х2. Необходимо только, чтобы разные выходные сигналы zi кодировались разными комбинациями х1, х2. Аналогично для wi и ai.
Получим кодированные таблицы переходов и выходов структурного автомата. Для этого в таблицах переходов и выходов исходного абстрактного автомата вместо zi, wi, ai cтавим соответствующие коды. Получим таблицы:
|
|
|
a1 |
a2 |
a3 |
a4 |
|
|
|
a1 |
a2 |
a3 |
a4 |
|
|
|
00 |
01 |
11 |
10 |
|
|
|
00 |
01 |
11 |
10 |
|
Z1 |
00 |
00 |
10 |
10 |
– |
|
Z1 |
00 |
01 |
00 |
11 |
– |
|
Z2 |
01 |
– |
11 |
00 |
– |
|
Z2 |
01 |
– |
11 |
00 |
– |
|
Z3 |
11 |
01 |
– |
01 |
Q1Q2 |
|
Z3 |
11 |
00 |
– |
10 |
y1y2 |
Рис. 30. Кодированная
таблица переходов
Рис. 31. Кодированная
таблица выходов
В кодированной таблице переходов заданы функции
В кодированной таблице выходов заданны функции:
4. При каноническом методе синтез сводится к получению функций:
и последующем построении комбинационных схем, реализующих данную систему булевых функций.
Функции у1 и у2 могут быть непосредственно получены из таблицы выходов, например, в виде :
Однако выражения для у1 и у2 можно существенно упростить в результате минимизации, например, с помощью карт Карно:
|
|
00 |
01 |
11 |
10 |
|
|
00 |
01 |
11 |
10 |
|
00 |
0 |
0 |
1 |
– |
|
00 |
1 |
0 |
1 |
– |
|
01 |
– |
1 |
0 |
– |
|
01 |
– |
1 |
0 |
– |
|
11 |
0 |
– |
1 |
0 |
|
11 |
0 |
– |
0 |
1 |
|
10 |
– |
– |
– |
– |
|
10 |
– |
– |
– |
– |
В результате минимизации имеем:
Для получения выражений для D1 и D2 необходимо получить таблицы функций возбуждения. Для чего в общем случае необходимо воспользоваться таблицей переходов и функциями входов элементов памяти. Зная код исходного состояния автомата и код состояния перехода на основании таблицы входов триггера получаем требуемое значение функции возбуждения, обеспечивающее заданный переход. Однако для D-триггеров, как отмечалось ранее, таблица переходов совпадает с таблицей функции возбуждения. Тогда либо непосредственно из этой таблицы, либо в результате минимизации получаем требуемые значения Di. Обычно используется минимизация с помощью карт Карно:
|
|
00 |
01 |
11 |
10 |
|
|
00 |
01 |
11 |
10 |
|
00 |
0 |
1 |
1 |
– |
|
00 |
0 |
0 |
0 |
– |
|
01 |
– |
1 |
0 |
– |
|
01 |
– |
1 |
0 |
– |
|
11 |
0 |
– |
0 |
1 |
|
11 |
1 |
– |
1 |
1 |
|
10 |
– |
– |
– |
– |
|
10 |
– |
– |
– |
– |
В результате минимизации получаем:
5. На основании полученных в результате синтеза булевых выражений ((*), (**)) ,строим функциональную схему автомата. Для этого уравнения ((*), (**)) представим в виде:
Функциональная схема автомата представлена на рис.36.
Дополнительно на функциональной схеме показан сигнал , устанавливающий автомат в начальное состояние (в данном случае 00).