Из разбиения видно, что классы 1 и 2 совпадают, значит, продолжать не имеет смысла.
Таблица переходов-выходов минимизированного автомата представлена в таблице 4:
Таблица 4. Таблица переходов-выходов минимизированного автомата
d(t-1)
|
0
|
1
|
|
d0
|
d1/1
|
d2/1
|
|
d1
|
d3/1
|
d4/1
|
|
d2
|
d7/0
|
d8/0
|
|
d3
|
-
|
d5/1
|
|
d4
|
-
|
d6/1
|
|
d5
|
d11/1
|
d11/0
|
|
d6
|
d11/0
|
-
|
|
d7
|
-
|
d9/1
|
|
d8
|
d10/0
|
d5/0
|
|
d9
|
d11/1
|
-
|
|
d10
|
-
|
d11/0
|
|
d11
|
d0/-
|
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. Таблица кодированных состояний
d(t-1)
|
Q0
|
Q1
|
Q2
|
Q3
|
|
d0
|
0
|
0
|
0
|
0
|
|
d1
|
0
|
0
|
0
|
1
|
|
d2
|
0
|
0
|
1
|
0
|
|
d3
|
0
|
0
|
1
|
1
|
|
d4
|
0
|
1
|
0
|
0
|
|
d5
|
0
|
1
|
0
|
1
|
|
d6
|
0
|
1
|
1
|
0
|
|
d7
|
0
|
1
|
1
|
1
|
|
d8
|
1
|
0
|
0
|
0
|
|
d9
|
1
|
0
|
0
|
1
|
|
d10
|
1
|
0
|
1
|
0
|
|
d11
|
1
|
0
|
1
|
1
|
|
|
2.2 Формирование функций возбуждения и выходных сигналов структурного автомата
По минимизированному графу переходов абстрактного автомата (Приложение 2) можно составить таблицу переходов, выходных сигналов и сигналов возбуждения D-триггеров автомата Мили (таблица 6), Т-триггеров автомата Мили (таблица 7), RS-триггеров (таблица 8), JK-триггеров (таблица 9).
D-триггер - элемент задержки - имеет один информационный вход D и один выход Q и осуществляет задержку поступившего на его вход сигнала на один такт. Состояние, в которое переходит триггер, совпадает с поступившим на его вход сигналом D(t).
Таблица 6. Таблица переходов, выходных сигналов и сигналов возбуждения D-триггеров
Номер перехода
|
Исходное состояние
|
Код исходного состояния
|
Следующее состояние
|
Код следующего состояния
|
Входной набор
|
Выходные сигналы
|
Сигналы возбуждения
|
|
|
|
|
|
|
|
0
|
1
|
D3
|
D2
|
D1
|
D0
|
|
1
|
d0
|
0000
|
d1
d2
|
0001
0010
|
0
1
|
|
d00
d01
|
|
|
d01
|
d00
|
|
2
|
d1
|
0001
|
d3
d4
|
0011
0100
|
0
1
|
|
d10
d11
|
|
d11
|
d10
|
d10
|
|
3
|
d2
|
0010
|
d7
d8
|
0111
1000
|
0
1
|
d20
d21
|
|
d21
|
d20
|
d20
|
d20
|
|
4
|
d3
|
0011
|
d5
|
0101
|
1
|
|
d31
|
|
d31
|
|
d31
|
|
5
|
d4
|
0100
|
d6
|
0110
|
1
|
|
d41
|
|
d41
|
d41
|
|
|
6
|
d5
|
0101
|
d11
|
1011
|
01
|
d50
|
d51
|
d50
d51
|
|
d50
d51
|
d50
d51
|
|
7
|
d6
|
0110
|
d11
|
1011
|
0
|
d60
|
|
d60
|
|
d60
|
d60
|
|
8
|
d7
|
0111
|
d9
|
1001
|
1
|
|
d71
|
d71
|
|
|
d71
|
|
9
|
d8
|
1000
|
d10
d5
|
1010
0101
|
0
1
|
d80
d81
|
|
d80
|
d81
|
d80
|
d81
|
|
10
|
d9
|
1001
|
d11
|
1011
|
0
|
|
d90
|
d90
|
|
d90
|
d90
|
|
11
|
d10
|
1010
|
d11
|
1011
|
1
|
d101
|
|
d101
|
|
d101
|
d101
|
|
12
|
d11
|
1011
|
d0
|
0000
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
Из таблицы следует, что выходные сигналы автомата Мили описываются следующими выражениями:
= d20 d21 d50 d60 d80 d81 d101= d2 d50 d60 d8 d101
= d00 d01 d10 d11 d31 d41 d51 d71 d90= d0 d1 d31 d41 d51 d71 d90
Также следует, что сигналы возбуждения D-триггеров автомата Мили описываются следующими выражениями:
D3 = d21 d50 d51 d60 d71 d80 d90 d101= d21 d5 d60 d71 d80 d90 d101
D2 = d11 d20 d31 d41 d81
D1 = d01 d10 d20 d41 d50 d51 d60 d80 d90 d101=
=d01 d10 d20 d41 d5 d60 d80 d90 d101
D0 = d00 d10 d20 d31 d50 d51 d60 d71 d81 d90 d101=
=d00 d10 d20 d31 d5 d60 d71 d81 d90 d101
Функциональная схема автомата Мили на D-триггерах, построенная по выражениям, описывающим выходные сигналы, приведена в Приложении 3.
Таблица 7. Таблица переходов, выходных сигналов и сигналов возбуждения T-триггеров
Номер перехода
|
Исходное состояние
|
Код исходного состояния
|
Следующее состояние
|
Код следующего состояния
|
Входной набор
|
Выходные сигналы
|
Сигналы возбуждения
|
|
|
|
|
|
|
|
0
|
1
|
T3
|
T2
|
T1
|
T0
|
|
1
|
d0
|
0000
|
d1
d2
|
0001
0010
|
0
1
|
|
d00
d01
|
|
|
d01
|
d00
|
|
2
|
d1
|
0001
|
d3
d4
|
0011
0100
|
0
1
|
|
d10
d11
|
|
d11
|
d10
|
d11
|
|
3
|
d2
|
0010
|
d7
d8
|
0111
1000
|
0
1
|
d20
d21
|
|
d21
|
d20
|
d21
|
d20
|
|
4
|
d3
|
0011
|
d5
|
0101
|
1
|
|
d31
|
|
d31
|
d31
|
|
|
5
|
d4
|
0100
|
d6
|
0110
|
1
|
|
d41
|
|
|
d41
|
|
|
6
|
d5
|
0101
|
d11
|
1011
|
01
|
d50
|
d51
|
d50
d51
|
d50
d51
|
d50
d51
|
|
|
7
|
d6
|
0110
|
d11
|
1011
|
0
|
d60
|
|
d60
|
d60
|
|
d60
|
|
8
|
d7
|
0111
|
d9
|
1001
|
1
|
|
d71
|
d71
|
d71
|
d71
|
|
|
9
|
d8
|
1000
|
d10
d5
|
1010
0101
|
0
1
|
d80
d81
|
|
d81
|
d81
|
d80
|
d81
|
|
10
|
d9
|
1001
|
d11
|
1011
|
0
|
|
d90
|
|
|
d90
|
|
|
11
|
d10
|
1010
|
d11
|
1011
|
1
|
d101
|
|
|
|
|
d101
|
|
12
|
d11
|
1011
|
d0
|
0000
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
Из таблицы следует, что сигналы возбуждения T-триггеров автомата Мили описываются следующими выражениями:
T3 = d21 d50 d51 d60 d71 d81= d21 d5 d60 d71 d81
T2 = d11 d20 d31 d50 d51 d60 d71 d81= d11 d20 d31 d5 d60 d71 d81
T1 = d01 d10 d21 d31 d41 d50 d51 d71 d80 d90= d01 d10 d21 d31 d41 d5 d71 d80 d90
T0 = d00 d20 d60 d81 d101
Функциональная схема автомата Мили на T-триггерах, построенная по выражениям, описывающим выходные сигналы, приведена в Приложении 4.
Таблица 8. Таблица переходов и сигналов возбуждения RS-триггеров
Номер перехода
|
Сигналы возбуждения
|
|
|
R3
|
S3
|
R2
|
S2
|
R1
|
S1
|
R0
|
S0
|
|
1
|
|
|
|
|
|
d01
|
|
d00
|
|
2
|
|
|
|
d11
|
|
d10
|
d11
|
|
|
3
|
|
d21
|
|
d20
|
d21
|
|
|
d20
|
|
4
|
|
|
|
d31
|
d31
|
|
|
|
|
5
|
|
|
|
|
|
d41
|
|
|
|
6
|
|
d50
d51
|
d50
d51
|
|
|
d50
d51
|
|
|
|
7
|
|
d60
|
d60
|
|
|
|
|
d60
|
|
8
|
|
d71
|
d71
|
|
d71
|
|
|
|
|
9
|
d81
|
|
|
d81
|
|
d80
|
|
d81
|
|
10
|
|
d90
|
|
|
|
|
|
|
|
11
|
|
|
|
|
|
|
|
d101
|
|
12
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
Из таблицы следует, что сигналы возбуждения RS-триггеров автомата Мили описываются следующими выражениями:
R3 = d81
S3 = d21 d50 d51 d60 d71 d90= d21 d5 d60 d71 d90
R2 = d50 d51 d60 d71= d5 d60 d71
S2 = d11 d20 d31 d81
R1 = d21 d31 d71
S1 = d01 d10 d41 d50 d51 d80= d01 d10 d41 d5 d80
R0 = d11
S0 = d00 d20 d60 d81 d101
Функциональная схема автомата Мили на RS-триггерах, построенная по выражениям, описывающим выходные сигналы, приведена в Приложении 5.
Таблица 9. Таблица переходов и сигналов возбуждения JK-триггеров
Номер перехода
|
Сигналы возбуждения
|
|
|
J3
|
K3
|
J2
|
K2
|
J1
|
K1
|
J0
|
K0
|
|
1
|
|
|
|
|
d01
|
|
d00
|
|
|
2
|
|
|
d11
|
|
d10
|
|
|
d11
|
|
3
|
d21
|
|
d20
|
|
|
d21
|
d20
|
|
|
4
|
|
|
d31
|
|
|
d31
|
|
|
|
5
|
|
|
|
|
d41
|
|
|
|
|
6
|
d50
d51
|
|
|
d50
d51
|
d50
d51
|
|
|
|
|
7
|
d60
|
|
|
d60
|
|
|
d60
|
|
|
8
|
d71
|
|
|
d71
|
|
d71
|
|
|
|
9
|
|
d81
|
d81
|
|
d80
|
|
d81
|
|
|
10
|
d90
|
|
|
|
|
|
|
|
|
11
|
|
|
|
|
|
|
d101
|
|
|
12
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
|
Из таблицы следует, что сигналы возбуждения RS-триггеров автомата Мили описываются следующими выражениями:
J3 = d21 d50 d51 d60 d71 d90= d21 d5 d60 d71 d90
K3 = d81
J2 = d11 d20 d31 d81
K2 = d50 d51 d60 d71= d5 d60 d71
J1 = d01 d10 d41 d50 d51 d80= d01 d10 d41 d5 d80
K1 = d21 d31 d71
J0 = d00 d20 d60 d81 d101
K0 = d11
Функциональная схема автомата Мили на JK-триггерах, построенная по выражениям, описывающим выходные сигналы, приведена в Приложении 6.
ЗАКЛЮЧЕНИЕ
В процессе выполнения работы мной были закреплены знания о синтезе конечных автоматов и получена практика в построении комбинационных схем.
В данной работе мной было выполнено проектирование конечного автомата по алфавитному отображению с использованием канонического метода структурного синтеза автоматов. Построены граф переходов абстрактного автомата с 17 состояниями и таблицы переходов-выходов. Минимизация состояний автомата выполнена путем разбиения на группы эквивалентных между собой состояний. После чего был построен минимальный граф Мили с 11 состояниями. Выполнен структурный синтез конечного автомата. Построены функциональные схемы автомата Мили на D, T, RS и JK-триггерах.
СПИСОК ЛИТЕРАТУРЫ
1. Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). - 2-е изд., перераб. и доп. - Л.: Энергия, 1979. - 232 с., ил.
2. Дегтярев В.М., Ерош И.Л., Михайлов В.В. Проектирование цифровых автоматов.-Л.:ЛИАП, 1974г.
3. Козин И.В., Иванов Н.М., Лупал А.М. Проектирование управляющих автоматов по алфавитному отображению. Учебное пособие по курсовому проектированию/ЛИАП. - Л., 1991. - 82 с., ил.
4. Лупал А.М. Теория автоматов. Учебное пособие/СПбГУАП. - СПб., 2000. - 120 с., ил.
5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. Учебник для вузов по спец. «Электронные вычислительные машины». - 2-е изд., перераб. и доп. - Мн.: Выш. школа, 1980. - 336 с., ил.
6. Конспект лекций по дисциплине «Теория автоматов», преподаватель Глебов Е.А., 2005-2006 уч.г.
Страницы: 1, 2
|