7.1 Синтез структурного автомата Мура на D -триггерах
Кратко отметим основные этапы синтеза автомата:
Находим количество элементов памяти $$R >=]Log_2M[,$$ ( М - число состояний абстрактного автомата) и кодируем состояния абстрактного автомата.
Кодируем входные и выходные сигналы.
Структурный автомат представляем обобщенной схемой.
Составляем закодированную таблицу выходов автомата и по ней записываем уравнения выходов.
Составляем закодированную таблицу переходов автомата и по ней записываем уравнения для функций возбуждения.
Уравнения функций возбуждения и выходов минимизируются (по картам Карно, например) и по ним строится схема в заданном функционально - логическом базисе базисе ({И, ИЛИ, НЕ}, {И-НЕ}, {ИЛИ-НЕ} ).
Рассмотрим синтез структурного автомата Мура, заданного табл.7.1, на D -триггерах в элементном базисе {И, ИЛИ, НЕ}.
| u |
u1 |
u2 |
u3 |
u1 |
|---|
| z\a |
a1 |
a2 |
a3 |
a4 |
| z1 |
a1 |
a3 |
a1 |
- |
| z2 |
- |
a1 |
a4 |
a2 |
| z3 |
a4 |
a2 |
a3 |
a3 |
Находим количество элементов памяти $$R=2$$ и кодируем состояния абстрактного автомата, например так, как показано в таблица 7.2
| $$\tau_1$$ |
$$\tau_2$$ |
| a1 |
0 |
0 |
| a2 |
0 |
1 |
| a3 |
1 |
0 |
| a4 |
1 |
1 |
Кодируем входные и выходные сигналы абстрактного автомата, например так, как показано в табл.7.3 и табл.7.4
Структурный автомат представляем обобщенной схемой (рис 7.1(рис 7.1)
|
X1 |
X2 |
|---|
| z1 |
0 |
1 |
| z2 |
1 |
0 |
| z3 |
1 |
1 |
|
r1 |
r2 |
|---|
| u1 |
0 |
0 |
| u2 |
0 |
1 |
| u3 |
1 |
0 |
Табл.7.1 представляем, используя коды состояний, входных и выходных сигналов (табл.7.5), и по ней записываем уравнения выходов.| r1r2 |
00 |
01 |
10 |
00 |
|---|
| x1 x2\ $$\tau_1 \tau_1$$ |
00 |
01 |
10 |
11 |
| 01 |
00 |
10 |
00 |
- |
| 10 |
- |
00 |
11 |
01 |
| 11 |
11 |
01 |
10 |
10 |
Функция выхода r1, зависящая для автомата Мура только от состояния, принимает единичное значение на единственном наборе 10, т.е $$\tau_1 \overline \tau_2$$. Функция выхода r2, принимает единичное значение так же на единственном наборе равном 01, то есть $$\overline \tau_1\tau_2$$.
Таким образом, уравнения выходов:
$$r_1=\tau_1 \overline \tau_2$$,
$$r_2=\overline \tau_1\tau_2$$.
Записываем уравнения для функций возбуждения. Так как в D -триггере функция возбуждения совпадает с состоянием перехода, то функцию возбуждения можно записать по табл.7.5. Находим единичные состояния первого триггера. Их всего пять, см. в табл.7.5. Функция возбуждения зависит от входных сигналов и состояния автомата, из которого был переключен данный триггер : $$\varphi_R= \varphi_R(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L)$$.Первое единичное значение функция возбуждения принимает при переходе из состояния а0, закодированного как 00, то есть $$а_0= \bar\tau_1 \bar\tau_2$$, при поступлении единичных входных сигналов $$х_{1х2} =11$$. Аналогично находим остальные термы и записываем функцию возбуждения первого триггера:
$$\varphi_1=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2 \vee \tau_1 \tau_2 x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 x_2$$Для второго триггера состояний перехода, в которых он принимает единичные значения, четыре. Они выделены темно красным цветом. По ним записана функцию возбуждения второго триггера:
$$\varphi_2=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2 \vee \tau_1 \tau_2 x_1 \bar x_2$$
Уравнения функций возбуждения и выходов минимизируются по картам Карно (рис.7.2).
(рис 7.2)
$$\varphi_1=\bar\tau_1 \tau_2 \bar x_1x_2 \vee \tau_1 \bar\tau_2 x_1 \vee \bar\tau_2 x_1 x_2 \vee \tau_1 x_1 x_2 \\
\varphi_2=\bar\tau_1 x_1 x_2 \vee \tau_1 x_1 \bar x_2$$
По полученным уравнениям функций возбуждения и выходов строим функционально - логическую схему (рис.7.3).
(рис 7.3)
7.2 Синтез структурного автомата Мура на Т -триггерах
Этапы кодирования, построения обобщенной схемы, построения уравнений выходов совпадают с этапами синтеза на D -триггерах. Рассмотрим построение уравнений функций возбуждения, то есть начиная с пятого этапа.
| $$\tau_{исх.}$$ |
$$\varphi$$ |
$$\tau_{пер.}$$ |
|---|
| 0 | 0 |
0 |
|---|
| 0 | 1 |
1 |
|---|
| 1 | 1 |
0 |
|---|
| 1 | 0 |
1 |
|---|
| r1r2 |
00 |
01 |
10 |
00 |
|---|
| $$x_1 x_2\ \tau_1 \tau_2$$ | 00 |
01 |
10 |
11 |
|---|
| 01 | 00 |
10 |
00 |
- |
|---|
| 10 | - |
00 |
11 |
01 |
|---|
| 11 | 11 |
01 |
10 |
10 |
|---|
| $$x_1 x_2 \tau_1 \tau_2$$ |
00 |
01 |
10 |
11 |
|---|
| 01 | 00 |
11 |
10 |
- |
|---|
| 10 | - |
01 |
01 |
10 |
|---|
| 11 | 11 |
00 |
00 |
01 |
|---|
Так как функция возбуждения Т -триггера (табл.7.6) $$\varphi = 1$$, только тогда, когда состояние автомата переходит из 0 в 1 или из 1 в 0, то по закодированной рис.7.7 переходов исходного автомата Мура находим такие переключения триггеров, при которых они меняли свои состояния. Составляем таблицу функций возбуждения, которая имеет в качестве заголовков столбцов коды состояний, а строки помечены кодами входных сигналов (табл.7.8). В каждой клетке таблицы записаны функции возбуждения $$\varphi_1 \varphi_2.$$ Составляем для них уравнения:
$$\varphi_1=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \vee \tau_1 \bar\tau_2 \bar x_1 x_2 \vee \tau_1 \tau_2 x_1 \bar x_2\\
\varphi_2=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \vee \bar\tau_1 \tau_2 x_1 \bar x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2 \vee \tau_1 \tau_2 x_1 x_2
$$
Далее уравнения минимизируются и по ним строится схема в заданном базисе.
7.3 Синтез структурного автомата Мили на RS -триггерах
Рассмотрим синтез структурного автомата Мили, заданного табл.7.9 и табл.7.10, на RS -триггерах в элементном базисе {И, ИЛИ, НЕ}.
| z\a |
a1 |
a2 |
a3 |
a4 |
|---|
| z1 | a1 |
a3 |
a1 |
- |
|---|
| z2 | - |
a1 |
a4 |
a2 |
|---|
| z3 | a4 |
a2 |
a3 |
a3 |
|---|
| z\a |
a1 |
a2 |
a3 |
a4 |
|---|
| z1 | w1 |
w3 |
w1 |
- |
|---|
| z2 | - |
w1 |
w2 |
w2 |
|---|
| z3 | w2 |
w2 |
w3 |
w3 |
|---|
Находим количество элементов памяти
| t 1 |
t 2 |
| a1 | 0 |
0 |
|---|
| a2 | 0 |
1 |
|---|
| a3 | 1 |
0 |
|---|
| a4 | 1 |
1 |
|---|
Кодируем входные и выходные сигналы абстрактного автомата, например, так, как показано в табл.7.12 и табл.7.13
Структурный автомат представляем обобщенной схемой (рис 7.4(рис 7.4)
Табл.7.10 представляем, используя коды состояний, входных и выходных сигналов (табл.7.14), и по ней записываем уравнения выходов. $$y_1=\bar\tau_1\tau_2 \bar x_1 x_2 \vee \tau_1 \bar \tau_2 x_1 x_2 \vee \tau_1 \tau_2 x_1 x_2\\
y_2=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2 \vee \tau_1 \tau_2 x_1 \bar x_2$$| x1x2\t 1t 2 |
00 |
01 |
10 |
11 |
|---|
| 01 | 00 |
10 |
00 |
- |
|---|
| 10 | - |
00 |
01 |
01 |
|---|
| 11 | 01 |
01 |
10 |
10 |
|---|
Составляем закодированную таблицу переходов автомата (табл.7.15) и по ней записываем уравнения для функций возбуждения.| r1r2 |
00 |
01 |
10 |
00 |
|---|
| x1x2\t 1t 2 | 00 |
01 |
10 |
11 |
|---|
| 01 | 00 |
10 |
00 |
- |
|---|
| 10 | - |
00 |
11 |
01 |
|---|
| 11 | 11 |
01 |
10 |
10 |
|---|
Функция возбуждения RS -триггера представлена в табл.7.16. Просматривая каждый переход триггеров по таблице переходов автомата (табл.7.15), составляем таблицу функций возбуждения (табл.7.17), которая имеет в качестве заголовков столбцов коды состояний, а строки помечены кодами входных сигналов. В каждой клетке таблицы записаны функции возбуждения для первого триггера $$\varphi_1 \psi_1$$ и для второго триггера $$\varphi_2 \psi_2$$. Составляем для них уравнения:
| $$\tau_{исх.}$$ |
$$\varphi \psi$$ |
$$\tau_{пер.}$$ |
|---|
| 0 | 0 - |
0 |
|---|
| 0 | 1 0 |
1 |
|---|
| 1 | 0 1 |
0 |
|---|
| 1 | - 0 |
1 |
|---|
| $$x_1 x_2 \ \tau_1 \tau_2$$ |
0 0 |
0 1 |
1 0 |
1 1 |
|---|
| 01 | 0- 0- |
10 01 |
01 0- |
- |
|---|
| 10 | - |
0- 01 |
-0 10 |
01 -0 |
|---|
| 11 | 10 10 |
0- -0 |
-0 0- |
-0 01 |
|---|
$$\varphi_1=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2\\
\psi_1=\bar\tau_1 \bar\tau_2 \bar x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2\\
\varphi_2=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2\\
\psi_2=\bar\tau_1 \tau_2 \bar x_1 x_2 \vee \bar\tau_1 \tau_2 x_1 \bar x_2 \vee \tau_1 \tau_2 x_1 x_2$$
Далее уравнения минимизируются и по ним строится схема в заданном базисе.
Аналогично проводится синтез и на JK -триггерах.
7.1 Синтез структурного автомата Мура на D -триггерах
Кратко отметим основные этапы синтеза автомата:
Находим количество элементов памяти $$R >=]Log_2M[,$$ ( М - число состояний абстрактного автомата) и кодируем состояния абстрактного автомата.
Кодируем входные и выходные сигналы.
Структурный автомат представляем обобщенной схемой.
Составляем закодированную таблицу выходов автомата и по ней записываем уравнения выходов.
Составляем закодированную таблицу переходов автомата и по ней записываем уравнения для функций возбуждения.
Уравнения функций возбуждения и выходов минимизируются (по картам Карно, например) и по ним строится схема в заданном функционально - логическом базисе базисе ({И, ИЛИ, НЕ}, {И-НЕ}, {ИЛИ-НЕ} ).
Рассмотрим синтез структурного автомата Мура, заданного табл.7.1, на D -триггерах в элементном базисе {И, ИЛИ, НЕ}.
| u |
u1 |
u2 |
u3 |
u1 |
|---|
| z\a |
a1 |
a2 |
a3 |
a4 |
| z1 |
a1 |
a3 |
a1 |
- |
| z2 |
- |
a1 |
a4 |
a2 |
| z3 |
a4 |
a2 |
a3 |
a3 |
Находим количество элементов памяти $$R=2$$ и кодируем состояния абстрактного автомата, например так, как показано в таблица 7.2
| $$\tau_1$$ |
$$\tau_2$$ |
| a1 |
0 |
0 |
| a2 |
0 |
1 |
| a3 |
1 |
0 |
| a4 |
1 |
1 |
Кодируем входные и выходные сигналы абстрактного автомата, например так, как показано в табл.7.3 и табл.7.4
Структурный автомат представляем обобщенной схемой (рис 7.1(рис 7.1)
|
X1 |
X2 |
|---|
| z1 |
0 |
1 |
| z2 |
1 |
0 |
| z3 |
1 |
1 |
|
r1 |
r2 |
|---|
| u1 |
0 |
0 |
| u2 |
0 |
1 |
| u3 |
1 |
0 |
Табл.7.1 представляем, используя коды состояний, входных и выходных сигналов (табл.7.5), и по ней записываем уравнения выходов.| r1r2 |
00 |
01 |
10 |
00 |
|---|
| x1 x2\ $$\tau_1 \tau_1$$ |
00 |
01 |
10 |
11 |
| 01 |
00 |
10 |
00 |
- |
| 10 |
- |
00 |
11 |
01 |
| 11 |
11 |
01 |
10 |
10 |
Функция выхода r1, зависящая для автомата Мура только от состояния, принимает единичное значение на единственном наборе 10, т.е $$\tau_1 \overline \tau_2$$. Функция выхода r2, принимает единичное значение так же на единственном наборе равном 01, то есть $$\overline \tau_1\tau_2$$.
Таким образом, уравнения выходов:
$$r_1=\tau_1 \overline \tau_2$$,
$$r_2=\overline \tau_1\tau_2$$.
Записываем уравнения для функций возбуждения. Так как в D -триггере функция возбуждения совпадает с состоянием перехода, то функцию возбуждения можно записать по табл.7.5. Находим единичные состояния первого триггера. Их всего пять, см. в табл.7.5. Функция возбуждения зависит от входных сигналов и состояния автомата, из которого был переключен данный триггер : $$\varphi_R= \varphi_R(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L)$$.Первое единичное значение функция возбуждения принимает при переходе из состояния а0, закодированного как 00, то есть $$а_0= \bar\tau_1 \bar\tau_2$$, при поступлении единичных входных сигналов $$х_{1х2} =11$$. Аналогично находим остальные термы и записываем функцию возбуждения первого триггера:
$$\varphi_1=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2 \vee \tau_1 \tau_2 x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 x_2$$Для второго триггера состояний перехода, в которых он принимает единичные значения, четыре. Они выделены темно красным цветом. По ним записана функцию возбуждения второго триггера:
$$\varphi_2=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2 \vee \tau_1 \tau_2 x_1 \bar x_2$$
Уравнения функций возбуждения и выходов минимизируются по картам Карно (рис.7.2).
(рис 7.2)
$$\varphi_1=\bar\tau_1 \tau_2 \bar x_1x_2 \vee \tau_1 \bar\tau_2 x_1 \vee \bar\tau_2 x_1 x_2 \vee \tau_1 x_1 x_2 \\
\varphi_2=\bar\tau_1 x_1 x_2 \vee \tau_1 x_1 \bar x_2$$
По полученным уравнениям функций возбуждения и выходов строим функционально - логическую схему (рис.7.3).
(рис 7.3)
7.2 Синтез структурного автомата Мура на Т -триггерах
Этапы кодирования, построения обобщенной схемы, построения уравнений выходов совпадают с этапами синтеза на D -триггерах. Рассмотрим построение уравнений функций возбуждения, то есть начиная с пятого этапа.
| $$\tau_{исх.}$$ |
$$\varphi$$ |
$$\tau_{пер.}$$ |
|---|
| 0 | 0 |
0 |
|---|
| 0 | 1 |
1 |
|---|
| 1 | 1 |
0 |
|---|
| 1 | 0 |
1 |
|---|
| r1r2 |
00 |
01 |
10 |
00 |
|---|
| $$x_1 x_2\ \tau_1 \tau_2$$ | 00 |
01 |
10 |
11 |
|---|
| 01 | 00 |
10 |
00 |
- |
|---|
| 10 | - |
00 |
11 |
01 |
|---|
| 11 | 11 |
01 |
10 |
10 |
|---|
| $$x_1 x_2 \tau_1 \tau_2$$ |
00 |
01 |
10 |
11 |
|---|
| 01 | 00 |
11 |
10 |
- |
|---|
| 10 | - |
01 |
01 |
10 |
|---|
| 11 | 11 |
00 |
00 |
01 |
|---|
Так как функция возбуждения Т -триггера (табл.7.6) $$\varphi = 1$$, только тогда, когда состояние автомата переходит из 0 в 1 или из 1 в 0, то по закодированной рис.7.7 переходов исходного автомата Мура находим такие переключения триггеров, при которых они меняли свои состояния. Составляем таблицу функций возбуждения, которая имеет в качестве заголовков столбцов коды состояний, а строки помечены кодами входных сигналов (табл.7.8). В каждой клетке таблицы записаны функции возбуждения $$\varphi_1 \varphi_2.$$ Составляем для них уравнения:
$$\varphi_1=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \vee \tau_1 \bar\tau_2 \bar x_1 x_2 \vee \tau_1 \tau_2 x_1 \bar x_2\\
\varphi_2=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2 \vee \bar\tau_1 \tau_2 x_1 \bar x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2 \vee \tau_1 \tau_2 x_1 x_2
$$
Далее уравнения минимизируются и по ним строится схема в заданном базисе.
7.3 Синтез структурного автомата Мили на RS -триггерах
Рассмотрим синтез структурного автомата Мили, заданного табл.7.9 и табл.7.10, на RS -триггерах в элементном базисе {И, ИЛИ, НЕ}.
| z\a |
a1 |
a2 |
a3 |
a4 |
|---|
| z1 | a1 |
a3 |
a1 |
- |
|---|
| z2 | - |
a1 |
a4 |
a2 |
|---|
| z3 | a4 |
a2 |
a3 |
a3 |
|---|
| z\a |
a1 |
a2 |
a3 |
a4 |
|---|
| z1 | w1 |
w3 |
w1 |
- |
|---|
| z2 | - |
w1 |
w2 |
w2 |
|---|
| z3 | w2 |
w2 |
w3 |
w3 |
|---|
Находим количество элементов памяти
| t 1 |
t 2 |
| a1 | 0 |
0 |
|---|
| a2 | 0 |
1 |
|---|
| a3 | 1 |
0 |
|---|
| a4 | 1 |
1 |
|---|
Кодируем входные и выходные сигналы абстрактного автомата, например, так, как показано в табл.7.12 и табл.7.13
Структурный автомат представляем обобщенной схемой (рис 7.4(рис 7.4)
Табл.7.10 представляем, используя коды состояний, входных и выходных сигналов (табл.7.14), и по ней записываем уравнения выходов. $$y_1=\bar\tau_1\tau_2 \bar x_1 x_2 \vee \tau_1 \bar \tau_2 x_1 x_2 \vee \tau_1 \tau_2 x_1 x_2\\
y_2=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2 \vee \tau_1 \tau_2 x_1 \bar x_2$$| x1x2\t 1t 2 |
00 |
01 |
10 |
11 |
|---|
| 01 | 00 |
10 |
00 |
- |
|---|
| 10 | - |
00 |
01 |
01 |
|---|
| 11 | 01 |
01 |
10 |
10 |
|---|
Составляем закодированную таблицу переходов автомата (табл.7.15) и по ней записываем уравнения для функций возбуждения.| r1r2 |
00 |
01 |
10 |
00 |
|---|
| x1x2\t 1t 2 | 00 |
01 |
10 |
11 |
|---|
| 01 | 00 |
10 |
00 |
- |
|---|
| 10 | - |
00 |
11 |
01 |
|---|
| 11 | 11 |
01 |
10 |
10 |
|---|
Функция возбуждения RS -триггера представлена в табл.7.16. Просматривая каждый переход триггеров по таблице переходов автомата (табл.7.15), составляем таблицу функций возбуждения (табл.7.17), которая имеет в качестве заголовков столбцов коды состояний, а строки помечены кодами входных сигналов. В каждой клетке таблицы записаны функции возбуждения для первого триггера $$\varphi_1 \psi_1$$ и для второго триггера $$\varphi_2 \psi_2$$. Составляем для них уравнения:
| $$\tau_{исх.}$$ |
$$\varphi \psi$$ |
$$\tau_{пер.}$$ |
|---|
| 0 | 0 - |
0 |
|---|
| 0 | 1 0 |
1 |
|---|
| 1 | 0 1 |
0 |
|---|
| 1 | - 0 |
1 |
|---|
| $$x_1 x_2 \ \tau_1 \tau_2$$ |
0 0 |
0 1 |
1 0 |
1 1 |
|---|
| 01 | 0- 0- |
10 01 |
01 0- |
- |
|---|
| 10 | - |
0- 01 |
-0 10 |
01 -0 |
|---|
| 11 | 10 10 |
0- -0 |
-0 0- |
-0 01 |
|---|
$$\varphi_1=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \bar\tau_1 \tau_2 \bar x_1 x_2\\
\psi_1=\bar\tau_1 \bar\tau_2 \bar x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2\\
\varphi_2=\bar\tau_1 \bar\tau_2 x_1 x_2 \vee \tau_1 \bar\tau_2 x_1 \bar x_2\\
\psi_2=\bar\tau_1 \tau_2 \bar x_1 x_2 \vee \bar\tau_1 \tau_2 x_1 \bar x_2 \vee \tau_1 \tau_2 x_1 x_2$$
Далее уравнения минимизируются и по ним строится схема в заданном базисе.
Аналогично проводится синтез и на JK -триггерах.
