WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 |
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования “Оренбургский государственный университет” Кафедра вычислительной техники И.В. ЖУКАЛИНА ТЕОРИЯ АВТОМАТОВ МЕТОДИЧЕСКИЕ УКАЗАНИЯ К КУРСОВОМУ ПРОЕКТУ ДЛЯ СПЕЦИАЛЬНОСТИ 230101 Рекомендовано к изданию Редакционно-издательским советом государственного образовательного учреждения высшего профессионального образования “Оренбургского государственного университета” Оренбург 2008 УДК ББК А Рецензент доктор технических наук, профессор А.М. Пищухин И.В. Жукалина Теория автоматов: методические указания к курсовому проекту для специальности 230101 / И.В. Жукалина. - Оренбург:

ГОУ ОГУ, 2008. – 29 с.

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

ББК © Жукалина И.В., 2008 © ГОУ ОГУ, 2008 2 Содержание 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 Построение функциональной схемы управляющего автомата …………...4 Пример синтеза управляющего автомата для заданного алгоритма ………....Список использованных источников.......................................................................Приложение А Пример оформления бланка задания на курсовой проект ……..Приложение В Функциональная схема управляющего автомата Мура (Мили).. 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 Определение элементной базы и оценка конструктивной сложности и быстродействия схемы Список использованных источников Заключение ПРИЛОЖЕНИЕ А Функциональная схема цифрового автомата Мура (Мили) 2 Общие сведения о цифровых автоматах 2.1 Модель В.М. Глушкова Согласно модели академика В.М. Глушкова цифровой автомат (ЦА) как устройство для автоматической обработки цифровой информации по заданным алгоритмам представляет собой совокупность операционного автомата (ОА) и управляющего автомата (УА).

Входные Выходные данные данные ОА Набор Набор управляющих осведомительных сигналов (Y) сигналов (Х) УА Код операции Рисунок 1 - Структура цифрового автомата Операционный автомат служит для выполнения собственно набора требуемых операций алгоритма. Управляющий автомат задает последовательность действий по алгоритму в зависимости от условий (которые также формируются ОА как логические сигналы), т.е. координирует действия узлов ОА. Он вырабатывает в некоторой временной последовательности управляющие сигналы, под действием которых в узлах ОА выполняются требуемые действия, например, установка регистра в некоторое состояние, инвертирование содержимого разрядов регистра, пересылка содержимого одного узла в другой, сдвиг содержимого узла влево, вправо, счет, при котором число в счетчике (регистре) возрастает или убывает на единицу, сложение и т.

д.

Работа автомата разбивается на такты (дискретные интервалы времени).

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



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

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

Формирование управляющих сигналов y1, y2…..yn для выполнения микрокоманд может происходить в зависимости от состояния узлов ОА, определяемого сигналами х1, x2,..., хs, которые подаются с соответствующих выходов ОА на входы УА. Управляющие сигналы y1, y2…..yn могут также зависеть от внешних сигналов xs+1, …., xL.

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

Результаты обработки, выполненной в ОА, снимаются с его выходов z1, z2, …zm.

Вход данных.........

X Y.

Y.

{. Управляющий Операционный.

.

XS+1 автомат автомат }.

.

.

XL Yn XS Синхросигнал Z1 Z2 Zm..........

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

2.2 Виды управляющих автоматов. Структуры автоматов Мили и Мура Существует два принципиально разных подхода к проектированию микропрограммного автомата (управляющего автомата): использование принципа схемной логики (автоматы с жесткой логикой УАЖЛ) и использование принципа программируемой логики (УАПЛ).

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

Устройства, основанные на таком принципе схемной логики, способны обеспечивать наивысшее быстродействие при заданном типе технологии элементов. Недостаток этого принципа построения автомата состоит в трудности использования БИС и СБИС. Это связано с тем, что при использовании схемного принципа каждый разрабатываемый автомат окажется индивидуальным по схемному построению и потребует изготовления индивидуального типа БИС.

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

Следует, однако, иметь в виду, что наивысшее быстродействие достигается в ЦА, в которых УА строится с использованием принципа схемной логики, а ОА выполняется в виде устройства, специализированного для решения конкретной задачи.

Автоматы с жесткой логикой строятся на базе памяти состояний, которая обычно реализуется совокупностью триггеров, и комбинационной схемы, которая управляет переключением триггеров (то есть - сменой состояний) и формированием выходных (управляющих) сигналов ym в зависимости от входных сигналов хn и текущего состояния Ql. Код текущего состояния хранится в триггерах. Схема жестко реализует закон функционирования автомата, откуда следует название автоматов данной группы.

X1 QЭлементы Комбинационный..

памяти.

Xn узел Ql Y1...... Ym Рисунок 3 - Структурная схема управляющего автомата с жесткой логикой Для построения обоих типов автоматов, но прежде всего, УАЖЛ, используется теория абстрактных конечных автоматов (КА). Для построения используется две базовые модели КА, функционально аналогичные: автомат Мура и автомат Мили.

Любой ЦА описывается следующем кортежем: М = {X, Y, S,,, s0}, где X, Y, S – соответственно множества входных, выходных значений ЦА и внутренних состояний.

X = {x1, x2, x3, …..xn} Y = {y1, y2, y3, …..ym} S = {s1, s2, s3, ……sk} где m, n, k – конечные значения.





