F1-37
© J. Kalisz, J. Pasierbiński, WAT, 2007
Metody minimalizacji
•
„Ręczne” przekształcanie wyrażeń
z zastosowaniem praw
algebry Boole’a:
Stosuje się tylko do prostych wyrażeń boolowskich – należy
dostrzec możliwość redukcji.
•
„Ręczna” metoda graficzna siatek Karnaugh
.
Stosuje się do funkcji o małej liczbie zmiennych (3, 4 –
teoretycznie 5, 6).
•
Metoda
algorytmiczna
Quine’a – McCluskeya
.
Systematyczne porównywanie mintermów różniących się
stanem jednej zmiennej, w celu jej wyeliminowania.
Stosuje się w komputerowych programach minimalizacji dla
funkcji do 10 – 12 zmiennych.
Wada
: forma minimalizowana musi być przedstawiona w
postaci sumy mintermów (kanoniczna forma sumacyjna) –
metoda „oparta na mintermach”
.
Na przykład, przy minimalizacji form o
n
zmiennych term
dwuliterowy musiałby być przekształcony do sumy 2
n
- 2
mintermów. Np.
n
= 20 ► 2
18
mintermów.
•
Metoda
algorytmiczna
Espresso
– heurystyczna,
„oparta na
kostkach”
przetwarzanych bezpośrednio.
1
Y
ABC
ABC
AB(C
C)
AB
AB
=
+
=
+
=
⋅ =