close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
ТЕОРИЯ АВТОМАТОВ
Методические указания к выполнению курсового проекта
2
ВАРИАНТЫ ЗАДАНИЙ ДЛЯ КУРСОВОГО ПРОЕКТА
Вариант 1
Вариант 2
a0
a0
0
a2
a3
a4
1
1
x1
a6
y1
y2
y1
x1
0
a2
0
x2
1
a3
y2
a1
a1
1
a5
y3
x2
0
a0
a6
a0
y3
Вариант 3
Вариант 4
a0
a0
a7
a1
y1
a3
a6
1
x1
a4
x2
0
0
1
x1
a5
y2
a2
1
0
a7
1
a3
a0
y1
y3
x2
y2
0
y3
a2
a0
3
Вариант 5
Вариант 6
a0
y1
a0
y2
0
1
x1
a1
a1
a2
y1
a2
y2
0
x2
a3
a4
1
x1
a3
0
1
y1
a4
y2
a5
1
y3
a6
a5
x2
y3
0
a6
a0
a0
Вариант 7
Вариант 8
a0
0
x2
a0
a7
y1
x1
1
1
a5
1
a6
a4
a5
a3
a6
y2
0
a1
a2
y3
y2
a0
0
x1
0
a7
a0
x2
y3
1
4
Вариант 9
Вариант 10
a0
1
a0
0
x1
a2
a4
y1
a3
y2
a5
a4
1
y1
x2
0
0
y2
a6
a7
1
x1
a2
y3
a7
a1
y3
a0
1
x2
0
a0
Вариант 11
Вариант 12
a0
a0
1
a6
a5
a7
0
1
a1
a1
a0
0
x2
0
a4
x2
1
a4
y2
y3
1
a3
y1
y1
x1
a3
0
x1
a0
y3
a2
y2
5
ВВЕДЕНИЕ
Процессор современного компьютера состоит из множества
простейших конечных автоматов. Овладение навыками синтеза конечных
автоматов позволяет получить общее представление о методах синтеза
электронных устройств различной сложности, вплоть до процессоров
суперкомпьютеров.
ЛИТЕРАТУРА
1. Сидоркин В. П. Синтез цифровых автоматов на микросхемах:
Лабораторный практикум / Под ред. А. В. Гусарова. – Рыбинск: РГАТА,
2003. – 103 с., ч. 1.
2. Сидоркин В. П. Синтез цифровых автоматов на микросхемах:
Лабораторный практикум / Под ред. А. В. Гусарова. – Рыбинск: РГАТА,
2003. – 107 с., ч. 2.
3. Гусаров А. В. Синтез конечных автоматов: Лабораторный
практикум. – Рыбинск: РГАТА, 2005. – 76 с.
4. Гусаров А. В. Синтез конечных автоматов: теория и практика. Ч. I.
Абстрактная теория автоматов. Синтез схем автоматов на универсальных
лабораторных стендах: учеб. пособие. – Рыбинск: РГАТА имени
П. А. Соловьева, 2010. – 112 с.
5. Гусаров А. В. Синтез конечных автоматов: теория и практика.
Ч. II. Структурный синтез автоматов: Учебное пособие. – Рыбинск:
РГАТА имени П. А. Соловьева, 2010. – 160 с.
УКАЗАНИЯ К ВЫПОЛНЕНИЮ КУРСОВОГО ПРОЕКТА
1. Номер варианта задания определяется по номеру фамилии
студента в журнале.
2. Курсовой проект оформляются в соответствии со стандартом СТО
ЮУрГУ-2008.
3. Курсовой проект должен включать в себя: абстрактный синтез
результирующего автомата (композиции автоматов) в соответствии с
вариантом задания и структурный синтез одного из автоматов по заданию
преподавателя. Примеры структурного синтеза автоматов Мура и Мили
приведены в пособиях [1 – 5] и в данном пособии. Курсовой проект
6
следует выполнять в соответствии с приведенным в данном пособии
примером.
1. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Пусть ГСА автомата Мура имеет n операторных вершин без учета
начальной и конечной вершин. Тогда орграф автомата Мура будет
содержать (n + 1) вершину.
Переход включает в себя несколько этапов.
1. Выполняется отметка вершин. Для этого символом a0 отмечается
начальная и конечная вершины. Остальные операторные вершины ГСА
отмечаются различными символами ai.
2. Строится орграф автомата. Вначале рисуют все вершины,
обозначая каждую из них символом ai. Над каждой вершиной ai
записывается оператор Yi, соответствующий этой вершине. Далее рисуют
дуги, соответствующие переходам, по следующим правилам:
– если в ГСА автомата Мура на пути от вершины am к вершине an
(am → an) нет условных вершин, то на дуге орграфа от вершины am к
вершине an ставится прочерк или пишется «1» (безусловный переход);
– если на пути от вершины am к вершине an (am → an) в ГСА есть
одна или несколько условных вершин, образующих некоторое логическое
условие, то это условие записывается над дугой.
После этого нужно проверить орграф на детерминированность и
отсутствие тупиковых вершин.
Рассмотрим пример.
Пусть ГСА автомата изображена на рис. 1.1. Требуется перейти от
ГСА к орграфу автомата Мура.
Начало Y0
0
X1
1
Y1
Y2
Y3
Конец Y0
1
X2
0
7
7
К
он
ец
Y0
7
Рис. 1.1. Исходная ГСА автомата
1. Выполняем отметку вершин. Для этого символом a0 отмечаем
начальную и конечную вершины. Остальные операторные вершины ГСА
отмечаем различными символами ai: операторную вершину Y1 отмечаем
символом a1, операторную вершину Y2 отмечаем символом a2,
операторную вершину Y3 отмечаем символом a3. (рис. 1.2).
Начало Y0
a0
a0
0
X1
1
1
a2
Y3
a3
Конец Y0
Y1
a1
1
Y2
0
X1
a1
Y1
Y0
1
X2
0
a0
X2
a2
Y2
a3
Y3
0
Y0
a0
Рис. 1.2. Отмеченная ГСА автомата
2. Строим орграф автомата (рис. 1.3). Вначале рисуем все вершины,
обозначая каждую из них символом ai. Над каждой вершиной ai
записываем оператор Yi, соответствующий этой вершине. Далее рисуем
дуги, соответствующие переходам.
Y1
Y0
X1
a0
a1
–
X1 X 2
–
X1 X 2
Y2
Y3
a3
–
a2
8
Рис. 1.3. Орграф автомата Мура, соответствующий ГСА на рис. 1.1
В ГСА автомата на пути от вершины a0 к вершине a1 (a0 → a1) есть
условная вершина X1, поэтому на дуге орграфа от вершины a0 к вершине
a1 ставим условие X1.
В ГСА автомата на пути от вершины a0 к вершине a2 (a0 → a2) есть
условные вершины X1 и X2, поэтому на дуге орграфа от вершины a0 к
вершине a1 ставим условие X 1 X 2 .
В ГСА автомата на пути от вершины a0 к вершине a3 (a0 → a3) есть
условные вершины X1 и X2, поэтому на дуге орграфа от вершины a0 к
вершине a1 ставим условие X 1 X 2 .
В ГСА автомата на пути от вершины a1 к вершине a2 (a1 → a2) нет
условных вершин, поэтому на дуге орграфа от вершины a1 к вершине a2
ставим прочерк.
В ГСА автомата на пути от вершины a2 к вершине a3 (a2 → a3) нет
условных вершин, поэтому на дуге орграфа от вершины a2 к вершине a3
ставим прочерк.
В ГСА автомата на пути от вершины a3 к вершине a0 (a3 → a0) нет
условных вершин, поэтому на дуге орграфа от вершины a3 к вершине a0
ставим прочерк.
Для осуществления структурного синтеза целесообразно перейти от
орграфа к отмеченной таблице переходов автомата. Однако
«классическая» форма таблицы не подразумевает наличие инверсных
значений входных сигналов. Поэтому в данном случае следует перейти к
прямой таблице переходов, которая, к тому же, облегчает процесс
структурного синтеза. Шаблон прямой таблицы переходов для
абстрактного синтеза автомата Мура приведен в табл. 1.1.
Таблица 1.1
Шаблон прямой таблицы переходов автомата Мура
для структурного синтеза автомата
Код
Номер Исходное
исходного
набора состояние
состояния
Условие
перехода
Следующее
состояние
Код
Выходной
следующего
сигнал
состояния
9
xk
an
ai
…
xk xn
…
af
yj
…
…
…
…
ak
x f xr
am
yj
Как видно из шаблона, условие перехода в общем случае включает
конъюнкцию прямых и инверсных значений входных сигналов. Выходной
сигнал зависит только от состояний автомата и является неизменным для
всех подстрок строки таблицы, соответствующих состоянию ai.
Столбец «Номер набора» заполняется по значениям столбцов «Код
исходного состояния» и «Условие перехода».
Столбец «Код следующего состояния» служит в качестве исходных
данных для получения функций возбуждения в зависимости от типа
триггера, реализующего элемент памяти.
10
2. ПРИМЕР СТРУКТУРНОГО СИНТЕЗА АВТОМАТА МУРА
Выполним каноническим способом [5] синтез конечного автомата
Мура S1, заданного кодированной граф-схемой алгоритма (рис. 2.1). В
качестве элементов памяти используем D-триггеры и JK-триггеры. Орграф
этого автомата приведен на рис. 2.2.
a0
000
a1
001
0
x1
1
a4
100
a2
010
y3
a3
011
y2
0
1
a5
001
y1
x2
Рис. 2.1. Граф-схема автомата Мура S1 с закодированными состояниями
Автомат имеет шесть состояний a0, a1, ... , a5, двоичные коды
которых равны 000, 001, ... , 101. Состояние a0 принято за начальное.
Входные сигналы x1 и x2 изменяют последовательность переходов
автомата из одного состояния в другое. Автомат в состояниях a1 и a2
формирует выходной сигнал y1, в состояниях a3 и a5 – выходные сигналы
y2 и y3 соответственно. Переключения автомата из состояния в состояние
происходят при подаче входных импульсов синхронизации.
11
a0
000
y3
a5
101
a1
001
a4
100
x1
x2
x1
y2
x2
y1
a2
010
y1
a3
011
Рис. 2.2. Ориентированный граф автомата Мура S1
В табл. 2.1 приведены переходы, выходные и входные сигналы,
сигналы возбуждения триггеров и схемы маршрутов автомата. Маршрут
автомата соответствует «прохождению» по ГСА при определенном наборе
входных сигналов. В табл. 2.1 приняты обозначения: Q2(t), Q1(t) и Q0(t) –
состояния триггеров до переключения, а Q2(t + 1), Q1(t + 1) и Q0(t + 1) –
после переключения. В случае синтеза автомата на D-триггерах состояние
Q(t + 1) в следующий момент автоматного времени – функция
возбуждения D(t) (см. табл. 2.1), поэтому колонки для Qi(t + 1) и Di(t) (где
i = 0, 1, 2) совмещены. Прочерки в табл. 2.1 соответствуют не полностью
определенным значениям.
При заполнении табл. 2.1 использовался рис. 2.1. Например, если
автомат находится в состоянии 1  Q2 Q1Q0  001, входные сигналы x1 = 1
и x2 = 0, то при подаче импульса синхронизации он должен перейти в
состояние 1  Q2 Q1Q0  010 (см. шестую строку сверху в табл. 2.1). Это
означает, что триггер 2 должен перейти из состояния «0» в состояние «0»,
триггер 1 – из «0» в «1», нулевой триггер – из «1» в «0».
Для переключения D-триггера 2 из «0» в «0» на вход D2 надо в
момент t подать «0», для переключения D-триггера 1 из «0» в «1» на вход
D1 надо в момент t подать «1», для переключения D-триггера 1 из «0» в
«1» на вход D1 надо в момент t подать «0».
Для переключения триггера 2 из «0» в «0» на вход J2 надо в момент t
подать «0», для входа K2 значение не определено (см. [1]). Переключение
триггера 1 из «0» в «1» можно выполнить сигналами J1(t) = 1 и K1(t) = 0
или 1, переключение нулевого триггера из «1» в «0» – сигналами J0(t) = 0
или 1, K0(t) = 1.
Таблица 2.1
Кодированная прямая таблица переходов, выходов и сигналов возбуждения автомата Мура S1
Состояния триггеров
Сигналы возбуждения
Выходные
Входные
JK-триггеров
сигналы
Q2(t +1) Q1(t +1) Q0(t +1)
Номера сигналы
Сигналы возбуждения
наборов (условия) Q2(t) Q1(t) Q0(t)
D-триггеров
J2(t) K2(t) J1(t) K1(t) J0(t) K0(t) y1(t) y2(t) y3(t)
x1(t) x2(t)
D2(t)
D1(t)
D0(t)
0, 8
1, 9
4, 12
5, 13
1
–
0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
1
0
1
1
0
1
–
–
–
–
0
1
0
0
0
0
–
–
–
–
1
–
1
–
–
1
–
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
0
0
0
1
1
0
1
0
1
0
0
0
0
0
–
–
–
–
0
1
–
–
–
–
0
1
1
–
1
–
–
1
–
1
0
1
1
0
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
1
0
0
1
0
0
1
0
0
1
0
1
1
0
0
1
–
–
–
–
1
0
1
–
0
–
–
1
–
1
–
1
–
–
1
–
0
0
1
1
0
0
0
0
0
0
0
0
1
–
–
–
–
–
–
–
–
–
–
–
–
–
–
24
25
26
29
1
1
0
0
0
1
2, 3, 6, 7,
10, 11,
14, 15,
20 – 23,
27, 28,
30, 31
–
–
–
a0
a1
a5 a4
a0
a3
a1
a2
a0
a1
a5
a2
10
16
17
18
19
0
0
0
1
1
Маршруты
11
Под номером набора в табл. 2.1 понимается десятичный эквивалент
двоичного числа, образованного значениями аргументов x1, x2, Q2, Q1, Q0 в
указанной последовательности. Например, 19-му набору соответствуют:
x1 = 1, x2 = 0, Q2 = 0, Q1 = 1, Q0 = 1. Часть наборов (2, 3, 6, ...) являются
запрещенными.
На рис. 2.2 приведен трафарет карты Вейча для синтеза
переключательной функций 5 аргументов. Номера наборов аргументов
получены для случая, когда двоичные веса аргументов x1, x2, Q2, Q1, Q0
соответственно равны 24, 23, 22, 21, 20.
б
в
x1
г
24 25 29 28 12 13
x2
a
9
8
26 27 31 30 14 15 11 10
18 19 23 22
6
7
3
2
16 17 21 20
4
5
1
0
Q2
Q0
в
a
Q1
Q0
б
г
Рис. 2.2. Трафарет карты Вейча для функций 5 аргументов x1, x2, Q2, Q1, Q0
При
минимизации
объединять
можно
клетки,
попарно
симметричные относительно осей а – а, б – б, в – в, г – г, а также соседние
клетки в строках и столбцах. При этом у каждой клетки из контура,
содержащего 2n элементов, должно быть ровно n соседних клеток.
D2
1
x1
x2
3
0
0
0
–
1
0
1
0
1
–
–
–
–
–
–
–
0
0
–
–
–
–
–
–
0
0
–
–
1
0
1
0
Q0
Q2
Q0
Рис. 2.3. Карта Вейча для функции D2
2
Q1
12
3
2
1
D2  Q2 Q0  x2Q1  x2Q1Q0  Q2 Q0  x2Q1  x2Q1Q0 
(2.1)
 (Q2 Q0 ) ( x2 Q1 ) ( x1 Q2 Q0 ) .
