Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.

§4.7. Синтез логических структур в топологических базисах 331

Уровнем типа А называется подмножество Х'А множества

букв X — {х,/ i = 1, ..., т } такое, что:

1) У fxi = R, У fxixj = 0, (4-14)

х>еХл ифХ] t

X11 Xj £Хд

где /х< — собственная частота буквы Xi\ fXiX. — взаимная частота

пары букв xi, Xj; R — число простых импликант в ДНФ функции

f{X), которое обычно называют рангом ДНФ; буквы являются

первичными термами рассматриваемой функции;

2) в структурном графе, реализующем эту функцию, найдется

ярус, вершины которого взаимно однозначно взвешены буквами

подмножества Х'А, так что не найдется ни одной вершины, не

принадлежащей этому ярусу и взвешенной буквой х,- (х, £ Х'А).

Уровнем типа В называется подмножество Х'в множества X

такое, что для него справедливо первое условие предыдущего опре

деления и не справедливо второе условие.

При взвешивании яруса в структурном графе буквами подмно

жества Хв так, чтобы ни одна буква х,- (х, G Хв ) не повторялась

дважды в структурном графе, получаем граф, не эквивалентный

искомому с числом путей, превосходящим R. Для удаления лиш

них путей в полученном графе необходимо расщепить некоторые

буквы подмножества Х'в . После расщепления расширенное под

множество Х'в преобразуется в подмножество, образующее уровень

типа А.

Операцию приведения уровня типа В к уровню типа А назовем

операцией расщепления первого типа.

Подграф G'(va) = (V', U') графа G = (V, U) называется под

графом с начальной вершиной va, если для каждой его вершины

Vi 6 V' имеется хотя бы один путь [и„, ..., и,].

Вершина Vj называется покрывающей вершину и,, если в гра

фе G = (V, U) имеется дуга вида (v,-, Vj) 6 U.

Расщепление первого типа производим в следующем случае.

Пусть построено I ярусов структурного графа G, причем вер

шины 7-го яруса взвешены множеством первичных термов X/, и

пусть в этом ярусе содержатся две вершины, и, и Vj, с весами

соответственно х,- и xj (х,, ху 6 X/) такие, что при построении

(I + 1)-го яруса множества весов и вершин, покры

вающих соответственно и^(х,) и fj(x j), являются пересекающи

мися:

*(J+i)i п *(»+!); ^ 0 ‘

Тогда, если подграф с начальной вершиной va, взвешенной

первичным термом ха (ха € Х^+ П Х{1+1^) и покрывающей

332

Гл. 4. Теория формальных грамматик и автоматов

и,(ж,), и подграф с начальной вершиной vp, взвешенной тем же

первичным термом ха и покрывающей вершину Vj(xj), реализуют

различные булевы функции, то вес ха расщепляется.

Уровнем типа С называется подмножество Х'с множества

букв X такое, что:

1) Y 1 ъ * °; (4-15)

xi€X'c х ,ф х3

xi I xj ^ С

2) подмножество Х'с является покрытием матрицы инцидент

ности, задающей функцию f(X).

Например, пусть задана булева функция

/(х 1, х2, х3) = х\х2х3 V V ххх2хг,

мограф которой имеет следующий вид:

GM(f) = (V, 52, 53>,

V = {zi, xi, х2, хз, х3}, S2 = { { ii, хз}})

S3 = {{xi, Х2, х3}, {xi, *2, Хз}}.

Определим подмножества букв, которые могут претендовать на

взвешивание вершин первого яруса искомого структурного графа.

Очевидно, что претендентом на веса первого яруса могут быть

уровни типа А или С.

Подмножество букв, претендующее взвесить первый ярус, дол

жно покрывать своими элементами все строки матрицы инцидент

ности

II Х2 Хз Хз

2 '

Согласно матрице инциндентности имеем следующие покрытия

этой матрицы:

{xi, x j , {хь х2}, {xi, х3}, {х2, х3}, {х3, х3}.

Первое и последние подмножества являются уровнями типа А,

остальные — типа С.

Операцией расщепления второго типа будем называть при

ведения уровня типа С к уровню типа А или В.

При расщеплении второго типа из подмножества Х'с удаляются

расщепленные элементы, образующие подмножество Хр такое, что

£ -ki = £ ~ £ fxixi~ £ fxixr /, 1ЙЧ

х&Хр xieX'c xi,xj€X/3 xitxjex>c (4-16;

1 0

0 1 0

§4.7. Синтез логических структур в топологических базисах 333

При расщеплении второго типа порождаются новые подмноже

ства уровней типов А, В к С.

Результат операции расщепления первого типа есть повторе

ние некоторых букв внутри одного яруса, а результат операции

расщепления второго типа есть повторение некоторых букв между

ярусами.

Используя введенные понятия, можно предложить следующий

метод синтеза структурных графов.

Для снижения трудоемкости при синтезе оптимальных струк

турных графов в предлагаемом методе используется понятие про

изводной от модели.

Подграф с начальной вершиной и,, являющийся концом дуги

(i)j, и,), будем называть подграфом, покрывающим вершину Vj

(рис. 4.45, а)

Рис. 4.45

Объединение подграфа с начальными вершинами и,х, и,2,...

..., Vim, являющимися концами дуг, начала которых есть вер

шины vjl , Vj3, . . Vjn, образующие подъярус, будем называть под

графом, покрывающим подъярус {t>j,, Vj2, ..., Vjn} (рис. 4.45,6).

Матрица инциндентности Q = [?,_,] модели Ф, по которой про

изводится оценка в предлагаемом методе, строится следующим

образом. Каждой строке взаимно однозначно сопоставляется пер

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

вень и

' 1, если веса вершин подграфа, покрывающего

_ J подъярус, взвешенный j-u подуровнем,

1 содержат i-й первичный терм,

. О в противном случае.

334 Гл. 4. Теория формальных грамматик и автоматов

Уровни, взвешивающие начальные вершины подграфов, покрываю

щих вершины построенного яруса, будем оценивать с помощью

функции

( дЛ и ,Л_1 =

____

\dS{'3)) / i- 2 /о + Л ’

являющейся обратно пропорциональной производной 9Ф/95 от

модели Ф и характеризующей степень пересечения этих уровней.

В качестве уровня, взвешивающего синтезируемый ярус, будем

выбирать уровень с максимальной оценкой.

Заметим, что понятия уровень и ярус совпадают, если булева

функция является решетчатой. В этом случае уровень является

идентификатором яруса.

Перед изложением метода синтеза рассмотрим случай неоди

наковой длины путей синтезируемого графа. В этом случае имеем

четвертый тип уровня — уровень типа D.

Подмножество Х'в множества X называется уровнем типа D,

если выполняются следующие условия:

1) Y 1 ь < Е = °; (4л?)

xi£.X'D x i,x jE X 'D

x .^ X j

2) не существует такого элемента хт € X, включение которого

в подмножество X'D приводит подмножество X'D к уровню типа А.

Проиллюстрируем введенное понятие на следующем примере.

Пусть дан граф (рис. 4.45, в), реализующий булеву функцию

}(хЪ Х2, ■ ■ ., Is) = Х1Х3Х6 v XiX4X6 V X!X4XS V 12*8 V

V х2х5х6 V х2хъх7.

Уровнем типа D является подмножество первичных термов

{ l 3, * 4 , *5'}-

Предлагаемый алгоритм осуществляет синтез структурного

графа по ярусам, т. е. на каждом шаге синтеза находятся пер

вичные термы Xs такие, что

Е Е /«ч = »■

xi Xi,Xj&Xs

x ,jtx j

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

мов (уровней типа А) необходимо в уровень типа D включать пер

вичный терм Xd такой, что

/х,I = R ~ У ^ /х,1 fxixi — 0, Xi 6 Xjj.

*,eX'D

С помощью такого включения производится выравнивание длин

путей.

§4.7. Синтез логических структур в топологических базисах 335

В рассматриваемом примере при синтезе булева графа в ка

честве подуровней, взвешивающих подграфы, покрывающие вер

шины, с весами хх и х2, выбираем соответственно { х з , 14} и

{xs, х8}.

Очевидно, что подграф Нх покрывающий вершину с весом хв,

является частью подграфа НХ4, покрывающего вершину с весом

Z4, и, следовательно,

/irgi /?Г* )

где /Wgl — взаимная частота подуровней, взвешивающих подгра

