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

Размещено на http://www.allbest.ru/

1

РОСОБРАЗОВАНИЕ

ГОУ ВПО «ПЕНЗЕНСКАЯ ГОСУДАРСТВЕННАЯ ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ»

Факультет «Институт промышленных технологий»

Кафедра «Вычислительные машины и системы»

Расчетно-пояснительная записка к курсовой работе

по дисциплине: Теория автоматов

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

Пенза 2011

Содержание

Введение

1. Анализ исходных данных

2. Разработка УА с жесткой логикой

2.1 Абстрактный синтез УА

2.2 Структурный синтез УА

3. Разработка УА с программируемой логикой

3.1 Преобразование ЛСА в ГСА

3.2 Структурная организация УА

3.3 Разработка таблицы прошивки ПЗУ

Заключение

Список литературы

Введение

По функциональному назначению основные устройства ЭВМ можно условно разделить на две категории:

· операционные устройства (ОУ);

· управляющие устройства (УУ).

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

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

Операционные автоматы реализуют действия над исходной информацией D с целью получения результатов R, то есть является исполнительной частью устройства (в соответствии с рисунком 1).



Рисунок 1. - Обобщённая структура операционного устройства

Управляющие автоматы используются не только в операционных устройствах вычислительной техники в системе УА - ОА, но и в разнообразных системах автоматики по управлению технологическими процессами и объектами, которые обобщённо можно назвать объектами управления (ОУ). В этом случае УА, в соответствии с алгоритмом функционирования ОУ и в зависимости от значений осведомительных сигналов о состоянии ОУ, поступающих от датчиков ОУ, и возможных внешних сигналов, вырабатывает и подаёт на исполнительные механизмы ОУ последовательность управляющих сигналов, обеспечивающих выполнение операций или процедур, предусмотренных целями управления. Для сложных систем управления, когда требуется выполнять большой объём работ по обработке информации о состоянии ОУ и выработки управляющих воздействий на ОУ в зависимости от целевой функции управления, в качестве УА могут выступать ЭВМ соответствующего класса [1].

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

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

б) для управления порядком следования микрокоманд используются логические условия (ЛУ), которые могут принимать значения 1 или 0. Множество ЛУ (осведомительных сигналов) обозначают символами, которые составляют входной структурный алфавит;

в) последовательность выполнения микрокоманд, определяемая функция перехода УА, записывается в виде алгоритма, представленного в терминах микроопераций и ЛУ и называемого микропрограммой. Микропрограмма определяет порядок проверки логических условий и следования микроопераций и используется как форма представления функции операционного устройства, на основании которой определяется структура и порядок функционирования устройства во времени [1].

1. Анализ исходных данных

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

где:

2. Выполнить преобразование ЛСА в графическую схему алгоритма (ГСА).

3. По ЛСА разработать УА с жесткой логикой, используя автомат Мили. Для построения памяти использовать JK - триггер.

4. По ГСА разработать таблицу прошивки ПЗУ для УА с программируемой логикой, с естественной адресацией микрокоманд.

2. Разработка УА с жёсткой логикой

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

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

Синтез УА с жёсткой логикой выполняется по заданной ЛСА. Для построения элементов памяти используется JK-триггер [1].

2.1 Абстрактный синтез УА

По заданной ЛСА построение таблицы переходов осуществляется по следующему алгоритму:

1) пронумеровать все операторные вершины ЛСА. Если в ЛСА имеются циклы из логических условий, то вводится пустой оператор, отмеченный входным сигналом.

2) Каждому оператору ЛСА поставить в соответствие вполне определённое

состояние автомата. Причём одинаковым операторам, стоящим в разных местах ЛСА, должны соответствовать разные состояния. Это обеспечивается сквозной нумерацией операторов ЛСА.

3) Каждому пути из логических условий от одного оператора к другому сопоставить конъюнкцию входных сигналов. В конъюнкцию логических переменных войдёт с отрицанием, если логическое условие истинно (тогда проверяется следующая по порядку записи логическая переменная, если она находится в строке), или без отрицания, если логическое условие ложно (тогда проверяется по стрелке, стоящей справа от , следующая логическая переменная, стоящая справа от конца стрелки ). Если в ЛСА имеется безусловный переход, то путь от исходного оператора до конечного в конце пути определится концом безусловного перехода.

4) Построить таблицу переходов автомата Мили. Для этого необходимо анализировать все полученные пути между операторами, учитывая, что каждый оператор отмечен совокупностью выходных сигналов [1].

Таблица 1. - Таблица переходов автомата Мили

