2.3 Расчёты и полученные результаты.
Построение таблиц переходов, выходов и общей таблицы переходов и выходов на основе заданных уравнений автомата Мили очевидно:
| x(j) s(j) | 0 | 1 | 2 | 3 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 2 | 1 | 0 | 1 | 0 |
| 3 | 0 | 1 | 0 | 1 |
| 4 | 1 | 0 | 1 | 0 |
| 5 | 0 | 1 | 0 | 1 |
| 6 | 1 | 0 | 1 | 0 |
| 7 | 0 | 1 | 0 | 1 |
Таблица 2.3.1 – Таблица выходов автомата
| x(j) s(j) | 0 | 1 | 2 | 3 |
| 0 | 0 | 1 | 2 | 3 |
| 1 | 2 | 3 | 4 | 5 |
| 2 | 4 | 5 | 6 | 7 |
| 3 | 6 | 7 | 0 | 1 |
| 4 | 0 | 1 | 2 | 3 |
| 5 | 2 | 3 | 4 | 5 |
| 6 | 4 | 5 | 6 | 7 |
| 7 | 6 | 7 | 0 | 1 |
Таблица 2.3.2 – Таблица переходов автомата
| x(j) s(j) | 0 | 1 | 2 | 3 |
| 0 | 0/1 | 1/0 | 2/1 | 3/0 |
| 1 | 2/0 | 3/1 | 4/0 | 5/1 |
| 2 | 4/1 | 5/0 | 6/1 | 7/0 |
| 3 | 6/0 | 7/1 | 0/0 | 1/1 |
| 4 | 0/1 | 1/0 | 2/1 | 3/0 |
| 5 | 2/0 | 3/1 | 4/0 | 5/1 |
| 6 | 4/1 | 5/0 | 6/1 | 7/0 |
| 7 | 6/0 | 7/1 | 0/0 | 1/1 |
Таблица 2.3.3 – Общая таблица переходов и выходов автомата
Перейдём непосредственно к минимизации полученного автомата по числу состояний. Для этого воспользуемся алгоритмом, известным в литературе как метод Гриса - Хопкрофта. Его достоинство в том, что он даёт гарантированно минимальную форму автомата. Однако в общем случае он является довольно трудоёмким и применяется, как правило, для автоматов с небольшим количеством состояний. Он основан на свойстве транзитивности эквивалентности
(si ~ sj) ∩ (sj ~ sk) (si ~ sk) (2.3.1)
Пара эквивалентных состояний переходит при всех возможных значениях входа в пары также эквивалентных состояний.
Алгоритм состоит из следующих шагов.
Сначала разбиваем все состояния автомата на множества по признаку совпадения выходных сигналов. В нашем случае получаем 2 множества: S1 = {0, 2, 4, 6} и S2 = {1, 3, 5, 7}.
Чтобы назвать каждый из полученных классов новым состоянием, нужно убедиться в том, что в каждый класс входят только эквивалентные между собой состояния. Для этого составляем таблицу пар эквивалентных состояний. При этом не забываем о том, что эквивалентными могут быть состояния, принадлежащие только одному классу. В таблицу заносим все те пары, в которые переходят при соответствующих входах исходные, вероятно эквивалентные, пары:
| пары | 0 | 1 | 2 | 3 |
| 0;2 | 0;4 | 1;5 | 2;6 | 3;7 |
| 0;4 | 0;0 | 1;1 | 2;2 | 3;3 |
| 0;6 | 0;4 | 1;5 | 2;6 | 3;7 |
| 2;4 | 4;0 | 5;1 | 6;2 | 3;7 |
| 2;6 | 4;4 | 5;5 | 6;6 | 7;7 |
| 4;6 | 0;4 | 1;5 | 2;6 | 3;7 |
| 1;3 | 2;6 | 3;7 | 4;0 | 5;1 |
| 1;5 | 2;2 | 3;3 | 4;4 | 5;5 |
| 1;7 | 2;6 | 3;7 | 4;0 | 5;1 |
| 3;5 | 6;2 | 7;3 | 0;4 | 1;5 |
| 3;7 | 6;6 | 7;7 | 0;0 | 1;1 |
| 5;7 | 2;6 | 3;7 | 4;0 | 5;1 |
Таблица 2.3.4 – Таблица пар эквивалентных состояний
Ищем в полученной таблице неэквивалентные пары – пары из разных множеств. В таблице таких нет, значит, окончательно получаем автомат с двумя новыми состояниями – обозначим их 0 и 1.
Следующим шагом оформляем общую таблицу переходов для минимизированной формы автомата:
| x(j) s(j) | 0 | 1 | 2 | 3 |
| 0 | 0/1 | 1/0 | 0/1 | 1/0 |
| 1 | 0/0 | 1/1 | 0/0 | 1/1 |
Таблица 2.3.5 – Новая общая таблица переходов.
На основании полученной общей таблицы переходов и выходов можно нарисовать граф минимизированного автомата с двумя состояниями:
0/1U 2/1 1/0 U 3/0 1/1U 3/1
0 1
0/0 U 2/0
Рисунок 2.3.1 – Граф минимизированного автомата
Для практической реализации полученного автомата надо двоично закодировать все сигналы. Для кодировки y и s достаточно одного двоичного разряда, x требует двух – x1 и x2:
| x | x1 | x2 |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
Таблица 2.3.6 – Двоичная кодировка x
Составляем таблицу истинности для комбинационной части схемы на основе таблицы (2.3.5). Получаем две функции трёх аргументов:
| x1(j) | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| x2(j) | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| s(j) | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| y(j) | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| s(j+1) | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
Таблица 2.3.7 – Таблица истинности комбинационной части
Каждую из функций y(j) и s(j+1) минимизируем с помощью карт Карно:
y(j) s(j+1)
x1(j)x2(j) x1(j)x2(j)
00 01 11 10 00 01 11 10
0 1 1 0 1 1
s(j) s(j)
1 1 1 1 1 1
Рисунок 2.3.2 – Карты Карно для комбинационной части
На основании выбранных покрытий записываем минимизированные выражения для функций переходов и выходов:
(2.3.2)
(2.3.3)
Реализуем полученные функции в виде комбинационной схемы, добавляя к ней элементы памяти – D - триггер и задержку. Комбинационную часть реализуем в базисе И – ИЛИ – НЕ.
Рисунок 2.3.2 – Схема минимизированного автомата в базисе И – ИЛИ – НЕ
0 комментариев