Конспект лекций по дискретной математике (стр. 8 из 14)
8) В реальных системах элементов как правило используется значительное разнообразие логических элементов, относящихся к разным базисам. Тем не менее построение схемы в рамках определенного базиса является достаточно актуальной задачей, так как позволяет уменьшить номенклатуру используемых элементов.
Построение комбинационных схем (КС) по минимальным нормальным формам в различных базисах.
1) Булев Базис (И, ИЛИ, НЕ)
_ _ _ _ _ _ _
y=x1x2x3vx1x2x4vx1x5vx6 (МДНФ)
-------- ------- -----
и (3) и (3) и (2)
Схема с парафазными входами
SQ=3+3+2=12 Sa<SQ<Sb Sa=9 Sb=9+4=13
В общем случае задержка Т=2t (схема 2-х уровневая).
При построении схемы по МКНФ элементами 1-го уровня будут ИЛИ, а 2-го И.
Схема с однофазными входами
SQ=16 T=3t
В общем случае задержка схемы с однофазными входами составляет 3t.
При построении схемы с однофазными входами целесообразно выбирать такую минимальную форму (если она не единственная) которая содержит наименьшее число инверсий над разными элементами.
При наличии единственной минимальной нормальной формы можно осуществить ее преобразование с использованием закона двойного отрицания и двойственности (Де Моргана)
ººº===ºººº==º===ººººº=--ºººº-º==-ºº
y=x1x2x3 v x1x2x4 v x4x5 v x6= x1x2x3* x1x2x4* x4x5* x6=
-------------------------------------------
=( x1v x2v x3)( x1v x2v x4)( x4v x5)* x6
Для реализации этой схемы понадобятся три инвертора.
По сравне6нию с предыдущей схемой цена уменьшается на единицу (SQ=15). Однако наличие выходного инвертора приведет к увеличению цены схемы T=4t.
2) Сокращенный булев базис (И, НЕ).
При использовании этого базиса необходимо из используемого выражения удалить все операции дизъюнкции, заменив их на конъюнкции и отрицания.
Используя предыдущие преобразования можно построить схему как с парафазными так и с однофазными входами.
Схема с парафазными входами :
SQ=16 T=4t
При построении схемы на элементах базиса И, НЕ по МДНФ задержка схемы в общем случае составляет 4t. А при использовании однофазных входов 5t.
3) Универсальные базисы И-НЕ и ИЛИ-НЕ (см. Практику).
Задача факторизации (факторного преобразования) булевой функции.
Факторизация булевой функции сводится к вынесению за скобки общих частей термов, что, как правило, приводит к уменьшению цены синтезируемой схемы.
_ _ _ _ _ _ _ _ _ _ _ _
y=x1x2x3 v x1x2x4 v x4x5 v x6= x1x2(x3v x4)v x4x5v x6=
SQ=12 SQ=10 T=3t
_ _ _ _ _ _ _ _ _
= x1(x2x3v x2x4 v x5 )vx6= x1(x2(x3v x4)v x5)vx6
T=4t SQ=11 T=5t SQ=10
Решение задачи факторизации приводя к уменьшению цены схемы увеличивает ее задержку.
_ _ _ _ _
1) y= x1x2(x3v x4)v x4x5v x6 SQ=10 T=3t
_ _ _ _
2) y= x1(x2(x3v x4)v x5)vx6 T=5t SQ=10
В тех случаях, когда схема синтезируется при ограничении на число входов в элементы, равное 2, предпочтение следует отдавать скобочной форме 2.
1)
SQ=10 T=3t
T=3t SQ=10 Квх=2
2)
T=5t SQ=10 Квх=2
Схема построенная по схеме 2 удовлетворяет ограничению на число входов и является более предпочтительной по сравнению со схемой 1 по критерию цены схемы, а по критерию минимальной задержки - лучше схема 1.
Пример факторного преобразования для МКНФ
_ _ _ _
y=(x1vx2vx3)(x1vx2vx4)(x1vx5)= SQ=11
_ _ _
=( x1vx2vx3 x4)(x1vx5)= SQ=9
_
=x1v(x2vx3)( x2vx4) x5= SQ=9
_ _
= x1v(x2vx3 x4) x5= SQ=8
Оценка эффекта факторизации.
Этот эффект характеризуется разностью цен схемы до и после факторизации.
Можно показать, что для однократной факторизации ее эффект определяется выражением :
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
Синтез многовыходных комбинационных схем.
МКС представляется в виде обобщенного «черного ящика»
Закон функционирования МКС представляется в виде системы булевых функций
|y1=f1(x1...xn)
|y2=f2
|.
|.
|.
|yn=fn
Естественным образом, при решении задачи синтеза МКС применяются методы факторизации и возможной декомпозиции, применительно не к одной функции, а к системе.
Минимизация системы Булевых функций
Задача минимизации применительно к системе Булевых функций решается аналогично как для одной функции и сводится к получению минимального покрытия. Для решения этой задачи система приводится к одной функции путем дополнения множества агументов подмножеством вспомогательных переменных, с помощью которых выделяются отдельные функции системы. Количество вспомогательных переменных k³log2m, m - количество функций.
Пример:
Раздельная минимизация:
y1 Cmin (y1)=
y2 Cmin (y2)=
МДНФ:
При построении схемы по этому выражению, она разлагается на две независимые подсхемы, отдельные для реализаций каждой функции.
Совместная минимизация
Пусть V=0 для у1; V=1 для y2