Синтез цифрового автомата с памятью
Синтез
цифрового автомата с памятью
Оглавление
Задание на
курсовое проектирование
Основная
часть
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
Схема автомата Мура:
