Ж 85 Теория автоматов: методические указания к курсовой работе для специальности 230101/ И.В. Жукалина. - Оренбург: ГОУ ОГУ, 2009. – 29 с.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

 

Государственное образовательное учреждение

высшего профессионального образования

“Оренбургский государственный университет”

 

Кафедра вычислительной техники

 

 

И.В. ЖУКАЛИНА

 

 

ТЕОРИЯ АВТОМАТОВ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К КУРСОВОЙ РАБОТЕ ДЛЯ СПЕЦИАЛЬНОСТИ 230101

 

Рекомендовано к изданию Редакционно-издательским советом

государственного образовательного учреждения

высшего профессионального образования

“Оренбургского государственного университета”

 

 

Оренбург 2009

 

УДК 004.3(076.5)

ББК 32.97я73

Ж 85

 

 

Рецензент

доктор технических наук, ст. н. с. Т. З. Аралбаев

 

Жукалина, И.В.

Ж 85 Теория автоматов: методические указания к курсовой работе для специальности 230101/ И.В. Жукалина. - Оренбург: ГОУ ОГУ, 2009. – 29 с.

 

Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория автоматов» для студентов, обучающихся по специальности 230101.

 

 

ББК 32.97я73

 

© Жукалина И.В., 2009

© ГОУ ОГУ, 2009

 

 

 

 

Содержание

 

1 Задание и содержание курсовой работы..............................................................4

2 Общие сведения о цифровых автоматах ………………………………………...5

2.1 Модель В.М. Глушкова ……………………...………………………………… 5

2.2 Виды управляющих автоматов. Структуры автоматов Мили и Мура……….7

3 Методические указания по синтезу управляющего автомата с жесткой логикой …………………………………………………………………………......10

3.1 Абстрактный синтез управляющего автомата ……………………………….10

3.1.1 Получение отмеченной граф-схемы алгоритма……………………….……11

3.1.2 Построение графа функционирования автомата ……………..………....…12

3.1.3 Построение таблицы переходов-выходов...………………………………..12

3.2 Структурный синтез управляющего автомата ……………………………….14

3.2.1 Кодирование внутренних состояний ……………………………………….14

3.2.2 Формирование структурной таблицы автомата …………………………...15

3.2.3 Формирование функций возбуждения и выходов …………………………15

3.2.4 Построение функциональной схемы управляющего автомата …………...15

4 Пример синтеза управляющего автомата для заданного алгоритма ………....17

Список использованных источников.......................................................................27

Приложение А Пример оформления бланка задания на курсовую работу……..28

Приложение В Функциональная схема управляющего автомата Мура (Мили)..29

 

 

1 Задание и содержание курсовой работы

 

 

Согласно заданию спроектировать управляющий цифровой автомат по заданной содержательной граф-схеме алгоритма. Проанализировать различные варианты построения комбинационной схемы ЦА и выбрать наиболее оптимальный с точки зрения аппаратурных затрат. Для данного варианта построить функциональную схему ЦА. Дать оценку конструктивной сложности ЦА. Представить рекомендации по выбору элементной базы для реализации цифрового автомата.

Исходными данными являются:

1) содержательная граф-схема алгоритма функционирования управляющего автомата;

2) тип элементов памяти и логических элементов;

3) требования к схеме автомата по стоимости и быстродействию.

Результаты курсовой работы должны быть представлены в форме пояснительной записки и графической части, содержащей функциональную схему управляющего автомата.

Общие требования к оформлению пояснительной записки и графи­ческой части курсового проекта изложены в стандарте СТП 101-00. Условные обозначения элементов цифровой техники определяет ГОСТ 2.743-91.

 

Курсовая работа должна содержать следующие разделы:

Содержание

1 Постановка задачи

2 Синтез управляющего автомата Мура (Мили) 2.1 Содержательная граф-схема алгоритма цифрового автомата

2.2 Кодированная и отмеченная граф-схема алгоритма цифрового автомата

2.3 Построение графа-переходов цифрового автомата

2.4 Вычисление количества элементов памяти для цифрового автомата

2.5 Кодирование состояний цифрового автомата Мура (Мили)

2.6 Построение структурной таблицы цифрового автомата

