Файл: Баранов, С. И. Синтез микропрограммных автоматов.pdf

после приведения по переменным х4, .v3, x lt а'3, л*в будет иметь вид:

Уt -> Ä'i (l2^^i\/^JÄ1feVfA/A-a (A-5r 4V.v5r 7))V/A-1Vr4))V

V *i ( й СчУсѴхіУ^Ѵх, (хі А зК Д А і№ W ) ) V ^ » ) ) . (4-20)

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

жения (4-20) приведена на рис. 4-9. Необходимо отметить, что для одинаковых подформул строится один подграф ГСА (подчеркнутым одинаковым выражениям в (4-20) соответствует обведенная штриховой линией часть ГСА на рис. 4-9).

Ясно, что число условных вершин в ГСА зависит от порядка при­ ведения, что сразу видно из выражений (4-17) и (4-18), где первое при­

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

Точно так же, как это сделано выше для граф-схемы алгоритма, можно определить значение системы формул перехода на произволь­ ной последовательности наборов значений переменных х ъ . . . , xL.

68

4-6. Матричная схема алгоритма

Пусть ГСА Г имеет начальную (У0), конечную (Ук) и Т оператор­ ных вершин с записанными в них различными операторами Ух, . . . ,

табл. 4-1. Для простоты нулевые функции перехода в матрицу не за­ носятся.

Таблица 4-1

Переход от MCA к ГСА состоит в последовательном получении системы формул перехода, системы скобочных формул перехода и после этого— граф-схемы алгоритма.

Как и для граф-схем, можно определить значения MCA на произ­ вольной последовательности наборов значений переменных.

69

Глава пятая

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

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

Конечный автомат, реализующий микропрограмму работы дискрет­ ного устройства, принято называть микропрограммным автоматом [6,8]. Синтез микропрограммного автомата по граф-схеме алгоритма осуществляется

каждому такому пути можно поставить в соответствие слово в ал­ фавите

X L Y

• > ЛЬ > 1 1'

70

показано на рис. 5-2, а, где волнистая линия соответствует пути через условные вершины.

В тех случаях когда нас будет интересовать не конъюнкция вида хт іц ■• • хм$> а некоТорое множество тех же, что и в конъюнкции, букв ІдЛ'п.......... А'с"ія]., мы будем использовать для этого множества то же обозначение, что и для конъюнкции, но с тильдой. Так,

v emR

71

Может случиться, что между ат и as имеется несколько путей вида

а,пХ н (а„„ as) Y (а,„, as) as (h = 1, . . . , Н), проходящих через одну и ту же операторную вершину (рис. 5-2, б). Будем считать, что этому

Н

множеству путей соответствует дизъюнкция X (ат, as) = \ / Х п (ат, as), h=1

а само множество путей обозначать атХ (ат, as) Y (ат , as) as, называя его обобщенным путем перехода.

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

Находим все пути перехода на отмеченной ГСА. Если при некото­

в этом пути. Так как множество условных вершин в данном случае пусто, а конъюнкция пустого множества переменных равна единице, то соответствующий входной сигнал полагаем равным единице, а вы­ ходной сигнал, как и раньше, Y (от, as).

Каждому пути перехода вида атХ (ат, at) аг ставим в соответст­ вие переход из ат в аг. При этом ат и входной сигнал определяются, как и раньше, а выходной сигнал полагаем равным К0 (пустой опера­ тор).

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

Входными сигналами автомата S, имеющего L входных каналов, является множество L-компонентных векторов Дг . . . , Д;-.......... Д2ь, где Д^. = (е^, . . .,

путь перехода атХ (ат , as) Y (ат, as) aSt проходящий через операторную вер­ шину Y {а„1, as), то дуге графа автомата приписывается входной сигнал X (ат, as) и выходной сигнал Y (ат , as). Отличительная особенность микропрограммных автоматов, синтезированных рассмотренным выше способом, состоит в том, что приписанные дугам графа входные сигналы являются элементарными произве­ дениями и, таким образом, булевыми функциями тех переменных, которые вхо­ дят в соответствующие пути перехода, причем длина этих произведении сущест­ венно меньше числа L всех входных переменных. Очевидно, что переход (о,„, as)

72

с выдачей выходного сигнала Y (ат , as) будет иметь место под действием тех входных наборов из множества | Аt, . . . , А2/„), на которых булева функция

X (ат , as) принимает значение единицы.

Условие детерминированности работы автомата требует, чтобы любое по­ парное произведение входных сигналов, вызывающих переход из некоторого состояния автомата, было равно нулю. Это условие всегда выполняется для ав­ томата, построенного по граф-схеме алгоритма. Действительно, если из неко­

переменных, принимающая значение единицы лишь на наборе Ау и значение нуля на остальных наборах. Тогда к каждому из первых R классоз Ег (г= 1, . . . , R) отнесем те и только те наборы значений входных переменных, для которых соответствующие конституенты единицы поглощаются определяющей этот класс конъюнкцией Хг, т. е.

зволяет определить, какой переход имеет место под действием каждого из этих наборов. Так как функция Хг принимает значение единицы на множестве на­ боров Ег {г = 1, . , . , R), то переход автомата из состояния ат под действием любого входного набора, попадающего в один из Ег классов, н соответствующий выходной сигнал совпадают с переходом автомата под действием определяющей этот класс конъюнкции и с выдаваемым при этом выходным сигналом, тогда как

1 Не исключен случай s = t, т. е. два перехода в одно и то же состояние. 2 А \ В обозначает разность множества А и В: А \ В = А(~\В.

73