Синтез синхронного управляющего автомата (стр. 1 из 7)

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

МЕЖДУНАРОДНЫЙ ИНСТИТУТ КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ И ЭНЕРГЕТИЧЕСКИХ СИСТЕМ

КАФЕДРА вычислительные машины, системы, комплексы и сети

КУРСОВОЙ ПРОЕКТ

по дисциплине " ТЕОРИЯ АВТОМАТОВ"

ТЕМА: "Синтез синхронного управляющего автомата"

Расчетно – пояснительная записка

Разработал студент гр. ВМо-072 / Н.А.Волокитина /

^{подпись, дата инициалы, фамилия}

Руководитель / C.H. Плотников /

^{подпись, дата инициалы, фамилия}

Нормоконтролер / /

^{подпись, дата инициалы, фамилия}

Защищен ________________ Оценка ___________________

^дата

ВОРОНЕЖ 2010

МЕЖДУНАРОДНЫЙ ИНСТИТУТ КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ

ФАКУЛЬТЕТ ИНФОРМАЦИОННЫХ И ЭНЕРГЕТИЧЕСКИХ СИСТЕМ

КАФЕДРА информатики и вычислительной техники

ЗАДАНИЕ

на курсовой проект

по дисциплине " ТЕОРИЯ АВТОМАТОВ"

Тема проекта: "Синтез синхронного управляющего автомата"

Студент группы ВМо-072 Волокитина Надежда Александровна

^{фамилия, имя, отчество}

Номер варианта___9 – 2.14 ____________________________________

Технические условия: тип управляющего автомата – Мура; способ кодирования внутренних состояний автомата –эффективный 2 способ; тип триггерных схем – комбинированные синхронные двухтактные RS - триггеры; элементная база логического преобразователя – двухуровневая программируемая логическая матрица; количество входных сигналов УА – 6; количество выходных сигналов (микроопераций) УА – 7; количество микрокоманд УА – 10; количество микроопераций в каждой микрокоманде – 2..5; количество операторных вершин ГСА – 13; количество условных вершин ГСА – 8; разновидность УА – инициальный.

Содержание и объем проекта

расчетно - пояснительная записка – страниц формата А4, поясняющие текст, рисунки, расчеты, таблицы, схема электрическая функциональная УА.

_

Задание принял студент гр. ВМо-072 / Н.А.Волокитина /

^{подпись, дата инициалы, фамилия}

Руководитель / C.H. Плотников /

^{подпись, дата инициалы, фамилия}

Замечания руководителя.

Содержание

ОСновная часть……………………………………………………………...….6

1. Основные особенности теории синхронных автоматов…….………..….…6

2. Общие принципы построения и реализации синхронных

управляющих автоматов………………………………………..…..……...7

2.1 Обобщённая структура и принцип функционирования

синхронных управляющих автоматов.……………….…..……..…........7

2.2 Последовательность синтеза синхронных управляющих

автоматов………………………………………………………..…..…….8

2.3 Начальная формализация задачи синтеза УА……………..……….…9

3. Исходные данные для курсового проектирования…………….…..…......11

4. Автоматное описание управляющего автомата………………..…..……..12

5. Анализ граф _- схемы алгоритма синтезируемого управляющего

автомата и детализация его структурной схемы. Исходные данные

для курсового проектирования………………………….…..………..…......14

5.1 Анализ и разметка граф-схемы алгоритма…………..……..………..14

5.2 Описание управляющего автомата с помощью таблиц переходов

и выходов. …………………………………………….……………….15

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

реализацией логики управления. ………………..………….…………....16

6.1 Тип элементов памяти. ………….…..…………………..…………...16

6.2 Структурное кодирование входных, выходных сигналов и

состояний автомата. ………….…..………..……………..…………..17

6.3 Детализация блока памяти…………………………………………...19

6.4 Составление расширенной структурной таблицы

переходов и выходов………………………………………………...20

6.5. Составление логических уравнений для выходных сигналов и

функций возбуждения блока памяти ……………………………....21

6.6 Минимизация логических функций возбуждения и выходов….….22

7. Разработка и оформление схемы электрической функциональной

синтезированного синхронного управляющего автомата…………………23

ЗАКЛЮЧЕНИЕ……………………………………………………….……….……25

Литература………………………………………………………….………….26

1. Основные особенности теории синхронных автоматов

Математической моделью дискретного устройства является абстрактный автомат, определяемый как шестикомпонентный кортеж, или вектор [4 - 11]:

S = (Z, A ,W, δ, λ, a₁), (1)

у которого:

Z={z₁,…z_f…z_F} - множество входных сигналов автомата (входной алфавит);

A={a₁,…a_m…a_M} - множество состояний автомата (алфавит состояний);

W={w₁,…w_g…w_G} – множество выходных сигналов автомата (выходной алфавит);

δ : A х Z ® A – функция переходов автомата, реализующая отображение D_δ

A х Z на A.

Другими словами, функция δ некоторым парам состояние - входной сигнал (a_m, z_f) ставит в соответствие состояние автомата a_s = δ (a_m, z_f), a_s

A;

λ : A х Z ® W – функция выходов, реализующая отображение D_

A х Z на W, которая некоторым парам состояние - входной сигнал (a_m, z_f) ставит в соответствие выходной сигнал автомата w_g = λ (a_m, z_f);

a₁

A – начальное состояния автомата.

Под алфавитом здесь понимается непустое множество попарно различных символов. Элементы алфавита называются буквами, а конечная упорядоченная последовательность букв - словом в данном алфавите.

Абстрактный автомат имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,… В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент времени t(0) автомат может находиться в начальном состоянии a(0) = a₁. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита z(t)

Z. В соответствии с функцией выходов он выдает в тот же момент времени t букву выходного алфавита w(t) = λ (a(t)_, z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t +1)=δ (a(t)_, z(t)), причем a(t +1) A, а w(t) W. Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z в множество слов выходного алфавита W. Иначе, если на вход автомата, установленного в начальное состояние a₁, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1), z(2), … - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1), w(2), … - выходное слово. Каждому входному слову соответствует определенное выходное слово, структура которого определяется функциями переходов и выходов.

Таким образом, на уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные слова. Структурной моделью нулевого уровня абстрактного автомата является модель, представленная на рис. 1.

Z W

Рис. 1 Структурная модель абстрактного автомата

(нулевой уровень)

Чтобы задать конечный автомат S, необходимо описать все компоненты вектора S = (Z, A ,W, δ, λ, a₁), т.е. входной и выходной алфавиты и алфавит состояний, а также функции переходов и выходов. Среди множества состояний может быть выделено начальное состояния автомата a₁, в котором автомат находится в момент t = 0.

По способу организации автоматного времени все автоматы делят на два больших класса: синхронные автоматы и асинхронные автоматы. Для синхронных автоматов моменты времени, в которых фиксируются изменения состояния автомата, задаются специальным устройством - генератором синхронизирующих сигналов (синхросигналов). Генератор формирует синхронизирующие сигналы через определенные промежутки времени, длительность которых может быть постоянной или переменной. В асинхронных автоматах моменты перехода автомата из одного состояния в другое заранее не определены, так как их продолжительность целиком определяется временем переходных процессов, происходящих в автомате.

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