2.7 Формирование и минимизация функций возбуждения элементов памяти и функций выходов

2.8 Составление таблицы покрытия конъюнкциями системы логических уравнений 2.9 Определение элементной базы и оценка конструктивной сложности и быстродействия схемы Список использованных источников Заключение

Приложение А Функциональная схема цифрового автомата Мура (Мили)

 

 

Общие сведения о цифровых автоматах

 

 

Модель В.М. Глушкова

Согласно модели академика В.М. Глушкова цифровой автомат (ЦА) как устройство для автоматической обработки цифровой информации по заданным алгоритмам представляет собой совокупность операционного автомата (ОА) и управляющего автомата (УА).

 

 

Рисунок 1 - Структура цифрового автомата

 

Операционный автомат служит для выполнения собственно набора требуемых операций алгоритма. Управляющий автомат задает последовательность действий по алгоритму в зависимости от условий (которые также формируются ОА как логические сигналы), т.е. координирует действия узлов ОА. Он выраба­тывает в некоторой временной последовательности управляющие сиг­налы, под действием которых в узлах ОА выполняются требуемые действия, например, установка регистра в некоторое состояние, инвертирование содержимого разрядов регистра, пересылка содержимого одного узла в другой, сдвиг содержимого узла влево, вправо, счет, при котором число в счетчике (регистре) возрастает или убывает на единицу, сложение и т. д.

Работа автомата разбивается на такты (дискретные интервалы времени). Каждое такое элементарное действие, выполняемое в одном из узлов ОА в течение одного тактового периода, называется микрооперацией.

Совокупность микроопераций, которые могут выполняться в ОА параллельно в одном такте, называется микрокомандой. Последовательность микрокоманд, реализующих алгоритм, называется микропрограммой.

Таким образом, если в ОА предусматривается возможность исполнения n различных микроопераций, то из УА выходят n управляющих цепей, каждая из которых соответствует определенной микрооперации. И если необходимо в ОА выполнить некоторую микрооперацию, доста­точно из УА по определенной управляющей цепи, соответствующей этой микрооперации, подать сигнал (например, напряжение уровня лог.1). В силу того, что УА определяет микропрограмму, т.е. какие и в какой временной последова­тельности должны выполняться микрооперации, он получил назва­ние микропрограммного автомата.

Формирование управляющих сигналов y₁, y₂…..y_n для выпол­нения микрокоманд может происходить в зависимости от состояния узлов ОА, определяемого сигналами х₁, x₂, ..., х_s, которые подаются с соответствующих выходов ОА на входы УА. Управляющие сигналы y₁, y₂…..y_n могут также зависеть от внешних сигналов x_s+1, …., x_L.

Для сокращения числа управляющих цепей, выходящих из УА (в тех случаях, когда оно конструктивно выполняется отдельно от операционного), микрокоманды могут кодироваться.

Результаты обработки, вы­полненной в ОА, снимаются с его выходов z₁, z₂, …z_m.

 

 

 

Рисунок 2 – Композиция операционного и управляющего автоматов

 

Таким образом, УА предназначен для выдачи управляющих сигналов в каждом такте работы ЦА, инициирующих выполнение определенных микроопераций (или микрокоманд) в ОА в соответствии с выполняемым алгоритмом и в зависимости от поступающих на входы УА информационных сигналов (условий). Фактически УА реализует последовательность действий по алгоритму, при этом содержание этих действий зависит от управляемого объекта, в данном случае – от ОА. Если ОА " знает как" делать, то УА " знает, что и когда", то есть в какой последовательности что делать. При этом для УА " что делать" – это просто коды команд, про их содержание он не знает.

 

Пример синтеза управляющего автомата для заданного алгоритма

 

По заданной содержательной схеме алгоритма в микрооперациях разработать функциональную схему управляющего автомата Мура (Мили) (рисунок 9), в качестве элементов памяти использовать D-триггеры, комбинационную схему реализовать на логических элементах. Дать оценку конструктивной сложности ЦА.

 

 

 

 

Рисунок 9 – Схема алгоритма в микрооперациях

 

