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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 23.10.2024

Просмотров: 108

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

В

результате сравнения ft10,

и 6 и

в табл. 7-9 оказывается, что

b,„

Ь1ІУ и мы приходим к табл.

7-10,

где содержится всего один ва­

риант подграфа ГСА, в котором будет

минимальное число условных

вершин. Соответствующий подграф с 9

условными вершинами приве­

ден на рис. 7-9.

 

 

 

 

Рис. 7-9. Минимальный подграф,

равносильный подграфу

 

 

 

 

 

на рис. 7-8

 

 

Таким образом, процедуру сжатия нужно проводить несколько раз.

Если

после окончательного

сжатия

в

одном или нескольких из

Yj (у --

1, . . . ,

т) остается более одного варианта, то можно приме­

нить описанную выше модификацию ме­

Ф

 

тода

Петрика,

поскольку

размерность

хі

задачи после сжатия существенно со­

 

 

кращается.

метод был

разработан

 

 

Изложенный

 

Хі

для минимизации ГСА, однако оказалось,

 

 

что он может быть без всяких изменений

 

 

использован для минимизации многовы­

Рис. 7-10. Соответствие между

ходных

схем

с непересекающимися

условной вершиной (а) и пере-,

множествами

значений реализуемых

ключательным контактом (б)

ими

выходных

функций,

построенных

 

 

.на переключательных контактах. Рис. 7-10 иллюстрирует однознач­ ное соответствие между условной вершиной и переключательным кон­ тактом. На рис. 7-11 показан пример шестивыходной релейной схемы до и после минимизации.

В случае неполностью определенной ГСА можно ввести понятие неполностью определенного отмеченного покрытия, в которое вклю­

чим кубы вида csZ, где Z — символ нейолной определенности, а cs — соответствующий куб, на котором это покрытие не определено. Алго­ ритм получения равносильных подграфов остается прежним с той

лишь разницей, что в -результате операции crYt х csZ получается

153

куб

cpY h

где ср определяется как и ранее, но координата х, по ко­

торой

происходит склеивание, не

подчеркивается (так же, как и в

случае c Y ,

х csY , ). Если считать,

что ГСА Г на рис.

7-8

не опреде-

 

 

 

лена на наборах

 

а)

X ,

 

 

 

 

 

 

 

ХІ1

10х

Z

 

 

 

1x1

10х

Z

 

 

 

Их

lOx

Z

^

—1_______________ „л

ff

 

X,

Xs

 

'

f

 

 

1—I I

I I

°4

 

—1r

~ ~ | X S —

-------

afl

 

 

 

1

 

 

Ez

n

x2

 

 

 

 

r

 

 

 

 

 

\

\ 1

 

 

 

 

Ч 1Тx3

 

 

 

 

 

. H r

------------------------------------------------------ off

 

 

 

Рис. 7-11. Схема на переключательных контактах:

а — до минимизации,

б — после минимизации

 

 

 

 

 

 

то в результате минимизации получим подграф с 7 условными верши­ нами.

7-2. Учет распределения сдвигов при минимизации граф-схем алгоритмов

Из содержательного смысла работы дискретного устройства, по­ ведение которого описано граф-схемой алгоритма, часто можно опре­ делить, какие логические условия могут меняться (или не меняться) во время выполнения того или иного оператора. Например,, если в ЦВМ в каждый момент времени выполняется не более одной команды— отсутствует локальный параллелизм [13], то код этой команды не ме­ няется от момента ее появления в регистре команд до выбора следую­ щей команды.

Если каждому оператору Yt (t = 0, 1, . . . , Т + 1; Y0, Y T+l —

начальный и конечный операторы) ГСА или MCA поставлено в соот­ ветствие некоторое подмножество Bt логических условий, элементы которого могут изменяться во время выполнения оператора Yt, то

154

говорят, что задано распределение сдвигов. Распределение сдвигов является дополнительной к ГСА или MCA информацией о логике ра­ боты устройства, и эта дополнительная информация может быть ис­ пользована для упрощения ГСА или MCA.