Если m, n, k конечны, то автомат называют конечным.

Состояние ЦА определяется состоянием элементов памяти, – соответственно характеристические функции перехода из одного состояния в другое () и функция выхода ЦА (). s0 – начальное состояние ЦА.

По закону функционирования или по виду выходной функции ЦА делятся на: автоматы 1-го рода (автоматы Мили) и автоматы 2-го рода (автоматы Мура).

Закон функционирования ЦА первого рода (автомата Мили) есть:

s (t)= (s (t-1), x (t)), y (t)= (s (t-1), x (t)), где s (t) - состояние автомата в настоящий момент;

s (t-1)- состояние автомата в предыдущий момент. Если t=0, то s(t-1)=s0;

x (t) - входной сигнал в текущий момент;

- оператор формирования данного состояния s;

- оператор формирования данного выходного сигнала y.

Т.е., закон функционирования представляет собой совокупность двух функций: функции перехода и функции выхода, а также, что данное состояние s (t) зависит от предыдущего состояния s (t-1) и входного сигнала в данный момент времени, что выходной сигнал в данный момент времени так же определяется предыдущим состоянием и входным сигналом в данный момент времени.

Функция выхода ЦА 2-го рода отличается от такой функции ЦА 1-го рода тем, что используется состояние в данный момент времени s (t). Таким образом, закон функционирования ЦА 2-го рода есть:

S (t) = (s (t-1), x (t)), y (t) = (s (t), x (t)).

У ЦА Мили выходной сигнал имеется только тогда, когда есть входной сигнал, а у ЦА Мура выходной сигнал имеется всегда.

Структурные схемы автомата Мили и автомата Мура изображены на рисунке 4 а) и б) соответственно.

а) б) Рисунок 4 - Структурные схемы автомата Мили (а) и автомата Мура (б) 3 Методические указания по синтезу управляющего автомата с жесткой логикой При синтезе управляющего автомата с жесткой логикой выделяются этапы абстрактного и структурного синтеза.

На этапе абстрактного синтеза по алгоритму, заданному на начальном языке строится таблица переходов, записываются системы канонических уравнений (СКУ) и системы выходных функций.

На этапе структурного синтеза строится логическая схема управляющего автомата.

3.1 Абстрактный синтез управляющего автомата Функция управляющего автомата задатся кодированной граф-схемой алгоритма (ГСА) микропрограммы. Кодированную ГСА (рисунок 5, б)) получают путм замены в содержательной ГСА (рисунок 5,а) микрооператоров (наборов совместимых микроопераций) на коды микрокоманд, а логических условий на их идентификаторы.

а) б) Рисунок 5 - Фрагмент содержательной (а) и кодированной (б) ГСА микропрограммы 3.1.1 Получение отмеченной ГСА Абстрактный синтез управляющего автомата начинается с отметки внутренних состояний кодированной ГСА. Отметка состояний должна соответствовать закону функционирования автомата Мура или Мили, то есть выполняется для них различным образом.

Будем полагать, что автомат начинает работу с состояния s0, в котором он не вырабатывает никаких выходных сигналов и после выполнения микропрограммы снова оказывается в этом же состоянии. Затем автомат переходит в состояния, предписанные законом функционирования, и формирует микрокоманды y, соответствующие текущим значениям сигналов x.

Момент окончания выполнения микропрограммы отмечается возвратом автомата в начальное состояние s0.

Поскольку в автомате Мура выходные сигналы связаны только с состоянием автомата, то каждой операторной вершине нужно поставить в соответствие одно из состояний автомата. Правило отметки состояний автомата на ГСА микропрограммы будет выглядеть следующим образом:

- символом s0 отмечаются начальная и конечная вершины ГСА;

- каждая операторная вершина отмечается единственным символом s1, s2, s3, s4, s5,...;

- две различные операторные вершины не могут быть отмечены одинаковыми символами.

На рисунке 6, а) представлена ГСА, отмеченная по приведенному выше правилу. В каждом такте автомат Мура, интерпретирующий данную микропрограмму, переходит из одного состояния в другое и выдат соответствующие выходные управляющие сигналы yi. Порядок выдачи выходных сигналов yi определяется значениями входных сигналов xi. Так, при наличии входного сигнала х1 = 0 автомат из состояния s0 перейдет в состояние s1 и выдаст выходной сигнал у1. В следующем такте работы под воздействием входного сигнала х2 = 1 автомат из состояния s1 перейдт в состояние s3 с выдачей выходных сигналов у2 и у3.

Если для интерпретации закодированной ГСА используется автомат Мили, то отметка граф-схемы производится в следующем порядке:

- символом s0 отмечается выход начальной и вход конечной вершины;

- символами s1, s2,... отмечаются входы вершин, следующие за операторными вершинами;

- входы двух различных вершин не могут быть отмечены одинаковыми символами;

- входы вершины могут отмечаться только одним символом состояния.

Приведенные правила означают, что если вершина имеет несколько входов, то символом состояния отмечается их подмножество, состоящее из входов, следующих только за начальной или за операторными вершинами.

Если один из входов конечной вершины соединен с выходом операторной вершины, то между ними необходимо ввести пустую операторную вершину, иначе автоматы Мура и Мили, построенные по одной ГСА не будут эквивалентными.

На рисунке 6, б) представлена ГСА, отмеченные по приведнному выше правилу.

Pages:     || 2 | 3 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.