1) Заменим наборы микроопераций О1, О2, О3, О4 на коды микрокоманд Y1, Y2, Y3, Y4. В результате получим кодированную ГСА в микрокомандах.

2) Построим отмеченную граф-схему алгоритма (ГСА) управляющего автомата Мура (Мили)

В соответствии с требованиями предъявляемыми к разметке состояний цифрового автомата Мура (Мили) получаем отмеченную ГСА цифрового автомата (рисунок 10, а), б)).

 

 

а) б)

 

а - для автомата Мура,

б - для автомата Мили.

 

Рисунок 10 – Отмеченные граф-схемы

 

3) Построение графа функционирования автомата

Согласно отмеченной граф-схеме алгоритма управляющего автомата Мура (Мили) строим граф функционирования автомата (рисунок 11, а), б)).

 

 

а)

 

 

б)

а - для автомата Мура,

б - для автомата Мили.

 

Рисунок 11 – Графы функционирования автоматов

4) Кодирование состояний устройства

Число разрядов кода состояния соответствует числу элементов памяти и определяется по формуле: k = ù log₂ S é , где

k – число разрядов (число элементов памяти)

S – число внутренних состояний;

ù é - округление в большую сторону.

В нашем случае для автомата Мура число состояний S = 6. Количество разрядов кода состояния (число элементов памяти): K = ]log₂S[ = ]log₂6[ = 3.

Для автомата Мили число состояний S = 5. Количество разрядов кода состояния (число элементов памяти): k = ]log₂S[ = ]log₂5[ = 3.

Таблицы кодировки состояний для автомата Мура и автомата Мили приведены на рисунке 12, а) и б) соответственно.

 

 

Состояние	Код состояния
S0
S1
S2
S3
S4
S5

Состояние	Код состояния
S0
S1
S2
S3
S4

 

а) б)

 

а - для автомата Мура,

б - для автомата Мили.

 

Рисунок 12 - Таблицы кодировки состояний

 

 

5) Построение структурной таблицы автомата

По отмеченной ГСА или графу функционирования автомата, таблицы кодировки состояний автомата и таблицы переходов триггеров строим структурную таблицу автомата.

 

Таблица 2 – Таблица переходов D-триггера

Q(t)®Q(t+1)	D
0 → 0
0 → 1
1 → 0
1 → 1

 

 

Таблица 3 – Структурная таблица автомата Мура

 

Исходное состояние

Усло-вия пере-хода

Последующее состояние

Функции возбуждения

Выходные функции

метка

код

метка

код

Q1

Q2

Q3

Q1

Q2

Q3

D1

D2

D3

Y1

Y2

Y3

Y4

S0

–

S1

S1

–

S2

S2

S3

S5

S3

S4

S5

S4

–

S5

S5

–

S­0

 

 

Таблица 4 - Структурная таблица автомата Мили

 

Исходное состояние

Условия перехода

Последующее состояние

Выходные функции

Функции возбуждения

метка

код

метка

код

Q1

Q2

Q3

Q1

Q2

Q3

D1

D2

D3

S0

–

S1

Y1, Y2, Y3

S1

–

S2

Y2, Y3

S2

S3

Y1, Y2

S4

–

S3

S4

Y1, Y2, Y3

–

S4

–

S0

Y2, Y3, Y4

 

6) Минимизация функций возбуждения элементов памяти и функций выходов

Из структурной таблицы автомата Мура (Мили) получаем систему логических уравнений для цифрового автомата Мура (Мили).

 

Система логических уравнений для цифрового автомата Мура:

 

 

 

Система логических уравнений для цифрового автомата Мили:

 

Из системы логических уравнений для цифрового автомата Мура получаем полное множество конъюнкций для данного автомата:

 

 

 

Из системы логических уравнений для цифрового автомата Мили получаем полное множество конъюнкций для данного автомата:

 

 

 

Из полного множества конъюнкций получаем таблицу покрытия конъюнкциями системы логических уравнений.

 

Таблица 5 - Таблица покрытия конъюнкциями для цифрового автомата Мура

K1

K2

K3

K4

K5

K6

K7

K8

K9

K10

K11

K12

D1

+

+

+

D2

+

+

D3

+

+

+

Y1

+

+

Y2

+

+

+

Y3

