Синтез цифрового автомата с памятью
Синтез
цифрового автомата с памятью
Оглавление
Задание на
курсовое проектирование
Основная
часть
1.
Проектирование автомата Мили
1.1 Разметка
ГСА
.2 Построение
графа переходов-выходов
.3 Составление
таблицы переходов-выходов
.4 Кодирование
состояний автомата
.5 Составление
структурной таблицы переходов-выходов
.6 Построение
функций выхода автомата Мили
.7 Построение
функций возбуждения автомата Мили на RS-триггерах
.8 Построение
логической схемы автомата Мили
2.
Проектирование автомата Мура
2.1 Разметка
ГСА
.2 Построение
графа переходов-выходов
.3 Составление
таблицы переходов-выходов
.4 Кодирование
состояний автомата
.5 Составление
структурной таблицы переходов-выходов
.6 Построение
функций выхода автомата Мура
.7 Построение
функций возбуждения автомата Мура на T-триггерах
.8 Построение
логической схемы автомата Мура
Заключение
Список
литературы
Приложение 1
Приложение 2
Задание на курсовое проектирование
Спроектировать цифровые автоматы Мили и Мура с памятью в Булевом базисе
по заданной ГСА (рисунок 1). В качестве элемента памяти выбрать T-триггер.
Для каждого автомата:
1. Разметка ГСА;
2. Построение графа переходов-выходов;
. Составление таблицы переходов-выходов;
. Кодирование состояний;
. Составление частично структурированной таблицы переходов-выходов;
. Построение функций выходов автомата;
. Построение таблицы функций возбуждения выходов для заданного
типа триггера;
. Построение функций возбуждения;
. Построение логической схемы автомата;
. Экспериментальная проверка автомата;
Рис. 1. Исходная ГСА проектируемого автомата
Основная часть
цифровой автомат логическая схема
1. Проектирование
автомата Мили
1.1 Разметка
ГСА
Производим разметку заданной ГСА для автомата Мили:
рис. 2. Разметка ГСА автомата Мили
1.2
Построение графа переходов-выходов
рис. 3. Граф переходов-выходов для автомата Мили
1.3
Составление таблицы переходов-выходов
Таблица 1. Таблица переходов-выходов
Состояние автомата
|
Входной сигнал
|
|
1
|
x1
|
_x1
|
x2
|
_x2x3
|
___x2x3
|
_x4
|
x4x5
|
_x4x5
|
q0
|
q1/y1
|
|
|
|
|
|
|
|
|
q1
|
|
q2/y2
|
q0/y5
|
|
|
|
|
|
|
q2
|
|
|
|
q3/y3
|
q3/-
|
q0/y5
|
|
|
|
q3
|
|
|
|
|
|
|
|
|
q4
|
|
|
|
|
|
|
q0/y5
|
q3/y3
|
q0/y5
|
1.4
Кодирование состояний автомата
Таблица 2. Кодирование состояний автомата Мили
Состояние
|
q0
|
q1
|
q2
|
q3
|
q4
|
Код α1α2α3
|
000
|
001
|
010
|
011
|
100
|
1.5
Составление структурной таблицы переходов-выходов
Таблица 3. Структурная таблица переходов-выходов
Состояние автомата
|
Входной сигнал
|
|
1
|
x1
|
_x1
|
x2
|
_x2x3
|
___x2x3
|
_x4
|
x4x5
|
_x4x5
|
000
|
001/y1
|
|
|
|
|
|
|
|
|
001
|
|
010/y2
|
0000/y5
|
|
|
|
|
|
|
010
|
|
|
|
011/y3
|
011/-
|
000/y5
|
|
|
|
011
|
100/y4
|
|
|
|
|
|
|
|
|
100
|
|
|
|
|
|
|
000/y5
|
011/y3
|
000/y5
|
1.6
Построение функций выхода автомата Мили
Функции выхода автомата Мили:
____
y1= α1α2α3
___
y2= α1α2α3x1
_ _ ___
y3= α1α2α3x2 +α1α2α3x4 x5
_
y4= α1α2α3
___ _ _ _ ____ ___ __ ___ _5= α1α2α3 x1+α1α2α3 x2 x3+
α1α2α3 x4+
α1α2α3 x4 x5
1.7 Построение
функций возбуждения автомата Мили на RS-триггерах
Таблица 4. Таблица истинности T-триггера
состояние
|
входной сигнал
|
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
Таблица 5. Функции возбуждения автомата Мили на T-триггерах
Состояние автомата
|
Входной сигнал
|
|
1
|
x1
|
x2
|
_x2x3
|
___x2x3
|
_x4
|
x4x5
|
_x4x5
|
000
|
001
|
|
|
|
|
|
|
|
|
001
|
|
011
|
001
|
|
|
|
|
|
|
010
|
|
|
|
001
|
001
|
010
|
|
|
|
011
|
111
|
|
|
|
|
|
|
|
|
100
|
|
|
|
|
|
|
100
|
111
|
100
|
Таким образом, получаем входные сигналы для T-триггеров:
_ ___ _ ___ ___ _ _ __
T1= α1α2α3 +α1α2α3 x4+α1α2α3 x4 x5+α1α2α3 x4 x5 = α1α2α3 +α1α2α3
___ _ _ ___ _ __
T2= α1α2α3 x1 +α1α2α3 x2 x3+α1α2α3 +α1α2α3 x4 x5
____ ___ ___ _ _ _ _ _ _ _ ___
T3= α1α2α3+α1α2α3 x1+α1α2α3 x1+α1α2α3 x2+α1α2α3 x2 x3+α1α2α3+α1α2α3 x4 x5=
___ _ _ _ _ _ ___ _
=α1α2+α1α2α3 x2+α1α2α3 x2 x3+α1α2α3 x4 x5+α1α3
1.8 Построение
логической схемы автомата Мили
Логическая схема автомата Мили представлена в приложении 1.
2.
Проектирование автомата Мура
2.1 Разметка
ГСА
Производим разметку заданной ГСА для автомата Мура:
Рис. 4. Разметка ГСА автомата Мура
2.2
Построение графа переходов-выходов
рис. 5. Граф переходов-выходов для автомата Мура
2.3 Составление
таблицы переходов-выходов
Таблица 6. Таблица переходов-выходов
функции выхода
|
|
y1
|
y2
|
y3
|
y4
|
y5
|
состояния
|
q0
|
q1
|
q2
|
q3
|
q4
|
q5
|
входные сигналы
|
|
|
|
|
|
|
1
|
q1
|
|
|
q4
|
|
q0
|
x1
|
|
q2
|
|
|
|
|
_x1
|
|
q5
|
|
|
|
|
x2
|
|
|
q3
|
|
|
|
_ x2
x3
|
|
|
q4
|
|
|
|
____x2
x3
|
|
|
q5
|
|
|
|
_ x4
|
|
|
|
|
q5
|
|
_ x4
x5
|
|
|
|
|
q5
|
|
x4 x5
|
|
2.4
Кодирование состояний автомата
Таблица 7. Кодирование состояний автомата Мура
Состояние
|
q0
|
q1
|
q2
|
q3
|
q4
|
q5
|
Код α1α2α3
|
000
|
001
|
010
|
011
|
100
|
101
|
2.5 Составление
структурной таблицы переходов-выходов
Таблица 8. Структурная таблица переходов-выходов
функции выхода
|
|
y1
|
y2
|
y3
|
y4
|
y5
|
состояния
|
000
|
001
|
010
|
011
|
100
|
101
|
входные сигналы
|
|
|
|
|
|
|
1
|
001
|
|
|
100
|
|
000
|
x1
|
|
010
|
|
|
|
|
_x1
|
|
101
|
|
|
|
|
x2
|
|
|
011
|
|
|
|
_ x2
x3
|
|
|
100
|
|
|
|
____x2
x3
|
|
|
101
|
|
|
|
_ x4
|
|
|
|
|
101
|
|
_ x4
x5
|
|
|
|
|
101
|
|
x4 x5
|
|
|
|
|
011
|
|
2.6 Построение
функций выхода автомата Мура
Функции выхода автомата Мура:
_ _ 1= α1α2α3
_ _2= α1α2α3
_ 3= α1α2α3
_ _4= α1α2α3
_5= α1α2α3
2.7 Построение
функций возбуждения автомата Мура на T-триггерах
Таблица 9. Таблица истинности T-триггера
состояние
|
входной сигнал
|
|
0
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
Таблица 10. Функции возбуждения автомата Мура на T-триггерах
функции выхода
|
|
y1
|
y3
|
y4
|
y5
|
состояния
|
000
|
001
|
010
|
011
|
100
|
101
|
входные сигналы
|
|
|
|
|
|
|
1
|
001
|
|
|
111
|
|
101
|
x1
|
|
011
|
|
|
|
|
_x1
|
|
100
|
|
|
|
|
x2
|
|
|
001
|
|
|
|
_ x2
x3
|
|
|
110
|
|
|
|
____x2
x3
|
|
|
111
|
|
|
|
_ x4
|
|
|
|
|
001
|
|
_ x4
x5
|
|
|
|
|
001
|
|
x4 x5
|
|
|
|
|
111
|
|
Таким образом, получаем входные сигналы для T-триггеров:
___ _ _ _ _ ___ _ _
T1= α1α2α3x1+α1α2α3x2+α1α2α3x4x5+α1α2α3+α1α2α3
___ _ ___ ___ _
T2= α1α2α3x1+α1α2α3x2+α1α2α3x4x5+α1α2α3
___ _ ___ _ _ ___ _ _ _
T3= α2α3+α1α2+α1α2α3x1+α1α2α3x2x3+α1α2α3+α1α2α3x2
2.8 Построение
логической схемы автомата Мура
Логическая схема автомата Мили представлена в приложении 2.
Заключение
Построение автоматов было произведено успешно, моделирование с помощью
компьютера показало правильную работу автоматов.
Автомат Мура, построенный по данной ГСА, имеет чуть меньше элементов, чем
автомат Мили, построенный по той же ГСА.
Таблица 10. Сравнительный анализ элементов автоматов
Логический элемент
|
Кол-во элементов в автомате
|
|
Мили
|
Мура
|
Элемент памяти (T)
|
3
|
3
|
Инвертор (НЕ)
|
5
|
3
|
Двухвходовой конъюнктор (И)
|
3
|
4
|
Трёхвходовой конъюнктор (И)
|
6
|
8
|
Четырехвходовой конъюнктор
(И)
|
5
|
4
|
Пятивходовой конъюнктор (И)
|
5
|
3
|
Двухвходовой дизъюнктор
(ИЛИ)
|
2
|
0
|
Четырехвходовой дизъюнктор
(ИЛИ)
|
2
|
1
|
1
|
1
|
Шестивходовой дизъюнктор
(ИЛИ)
|
0
|
1
|
Всего элементов
|
32
|
29
|
Список
литературы
1. Савельев
А.Я. Прикладная теория цифровых автоматов. - М. Высшая школа. 1987, 272 с.
2. Самофалов
К.Г. Прикладная теория цифровых автоматов. - К. Высшая школа. 1987, 375 с.
. Прикладная
теория цифровых автоматов. Часть 3. Логические основы и абстрактная теория
автоматов: Методические указания к лабораторным работам / Смирнов Г.Б. -
Екатеринбург, УГТУ, 1996, 32 с.
. Прикладная
теория цифровых автоматов. Часть 4. Проектирование цифровых автоматов с
памятью: Методические указания к лабораторным работам / Смирнов Г.Б. -
Екатеринбург, УГТУ, 1996, 28 с.
. Прикладная
теория цифровых автоматов. Часть 4. Построение и моделирование логических схем
в пакете "LCS":
Методические указания к лабораторным работам/ Смирнов Г.Б. - Екатеринбург.
Приложение 1
Схема автомата Мили:
Приложение 2
Схема автомата Мура: