Декомпозиция булевых функций.
Построение одновыходных схем.
Оценка эффекта факторизации.
Этот эффект характеризуется разностью цен схемы до и после факторизации.
Можно показать, что для однократной факторизации ее эффект определяется выражением :
DSQ= SQдо - SQпосле=m(k-1)+q-D ,
где m - количество букв, выносимых за скобки;
k - количество термов, из которых происходит вынесение. q - количество термов, в которых после вынесения осталась одна буква (q£k);
D=1, если вынесение осуществляется из всех термов;
D=2, если не из всех.
Для эффективного решения задачи факторизации необходимо учитывать следующий момент :
1) При наличии у булевой функции нескольких минимальных форм целесообразно выбрать из них такие, для которых применение факторизации даст выигрыш в цене схемы.
2) При минимизации не полностью определенной булевой функции может оказаться, что максимальный эффект за счет факторизации дает нормальная форма, не являющаяся минимальной.
Пример :
|10x1 _ _
cmin(f)=|xx10 МДНФ y=x3x4vx1x2x4 SQ=7
|10x1 _ _ _
cmin(f)=|101x ДНФ y= x1x2x4 vx1x2 x3= x1x2(x3v x4) SQ=5
В некоторых случаях максимального эффекта за счет факторизации можно достичь путем расширения термов МНФ с применением законов товтологии
МДНФ y=x1x2x3vx1x2x4vx1x3x5x6vx2x4x5x6= SQ=18
= x1x2(x3v x4)v x5x6(x1x3v x2x4)= SQ=16
= x1x2(x1x3v x2 x4)v x5x6(x1x3v x2x4)= SQ=20
=(x1x3v x2 x4)( x1x2v x5x6) SQ=14
Задача декомпозиции булевой функции в общем случае состоит в таком разделении множества ее аргументов на ряд подмножеств, при котором можно выразить исходную функцию f(x) через вспомогательную промежуточную функцию j(z), где zÌx.
В частном случае имеет место так называемая простая разделительная декомпозиция, при которой множество аргументов x разделяется на два непересекающихся подмножества (z,w®(zÇw=j;zÈw=x)) и приведение исходной функции к виду f(x)=f(j(z,w)).
Пример : f3(x)=V(1,2,4,7)
(f=1)
z=(x2x3) W={x1}
_ _
j(z)=x2x3vx2x3
_ _
f(x)=x1j(z)vx1j(z) SQ=13
SQ=13 T=5t
Схема базиса Жигалкина.
SQ=4 T=2t
Применение декомпозиции там, где он уместно, во многих случаях позволяет уменьшить цену синтезируемой схемы.
_ _ _ _ _ _ _ _ _ _
МДНФ y=x1x2x3x4vx2x5vx3x5vx4x5=x1x2x3x4vx5(x2vx3vx4)
SQ=14
_
j(z)=x2vx3vx4
___ _
f(x)=x1*y(z)vx5*j(z) SQ=10