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

ние: пусть R — число

условных вершин

в Г, а R ‘ — число услов­

ных вершин в г

(/і =

1, . . . , Я). Тогда R

н

h

=2

*

■

/ і = і

на

под­

После этого нетрудно доказать, что если Г разбивается

графы Г1,

Гн и в

каждом Гк (h = 1,

. . . , Я)

число условных

вершин минимально

’min), то число условных вершин в Г также бу­

[Rr

дет

минимально

и

равно1

и

л

2

Ятіп.

ft=l

В качестве примера приве­

дем разбиение

изображенной

на рис. 7-1

граф-схемы алго­

ритма Г, имеющей 6 оператор­

ных и 6 условных вершин.

Применение

алгоритма

раз­

биения дает 3 подграфа:

Г1,

Г 2, Г 3. Условное изображение

этих

подграфов,

полученных

в процессе разбиения,

и сами

подграфы

приведены

на

рис. 7-2.

В этих

подграфах:

Г1

: А 1= (У0,

Уа,

У4);

в г = [ ѵ и у», Кв); р х= ( р і,

Ре» р4І;

r * : A * = { Y lt

Y з,

У0};

В2={ У 2,

Y it

Y я); P 2=

{p2,

Pb,

Pc);

Рис. 7-1.

ГСА Г до разбиения

Г2

\ A 2

= [Y5}\

ß 3= [K K);

Р 3=

0 .

Номера условных вершин в ГСА Г и в подграфах проставлены ря­

дом с вершинами. Интересно заметить, что

А 2

П В 2 — (F 0)

0 ,

что допустимо (А1 П В1 может быть не пусто,

обязательно А 1

П А' =

= 0 и В 1 П В1 = 0 ).

В работе

[17]

подробно изложены разработанные Ротом (J. Roth)

метрическое представление булевой функции,

которая является ото­

1 Для доказательства достаточно предположить,

что существует некоторая

а)

б)

В)

А3

Ун В1

к операторам

,

Yt,

, Y T+V

можно записать с помощью

выражения:

Yf -> cCfiYi V

•••

V aftY t V

V a f. r+i^r-fi»

(7-2)

где af( — булева

функция,

равная дизъюнкции конъюнкций,

соот­

введем

геометрическое

представление

формул

перехода.

Пусть

У,-*

Г-Н

пере-

V aftY t— формула

хода.

і=1

перехода

aft

Функцию

(*і.

. . . ,

хп)

от

Yf

к

Y,

(/

=

= 1, . . . , Т + 1) представим в ви­

де кубического покрытия, причем

каждому

из

кубов,

входящих

в покрытие, припишем оператор

Yt\ /г-мерный

куб вместе с при­

писанным

оператором

назовем

отмеченным кубом. Если D , —

множество

отмеченных

кубов,

порождаемых

функцией allt

то

г-н

формуле перехода Yf -> V

аи Y t

Рис. 7-3.

Подграф

с одной

исходящей

соответствует

множество

кубов

операторной вершиной

Г+1

0 (У Л = и

Dt, которое назовем

покрытием формулы перехода. Например,

/=і

для формулы перехода из

оператора Y4 в ГСА на рис.

7-3

Y 4 --

(хул'о \ / х^ХоА'з) Y 2 V

(*і*а*я V

Н^-а-^з) У4 \ /

\ / x^x^x^Y

покрытие D (У4)

будет иметь вид:

01x

Y 2

100 Y 2

D{Yt) =

001 Yj.

(7-3)

000 Ex

11* Уз

101 Yj.

Над парой отмеченных кубов с

Y, — (а4...........ah

. . . , ап)

Yt и

csY m =

(£>!, . . . ,

bt, . . . , bn) Ym,

принадлежащих

покрытию фор-

(7-5)

предполагается

а1 = е{ = 1; Ьс = е(- = 0.

Если aL=

ег = 0,

Ьі =

е( = 1, то

операторы

У, и Ym необходимо

поменять местами:

Y q =

xtY mYi. Если

У, =

Y m, то из (7-4) получим:

Y q ^ X i ‘Y m \ / x / Y m = Y m.

Таким образом,

Y

-

0 , если cr X c s= 0 \

CrY ; X

т

< ? Y q,

если cr X c s = £ 0 , где

cp = cr X c s,

а

1

У0, Уъ • •

• , Ут-

Введенную

X-операцию

над

парой отме­

Рис. 7-4. Подграф для

ченных

кубов сгУ,

и сяУ,„ назовем

склеиванием

формулы перехода

и будем

говорить,

что

эти

кубы

склеиваются

-> А ™ I V x f i Y m

по переменной

xt,

если

они

имеют противопо­

1x0*1

У8

1*1*1

У8

Іхххі

У8

Однако

1x0x1

У8

lx llx

У8

lxxl1

У8