Номер строки	Исходное состояние Si(t)	Частный входной сигнал Xij(t)	Состояние перехода Sj(t+1)	Выходной сигнал Yij(t)
1
2
3
4
5
6
7		1
8
9
10		1
11
12
13		1
14

Найдём 1-эквивалентные разбиения состояний автомата Мили.

На основе таблицы пар определяем эквивалентные разбиения состояний. Она строится непосредственно по таблице переходов. Первый столбец таблицы пар содержит все пары 1-эквивалентных состояний. Столбцы таблицы пар обозначаются входными сигналами. На пересечении строк и столбцов таблицы пар записываются пары состояний, являющиеся первоприемниками по отношению к конкретному входному сигналу. Таблица пар для автомата Мили представлена в таблице 2.

Таблица 2. ? Таблица пар для автомата Мили

Пары 1-эквивалентные состояния
0-1	2-2	1-1
6-13			7-7
7-10	2-2	14-14

В таблице пар последовательно по строкам отыскиваем пары состояний и , где , которые отсутствуют в первом основном столбце таблицы пар. Если в строке имеется хотя бы одна такая пара, то в этой строке зачеркивается пара в первом столбце. После этого в таблице пар отыскиваем строки, которые были вычеркнуты на предыдущем этапе. Такие пары не были найдены. Строки, не вычеркнутые в первом столбце, образуют пары эквивалентных состояний.

Каждому классу эквивалентного разбиения состояний присвоим произвольный соответствующий символ:

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

Таблица 3. - Минимальная таблица переходов автомата Мили

Номер строки	Исходное состояние Si(t)	Частный входной сигнал Xij(t)	Состояние перехода Sj(t+1)	Выходной сигнал Yij(t)
1
2
3
4
5
6		1
7
8
9		1
10
11		1

Далее записываются СКУ и СВФ:

СКУ:



СВФ:

2.2 Структурный синтез УА

управляющий автомат логика микрокоманда

На данном этапе строится логическая схема полученного ранее автомата Мили. Для этого используется канонический метод структурного синтеза, предложенный академиков В.М.Глушковым. Этот метод позволяет свести задачу синтеза схемы автомата к задаче синтеза комбинационной схемы. При этом предлагается представление схемы автомата в виде памяти и комбинационных схем (в соответствии с рисунком 2).

Рисунок 2. - Структура УА с жёсткой логикой

Вначале следует выполнить кодирование состояний автомата кодами минимальной длины:

.

Память данного автомата будет состоять из четырёх триггеров, которые будут служить для отображения состояния автомата. Каждое состояние будет кодироваться двоичным набором (код состояния автомата), компоненты которого - состояния триггеров Результаты кодирования состояний автомата поместим в карту Карно (в соответствии рисунком 3.2.2).

Рисунок 3. - Результаты кодирования состояний автомата Мили

Используя результаты кодирования, необходимо построить структурную таблицу переходов для автомата Мили. Для этого дополняем таблицу переходов автомата (таблица 3) кодами состояний автомата и, используя таблицу переходов JK-триггера (таблица 4).

Таблица 4. - Структурная таблица переходов автомата Мили

Исходное состояние	Частный входной сигнал Xij(t)	Состояние перехода	Сигналы возбуждения памяти
ai(t)	Q1	Q2	Q3	Q4		aj(t+1)	Q1	Q2	Q3	Q4	J1	J2 K2	J3 K3	J4 K4
a1	0	0	0	0			0	0	1	0			J3
							0	0	0	0
a2	0	0	1	0			0	0	1	1				J4
							0	1	1	0		J2
							1	1	1	0	J1	J2
							0	1	1	0		J2
							1	0	1	0	J1
							0	0	1	0
a3	0	0	1	1			0 0	1 1	0 0	0 1		J2 J2	K3 K3	K4
a4	0	1	0	0			0	1	1	1			J3	J4
							1	1	1	1	J1		J3	J4
							0	0	0	1		K2		J4
a5	0	1	1	1			0	1	0	1			K3
							0	1	1	1
a6	0	1	0	1	1		0	0	0	1		K2
a7	0	0	0	1			1	0	1	0	J1		J3	K4
							0	0	1	0			J3	K4
a8	0	1	1	0			1	1	1	1	J1			J4
							0	0	0	1		K2	K3	J4
a9	1	1	1	1	1		0	0	0	1	K1	K2	K3
a10	1	1	1	0			1	1	0	0			K3
							1	1	1	0
							0	1	1	0	K1
