Задача факторизации (факторного преобразования) булевой функции.

Факторизация булевой функции сводится к вынесению за скобки общих частей термов, что, как правило, приводит к уменьшению цены синтезируемой схемы.

_ _ _ _ _ _ _ _ _ _ _ _

y=x₁x₂x₃ v x₁x₂x₄ v x₄x₅ v x₆= x₁x₂(x₃v x₄)v x₄x₅v x₆=

S_Q=12 S_Q=10 T=3t

_ _ _ _ _ _ _ _ _

= x₁(x₂x₃v x₂x₄ v x₅)vx₆= x₁(x₂(x₃v x₄)v x₅)vx₆

T=4t S_Q=11 T=5t S_Q=10

Решение задачи факторизации приводя к уменьшению цены схемы увеличивает ее задержку.

_ _ _ _ _

1) y= x₁x₂(x₃v x₄)v x₄x₅v x₆ S_Q=10 T=3t

_ _ _ _

2) y= x₁(x₂(x₃v x₄)v x₅)vx₆ T=5t S_Q=10

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

1)

S_Q=10 T=3t

T=3t S_Q=10 К_вх=2

2)

T=5t S_Q=10 К_вх=2

Схема построенная по схеме 2 удовлетворяет ограничению на число входов и является более предпочтительной по сравнению со схемой 1 по критерию цены схемы, а по критерию минимальной задержки - лучше схема 1.

Пример факторного преобразования для МКНФ

_ _ _ _

y=(x₁vx₂vx₃)(x₁vx₂vx₄)(x₁vx₅)= S_Q=11

_ _ _

=(x₁vx₂vx₃ x₄)(x₁vx₅)= S_Q=9

_

=x₁v(x₂vx₃)(x₂vx₄) x₅= S_Q=9

_ _

= x₁v(x₂vx₃ x₄) x₅= S_Q=8

Дата добавления: 2015-08-02