+

+

+

Y4

+

 

 

Таблица 6 - Таблица покрытия конъюнкциями для цифрового автомата Мили

 

	K1	K2	K3	K4	K5	K6	K7	K8	K9
D1	+	+
D2			+	+
D3				+	+
Y1				+	+	+
Y2			+	+		+	+
Y3						+		+	+
Y4									+

 

 

7) Построение функциональной схемы управляющего автомата Мура (Мили)

На основе полученных функций возбуждения и функций выходов строим функциональную схему управляющего автомата Мура (Мили).

 

Рисунок 13 - Функциональная схема управляющего автомата Мура

 

 

 

 

Рисунок 14 - Функциональная схема управляющего автомата Мили

 

8) Оценка конструктивной сложности управляющего автомата Мура (Мили):

- определение конструктивной сложности автомата Мура методом Квайна - число входов логических элементов: 59.

- число ярусов сигнала на самом длинном пути от входа к выходу: 4.

- количество элементов необходимых для построения функциональной схемы:

 

Таблица 7 – Оборудование для реализации автомата Мура

 

Автомат	Логические элементы	на 2 входа	на 3 входа	на 4 входа	D -триггеров	Всего элементов
Мура	И
ИЛИ
И-НЕ

 

- определение конструктивной сложности автомата Мили методом Квайна - число входов логических элементов: 51.

- число ярусов сигнала на самом длинном пути от входа к выходу: 4.

- количество логических элементов необходимых для построения функциональной схемы:

 

Таблица 8 – Оборудование для реализации автомата Мили

 

Автомат	Логические элементы	на 2 входа	на 3 входа	на 4 входа	D -триггеров	Всего элементов
Мили	И
ИЛИ
И-НЕ

 

Приложение А

(обязательное)

Пример оформления бланка задания на курсовую работу

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

 

Факультет информационных технологий

 

Кафедра вычислительной техники

 

 

Задание на курсовую работу

 

Синтез управляющего автомата

 

 

Исходные данные: Граф- схема алгоритма функционирования управляющего автомата;

тип автомата: автомат Мура (Мили);

тип элемента памяти: D (Т, RS, JK) – триггер.

 

Разработать: Функциональную схему управляющего автомата по заданной граф – схеме алгоритма, используя в качестве элементов памяти D (Т, RS, JK) – триггеры, комбинационную схему реализовать на логических элементах.

 

Дата выдачи задания " ____" _____________200__г.

 

Руководитель Петров А.Б.

 

Исполнитель

студент группы 07ВМК1 Иванов Д.И.

 

Срок защиты проекта " ____ " ____________200__г.

Приложение Б

(справочное)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

 

Государственное образовательное учреждение

высшего профессионального образования

“Оренбургский государственный университет”

 

Кафедра вычислительной техники

 

 

И.В. ЖУКАЛИНА

 

 

ТЕОРИЯ АВТОМАТОВ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К КУРСОВОЙ РАБОТЕ ДЛЯ СПЕЦИАЛЬНОСТИ 230101

 

Рекомендовано к изданию Редакционно-издательским советом

государственного образовательного учреждения

высшего профессионального образования

“Оренбургского государственного университета”

 

 

Оренбург 2009

 

УДК 004.3(076.5)

ББК 32.97я73

Ж 85

 

 

Рецензент

доктор технических наук, ст. н. с. Т. З. Аралбаев

 

Жукалина, И.В.

Ж 85 Теория автоматов: методические указания к курсовой работе для специальности 230101/ И.В. Жукалина. - Оренбург: ГОУ ОГУ, 2009. – 29 с.

 

Методические указания предназначены для выполнения курсовой работы по дисциплине «Теория автоматов» для студентов, обучающихся по специальности 230101.

 

 

ББК 32.97я73

 

© Жукалина И.В., 2009

© ГОУ ОГУ, 2009

 

 

 

 

Содержание

 

1 Задание и содержание курсовой работы..............................................................4

2 Общие сведения о цифровых автоматах ………………………………………...5

2.1 Модель В.М. Глушкова ……………………...………………………………… 5

2.2 Виды управляющих автоматов. Структуры автоматов Мили и Мура……….7

