bigpo.ru
добавить свой файл
1


ЛАБОРАТОРНАЯ РАБОТА 16.


СИНТЕЗ МИКРОПРОГРАММНОГО АВТОМАТА
ПО БЛОК-СХЕМЕ АЛГОРИТМА



Цель работы: Изучить способы синтеза микропрограммного автомата по блок-схеме алгоритма.


Порядок выполнения работы.

  1. Изучить теоретические сведения.

  2. Получить задание у преподавателя.

  3. Исследовать способы синтеза микропрограммного автомата по блок-схеме алгоритма.

  4. Сделать выводы по результатам исследований.

  5. Оформить отчет.


Требования к отчету.

  1. Цель работы.

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

  3. Результаты исследования способов синтеза микропрограммного автомата по блок-схеме алгоритма.

  4. Выводы.


Теоретические сведения.

1. Операционный и управляющий автомат. Микропрограммный автомат. Граф-схема алгоритма.



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



XL=XL1 V XL2

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

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

Пусть Y={y1, y2, …, yn} – множество микроопераций, реализуемое в ОА. Эти микрооперации возбуждаются сигналами y1, y2, …, yn. Если должна быть выполнена микрооперация yn, то сигнал yn=1. Совокупность микроопераций, выполняемых за 1 такт автоматического времени образуют микрокоманду. Для задания порядка следования микрокоманд вводят специальные переменные, называемые «логические условия». Проверка значения логического условия в каждом такте работы управляющего автомата, позволяет определить микрокоманду, реализуемую в следующем такте. Пусть Y1, …, YT – микрокоманды, которые могут выполнятся в операционном автомате, тогда последовательность выполнения микрокоманд определяется функциями перехода, аргументами которого являются логические условия из множества XL. Совокупность микрокоманд и функций переходов, образуют микрокоманду. УА, реализующий микропрограммы работы дискретного устройства, называют микропрограммный автомат.


2. Синтез микропрограммного автомата Мили.


Управляющий автомат, реализующий микропрограмму работу дискретного устройства принято называть микропрограммным автоматом.

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




ОА выполняет преобразования входной информации двоичных векторов, поступающей на её входы xL+1xk. Этими словами могут быть слагаемые для операции сложения, множитель и множимое для операции умножения, делимое и делитель для операции деления. Результаты преобразования, реализованные в ОА формируются на выходах 1G. Задачей УА является выработка распределённой по времени последовательности управляющих сигналов y1…yN под воздействием которых в ОА выполняются некоторые операции.

Определение: Микрооперацией называется элементарный неделимый акт обработки информации в ОА, происходящей в течении одного такта автоматного времени.

Определение: Микрокоманда – совокупность микроопераций, выполняемых за 1 такт автоматного времени.

Для задания порядка следования микрокоманд, вводятся специальные переменные, называемые логическими условиями. Проверка значения логического условия в каждом такте работы УА позволяет определить микрокоманду, реализуемую в следующем такте. Пусть множество Y={y1…yN} – множество микроопераций, возбуждаемых по входам y1…yN в ОА. Из множества Y составляется микрокоманда, представленная множеством: Y1=y1, y2, y3; Y2=y3, y5,…, yN; … YT; {Y1, Y2,…,YT} – множество микрокоманд. Пусть Y1…YT – микрокоманды ОА, тогда последовательность выполнения микрокоманд определяется функциями переходов, аргументами которой является переменные из множества X={x1, …, xM, xM+1,…,xL}. Логическим условием x1…xL ставят по взаимооднозначное соответствие входные переменные x1…xL управляющего автомата, которые целесообразно обозначать теми же символами. Совокупность микрокоманд и функций перехода образует микропрограмму.

Для описания микропрограмм используют язык ГСА (граф-схем-алгоритмов). ГСА – ориентированный связанный граф, включающий вершины четырёх типов: 1) начальная; 2) конечная; 3) операторная; 4) условная. Синтез микропрограммного автомата Мили по ГСА выполняется в два этапа: 1) получение отмеченной ГСА; 2) построение графа автомата. Рассмотрим 1 этап.

При этом ГСА микропрограммного автомата имеет следующий вид:





Отметка ГСА проводится по алгоритму Ф1 метками a1, …, aM:

Символом a1 отмечается вход вершины, следующей за начальной и вход конечной вершины. Входы всех вершин, следующих за операторными, кроме входа конечной вершины отмечаются символами a2…aM.Если вход вершины отмечается, то только одним символом. Входы различных вершин за исключением конечной отмечаются различными символами. В результате получают ГСА, которая называется отмеченной. Если рассмотреть пути от одной метки к другой в направлении ориентации дуг ГСА, то в графе можно выделить несколько путей (am  as).

1) ;

2)

Путь вида 1 – это путь из одной отметки в другую, содержащий операторную вершину.

Путь вида 2 – это путь, содержащий безоператорную вершину.

Эти пути называются путями перехода.

Пример: Для отмеченного графа возможны пути переходов: a1 x1 Y1 a2; a1x1 x2 Y5 a2; a1x1x2 Y7 a5; a2 x3 Y2 a3; a2x3 x1 Y4 a2; a2x3x1 Y6 a1; a3 x4 Y3 a4; a3x4 x1 Y4 a2; a3x4x1 Y6 a1; a4 x5 a1; a4x5 Y4 a2; a5 Y6 a1.


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

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

Таблицы переходов содержат 5 основных столбцов:

1 – am – исходное состояние.

2 – as – состояние перехода.

3 – X(am, as) – конъюнкция переменных из множества Х, принимающих значение 1 на данном переходе.

4 – Y(am, as) – подмножество выходных переменных, принимающих значение 1 на данном переходе.

5 – вспомогательный порядковый номер пути. (h).

Таблица переходов может быть построена по ГСА, а может быть построена по графу переходов.

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

am

as

X

Y

h

a1

a2

x1

y1 y2

1

a1

a2

x1 x2

y1 y3

2

a1

a5

x1x2

y6 y7

3
















a2

a3

x3

y4

4

a2

a2

x3 x1

y8

5

a2

a1

x3x1

y3 y4

6
















a3

a4

x4

y5 y6 y7

7

a3

a2

x4 x1

y8

8

a3

a1

x4x1

y3 y4

9
















a4

a1

x5

-

10

a4

a2

x5

y8

11
















a5

a1

1

y3 y4

12

Расширением этой таблицы переходов является структурная таблица переходов автоматов. В отличии от предыдущей таблицы, в неё вводят 3 дополнительных столбца: 1) код исходного состояния K(am); 2) код состояния перехода K(as); 3) множество компонентов функции возбуждения, вырабатываемых на переходе am as.


am

K(am)

as

K(as)

X(am, as)

Y(am, as)

D(am, as)

h

a1

001

a2

000

x1

y1 y2

-

1

a1

001

a2

000

x1 x2

y1 y3

-

2

a1

001

a5

011

x1x2

y6 y7

D2D3

3

























a2

000

a3

010

x3

y4

D2

4

a2

000

a2

000

x3 x1

y8

-

5

a2

000

a1

001

x3x1

y3 y4

D3

6

























a3

010

a4

100

x4

y5 y6 y7

D1

7

a3

010

a2

000

x4 x1

y8

-

8

a3

010

a1

001

x4x1

y3 y4

D3

9

























a4

100

a1

001

x5

-

D3

10

a4

100

a2

000

x5

y8

-

11

























a5

011

a1

001

1

y3 y4

D3

12


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

Проведём кодировку состояний: a1 – 001; a2 – 000; a3 – 010; a4 – 100; a5 – 011;

Тривиальный (простейший) метод синтеза логический схемы микропрограммного автомата по его структурной схеме.


Из этой таблицы можно сформировать выражения для функций выходов и функций возбуждения. Например, для функции y1: y1 принимает единичное значение, когда у автомата состояние 001 (T1T2 T3 ) и входные значения x1 илиx1x2. yi=(ai, xi)





Функции возбуждения формируются аналогично.




Построим логическую схему микропрограммного автомата на основе D-триггера в качестве элемента памяти.


3. Синтез графа микропрограммного автомата Мура.

Получение отмеченной ГСА.



Синтез микропрограммного автомата Мура по ГСА состоит из двух этапов: 1) получение отмеченной ГСА; 2) построение графа переходов автомата.

На первом этапе начальная, конечная и операторные вершины отмечаются символами а1, …, аn по алгоритму Ф2:

1) Символами а1 отмечаются начальная и конечная вершины.

2) Различные операторные вершины отмечают различными символами.

Все операторные вершины должны быть отмечены.

Пример ГСА автомата Мура:





Получаем отмеченную ГСА автомата Мура.


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


