Абстрактный синтез микропрограммного автомата

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 17:59, 20 мая 2016.

Общие правила составления граф-схемы микропрограммы

Рис. 1. Граф-схема микропрограммы

ГСМ считается корректной, если выполняются следующие условия:

  • ГСМ содержит конечное число вершин, каждая из которых принадлежит к перечисленным типам;
  • имеет одну начальную и одну конечную вершины;
  • выходы и входы вершин соединяются с помощью дуг, направленных от выхода ко входу;
  • каждый выход соединён с одним входом;
  • из любой вершины существует хотя бы один путь к конечной;
  • один из выходов условной вершины может соединяться с её входом, что недопустимо для операторной вершины;
  • в каждой условной вершине записывается один из входных сигналов управляющего автомата;
  • в каждой операторной вершине записывается оператор (микро-команда из множества микрокоманд).

Абстрактный синтез МПА Мили

Синтез микропрограммного автомата Мили осуществляется в два этапа:

  1. Получение отмеченной граф-схемы микропрограммы
  2. Построение графа микропрограммы

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

На этапе получения отмеченной ГСМ входы вершин, следующих за операторными, отмечаем символами по следующим правилам:

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

Пусть для отметки входов вершин использовались символы . Результатом первого этапа является отмеченная ГСМ, что является основой для второго этапа – перехода к графу автомата.

Если идти от одной отметки к другой отметке в направлении ориентации дуг ГСМ, выписывая содержимое лежащих на этом пути вершин, то каждому такому пути можно поставить в соответствие слово в алфавите где при выходе из условной вершины по единице в соответствующем пути, или 0 при выходе из условной вершины по нулю.


Рис.2. Отмеченная ГСМ при абстрактном синтезе автомата Мили

Чтобы подчеркнуть, что выписанное слово соответствует пути из в , будем ограничивать это слово слева и справа символами и соответственно. В дальнейшем нас будут интересовать слова вида или

Соответствующие этим словам пути в граф-схеме называются путями перехода. В первом случае – путь в ГСМ из одной отметки в другую , содержащий точно одну операторную вершину, во втором случае – это путь из некоторой отметки в отметку , проходящий только через условные вершины. Каждому пути можно поставить в соответствие конъюнкцию Схематично путь перехода можно изобразить на рис. 3, где волнистая линия – условные вершины.

Рис. 3. Условное изображение пути перехода. а - один путь, б - H путей

Построение графа микропрограммы

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

Каждому пути перехода вида поставим в соответствие переход автомата из состояния в состояние под действием входного сигнала с выдачей выходного сигнала . Каждому пути вида поставим в соответствие переход автомата из состояния в состояние , где состояния определяются как раньше. Входной сигнал на этом переходе также равен конъюнкции содержимого условных вершин на этом пути. Так как множество условных вершин в данном случае пусто, а конъюнкция пустого множества переменных равна 1, то соответствующий входной сигнал полагаем равным 1.

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

Граф автомата Мили

Абстрактный синтез МПА Мура

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

На первом этапе начальная, конечная и операторные вершины помечаются символами по следующим правилам:

  1. Символом отмечаются начальная и конечная вершины
  2. Различные операторные вершины отмечаются различными символами
  3. Все операторные вершины должны быть отмечены.

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

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

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

Рис. 5. Отмеченная ГСМ автомата Мура

Построение графа микропрограммы

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

Рис. 6. Граф автомата Мура

Таблицы переходов

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

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





















Таблица №2. Обратная таблица переходов автомата Мура






















где – исходное состояние, – состояние перехода, – входной сигнал на переходе , – выходной сигнал на переходе .

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

Источники

  1. Рафиков А.Г. Курс лекций по предмету "Аппаратные средства вычислительной техники"
  2. Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы).- Л.: Энергия, 1979.- 232 с.