фы HXt и НХ1; /*« — собственная частота подуровней, взвешиваю

щих подграф HXt.

Частоты /тгл и /Wg вычисляются по матрице инцидентности

модели Ф, построенной на этом шаге синтеза.

Опишем процедуру выравнивания длин путей.

1. Отыскивается пара первичных термов х, и xj, для которых

справедливо U%] = fnj.

2. Проверяется равенство длин путей, началом которых явля

ются соответственно вершины, взвешенные х{ и xj.

3. Если длины путей не равны, то в покрытие вершины, вхо

дящей в путь с меньшей длиной, включается расщепленный ее

вес.

Для рассматриваемого примера повторяем вес Xg (рис. 4.45, г).

Входной информацией для алгоритма синтеза структурных

графов является матрица инциндентности модели Ф, задающая

ДНФ функции /.

Опишем теперь алгоритм синтеза структурных графов.

1. Выделяем множество уровней типов

А и С, претендующих

на взвешивание первого яруса. Каждый уровень выделяется с

помощью покрытия в матрице инциндентности строк столбцами.

Каждое покрытие взаимно однозначно сопоставляется выделяемо

му уровню.

Число выделенных уровней определяет число различных

структурных графов, которые необходимо построить для поиска

графа минимальной сложности.

Выбираем уровень, соответствующий первому покрытию ма

трицы инциндентности.

2. Для каждого первичного терма х,- в выбранном уровне по

строим подматрицу инциндентности, соответствующую подграфу,

покрывающему вершину с весом х,-.

Покрытием подматриц инциндентности находим подуровни,

взвешивающие вершины следующего яруса.

3. Для найденного множества подуровней В = {Ь,/ i = 1, ...

..., N} строим модель для оценки уровней, претендующих на

взвешивание строящегося яруса.

336

Гл. 4. Теория формальных грамматик и автоматов

Каждый уровень X/ = {bj/ j = 1, . . к} оцениваем с помощью

функции

р(Х,) =

,=1 j=.+i •'* “J,3 1 J3

где частоты /,-, Д,, fj являются элементами частотной матрицы

отношений F(4f) (-Р(Ф) = Qr X Q).

4. При наличии нескольких максимальных значений оценок,

полученных в п. 3, оцениваем число расщеплений первого типа как

расщеплений, оказывающих наибольшее влияние на сложность

синтезируемого графа.

Выбираем уровень с наибольшим значением p(Xj); при нали

чии уровней с несколькими максимальными значениями p(Xi)

выбираем из них уровень с минимальной оценкой числа расщеп

лений первого типа.

5. Производим выравнивание длин путей.

6. Если структурный граф не построен, т. е. порядковый номер

синтезированного яруса не равен максимальной длине пути графа,

то переходим к п. 2, в противном случае производим подсчет слож

ности

L(Hk) синтезированного графа.

7. Если L(Hk) = n(f) (n(f) — число первичных термов исход

ной ДНФ функции /), то получена бесповторная реализация графа

и осуществляем переход к п. 9.

Если Ь(Нк) > n(f), то выбираем граф Н из следующего соот

ношения: , .

L(H) = min

где L(Hk-i) — сложность графа, полученного на предыдущем

этапе; L(Hk) — сложность графа, полученного на данном этапе.

8. Выбираем следующий элемент из множества уровней, пре

тендующих на покрытие первого яруса, и переходим к п. 2. Если

для всех уровней, полученных в п. 1, графы синтезированы, то

переходим к п. 9.

9. Конец.

Проиллюстрируем предлагаемый метод синтеза структурных

графов на следующем примере.

Пример 4.6. Синтезировать структурный граф, реализующий булеву функ

цию вида

f(x 1, Х2, . . ., xs) = XlXlXs V ХуХзХа V Х1Х3Х5 V Х1ХЗХ4 V 11X3X5 V Х2Х4Х5.

Заданной ТДНФ этой функции соответствует матрица инцидентности вида

*1 *2 *3 *3

*4 х4

0 1 0

0 0

0 1

0 0 0 1 0

0 0 1 2

0 1

0 0 0 1 0 3

1 0

0 0 1

0 0

1 0

0 0 0

1 5

0 0 1

0 1 0

1 0

Е Е Т . - ё г г г . ( « 8 )

§4.7. Синтез логических структур в топологических базисах 337

Выделяем множество претендентов иа первый ярус. Каждый претендент на

взвешивание первого яруса является покрытием матрицы инцидентности (уров

нем типа А или С). В иашем случае имеем следующие покрытия:

{Х1,ХЗ,Х5}, {xi,x5,x5},

{Xl, Xl, Х4}, {^2i ХЗ, Хз}, {*4, X5, 15},

{Xl, 11, 15}, {xj,x3,r 5}, {xi, X2, Г4, XS},

{Xl, X2 , X3}, { l3 , X4, Is} , {Xl, X4, X4, I 5},

{Xl, X3, 14}, {хз, X5, X5}, {xi, Xj, X3, X5}.

Всего имеем 15 покрытий (|Хд U Х'с \ = 15). Следовательно, для нахождения

графа минимальной сложности необходимо синтезировать 15 графов и выбрать

граф с минимальной сложностью.

Взвесим первый ярус уровнем {xi, xi, хг}, расщепив хг. Элементам выб

ранного уровня соответствуют подматрицы

Q* 1 —

Х2 хз

ХЗ

Х4 Х4 Х5

Х5

0 0

1 0

0 0

0 1

0 0 0 1 0 0

0 0 0

0 0 0 1 0

х2

хз

Х4

Х5 Х5

1°

0 0

°1

|о

0 0

Х2

®3

хз Х4

Х4

Х5

1°

0 0 0

1 0

0)1

Q*?

Длина всех рассматриваемых слов одна и та же.

Производя покрытие подматриц QXl, Qix и Q*a, выделяем подуровни. В

результате покрытия подматрицы QXl имеем следующие множества:

{is, Х5}, {х г, х з, х з }, {х з, Х5}, {х г , Хз, Х5}.

Подуровни {хз}, {?4, xs} образуют множество покрытий подматрицы Qix.

Покрытиями подматрицы Q*, являются {х<}, {15}.

Весе подграфов, покрывающих полученные подуровни, образуют следующие

множества:

для подуровней буквы x i

6 1(15 , Х5) = { x j, х з, х з }, Ьз(Х2, Хз, хз) = { х 5, x s },

Ь г(хз, х 5) = { x j, хз, х 5}, bt(x2, Хз, хц) = { х 3, x s } ;

для подуровней буквы xi

65(13) = {Х4, Х5}, Ь«(Х4, х 5) = {х 3};

для подуровней буквы х2

br(xs) = {х4}, Ьв(х4) = {х5}.

Матрица инциидеитности имеет следующий вид:

<?(*) =

Ь 2

Ьз

Ъ<

Ь5 h

1 1 0 0

0 0 0

Х2

0 0 1

ХЗ

1 0 0 0 0 0

Хз

0 0 0 0

0 0

Х4

0 0

1 0 0 0

Х4

1 0

0 0 0 1

Х5

0 0 1 1 1 0 0

Х5

338

Гл. 4. Теория формальных грамматик и автоматов

Каждый уровень, взвешивающий синтезируемый ярус, оценивается суммар

ной величиной обратных значений производных, вычисленных для каждой пары

подуровней, входящих в оцениваемый уровень:

p(b1 ,bSlbr) = Е Е /. - 2 fij + f, = fi - 2/is + fs +

i* ’i % }

+ fl — 2 / l7 + /7 + /5 — 2fsr + / 7 = Q + Q + Q = 0 ’

p(b 1 ,Ь,,Ьт) h _ //ig + fs + f l _ 2д т + /t +

+ / T -lf„ + /7 = 3 ™ ' 1+ T +0 + 0 = 0,5,

Р(ЬЗ’ Ь5’ M = Л -2/35 + Л + / г ^ ё + /8 +

= 1 + 1 + 0 = j 5

/5 - 2/58 + /8 2 — 2-1+2 2 — 2-1 + 1 2 — 2-0 + 1 ’ ’

Оценка принимает наибольшее значение для уровня {Ьз, 65, Ь8}, элементы

которого выбираются в качестве весов второго яруса. Следовательно, вершины

второго яруса взвешивают подуровни

Ьз = {*2, хз, хз}, 65 = {хз}, 68 = {х4}.

Подматрицы иициндентности, соответствующие хз € Ьз и хз € 65, не равны

друг другу, следовательно, имеем расщепление первого типа буквы хз.

а б

Рис. 4.46

Дальнейшее построение искомого графа однозначно. Сложность получен

ного структурного графа (рис. 4.46,а) равна 11 (L(ifi) = 11). Остальные 14

структурных графов проектируются аналогичным образом.

Трудоемкость.алгоритма проектирования структурного графа

оптимальной сложности существенно уменьшается, если произве

сти оценку покрытий в п. 1 с помощью функционала

¥> = Е ]/ « --Д + Y1 (4-19)

где i, j — элементы покрытия; Д,- — частоты букв; R — число

слов мографа.

§4.7. Синтез логических структур в топологических базисах 339

Этот функционал показывает удаленность элементов покрытия

от условий взвешивания этими элементами яруса синтезируемого

графа Н согласно (4.13).

С учетом такой модификации п. 1 алгоритма поиска оптималь

ного структурного графа среди 15 графов заменяется на поиск

среди трех графов, которым соответствуют покрытия с минималь

ным значением (4.19). Этими покрытиями являются покрытия

{ i l l ®1, * 4 } i { х2, *3, 13)1 ( l4 ) х5, Хб}

с оценкой функциойала, равной нулю.

Последние два покрытия порождают абсолютно минимальные

структурные графы (рис. 4.46,6).

Переход Н —► S от структурного графа Н к переключательной

схеме S в базисах первого и третьего топологических классов осу

ществляется тривиально: заменой вершин на ключевые элементы,

дуг — на соединительные каналы с односторонней проводимостью

и включением выходного сопротивления в эмиттерную цепь. За

метим, что включение этого сопротивления в коллекторную цепь

соответствует реализации отрицания заданной булевой функции.

При преобразовании Н S в базисах второго топологического

класса возможно появление лишних путей из-за двусторонней про

водимости соединительных кана

лов, если структурный граф Н со

держит подграф Qb, изображен

ный на рис. 4.47, а. При снятии

ориентации дуг (рис. 4.47,6) не

сравнимые элементы становятся

сравнимыми и появляется лиш

ний путь, что выводит граф из класса эквивалентных в смысле

реализации заданной функции графов. Для ликвидации лишних

путей необходимо ориентировать диагональное ребро, помещая на

него развязывающий диод (рис. 4.47, в).

Утверждение. Граф Q в (рис. 4.47, а) является запрещен

ной фигурой преобразования Н S в базисах второго тополо

гического класса.

Следовательно, минимизация развязывающих диодов сводится

к покрытию семантической таблицы, в которой запрещенными

фигурами являются подграфы Qb, а их компонентами — диаго

нальные ребра, в которые помещаются развязывающие диоды.

Переход Н —► S в базисах второго топологического класса осу

ществляется, как и в базисах первого класса, ориентацией диа

гональных ребер в запрещенных фигурах Qb- Например, пе

реключательная схема, реализованная на МОП-транзисторах по

структурному графу Н (рис. 4.46,6), соответствующему покрытию

{2Г4, 15, 15}, имеет вид, изображенный на рис. 4.48, а.

При преобразовании Н S в базисах этого класса абстрак

цией переключательной схемы (рис. 4.48, а) является линейный

а б в

Рис. 4.47

340

Гл. 4. Теория формальных грамматик и автоматов

граф (рис. 4.48,6), дуги которого взвешены первичными термами

или единицами, соответствующими разрывающим диодам. Линей

ный граф получается заменой вершин структурного графа Н ду

гами с теми же весами при сохранении исходных путей.

При преобразовании Н -+ S в базисах четвертого топологиче

ского класса возможно появление лишних путей не только из-за

двусторонней проводимости соединительных каналов, но и в ре

зультате двусторонней проводимости элементов. При этом лишние

пути возникают, если структурный граф содержит подграф Qi, го

меоморфный подграфу Qb-

Утверждение. Запрещенной фигурой Qp (рис. 4.49, а) пре

образования Н -r¥ S в базисах четвертого топологического

класса является подграф, гомеоморфный фигуре Qb-

Рис. 4.49

В рассматриваемом структурном графе Н (см. рис. 4.46,6) при

его преобразовании в переключательную схему четвертого тополо

гического базиса запрещенными фигурами будут подграфы Qbi и