Для построения графа переходов автомата Мура по ГСА находятся пути перехода вида 1: amxm1xmkas (1), где am и as – это отметки принадлежащие множеству всех отметок ГСА. Соответствующая этому пути конъюнкция x(am, as) определяется также, как и для автомата Мили. Если между операторными вершинами в ГСА am и as лежит пустое множество условных вершин, т.е. вершина as следует непосредственно за вершиной a­m, то конъюнкция x(am, as)=1 и переход вида 1 получают в виде amas. Для построения графа Мура, каждому символу a1an, полученному на первом этапе ставят в соответствие вершину графа автомата Мура.

Если в ГСА существует путь вида 1 из am в as, то вершина am соединяется с вершиной as дугой, направленной из am в as. В начале дуги записывается конъюнкция x(am, as).



Рядом с вершиной am графа автомата записываются элементы множества Ym. Под Ym понимают микрокоманду, соответствующую операторной вершине am. Допускается Y(am) = 0. Если в ГСА из am в as имеется несколько путей вида 1. Например i j k, то вершины am и as графа автомата соединяют одной дугой, направленной из am в as, а в начале дуги последовательно записывают конъюнкции xi(am, as), xj(am, as), xk(am, as). Любой переход в полученном графе автомата Мура из состояния am в as осуществляется под действием такого набора переменных х, для которого конъюнкция x(am, as)=1.

Граф автомата Мура:



При наличии в отмеченной ГСА контуров, включающих только условные вершины, формируется конъюнкция x(am, as) по правилам, изложенным выше.

Построение таблицы переходов микропрограммного автомата Мура.


Таблица переходов микропрограммного автомата Мура содержит 3 столбца. В ней выходные сигналы из множества Y(am) записываются в столбце am рядом с состоянием, в котором они формируются.


am, Y(am)

as

X(am, as)

a1

a2

1

a2, y1y3

a2

a3

a4

a6

x1x2x3

x1 x2

x1x2 x3

x1

a3, y2y3

a5

1

a4, y4

a1

a7

x2

x2

a5, y1y2

a1

a7

x2

x2

a6, y2

a5

a6

a8

x4

x4 x1

x4x1

a7, y5

a8

1

a8, y6

a1

1


При наличии таблицы переходов строят структурную таблицу переходов.


am, Y(am)

K(am)

as

K(as)

X(am, as)

D(am, as)

a1

000

a2

001

1

D3

a2, y1y3

001

a2

a3

a4

a6

001

010

011

101

x1x2x3

x1 x2

x1x2 x3

x1

D3

D2

D2D3

D1D3

a3, y2y3

010

a5

100

1

D1

a4, y4

011

a1

a7

000

110

x2

x2

-

D1D2

a5, y1y2

100

a1

a7

000

110

x2

x2

-

D1D2

a6, y2

101

a5

a6

a8

100

101

111

x4

x4 x1

x4x1

D1

D1D3

D1D2D3

a7, y5

110

a8

111

1

D1D2D3

a8, y6

111

a1

000

1

-


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

yi=(Si)




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





Индивидуальные задания

Вопрос 1. 1) Составить ГСА на 6 операторных и 5 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 2. 1) Составить ГСА на 7 операторных и 5 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 3. 1) Составить ГСА на 8 операторных и 5 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 4. 1) Составить ГСА на 6 операторных и 4 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 5. 1) Составить ГСА на 6 операторных и 7 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 6. 1) Составить ГСА на 6 операторных и 6 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 7. 1) Составить ГСА на 5 операторных и 7 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 8. 1) Составить ГСА на 5 операторных и 4 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 9. 1) Составить ГСА на 5 операторных и 3 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 10. 1) Составить ГСА на 7 операторных и 3 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 11. 1) Составить ГСА на 4 операторных и 3 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 12. 1) Составить ГСА на 5 операторных и 6 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 13. 1) Составить ГСА на 7 операторных и 6 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 14. 1) Составить ГСА на 4 операторных и 5 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.

Вопрос 15. 1) Составить ГСА на 5 операторных и 5 условных вершин. 2) Отметить ГСА метками МПА Мура. 3. Построить по отмеченной ГСА граф МПА, структурную таблицу МПА и систему булевых функций для реализации логической схемы МПА.


Вариант

задание1

1

8

2

15

3

6

4

11

5

10

6

2

7

7

8

14

9

1

10

9

11

13

12

4

13

12

14

3

15

5



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


1 Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов. - 3-е изд. - М.: Энергоатомиздат, 1989.