Синтез комбинацонных схем и конечных автоматов, сети Петри
Рефераты >> Программирование и компьютеры >> Синтез комбинацонных схем и конечных автоматов, сети Петри

(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


Страница: