Синтез комбинацонных схем и конечных автоматов, сети ПетриРефераты >> Программирование и компьютеры >> Синтез комбинацонных схем и конечных автоматов, сети Петри
(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.
Следующим шагом оформляем общую таблицу переходов для минимизированной формы автомата:
|
s(j) |
0 |
1 |
2 |
3 |
|
0 |
0/1 |
1/0 |
0/1 |
1/0 |
|
1 |
0/0 |
1/1 |
0/0 |
1/1 |
x(j)
Таблица 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 |