a11	1	1	0	0	1		0	1	0	1	K1			J4

По таблице строим СКУ функции возбуждения памяти:

=

=

=

=

=

=

=

=

Система выходных функций была получена ранее на этапе абстрактного синтеза.

Электрическая функциональная схема УА Мили построена с использованием СКУ функций возбуждения памяти и СВФ (Приложение А).

Также, для реализации в базисе И-НЕ опишем СВФ:

3. Разработка УА с программируемой логикой

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

Структурная схема УА с хранимой в памяти логикой показана на рисунке 4:

Рисунок 4. - Структурная схема УА с программируемой логикой

Для хранения микропрограмм используется блок управляющей памяти (УП), которая как правило строится на основе постоянного запоминающего устройства (ПЗУ). Регистр адреса микрокоманд (РА) хранит адрес микрокоманды, выполняемой в данном такте. Блок формирования адресов микрокоманд (БФА) является основным блоком автомата. Блок БФА после установки на РА начального адреса микрокоманды определяет все последующие адреса микрокоманд в соответствии с исходным алгоритмом управления. Регистр микрокоманд (РМК) включает в себя две основные части (поля МК): адресную (АЧ) и операционную (ОЧ). Генератор тактовых импульсов (ГТИ) определяет тактовую работу автомата.

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

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

3.1 Преобразование ЛСА в ГСА

Язык ГСА - графический язык, поэтому символы, применяемые в нём, имеют определённое геометрическое начертание, определяемое ГОСТом. ГСА - ориентированный связный граф, содержащий одну начальную, одну конечную и множество условных и операторных вершин.

ГСА удовлетворяет следующим условиям:

1. Входы и выходы вершин соединяются друг с другом с помощью дуг, направленных от выхода к входу;

2. Каждый выход соединён точно с одним входом;

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

4. Для любой вершины графа существует, по крайней мере, один путь из этой вершины к конечной вершине;

5. Один из выходов условной вершины может соединяться с её входом, что не допустимо для операторной вершины.

При соединении выхода условной вершины с её входом в цепь обратной связи вводится пустая операторная вершина, отмеченная пустым выходным сигналом .

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

3.2 Структурная организация УА

Структурная схема УА с хранимой в памяти логикой показана на рисунке 3.

Для хранения микропрограмм используется блок управляющей памяти (УП), которая в большинстве случаев строится на основе ПЗУ. Регистр адреса микрокоманд (РА) хранит адрес микрокоманды выполняемой в данном такте. Блок формирования адресов микрокоманд (БФА) является основным блоком автомата.

Размещено на http://www.allbest.ru/

1

Рисунок 5. - Структурная схема УА с хранимой в памяти логикой

Этот блок после установки на РА начального адреса микрокоманды определяет все последующие адреса микрокоманд в соответствии с исходным алгоритмом управления. Регистр микрокоманд (РМК) включает в себя две основные части (поля МК): адресную (АЧ) и операторную (ОЧ), Генератор тактовых импульсов (ГТИ) определяет такты работы автомата.

Для разработки микропрограммы (таблицы прошивки ПЗУ) будем использовать естественный способ адресации микрокоманд.

3.3 Разработка таблицы прошивки ПЗУ

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

При естественной адресации обычно используются микрокоманды двух типов: операционные и управляющие. Их структура представлена на рисунках 6 и 7.

0	Y1	Y2		0	П	X1	АП
0	1	5	6	11		0	1	2	5	6	11
Рисунок 6. - Структура операционной микрокоманды		Рисунок 7. - Структура управляющей микрокоманды

Операционная микрокоманда содержит только операционные поля, в которых задаются коды микроопераций, и неявно полагает адрес следующей микрокоманды равным А+1. Микрокоманда может содержать одно или несколько операционных полей. Число операционных полей влияет на быстродействие операционного устройства и на сложность УА.

Управляющая микрокоманда содержит поле для определения адреса перехода АП, поле для кодов логических условий Х и поле П. Поле П является признаком прямой или инверсной проверки логических условий (если П=1, то проверяется инверсное значение логического условия; если П=0, то прямое). Эта микрокоманда используется для изменения естественного порядка следования микрокоманд.

Для распознания операционных и управляющих команд в их кодах отводится один разряд под признак кода микрокоманды Р. Если Р=0, микрокоманда является операционной, если Р=1, то - управляющей.

Простейшая структура УА, работающего с рассмотренными микрокомандами, приведена на рисунке 8. Блок управляющей памяти представлен ПЗУ на 64 12 - разрядных слова. В качестве регистра адреса (РА) используется двоичный счетчик с возможностью параллельной записи информации. Пуск автомата осуществляется подачей сигнала РА:=0.

