ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.10.2024
Просмотров: 124
Скачиваний: 0
при таком построении по сравнению с непосредственной реализацией формулы (6-6) составит
ДѴ = тп —т —2 + г = /п (п — 1) —2 + г.
Задачу вынесения общего множителя за скобки, в отличие от за дачи в следующем параграфе, будем называть вынесением вверх по аналогии с тем, что общий множитель выносится над схемой «ИЛИ». Рассмотрим один из возможных алгоритмов вынесения вверх на при мере формулы (6-3). Пересечения множеств букв, входящих в конъюнк ции Х 4, . . . , Х 5, дают всевозможные наибольшие общие части, по лученные попарным сравнением. Эти общие части могут быть выне сены вверх1:
X j= |
1, |
2, |
3, |
4, |
5, |
6, 7, |
11 |
|
|
Хг |
|
|
X, |
|
||
Х .= 1, 2, 3, |
8 |
|
|
|
|
1, 2, |
3 |
|
|
|||||||
Х3= |
1, |
2, |
5, |
6, |
10, |
11, |
12 |
1, |
2, |
5, |
6, |
11 |
1, |
2 |
X, |
|
Х4 = |
5, |
6, |
9 |
|
|
|
|
|
|
5, |
6 |
|
|
— |
|
5, 6 |
Х5=- 1, |
2, |
5, |
6, |
10, |
12, |
13 |
|
1, |
2, |
5, |
6 |
1, 2 |
1, 2, 5, 6, 10, 12 |
|||
В нашем примере это будут общие части:
2 д = 1, 2, 3 |
(Xlt |
Х2); |
Za= l , |
2, 5, 6,11 (Х4, Х3); |
|||
Za = 5, |
6 (Xu |
Х3, Xu |
Хв); |
Z4= l , |
2, 5, 6 |
(Х4, X3, X5); |
|
Z6= l , |
2 (Xu |
X a, |
X 3, |
X5); Z0= l , |
2, 5, 6, |
10,' 12 (X3, XB). |
|
В скобках после общей части указаны конъюнкции, в которые она входит.
По приведенным выше формулам легко подсчитать цену каждой из общих частей Z4, . . . , Z0 как выигрыш, который дает вынесение этой общей части:
|
|
W(Z1) = |
2- |
W (Z2) = |
3; |
W (Z8) = 5; |
|
|
|||
|
|
W (Z4) = |
6; |
W (Z5) = |
4; |
W(Ze) = 6 . |
|
|
|||
|
На первом шаге для вынесения выбирается общая часть, имеющая |
||||||||||
наибольшую цену: |
W (Z4) = max |
(W (Z4), . . . , W (Z0)) = 6. В |
ре |
||||||||
зультате |
вынесения общей |
части |
Z4 |
из |
исходного |
множества |
слов |
||||
А 1 |
= [Хи ■■■, Х5) |
образуются |
два |
мнол<ества: |
А.г = {Х6, |
Х7, |
|||||
Х8) — конъюнкции, из которых удалены буквы, входящие в Z4 (Хе = |
|||||||||||
= |
Х 4 \ |
Z4; Х7 = |
Х3 \ |
Z4; |
Х8 = |
X, \ |
Z4), и В 2 = |
(Х2, Х4, Z4) - |
|||
конъюнкции, из которых не делалось вынесение, плюс общая часть Z4. Это разбиение иллюстрируется рис. 6-11, а, а полученная в резуль тате вынесения Z4 схема приведена на рис. 6-11, б. На рис. 6-11, a под общей частью Z4 стоит W (Z4) = 6.
1 В изложенной ниже процедуре переменные (д.у) заменены их индексами
(/). Кроме того, конъюнкции X Jt ■. . , Хь будем иногда называть словами, со стоящими из соответствующих букв.
109
Из рис. 6-11, б видно, что дальнейшее вынесение возможно только раздельно для множеств /1.2 и В 2. Продолжая аналогично отдельно для А о и В .2 до тех пор, пока не найдется ни одной общей части, имею щей цену больше нуля, получим процедуру вынесения вверх, в кото рой на каждом шаге выбирается общая часть, определяемая по наи большей цене. Такой алгоритм необязательно приведет к оптимальной схеме, так же как и алгоритм, изложенный в [17], где на каждом шаге предлагается выносить общую часть, имеющую наибольшую длину. Эксперименты над комбинационными схемами микропрограммных
автоматов |
показали, что вынесение |
по наибольшей цене в большин |
||||||
|
|
|
стве случаев дает решение, близ |
|||||
в) |
|
|
кое к оптимальному. Процедура |
|||||
|
|
вынесения |
по |
этому |
алгоритму |
|||
|
|
|
для рассмотренного |
примера |
||||
|
|
|
приведена на рис. 6-12, а. Дадим |
|||||
|
|
|
краткие пояснения |
к |
этому ри |
|||
|
|
|
сунку. Ищем пересечения слов |
|||||
|
|
|
в множестве Л 2: |
|
|
|
||
|
|
|
оX II CO |
|
|
|
|
|
|
|
|
X7=10, |
11, |
12 |
11 |
X7 |
|
|
|
|
X8=10, |
12, |
13 |
— |
10, |
12 |
|
|
|
Z7= l l ( X e, Х7); |
W (Z7) = |
— 1; |
|||
|
|
|
Z8= 10, 12 (Х7, Х8); |
W(Za) = 2. |
||||
|
|
|
Вынесение Z8 порождает |
два |
||||
|
|
|
множества, |
А 3, В 3: |
|
|
||
3 4 711 |
10 И 12 |
10 1213 |
Л з = ( Х 9, |
х 10]; x 9 = x 7\ z |
8; |
|||
|
|
|
||||||
Рис. 6-11. |
Вынесение Z4: а — условное |
Xio = X8\ Z 8; |
|
|||||
изображение процесса |
вынесения, б — |
|
||||||
|
логическая |
схема |
В3 = {Х„ |
Z8| . |
|
|||
|
|
|
|
|||||
В каждом из множеств А 3, В 3 слова не пересекаются. Дальнейшие вынесения невозможны.
Переходим к множеству ß 2:
x a= l , |
2, 3, |
8 |
*2 |
|
X4= 5, 6, 9 |
|
— |
*4 |
|
Z4= 1, 2, 5, 6 |
1,2 |
5, 6 |
||
Z0 = 1 , |
2(Х 2, |
Z4); |
W (Z9) = 0; |
|
Z10 = 5, |
6 (X4, |
Z4); |
W (Z10) = 1. |
|
110
Вынесение Z10 порождает два множества, Л4, В:і:
Л,]=(Хц, Х12); Xu = A4\ Z 10; X12 = Z.1\ Z l0; Ві — IX.,, Z10].
В каждом из множеств Л4, В4 слова не пересекаются, дальнейшие вынесения невозможны.
Рис. 6-12. Пример вынесения вверх: а — условное изображение процесса, б — логическая схема
Схема, соответствующая процедуре на рис. 6-12, а, приведена на рис. 6-12, б. Выигрыш в результате вынесений общих частей
W = W ( Z i) + W(Zs) + W(Z10) = 9.
6-7. Декомпозиция схемы из однотипных элементов
Пусть задана система функций:
f i — ХіХ^ХзХ^х^ХдХ^Хц;
f2 |
Х4.Ѵ2ХуХд , |
|
f S= |
-'-'lX2X5-*-VC10*11* 12 > |
(6-7) |
/4 = |
*5*0*9i |
|
fi — * 1* 2* 5* 0* 10*12 ■
Очевидно, что возможна минимизация схемы, реализующей эту систему функций, если предварительно построить какую-либо общую для некоторых из этих функций конъюнкцию, например х гх 2, в виде отдельного логического элемента, выход которого подать на входы схем, реализующих /у, / 2, /3, /в; при этом число входов в логические элементы уменьшится на два (рис. 6-13).
111
В общем случае пусть задано множество функций /у, |
|
, |
||
fr от множества двоичных переменных X -- |
|.ѵ,, . . . . |
.Ѵ/, |
, ,vL): |
|
ft ' xn О • • • Оxir • • • Ѳ-Ѵщ/, ( — |
l, |
T\ |
хІГ(^Х. |
|
Операция 0 есть некоторая логическая функция, например дизъюнкция или конъюнкция, но обязательно только одна из них.
X, хг
Рис. 6-13. Вынесение вниз лцаъ
Эти функции можно реализовать с помощью Т логических элементов,
каждый из которых имеет R t входов. |
Обозначим через X t (/ |
= |
1, |
. . . , |
||||||||||
Т) |
множество переменных, поступающих на входы /-го элемента. Мо- |
|||||||||||||
|
|
|
|
|
жет случиться, |
что пересечение |
||||||||
|
|
|
|
|
некоторых множеств из системы |
|||||||||
|
|
|
|
|
множеств Х 1? |
. . . , Х т не пусто. |
||||||||
|
|
|
|
|
Пусть, |
|
например, |
это |
будут |
|||||
|
|
|
|
|
первые |
|
п |
множеств |
Х г, |
. . . , |
||||
|
|
|
|
|
|
П |
|
|
|
|
|
і |
|
|
|
|
|
|
|
Хп: П |
Xj = Z Ф 0 . Тогда мно- |
||||||||
|
|
|
|
|
|
і=і |
функций |
можно |
пред |
|||||
|
|
|
|
|
жество |
|||||||||
|
|
|
|
|
ставить |
|
в |
виде |
декомпозиции |
|||||
|
|
|
|
|
(рис. 6-14), такой, что ft = f |
|||||||||
Рис. 6-14. |
Общий вид вынесения вниз |
fz), |
где |
|
X't |
-- |
X t \ |
Z; |
/ = |
|||||
П |
|
|
I |
|
== |
1, . . |
|
. , |
n. |
Ясно, |
что |
если |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
2 |
[Р |
-I-1) + P (Z) < 2 1 |
P (^/). |
T0 |
полученная |
в |
результате |
|||||||
декомпозиции |
схема имеет |
меньшую цену. |
|
В |
последней |
формуле |
||||||||
Р ( 0 ’), Р (Z) |
и Р (X,) — число элементов в множествах X ', |
Z |
и X, |
|||||||||||
соответственно. Ставится задача нахождения |
среди множества экви |
|||||||||||||
валентных схем, реализующих функции f lt . . . |
, fT, схемы с минималь |
|||||||||||||
ной ценой, выполненной в виде декомпозиции однотипных элементов (т. е. реализующих одинаковые логические функции). В отличие от задачи в предыдущем параграфе (вынесение вверх), назовем эту за
112
дачу вынесением вниз. Из рис. 6-14 видно, что выигрыш от вынесения вниз из п слов общей .части Z, состоящей из т букв, равен
|
W{Z) = m{n— \) — n + r, |
(6-8) |
где |
г — число множеств из Х г, . . . , Х Т, полностью |
совпадающих |
с Z, |
поскольку соответствующие им функции можно снять прямо с вы |
|
хода схемы для общей части Z.
Вернемся к функциям (6-7). Пересечения множеств букв, входящих в Хі, . . . , Х5, дают всевозможные наибольшие общие части, полу ченные попарным сравнением. Они могут быть вынесены вниз1:
<9
12 56
Рис. 6-15. Пример вынесения вниз: а — условное изобра жение процесса, б — логическая схема
Х г= 1, |
2, |
3, |
4, |
5, 6, 7, |
11 |
|
|
|
|
|
|
|
|
||
Х2= |
1, |
2, |
3, |
8 |
|
|
1, |
2, |
3 |
|
Хо |
|
|
||
Х3= |
1, |
2, |
5, |
6, |
10, |
11, |
12 и 2, |
5, |
6, |
11 |
1, 2 |
*3 |
|
||
X., = 5, |
6, |
9 |
|
|
|
|
5, |
|
6 |
|
|
— |
5, 6 |
*4 |
|
Хв = |
1, |
2, |
5, |
6, |
10, |
12 |
1, |
2, |
|
5, |
|
6 |
1, 2 |
1, 2, 5, 6, 10, 12 |
5, 6 |
В нашем примере это будут общие части:
Zx = |
1, |
2, 3 (Хь Х2); |
Za= l , |
2, |
5, 6, |
Щ Х ,. |
Х3); |
|||||
Z3 = |
5, |
6 (Xlt |
Xa, |
X4, |
X5);Zj = |
1, |
2, |
5, |
6 (Xu |
X,, |
X6); |
|
Z6= l , |
2 ( X lt |
X2, |
X 3, |
XB);Ze= |
1, |
2, |
5, |
6, |
10, |
12 (X3, X 6). |
||
В скобках после общей части указаны слова, в которые она входит. По формуле (6-8) легко подсчитать цену каждой из общих частей
1 См. сноску па стр. 109.
ö За к аз ■Ne 2225 |
113 |
Zx, . . . , Z0 как выигрыш, который дает вынесение вниз этой общей части:
|
W(Z1) = U |
W (Z2) = 3; |
IF (Z3) = |
2; |
|
||
|
W(Z,) = 5; |
W(Z6) = 2; |
fi/(Z0) = |
5. |
|
||
В результате вынесения |
из множества слов Х х, . . . , Х т некото |
||||||
рой общей части Z, входящей в первые п слов Х х, |
. . . , Х п, образуется |
||||||
новое множество слов по следующим правилам: |
|
|
|||||
1. Если |
некоторое слово |
из |
Х х, . . . , Х п совпадает с Z, то оно |
||||
исключается из множества слов. |
|
|
|
|
|||
2. В Х х, |
. . . , Х п множество букв, входящих в Z, заменяется но |
||||||
вой буквой |
хр, не принадлежащей алфавиту X |
— |
{хх, . . . , xL). |
||||
3. В множестве слов Х х, |
. . . , |
Х т слова Х; (і = |
1, . . . , п) заме |
||||
няются словами Х т+І = (X; \ |
Z) |
U {*„)• |
|
|
|
||
4. К полученным в пп. 1—3 словам добавляется слово Z.
. Построение нового множества слов иллюстрируется рис. 6-15. По сле вынесения общей части Z4 = 1,2, 5,6 из слов Х х, Х 3 и Х8 эти слова заменяются словами Х 6, X-, и Х 8 соответственно, в которых вместо букв 1, 2, 5, 6 появляется новая буква 13. Из полученного множества слов возможны дальнейшие вынесения. Найдем всевозможные общие части в этих словах. Так как вынесение вниз одной буквы смысла не имеет, ищем пересечения слов, имеющие не менее двух букв:
|
II |
1 |
|
|
|
|
N |
< |
|
Х4 |
= |
5, |
Х6 |
= |
3, |
|
>< |
II |
О |
|
«J |
||
Х8= ю ,
Z4= 1,
|
of |
со |
00 |
6, |
9 |
|
4, |
7, |
11, |
|
|
ю |
12, |
13 |
|
2, |
5, |
6 |
|
— |
* 4 |
|
|
|
13 |
— |
— |
*0 |
|
|
|
со |
— |
— |
11, 13 |
* 7 |
|
|
— |
— |
— |
10, 12, 13 |
*8 |
|
1, 2 |
5, 6 |
— |
— |
— |
Z7= |
1, |
2 (Х2, Z4); W (Z7) = 0; |
Z8 = 5, |
6 (Х4, |
Z4); |
W (Z8) == 0; |
||
ZB= |
11, |
13 (Xc, |
X7); W (Z9) = 0; Z10= 10, |
12, |
13 (X7t X8); |
|||
W(Z10) = 2. |
|
|
|
|
|
|
||
После |
вынесения |
общей части |
Z10 = |
10, |
12, |
13 |
получаем новое |
|
множество слов, у которых нет пересечений, содержащих более одной буквы. Логическая схема, соответствующая процедуре на рис. 6-15, а, приведена на рис. 6-15, б.
При синтезе микропрограммного автомата по ГСА после построе ния всех переходов в узлы и состояния схема может быть проминимизирована за счет операций вынесения вверх (для каждой отдельной функции) и вынесения вниз общих частей у схем «И» для различных функций. В качестве примера на рис. 6-16, а приведена схема, построен ная по табл. 6-9, представляющей собой фрагмент некоторой струк-
114