Синтез комбинационных схем. Довгий П.С - 24 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

Составители: 

Рубрика: 

24
),(
31
xx
ϕ
ϕ
=
.
31
xx ∨=
.16,2.
31
==∨=
f
QQ
SSxx
ϕ
ϕ
2.5. Преобразование минимальных форм булевой функции
МНФ, как правило, не дают абсолютного минимума цены схемы S
Q
,
реализующей заданную функцию. В связи с этим после нахождения
МДНФ и МКНФ производится их дальнейшее преобразование путем ре-
шения задач факторизации и декомпозиции.
Эффект факторного преобразования, связанный с изменением цены
схемы ΔS
Q
за счет вынесения m букв из k термов МНФ, можно оценить вы-
ражением
ΔS
Q
= m (k-1) + p - Δ,
где p – число термов, в которых после вынесения m букв остается од-
на буква (p
≤
k); Δ=1, если вынесение производится из всех термов МНФ,
или Δ=2, если не из всех.
Факторное преобразование для МДНФ:
=∨∨∨∨∨=
43214214325425153
xxxxxxxxxxxxxxxxxf
(S
Q
=23)
=∨∨∨∨∨=
43213142542315
)()( xxxxxxxxxxxxxx
(S
Q
=20)
.))((
432154254231
xxxxxxxxxxxx ∨∨∨∨=
(S
Q
=18) (3)
Решим задачу декомпозиции применительно к полученной форме.
Для этого введем вспомогательную функцию
Инверсия этой функции имеет вид
С учетом новой функции выражение (3) преобразуется к виду:
.)(
4
2
5425
42
xxxxxxxxf ⋅∨∨∨⋅=
ϕϕ
(4)
Реализация комбинационной схемы по выражению (4) с учетом затрат
на вспомогательную функцию
ϕ
и ее инверсию дает цену схемы S
Q
=18, та-
кую же, как и для схемы, построенной по форме (3), но задержка схемы
будет больше (Т=4τ,).
Факторное преобразование для МКНФ:
=∨∨∨⋅∨∨∨⋅
⋅
∨∨∨
⋅
∨∨⋅∨=
)()(
)()()(
54215432
532143142
xxxxxxxx
xxxxxxxxxf
(S
Q
=22)
)19().(
)5()())((
5321
315423124
=∨∨∨⋅
⋅
∨∨∨
⋅
∨∨=
Q
Sxxxx
xxxxxxxxx
Следует отметить, что вынесение x
4
из первых двух термов МКНФ не
дает уменьшения цены схемы: ΔS
Q
= 0 (m=1, k=2, p=1, Δ=2), однако являет-
.
3
1
xx=
ϕ

Страницы