3 Методические указания по синтезу управляющего автомата с жесткой логикой …………………………………………………………………………......10

3.1 Абстрактный синтез управляющего автомата ……………………………….10

3.1.1 Получение отмеченной граф-схемы алгоритма……………………….……11

3.1.2 Построение графа функционирования автомата ……………..………....…12

3.1.3 Построение таблицы переходов-выходов...………………………………..12

3.2 Структурный синтез управляющего автомата ……………………………….14

3.2.1 Кодирование внутренних состояний ……………………………………….14

3.2.2 Формирование структурной таблицы автомата …………………………...15

3.2.3 Формирование функций возбуждения и выходов …………………………15

3.2.4 Построение функциональной схемы управляющего автомата …………...15

4 Пример синтеза управляющего автомата для заданного алгоритма ………....17

Список использованных источников.......................................................................27

Приложение А Пример оформления бланка задания на курсовую работу……..28

Приложение В Функциональная схема управляющего автомата Мура (Мили)..29

 

 

1 Задание и содержание курсовой работы

 

 

Согласно заданию спроектировать управляющий цифровой автомат по заданной содержательной граф-схеме алгоритма. Проанализировать различные варианты построения комбинационной схемы ЦА и выбрать наиболее оптимальный с точки зрения аппаратурных затрат. Для данного варианта построить функциональную схему ЦА. Дать оценку конструктивной сложности ЦА. Представить рекомендации по выбору элементной базы для реализации цифрового автомата.

Исходными данными являются:

1) содержательная граф-схема алгоритма функционирования управляющего автомата;

2) тип элементов памяти и логических элементов;

3) требования к схеме автомата по стоимости и быстродействию.

Результаты курсовой работы должны быть представлены в форме пояснительной записки и графической части, содержащей функциональную схему управляющего автомата.

Общие требования к оформлению пояснительной записки и графи­ческой части курсового проекта изложены в стандарте СТП 101-00. Условные обозначения элементов цифровой техники определяет ГОСТ 2.743-91.

 

Курсовая работа должна содержать следующие разделы:

Содержание

1 Постановка задачи

2 Синтез управляющего автомата Мура (Мили) 2.1 Содержательная граф-схема алгоритма цифрового автомата

2.2 Кодированная и отмеченная граф-схема алгоритма цифрового автомата

2.3 Построение графа-переходов цифрового автомата

2.4 Вычисление количества элементов памяти для цифрового автомата

2.5 Кодирование состояний цифрового автомата Мура (Мили)

2.6 Построение структурной таблицы цифрового автомата

2.7 Формирование и минимизация функций возбуждения элементов памяти и функций выходов

2.8 Составление таблицы покрытия конъюнкциями системы логических уравнений 2.9 Определение элементной базы и оценка конструктивной сложности и быстродействия схемы Список использованных источников Заключение

Приложение А Функциональная схема цифрового автомата Мура (Мили)

 

 

1234	Поделиться:

Популярное:

1. Dermal mask, Коллагеновая тканевая маска для лица, 23гр -
2. I. Его руки подняты для благословения.
3. I. Смотрите на Него, приготовляющего для Себя престол.
4. I. ТИТУЛ «ИНТЕРНАЦИОНАЛЬНЫЙ ЧЕМПИОН ПО КРАСОТЕ» (C.I.B.) ДЛЯ ПОРОД С ОБЯЗАТЕЛЬНЫМИ И НЕОБЯЗАТЕЛЬНЫМИ РАБОЧИМИ ИСПЫТАНИЯМИ СОГЛАСНО НОМЕНКЛАТУРЕ FCI.
5. II. БИХЕВИОРИЗМ И ТЕОРИЯ СРЕДЫ
6. II. Извлеки урок для совести.
7. II. ТЕКСТЫ ДЛЯ РАБОТЫ НАД ГОЛОСОМ.
8. III. БАЗИСНЫЕ РАЗДЕЛЫ ДЛЯ ПОВТОРЕНИЯ
9. III. Реакции, характерные только для альдегидов
10. IX. Разработка тезисов доклада для защиты
11. S: Для пролонгирования действий анестетика используют
12. V. «Умственный мусор»: пища для страждущих