Размещено на http://www.allbest.ru/

1

Рисунок 8. - Схема УА с естественной адресацией микрокоманд

При составлении микропрограммы необходимо вначале ввести пустые операторные вершины, если в ГСА есть циклы из условных вершин. Кроме этого, если в ГСА есть операторные вершины, в которых записано более двух микроопераций, то они должны быть разбиты на последовательность вершин, так как операционная микрокоманда имеет только два поля. После этого необходимо пронумеровать все вершины ГСА. Граф - схема алгоритма по варианту представлена в приложении Б.

После всех преобразований по ГСА строится таблица прошивки ПЗУ с естественной адресацией микрокоманд (таблица 5).

Таблица 5. - Таблица прошивки ПЗУ с естественной адресацией

микрокоманд

Адрес слова ПЗУ	Микрокоманда	Номера вершин ГСА
	0	1	2	3	4	5	6	7	8	9	10	11
0	1	0	0	0	0	1	0	0	0	0	0	0	1	1
1	0	0	0	0	0	1	0	0	0	0	1	1		3
2	1	0	0	0	1	0	0	0	1	1	1	0		4
3	0	0	0	1	0	0	0	0	0	1	0	1		5
4	1	0	0	0	1	1	0	1	1	0	1	0		6
5	0	0	0	0	1	0	0	0	0	1	1	0		7
6	0	0	1	1	0	0	0	0	0	0	0	0		7'
7	1	0	0	1	0	1	0	1	0	0	0	0		8
8	0	0	0	1	0	0	0	0	0	1	1	1		9
9	1	0	0	1	0	0	0	0	1	0	0	0		10
10	0	0	1	0	0	0	0	0	0	0	0	0		11
11	0	0	0	0	1	1	0	0	1	0	0	1		12
12	1	1	0	0	0	1	0	0	0	0	0	1	13
13	1	0	0	0	0	0	0	1	1	1	0	0		БП на 14
14	1	0	0	0	1	1	0	1	0	1	0	0		15
15	0	0	1	0	0	0	0	0	1	0	1	0		16
16	1	0	0	1	0	0	0	1	0	0	1	0		17
17	0	0	0	1	0	0	0	0	0	1	1	1		18
18	0	0	1	0	1	1	0	0	0	0	0	0	19
19	1	0	0	0	0	0	0	0	1	1	0	0	БП на 13
20	1	0	0	1	1	0	0	0	1	1	0	0		20
21	1	0	0	1	1	1	0	0	1	1	1	1		21
22	0	0	1	0	0	0	0	0	1	0	1	0		22
23	1	0	0	1	0	0	0	1	0	1	0	1		23
24	0	0	0	0	1	0	0	0	0	1	1	0		24
25	0	0	1	1	0	0	0	0	0	0	0	0	24'
26	0	0	1	1	0	0	0	0	0	0	0	0	25
27	1	0	0	0	0	0	0	0	1	0	1	1	БП на 12
28	0	0	0	0	0	0	1	1	1	1	1	1	КОНЕЦ

Заключение

В ходе курсовой работы был синтезирован управляющий автомат Мили в соответствии с заданием:

· синтез УА с жёсткой логикой, который выполнялся в два этапа - абстрактного и структурного синтеза и построение электрической функциональной схемы;

· синтез УА с программируемой логикой, с естественной адресацией микрокоманд и построение таблицы прошивки ПЗУ, в которой размещается микропрограмма.

Из проделанной работы можно сделать следующие выводы:

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

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

Список литературы

1. Федосеева Л.И. Элементы теории цифровых автоматов: Учеб. пособие. - 2-е изд., перераб. и доп. - Пенза: Изд-во Пенз. гос. технол. акад., 2004. - 132 с.

2. Федосеева Л.И. Синтез управляющих автоматов. Методические указания. - Пенза: Изд-во Пенз. технол. ин-та, 2002. - 55 с.

3. ГОСТ 2.105-95 ЕСКД Общие требования к текстовым документам.

4. ГОСТ 2.743-91 ЕСКД Обозначения условные графические в схемах. Элементы цифровой техники. ? М.: Изд-во стандартов, 1993. - 61 с.

5. ГОСТ 19.701-90 ЕСПД Схемы алгоритмов, программ, данных и систем. Общие требования и правила оформления. - М.: Изд-во стандартов, 1991. - 25 с.

Размещено на Allbest.ru