Metody analityczne i komputerowe
w minimalizacji funkcji boolowskich
Metoda Quine a McCluskey a
a) generacja implikantów prostych
E selekcja implikantów (tzw. pokrycie)
System Espresso
ndu a liczba ró norodnych procedur
n procedury heurystyczne
Dane wej ciowe w postaci zbiorów kostek.
Kostka K to krotka o składowych 0, 1, * reprezentuj ca
zbiór wektorów zero-jedynkowych.
K = (0*1*), to zbiór wektorów:
0010
0011
0110
0111
Kostka reprezentuje niepełny iloczyn.
K=0*1*= x x3
1
11
Implikant funkcji boolowskiej
Implikant danej funkcji f jest to iloczyn literałów
(zmiennych prostych i zanegowanych) o nast puj cej
własno ci: dla wszystkich kombinacji warto ci
zmiennych, dla których implikant jest równy jedno ci,
równie funkcja f jest równa jedno ci.
Prosty implikant jest to implikant, który zmniejszony o
dowolny literał przestaje być implikantem.
W interpretacji tablic Karnaugha implikant prosty
odpowiada grupie jedynek (i kresek), której nie mo na
powi kszyć.
12
Ekspansja
Ekspansja jest procesem działaj cym na kostkach
zbiorów F i R, a jej celem jest uzyskanie dla danej k ~

F kostki k' tak du ej, jak to tylko mo liwe (tzn. z
mo liwie du liczb pozycji o warto ci *) i nie
pokrywaj cej adnego wektora zbioru R. W swoich
obliczeniach Ekspansja wykorzystuje tzw. macierz
blokuj c B.
Macierz blokuj ca dla danej kostki k powstaje z
macierzy R przez zanegowanie tych kolumn R, których
pozycje s wyznaczone przez pozycje jedynek w kostce
k.
13
Przykład
x1 x2 x3 x4 x5 x6 x7 f
10001010
10111100
11011100
11101110
k1 01001011
k2 10001101
k3 10100001
k4 10101101
k5 11101011
14
Ekspansja - przykład
Wyznaczymy macierz blokuj c dla f = (F,R) i
kostki k1 wiedz c, e F i R s opisane macierzami:
�0 1 0 0 1 0 1�
�
1 0 0 0 1 0 1�
�1 0 0 0 1 1 0ł
� ł
�
� ł 1 0 1 1 1 1 0ł
� ł
F = R =
�
�1 0 1 0 0 0 0ł
1 1 0 1 1 1 0ł
� ł
�1 0 1 0 1 1 0ł � ł
�
1 1 1 0 1 1 1ł
Ź ć
�1 1 1 0 1 0 1ł
Ź ć
Skoro k1 = (0100101), to dla uzyskania B wystarczy
w macierzy R "zanegować" kolumny drug , pi t i
siódm . Zatem B(k1,R):
�1 1 0 0 0 0 0�
�1 1 1 1 0 1 1ł
B =
� ł
�1 0 0 1 0 1 1ł
�1 0 1 0 0 1 0ł
Ź ć
15
Pokrycie kolumnowe
Pokryciem kolumnowym macierzy B jest zbiór kolumn
L (L {1,...,n}) taki, e dla ka dego wiersza i istnieje
kolumna j ~
L, która w wierszu i ma jedynk .
Macierz blokuj ca B(k,R) pozwala wyznaczyć
ekspansj kostki k oznaczan k+(L,k) w sposób
nast puj cy: wszystkie składowe kostki k nale ce do L
nie ulegaj zmianie, natomiast składowe nie nale ce do
L przyjmuj warto ć *.
Ekspansja kostki k jest jest implikantem funkcji f =
(F,R). W szczególno ci k+(L,k) jest implikantem
prostym, gdy L jest minimalnym pokryciem
kolumnowym macierzy B(k,R).
16
Ekspansja - przykład c.d.
Dla kostki k2 = (1000110) i macierzy B:
1 2 3 4 5 6 7
�
0 0 0 0 0 1 1�
� ł
�
0 0 1 1 0 0 0ł
� ł
� ł
B =
�
0 1 0 1 0 0 0ł
� ł
� ł
� ł
0 1 1 0 0 0 1ć
Ź
zbiór L = {4,7} jest pokryciem kolumnowym B, a wi c
k+(L,k) = (***0**0), czyli implikantem F jest x x .
4 7
Natomiast dla L = {2,3,6} (inne pokrycie
kolumnowe), k+(L,k) = (*00**1*) = x x x6.
2 3
Implikanty proste
I1 = x I5 = x
1 5
I2 = x2x I6 = x x
6 6 7
I3 = x x I7 = x3 x
4 7 6
I4 = x x x6
2 3
17
Selekcja implikantów prostych
Tablica implikantów prostych
I1 I2 I3 I4 I5 I6 I7
k1 1100000
k2 0011000
k3 0010111
k4 0010000
k5 0100001
Inny zapis Tablicy:
I1, I2
I3, I4
I3, I5, I6, I7
I3
I2, I7
Minimalne pokrycie: I2, I3
Minimalna formuła:
f = x x + x2x
4 7 6
18
Procedury systemu ESPRESSO
F,R Complement
Expand
Essential primes
Irredundant-Cover
Reduce
Last-gasp Make-Sparse FM
19