Цена покрытия

Цена r-куба представляет собой количество несвязанных координат. Sr=n*r

Для оценки качества покрытия используют два вида цены покрытия:

m

1) S^a=åS_rN_r, где N_r - количество r-кубов, входящих в по-

r=0

крытие, m - максимальная размерность куба. Цена S^a представляет собой сумму цен кубов, входящих в покрытие.

2) S^b=S^a+k, где k - количество кубов, входящих в покрытие

m m

S^a =å(n-r) N_r ; S^b=å(n-r)(N_r+1)

r=0 r=0

Под минимальным покрытием понимают покрытие, обладающее минимальной ценой S^a по сравнению с любым другим покрытием этой функции.

Можно показать, что покрытие, обладающее минимальной ценой S^a обладает также и минимальной ценой S^b.

Пример: f³(x)=V(0,1,4,6,7)

(f=1)

C⁰(f)=K⁰(f); S^a=5*3=15; S^b=S^a+5=20

C¹(f)=K¹(f); S^a=4*2=8; S^b=S^a+4=12

C_min(f): S^a=3*2=6; S^b=9

Цена покрытия S^a представляет собой количество букв, входящих в ДНФ, которая соответствует данному покрытию.

Цена S^b представляет для ДНФ сумму количества букв и количества термов.

Цена покрытия хорошо согласуется с ценой схемы по Квайну, которая строится по нормальной форме, соответствующей этому покрытию.

Для приведенной схемы цена по Квайну S_Q=9=S^b (9-число входов).

В принципе, между S_Q и ценами S^a и S^b существует соотношение S^a £ S_Q £ S^b Это неравенство имеет место при следующих допущениях по комбинационной схеме:

1) Схема строится по нормальной форме (ДНФ или КНФ).

2) Схема строится на элементах булевого базиса (И, ИЛИ).

3) На входы схемы можно подавать как прямые, так и инверсные значения входных переменных, представляющие собой значения аргументов булевой функции (схема с парафазными входами). Элементы НЕ (инвертора в схеме отсутствуют.

Дата добавления: 2014-11-29