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

Увеличим число путей в точку Q и из точки Q в другие состояния (рис. 6-8, о). Доопределяя функции возбуждения на переходах из мно­ жества состояний G (Q) = (аа, . . . , ат, . . . , аЛ,} в каждое состоя­ ние аг (г — М -|- 1, . . . , R), получим:

Ш =1

Y ( Q ,a r) = F (G (Q),ar) = Ф (Q) X (Q, аг).

Рис. 6-6. Узел в ГСА: а — под­ граф, содержащий узел, б — условное изображение под­ графа

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

103

Один из путей может не содержать ни одной условной вершины {R = 0), т. е. иметь вид amQk. Тогда вход некоторой условной вер­ шины имеет две отметки — состояния и узла, причем отметку-узел

а т рюХ(ат,0) ссп р пХ(а„.0)

Рис. 6-7. Логическая схема для подграфа ГСА на рис. 6-6: а — без доопределения функции возбуждения, б — с доопределением функций возбуждения

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

а)

Рис. 6-8. Подграф ГСА с большим числом путей из узла в состояния (а) и соответствующая логическая схема (б)

В общем случае могут быть пути в узел не только из состояний, но и из других узлов. Будем считать, что существует путь из узла Qp

в узел Qk, если па граф-схеме есть путь вида Qp.v^ 1 . . . xeppQk. На рис. 6-9, а в узел Qk есть пути из ат и ап и узла Qp. G (Qk) = [ат,

104

представление микропрограммного автомата в виде списка. В каждой

Рис. 6-9. Подграф ГСА с путем «узел—узел» (а) и соответствую­ щая логическая схема (б)

строке структурной таблицы записывается путь перехода вместе с ко­ дами состояний и вырабатываемыми на этом переходе обязательными функциями возбуждения. Расширим теперь понятие структурной таблицы, введя туда пути «состояние — узел», «узел — состояние» и «узел — узел». Таким образом, всевозможных различных комбина­ ций путей на графе алгоритма будет четыре. Общий вид структурной таблицы иллюстрируется табл. 6-7.

105

Необходимо подчеркнуть, что узел не является состоянием авто­ мата и введен лишь для облегчения построения и упрощения схемы микропрограммного автомата. На самом деле никаких переходов в узел и из узла в обычном понимании слов «переход автомата» не суще­ ствует. Таким образом, расширение понятия структурной таблицы привело к тому, что она уже не представляет граф автомата в виде списка. В то же время в этой таблице уже учтены некоторые структур­ ные особенности будущей схемы автомата.

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

—в состояния alt а2, . . . Такая таблица для ГСА на рис. 6-1 приведена в табл. 6-8. Сравнение этой и структурной таблицы без узлов для той же граф-схемы (табл. 6-5) показывает, что введение узлов позволяет существенно сократить длину структурных таблиц.

6-6. Задача факторизации

А5 = XiX2 x5 X(jXioXi2Xi3.

Очевидно, что возможна минимизация схемы, реализующей эту функцию, если предварительно вынести общий множитель из всех или нескольких конъюнкций. Так, например, формулу (6-3) можно преобразовать:

Схема для формулы (6-4) требует на 4 входа в логические элементы меньше, чем схема для формулы (6-3).

В общем случае, если имеется дизъюнкция п конъюнкций

т. е. у всех конъюнкций есть общий множитель х х . . . хт1, он может быть вынесен за скобки, и тогда соответствующая схема реализуется так, как показано на рис. 6-10, а. Очевидно, что выигрыш в числе входов в логические элементы в этой схеме по сравнению с непосредст­ венным построением по формуле (6-5) будет

ДV = тп —т — 1 = т ( п — 1)— 1,

где т — число общих букв во всех конъюнкциях, п — число конъ­ юнкций.

Может случиться, что вынесение возможно не из всех конъюнкций. Так, если

106

причем только первые п конъюнкций содержат общий член хл .

то функция / может быть реализована так, как показано на рис. 6-10,6. В этом случае

АV = тп—т — 1 — 1 = m (п— 1) —2.

Если к тому же у г из первых п конъюнкций (предположим для про­ стоты, что это Х ъ . . . , Х ‘) после вынесения общего члена х г . . . хт остается по одной букве: Х р — х х . . . xmzp (р — 1, . . . . г), то имеет место наиболее общий случай, при котором первые г конъюнкций на рис. 6-10, б исчезают, схема принимает вид рис. 6-10, в, а выигрыш

107

Таблица 6-8

Структурная таблица автомата Мили (с узлами), построенного по рис. 6-1

108