1
2
D1  x2Q1 Q0  x1 Q2Q1Q0  x2Q1 Q0  x1 Q2Q1Q0 
 ( x2 Q1 Q2 ) ( x1 Q2 Q1 Q0 ) .
2
D1
1
x1
x2
1
0
1
0
–
0
0
0
0
0
–
–
–
–
–
–
–
1
0
–
–
–
–
–
–
0
1
–
–
0
0
0
0
2
Q2
Q0
Q1
1
Q0
Рис. 2.4. Карта Вейча для функции D1
D0
x2
1
x1
2
1
0
1
–
1
1
0
1
1
–
–
–
–
–
–
–
1
0
–
–
–
–
–
–
1
0
–
–
1
1
0
1
Q0
Q2
Q1
Q0
Рис. 2.5. Карта Вейча для функции D0
(2.2)
13
2
1
(2.3)
D 0  Q0  Q 2  Q0  Q 2  Q0 Q 2 .
J2
2
x1
x2
0
0
–
–
–
–
1
0
1
–
–
–
–
–
–
–
0
0
–
–
–
–
–
–
0
0
–
–
–
–
1
0
Q2
Q0
1
Q1
Q0
Рис. 2.6. Карта Вейча для функции J2
1
2
J 2  x2Q1  x1Q0  x2Q1  x1Q0  ( x2 Q1 ) ( x1 Q0 ) .
K2
(2.4)
x1
x2
–
–
1
–
0
1
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
0
1
–
–
Q0
Q2
Q1
Q0
Рис. 2.7. Карта Вейча для функции K2
K2 = Q0.
(2.5)
14
J1
x1
x2
0
1
0
–
0
0
0
0
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
–
0
1
–
–
0
0
0
0
Q2
Q0
Q1
Q0
Рис. 2.8. Карта Вейча для функции J1
J1  x1 Q2 Q0 .
K1
2
x1
x2
(2.6)
1
–
–
–
–
–
–
–
–
1
–
–
–
–
–
–
–
0
1
–
–
–
–
–
–
–
–
–
–
–
–
–
–
Q0
Q2
Q1
Q0
Рис. 2.9. Карта Вейча для функции K1
1
2
K1  x2  Q0  x2  Q0  x2 Q0 .
(2.7)
15
J0
x1
x2
1
–
–
–
1
–
–
1
1
–
–
–
–
–
–
–
1
–
–
–
–
–
–
–
1
–
–
–
1
–
–
1
Q2
Q0
Q1
Q0
Рис. 2.10. Карта Вейча для функции J0
J0 = 1.
K0
x2
(2.8)
x1
–
1
0
–
–
0
1
–
–
–
–
–
–
–
–
–
–
1
–
–
–
–
–
–
–
1
–
–
–
0
1
–
Q0
Q2
Q1
Q0
Рис. 2.11. Карта Вейча для функции K0
K 0  Q2 .
(2.9)
16
2
2
y1
1
x1
x2
1
0
1
0
–
0
0
1
0
1
–
–
–
–
–
–
–
1
0
–
–
–
–
–
–
0
1
–
–
0
0
1
0
Q2
Q0
2
Q0
Q1
1
2
Рис. 2.12. Карта Вейча для функции y1
1
2
y1  Q1 Q0  Q2Q1Q0  Q1 Q0  Q2Q1Q0  (Q1 Q0 ) (Q2 Q1 Q0 ) . (2.10)
y2
x1
x2
0
0
0
–
0
0
0
0
0
–
–
–
–
–
–
–
0
1
–
–
–
–
–
–
0
0
–
–
0
0
0
0
Q0
Q2
Q1
Q0
Рис. 2.13. Карта Вейча для функции y2
y2 = Q1Q0.
(4.11)
17
y3
x1
x2
0
0
1
–
0
1
0
0
0
–
–
–
–
–
–
–
0
0
–
–
–
–
–
–
0
0
–
–
0
1
0
0
Q0
Q2
Q1
Q0
Рис. 2.14. Карта Вейча для функции y3
y3 = Q2Q0 .
(4.12)
Карты Вейча и выражения для сигналов возбуждения D-триггеров,
JK-триггеров и выходных сигналов y1, y2 и y3 приведены ниже. Схемы
автомата Мура на D- и JK-триггерах представлены на рис. 2.15 и рис. 2.16.
Сигнал R («Сброс») нужен для установки автомата в начальное состояние.
10
Q1
2
&
D2
&
13
Q0
4
x2
10
Q1
12
Q0
1
x1
«1»
x1
6
Q2
9
13
Q1
Q0
&
&
D2
x1
x2
«1»
D1
6
13
Q2
&
D0
Q0
R TT
D
C
7
Q2
13
Q0
&
y3
&
y3
«1»
«1»
«1»
8
6
7
R
14
&
3
4
5
1
2
Входы
y1
&
&
5
Q2
Q0
Q1
y2
18
6
13
x1
&
9
&
Q0
R
Q2
D1
Q2
«1»
S
R TT
D
C
Q1
R
D0
Q1
«1»
S
R TT
Q0
D
C
Q0
14
15
16
16
15
x2
Q2
y2
12
13
3
6
13
&
11
Q0
Q0
11
12
&
12
10 Q1
&
9
10
Q2
Q1
8
7
10
S
x2
Синхр.
Q2
Q1
Рис. 2.15. Автомат Мура S1 на D-триггерах
Q0
y1 y2 y 3
Q2
&
Q0
y3
&
«1»
«1»
26
Q0
&
x1
Q2
Q2
J
«1»
S
«1»
«1»
«1»
Q1
C
K1
&
K
R
J
C
R
«1»
«1»
R TT
Q2
1
&
«1»
«1»
«1»
10
1
5
6
R
y3
27
9
4
17
«1»
J2
K2 = Q0
23
R TT
&
19
x2
«1»
«1»
y2
21
K1
R TT
&
x1
«1»
14
1
2
3
4
10
R
x1
&
13 12
&
22
y1 11
6
10
Q2
x2
Q1
Q0
13
x2
Входы
7
10
&
&
y2
&
11
12 13
J2
&
Q2
Q0
9
x1
&
Q0
12
11
5
20
10
5
2
10
&
Q1
8
Q1
Q0
8
7
8
9
&
10
x2
Q1
5
3
8
Q0
J
C
R
Q2
Q1
&
K
«1»
«1»
K
S 2
«1»
S
Q0
3
Синхр.
Q2
Q1
Рис. 2.16. Автомат Мура S1 на JK-триггерах
Q0
y1 y2 y3
1/--страниц
Пожаловаться на содержимое документа