Один из алгоритмов минимизации полностью определенных автоматов заключается в следующем. Множество состояний исходного абстрактного автомата разбивается на попарно пересекающиеся классы эквивалентных состояний, далее каждый класс эквивалентности заменяется одним состоянием. В результате получается минимальный автомат, имеющий столько же состояний, на сколько классов эквивалентности разбиваются исходные состояния автомата.
0 класс эквивалентности:
a0, a1
b0
a2, a11
b1
a14
b2
a3, a4, a10
b3
a5, a15
b4
a6
b5
a7, a8, a9, a13, a16, a17, a18
b6
a12
b7
1 класс эквивалентности:
a0
c0
a1
c1
a2
c2
a3
c3
a4
c4
c5
c6
a10
c7
a11
c8
c9
c10
c11
2 класс эквивалентности:
a0d0
d1
d2
d3
d4
d5
d6
d7
d8
d9
d10
d11
Из разбиения видно, что классы 1 и 2 совпадают, значит, продолжать не имеет смысла.
Таблица переходов-выходов минимизированного автомата представлена в таблице 4:
Таблица 4. Таблица переходов-выходов минимизированного автомата
d(t-1)
0
1
d0
d1/1
d2/1
d3/1
d4/1
d7/0
d8/0
-
d5/1
d6/1
d11/1
d11/0
d9/1
d10/0
d5/0
d0/-
Граф переходов минимизированного автомата представлен в приложении 2.
2. СТРУКТУРНЫЙ СИНТЕЗ КОНЕЧНОГО АВТОМАТА
2.1 Кодирование состояний, входных и выходных сигналов
Для кодирования состояний, входных и выходных сигналов конечного автомата, необходимо вычислить число элементов памяти:
а) рассчитаем число элементов памяти: Н = ] log2h [, где h - число состояний после минимизации D = {}
H = ] log2 12 [ = 4
б) рассчитаем число входных (L) и выходных (М) шин: L = ] log2n[
М =] log2m [,
где n, m - число букв входного и выходного алфавитов
Z = {0, 1} L = ] log2 2 [ = 1
W = {0, 1} M = ] log2 2 [ = 1
Из приведённого выше следует, что для кодирования состояний необходимо 4 элемента памяти, обозначим их Q0, …, Q3. Закодируем состояния (таблица 5) случайными кодами.
Таблица 5. Таблица кодированных состояний
Q0
Q1
Q2
Q3
2.2 Формирование функций возбуждения и выходных сигналов структурного автомата
По минимизированному графу переходов абстрактного автомата (Приложение 2) можно составить таблицу переходов, выходных сигналов и сигналов возбуждения D-триггеров автомата Мили (таблица 6), Т-триггеров автомата Мили (таблица 7), RS-триггеров (таблица 8), JK-триггеров (таблица 9).
D-триггер - элемент задержки - имеет один информационный вход D и один выход Q и осуществляет задержку поступившего на его вход сигнала на один такт. Состояние, в которое переходит триггер, совпадает с поступившим на его вход сигналом D(t).
Таблица 6. Таблица переходов, выходных сигналов и сигналов возбуждения D-триггеров
Номер перехода
Исходное состояние
Код исходного состояния
Следующее состояние
Код следующего состояния
Входной набор
Выходные сигналы
Сигналы возбуждения
D3
D2
D1
D0
0000
d1 d2
0001 0010
0 1
d00 d01
d01
d00
2
0001
d3 d4
0011 0100
d10 d11
3
0010
d7 d8
0111 1000
d20 d21
d21
d20
4
0011
0101
d31
5
0100
0110
d41
Страницы: 1, 2, 3, 4