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

Продолжение табл. 6-11

128

из состояний b2, Ь3, &4, проходящие через пустое множество условных вершин. Переходя от примера к общему случаю, получим, что мно­ жеству состояний В(, порождаемому состоянием at, можно поставить в соответствие узел Spr в который есть

мом столбце проставлены обязательные функции возбуждения в пред­ положении, что в качестве элементов памяти автомата исполь-

Ö)

Рис. 6-26. Схема, реализу­ ющая пути в Qj и b-„\ а — раздельное построение; б — совместное построение с вы­ несением

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

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

129

130

jniJfßjriS ЛУ4.ІП9пИ7/ „ИЧ5Л‘19 JTß.H'21

131

ляются непосредственно из таблицы 6-13 следующим образом:

гі = = Т\ ТоТз\ го = cc0ßo — Т\ Т2 Тз,

7-3 = a 2ßi V a oßi = TJ'{TZV Т\Т2 Т3\ гі = а0^п = Т 1 Т 2 Т 3.

Логическая схема автомата, построенная по табл. 6-13, приведена на рис. 6-27. Во избежание гонок и для обеспечения устойчивости состояний в схеме используется двойная память.

Глава седьмая

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

7-1. Минимизация условных вершин в граф-схеме алгоритма

В работе [8 ] отмечалось, что предложенная ІО. И. Яновым [24] полная система тождественных преобразований логических схем алго­ ритмов (ЛСА) «дает возможность получить ЛСА с минимальным чис­ лом логических условий, однако этого можно достигнуть лишь путем полного перебора всех возможных ЛСА, равносильных заданной, так как отсутствует алгоритм последовательного применения преобра­ зований для получения минимальной ЛСА». В данном разделе опи­ сывается предложенный автором в работе [3] алгоритм минимизации логических условий с той лишь разницей, что изложение ведется применительно к граф-схемам, но все сказанное ниже может быть однозначно использовано и для логических схем алгоритмов.

Постановка задачи в общем сводится к следующему. Пусть задана

в ней оператором, Р = |р х...........рг..............pR) — множество услов­ ных вершин, в которых записаны логические условия X -- (,ѵх, . . . , Х[, . . . , xL\. Требуется среди множества граф-схем, равносильных Г (У0, Ук, У, Р), найти граф-схему с минимальным числом условных

вершин.

Покажем, что задачу минимизации ГСА Г (У0, Ук, У , Р) можно разделить на несколько независимых подзадач путем разбиения ГСА

на подграфы Г1 ...........Г1', . . . , Гн , такие, что если для каждого под­ графа найти равносильный ему с минимальным числом условных вер­

шин (подграфы Рmin» • • • >Amin» • • • >Утіп)> то граф Гmjn, полученный после объединения этих подграфов, будет иметь минимальное

Y\q, . . . , Ущ.І. такое, что из Yt есть пути в Yfq, проходящие только через условные вершины, вида:

132

где [ptl, . . . , pIM] С P — множество условных вершин, лежащих на пути из Y t в y s; е1т ^ (0, 1} — символ, приписанный выходу ус­ ловной вершины ріт, через который проходит рассматриваемый путь.

В1 = Вп.

Вграф-схеме Г выделим подграф Г1, включающий в себя опера­

торные вершины из А 1 (назовем их исходящими вершинами) и В 1 (вхо­ дящие) и множество условных вершин Р1, через которые проходят пути из элементов Л1 в элементы В 1. Вершину Yt назовем опорной

честве опорной вершину, не вошедшую в уже построенные множества

2. Разбиение единственно, независимо от выбора на каждом шаге опорных вершин для подграфов. Из единственности разбиения и ус­

ловия Р1 П Р‘ — 0 непосредственно вытекает следующее утвержде­

133