Если каждому оператору Y t поставлено в соответствие полное мно­

жество логических

условий (Bt = X = [xlt . . .

, xL\),

то

такое рас­

пределение

сдвигов

называется

универсальным.

Если

же

для всех

t = 0, 1, . .

. , Т

1 Bt = 0

(ни одно логическое условие не изме­

няется во время выполнения операторов), то такое распределение сдви­ гов называется пустым.

Пусть для MCA М (табл. 7-11) задано распределение сдвигов:

Уо

Уі-

Уз

г 4

Уз

Ув

Y о

B q — 0 ;

Y 4 -------------------

ß . j - -

( х 2 } ;

Yi

Вх— \х2, х3);

Y г,

В5={л'1; х2, *з);

Y 2-------

В2 = [х2];

Y о-------

В(; = [х2]

Y з

В3 [хі, х2, х3];

Кк

Вк =

0 .

Таблица 7-11

MCA М до учета распределения сдвигов

У,

у,

уа

У.

у-.

у«

ук

*2*1

 

 

*2*1

- *2*1

 

 

 

 

*2*1

 

 

 

 

 

 

 

 

 

 

X2 Ху

 

 

 

*2

 

 

 

 

 

*2*1

 

 

 

 

 

 

*2*1

 

 

 

*2

 

 

 

 

 

*2*1

 

 

 

 

 

 

 

 

 

 

 

*1

*1

 

 

 

 

 

 

 

 

*2

 

 

 

 

 

*2*1*3

*2*1

 

 

 

 

 

 

*2*1*3

 

*1

 

 

 

*

*1

 

 

 

 

 

 

 

1

 

 

/

 

 

 

 

 

 

 

155

Анализ столбца Y x показывает, что

оператор

может

выпол­

няться только после У0 и Y 2, но всегда

при хх= 1

и х2 — 0.

Из рас­

пределения сдвигов видно,

что л*1 не изменяется во время выполнения

оператора Уг, т. е. после выполнения Y L логическое условие х х

остается равным единице.

В связи с этим в строку Ух можно вместо

переменной х х подставить ее значение — единицу. Так как x s входит

в распределение сдвигов для И1, то значение х 2

может

измениться,

а потому в строке

Ух нельзя х 2

заменить на нуль.

 

Перейдем к следующему столбцу, У„. Аналогично У2 выполняется

после Y-a только при ,vx = 1,

 

не входит в распределение сдвигов

для Y о (.vx

(£ Во),

поэтому в строке У, можно заменить х х на единицу.

Продолжая точно так же для остальных операторов, придем к MCA

М' в табл.

7-12.

 

 

 

 

 

 

 

 

 

 

 

 

 

Таблица 7-12

 

MCA М' после учета распределения сдвигов

 

 

У і

Y o

У з

у .,

У 5

y e

У к

 

 

Уо

Л'іЛ'2

 

 

X i

•Ѵ Л

 

 

У і

 

 

А'2

 

 

 

Ао

к 2

-Ѵ'2

 

 

 

А2

 

 

у 3

 

 

 

X i

X i

 

 

У 4

 

 

 

 

 

 

I ■

у *

 

X 1

 

 

 

 

-Ѵ'і

Уо

 

 

1

 

 

 

 

 

 

 

 

 

 

 

Интересно заметить, что все элементы столбца У„ оказались рав­ ными нулю. Это значит, что к оператору У„ нельзя перейти ни от ка­ кого оператора, а потому строку и столбец У„ из MCA М' можно уда­ лить.

На рис. 7-12 и 7-13 приведены граф-схемы Г и Г', построенные по MCA М и М ’. Как видно из нашего примера, учет распределения сдви­ гов позволил существенно упростить ГСА и MCA.

В работе [8] предложена простая процедура учета распределения сдвигов при минимизации MCA, сущность которой сводится к следую­ щему. Для каждого столбца Yt (t = 1...........Т + 1) матричной схемы

156

Смотрите также файлы