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

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

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

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

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

Добавлен: 23.10.2024

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

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

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

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

В табл. 7-5 варианты Ь0 и Ьв имеют минимальную длину,'равную четырем. Один из них (bä) реализован подграфом на рис. 7-7.

Рис. 7-6. Подграф ГСА, равносильный подграфу на рис. 7-3

Прежде чем рассмотреть получение равносильных ГСА для под­ графа с несколькими исходящими операторными вёршинами, введем

операцию пересечения над парой отмеченных кубов с У) =; (я±, . . . ,

ot-, • • ■, ап) Уі

и

csУт =

(Ьг........... Ьі

bn) Ут\ в результате

этой операции получается новый куб (?Yq =

сгУ1 П csYm:

 

r

s

I 0 ,

если

У,

У,п или

если ср = 0

;

 

/П

 

і cpY q, где

ср = сг Г \с\

а К17=

К/ =

У„І.

 

 

 

 

 

 

 

 

 

Таблица 7-5

 

 

Таблица вариантов реализации D0 (Г,і)

 

 

b,

h

 

b.,

(-<

 

Ь;

b,-,

b-

 

35

36

 

37

38

 

39

40

41

42

28

30

 

28

30

 

21

21

32

34

27

27

 

29

29

 

31

33

20

20

26

21

 

26

21

 

25

24

26

24

23

25

 

20

25

 

22

 

23

 

20

23

 

21

22

 

 

 

 

 

 

20

 

22

 

 

 

 

 

 

144

Операция пересечения над логическими частями отмеченных ку­ бов сг П °s есть покоординатная операция, определяемая с помощью табл. 7-6.

С — ( ^ 1 ) ■ • • г & І І

• • • » ^ 7 і ) П ( ^ 1 >

• • • 1 & І1 • • • >

»

0 , если

у

встречается

хотя

бы

в

одной координате;

(т (ах П &і),

• •

• , т(аі f|

&,), •

• •

,

т{ап П Ь„)),

если у

не встречается

ни

в

одной координате;

 

ш(а,-П&і)

есть

m

(0)

= 0,

/п (1)

=

1,

т(х) = х.

 

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

Перейдем к случаю, когда после разбиения ГСА имеем подграф Г, содержащий более одной, например т, исходящих операторных вер­

шин

 

. . .

,

Y m.

Пусть

ПО-преж-

 

 

Таблица 7-6

нему

число

различных

логических

Таблица

^-операции

 

условий в подграфе равно п (хх, . . . ,

 

0

 

 

хп).

Очевидно,

что

для

 

каждого

п

 

X

исходящего

оператора Y,-

можно,

0

0

У

0

как

и

выше,

построить

соответст­

вующее

ему

 

отмеченное

 

покрытие

1

У

1

1

 

 

X

0

1

X

D 1 (/

=

1, . . .

, т).

Для

 

подграфа

 

 

 

 

Г (рис. 7-8) с тремя исходящими операторными вершинами имеем три покрытия:

100

4

ОН 4

 

 

100

по

4

 

 

100

4

 

 

111

001

5

 

 

D2 = 001

 

 

 

ПО

000

5 ,

5

’

D3 =

ш*

6

000

5

 

0*0

11*

6

 

 

101

111X

7

 

 

101

7

101

7

 

 

0*1

 

 

 

 

 

Как и ранее, при одной исходящей операторной вершине, выпол­ ним всевозможные операции полного склеивания и поглощения в пре­

(> З а к а з № 2225

145

делах каждого покрытия. В нашем примере получим:

 

1*0

 

01*

4

 

100

4

 

 

 

100

4

 

11*

5

 

 

00л:

Dl

 

 

 

00*

5 ,

Dl =

0*0

6

 

£>о = 01*

 

 

1*1

 

11*

6

 

101

7

 

 

 

101

7

 

0*1

8

 

 

 

 

 

 

Вторая

предварительная операция

в случае, т покрытий состоит

в нахождении их всевозможных пересечений, т. е. D 0]

П £>о, Do П

°о,

. . . ,

П Do, D 0l

П Dl П D l,.. .

. , Di

П D\ П • • •

П Я Г

Да­

лее аналогично методу меток при минимизации системы булевых функ­ ций [17] увеличим на т координат логическую часть °г = (ах, . . . , ап) каждого куба crYt всех покрытий и их пересечений, добавив слева

* 11.. . . 1 для

кубов

из Dl,

1*11 . . .

1 для

кубов

из £>о, * 1*1

. . . 1

для кубов из D\ fl Dl, XX . . .

* для кубов из £>о П

£>о П •

■■ П D 't

Таким образом, символ *

в

/-координате

приписанного

вектора

(1<! І ^.т) означает,

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

Do, а символ

1 — что данный отмеченный куб покрытию DÖ не

при­

надлежит.

 

 

 

 

 

 

 

 

 

После этого получим покрытие D для подграфа как объединение

кубов, входящих в

. . . ,

D™

. В рассматриваемом примере

 

 

 

 

*11

1*0

 

 

 

 

 

 

 

*11

00*

 

 

 

 

 

 

 

*11

01*

 

 

 

 

 

 

 

*11

1*1

 

 

 

 

 

 

D-.

1*1

01*

 

 

 

 

 

 

1*1

100

 

 

 

 

 

 

 

1*1

00*

 

 

 

 

 

 

 

1*1

11*

 

 

 

 

 

 

 

1*1

101

 

 

 

 

 

 

 

11*

100

 

 

 

 

146

Их

Их

5

Их

0x0

6

Их

101

7

11х

0x1

8

X X 1

о о

5

 

X X 1

100

4

X X 1

101

7

ХІХ

100

4

ХІХ

101

7

ХІХ

010

6

Іхх

100

4

Іхх

101

7

XXX

100

4

XXX

101

7

Проделав в D всевозможные операции поглощения, получим по­ крытие D 0, являющееся исходным для дальнейшей процедуры1:

х 11

1x0

4

 

01х

6

 

1x 1

7

1x1

01х

4

 

Их

6

Их

Их

5

 

0x0

6

 

0x 1

8

X X 1

00х

5

ХІХ

010

6

XXX

100

4

 

101

7

Алгоритм получения равносильных подграфов, состоящий из Я шагов (Я •<«), аналогичен алгоритму для подграфа с одной исходящей операторной вершиной с той лишь разницей, что:

а) , если в результате X-операции получается отмеченный куб, у которого в первых т координатах стоят только единицы, то этот от­ меченный куб из покрытия удаляется. Например,

*11 1x0 У4 X Их 0x0 УѴ,

1 Для наглядности первые три координаты отделены от логической части куба и не приписываются каждому кубу, однако их наличие в этих кубах все время подразумевается.

6*

147

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