Конспект лекций по дискретной математике
Информация - Математика и статистика
Другие материалы по предмету Математика и статистика
ДНФ)
-------- ------- -----
и (3) и (3) и (2)
Схема с парафазными входами
SQ=3+3+2=12 Sa<SQ<SbSa=9Sb=9+4=13
В общем случае задержка Т=2 (схема 2-х уровневая).
При построении схемы по МКНФ элементами 1-го уровня будут ИЛИ, а 2-го И.
Схема с однофазными входами
SQ=16 T=3
В общем случае задержка схемы с однофазными входами составляет 3.
При построении схемы с однофазными входами целесообразно выбирать такую минимальную форму (если она не единственная) которая содержит наименьшее число инверсий над разными элементами.
При наличии единственной минимальной нормальной формы можно осуществить ее преобразование с использованием закона двойного отрицания и двойственности (Де Моргана)
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=4.
- Сокращенный булев базис (И, НЕ).
При использовании этого базиса необходимо из используемого выражения удалить все операции дизъюнкции, заменив их на конъюнкции и отрицания.
Используя предыдущие преобразования можно построить схему как с парафазными так и с однофазными входами.
Схема с парафазными входами :
SQ=16 T=4
При построении схемы на элементах базиса И, НЕ по МДНФ задержка схемы в общем случае составляет 4. А при использовании однофазных входов 5.
- Универсальные базисы И-НЕ и ИЛИ-НЕ (см. Практику).
Задача факторизации (факторного преобразования) булевой функции.
Факторизация булевой функции сводится к вынесению за скобки общих частей термов, что, как правило, приводит к уменьшению цены синтезируемой схемы.
_ _ _ _ _ _ _ _ _ _ _ _
y=x1x2x3 v x1x2x4 v x4x5 v x6= x1x2(x3v x4)v x4x5v x6=
SQ=12SQ=10 T=3
_ _ _ _ _ _ _ _ _
= x1(x2x3v x2x4 v x5 )vx6= x1(x2(x3v x4)v x5)vx6
T=4 SQ=11 T=5 SQ=10
Решение задачи факторизации приводя к уменьшению цены схемы увеличивает ее задержку.
_ _ _ _ _
- y= x1x2(x3v x4)v x4x5v x6SQ=10 T=3
- y= x1(x2(x3v x4)v x5)vx6T=5 SQ=10
_ _ _ _
В тех случаях, когда схема синтезируется при ограничении на число входов в элементы, равное 2, предпочтение следует отдавать скобочной форме 2.
SQ=10 T=3
T=3 SQ=10 Квх=2
T=5 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
Оценка эффекта факторизации.
Этот эффект характеризуется разностью цен схемы до и после факторизации.
Можно показать, что для однократной факторизации ее эффект определяется выражением :
SQ= SQдо - SQпосле=m(k-1)+q- ,
где m - количество букв, выносимых за скобки;
k - количество термов, из которых происходит вынесение. q - количество термов, в которых после вынесения осталась одна буква (qk);
=1, если вынесение осуществляется из всех термов;
=2, если не из всех.
Для эффективного решения задачи факторизации необходимо учитывать следующий момент :
- При наличии у булевой функции нескольких минимальных форм целесообразно выбрать из них такие, для которых применение факторизации даст выигрыш в цене схемы.
- При минимизации не полностью определенной булевой функции может оказаться, что максимальный эффект за счет факторизации дает нормальная форма, не являющаяся минимальной.
Пример :
|10x1 _ _
cmin(f)=|xx10МДНФ y=x3x4vx1x2x4SQ=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) через вспомогательную промежуточную функцию (z), где zx.
В частном случае имеет место так называемая простая разделительная декомпозиция, при которой множество аргументов x разделяется на два непересекающихся подмножества (z,w(zw=;zw=x)) и приведение исходной функции к виду f(x)=f((z,w)).
Пример : f3(x)=V(1,2,4,7)
(f=1)
z=(x2x3) W={x1}
_ _
(z)=x2x3vx2x3
_ _
f(x)=x1(z)vx1(z) SQ=13
SQ=13T=5
Схема базиса Жигалкина.
SQ=4T=2
Применение декомпозиции там, где он уместно, во многих случаях позволяет уменьшить цену синтезируемой схемы.
_ _ _ _ _ _ _ _ _ _
МДНФ y=x1x2x3x4vx2x5vx3x5vx4x5=x1x2x3x4vx5(x2vx3vx4)
SQ=14
_
(z)=x2vx3vx4
___ _
f(x)=x1*y(z)vx5*(z)SQ=10
Синтез многовыходных комбинационных схем.
МКС представляется в виде обобщенного черного ящика
Закон функционирования МКС представляется в виде системы булевых функций
|y1=f1(x1...xn)