| S4
W0 | S6
W1 | S8
W2 | S1
W0
X2 | S4
W2 | S6
W0 | S8
W1 | S1
W2 | S3
W0 | S5
W1 | S7
W2 | S0
W0 | S2
W1
X3 | S5
W0 | S7
W1 | S0
W2 | S2
W0 | S4
W1 | S6
W2 | S8
W0 | S1
W1 | S3
W2
Рисунок 2.2.3 – Загальна таблиця переходів
Мінімізовуємо автомат за числом станів з використанням отриманих таблиць:
B0 = { S0, S3, S6 } (2.2.4)
B1 = { S1, S4, S7 } (2.2.5)
B2 = { S2, S5, S8 } (2.2.6) |
B0 | B1 | B2
S(j) X(j) | S0 | S3 | S6 | S1 | S4 | S7 | S2 | S5 | S8
X0 | B2 | B2 | B2 | B1 | B1 | B1 | B0 | B0 | B0
X1 | B0 | B0 | B0 | B2 | B2 | B2 | B1 | B1 | B1
X2 | B1 | B1 | B1 | B0 | B0 | B0 | B2 | B2 | B2
X3 | B2 | B2 | B2 | B1 | B1 | B1 | B0 | B0 | B0
Рисунок 2.2.4 – Мінімізована таблиця переходів за станами
S(j) X(j) | S0 | S1 | S2
X0 | S2 | S1 | S0
X1 | S0 | S2 | S1
X2 | S1 | S0 | S2
X3 | S2 | S1 | S0
Рисунок 2.2.5 – Мінімізована таблиця переходів
S(j) X(j) | S0 | S1 | S2
X0 | W0 | W1 | W2
X1 | W1 | W2 | W0
X2 | W2 | W0 | W1
X3 | W0 | W1 | W2
Рисунок 2.2.6 – Мінімізована таблиця виходів
Будуємо граф мінімізованого автомата:
Рисунок 2.2.7– Граф мінімізованого автомата
Виписуємо для нього загальну матрицю переходів:
S(j) X(j) | S0 | S1 | S2
X0 | S2
W0 | S1
W1 | S0
W2
X1 | S0
W1 | S2
W2 | S1
W0
X2 | S1
W2 | S0
W0 | S2
W1
X3 | S2
W0 | S1
W1 | S0
W2
Рисунок 2.2.8 – Загальна матриця переходів
Переходимо до двійкового подання входу X, виходу Y і стану S: |
Z1 | Z2
X0 | 0 | 0 | Y1 | Y2 | Q1 | Q2
X1 | 0 | 1 | W0 | 0 | 0 | S0 | 0 | 0
X2 | 1 | 1 | W1 | 0 | 1 | S1 | 0 | 1
X3 | 1 | 0 | W2 | 1 | 1 | S2 | 1 | 1
Рисунок 2.2.9
Складаємо відповідно таблиці переходів та виходів комбінаційної схеми автомата:
Q1Q2 Z1Z2 | 00 | 01 | 11
00 | 11 | 01 | 00
01 | 00 | 11 | 01
11 | 01 | 00 | 11
10 | 11 | 01 | 00
Рисунок 2.2.10 – Мінімізована таблиця переходів
Q1Q2 Z1Z2 | 00 | 01 | 11
00 | 00 | 01 | 11
01 | 01 | 11 | 00
11 | 11 | 00 | 01
10 | 00 | 01 | 11
Рисунок 2.2.11 – Мінімізована таблиця виходів
На основі мінімізованої таблиці виходів складаємо мінімізоване рівняння булевої функції:
На основі мінімізованої таблиці виходів складаємо мінімізоване рівняння булевої функції:
(2.2.7) (2.2.8)
На основі таблиці функцій входів RS-тригера складаємо таблиці збудження:
Qt | Qt+1 | R | S
0 | 0 | X | 0
0 | 1 | 0 | 1
1 | 0 | 1 | 0
1 | 1 | 0 | X
Рисунок 2.2.12 – Таблиця функцій входів RS-тригера
Q1Q2 Z1Z2 | 00 | 01 | 11 | 10
00 | 01 | X0 | 10 | -
01 | X0 | 01 | 10 | -
11 | X0 | X0 | 0X | -
10 | 01 | X0 | 10 | -
Рисунок 2.2.13 – Карта Карно для R1S1
Q1Q2 Z1Z2 | 00 | 01 | 11 | 10
00 | 01 | 0X | 10 | -
01 | 01 | 0X | 0X | -
11 | 01 | 10 | 0X | -
10 | 01 | 0X | 10 | -
Рисунок 2.2.14 – Карта Карно для R2S2
Із отриманих таблиць складаємо рівняння мінімізованих функцій входів R1, S1, R2, S2:
(2.2.7) (2.2.8)
Складаємо логічну схему автомата в базисі І, НЕ, АБО, реалізуючи елементи пам’яті на тригерах:
Рисунок 2.2.15 – Логічна схема автомата
Висновки по розділу
Під час виконання поставленої задачі я навчився мінімізувати скінченні автомати за кількістю станів і будувати графи цих автоматів. Також я оволодів методами синтезу автоматів з елементами пам’яті у заданому елементному базисі.
2.3 Завдання 3.
Будуємо довільну ГСА і відмічаємо за правилами операторні вершини, умовні переходи, вхідні та вихідні сигнали.
Рисунок 2.3.1 – ГСА, зазначена для автомата Мілі
На основі ГСА будуємо граф автомата Мілі.
На основі ГСА будуємо граф автомата Мілі.
Рисунок 2.3.2 – Граф автомата Мілі
На підставі зазначеної ГСА або графа автомата можна побудувати таблицю переходів-виходів. Для мікропрограмних автоматів таблиця переходів-виходів будується у вигляді списку та розрізняються пряма і зворотня таблиці.
am | as | X | Y
a1 | a2
a3
a2 | a2
a4
a1
a3 | a3
a5
a4 | a5 | 1
a5 | a1
a1
Рисунок 2.3.3 – Пряма таблиця переходів-виходів автомата Мілі
am | as | X | Y
a2 | a1
a5
a5
a2 | a2
a1
a3 | a3
a1
a2 | a4
a3 | a5
a4 | 1
Рисунок 2.3.4 – Зворотня таблиця переходів-виходів автомата Мілі
У наведених таблицях am - початковий стан, as