Metoda Karnaugh
Z Wikipedii
Metoda Karnaugh (czyt. karno) – sposób minimalizacji funkcji boolowskich. Został odkryty w 1950 roku przez Maurice Karnaugha. W ogólnym przypadku znalezienie formuły minimalnej dla zadanej funkcji boolowskiej jest bardzo skomplikowanym problemem. Jednak jeśli funkcja ma małą liczbę zmiennych (do sześciu) i zostanie zapisana w specjalnej tablicy zwanej tablica Karnaugh, wówczas znalezienie minimalnej formuły odbywa się na drodze intuicyjnej. W celu minimalizacji funkcji o większej liczbie wejść stosuje się z powodzeniem metody komputerowe.
Spis treści |
[edytuj] Tablica Karnaugha
[edytuj] Indeksy kratek
Tablicę Karnaugha zaczynamy tworzyć przypisując część zmiennych binarnych wierszom, a część kolumnom. To, jak zostanie to zrobione, rzutuje potem na sposób indeksowania kratek. Dlatego, aby uniknąć pomyłek, pierwszą połowę zmiennych przypisuje się wierszom, a drugą - kolumnom. Aby łatwo korzystać z metody Karnaugha liczba zmiennych binarnych przypisanych wierszom i liczba zmiennych binarnych przypisana kolumnom powinna różnić się maksymalnie o 1.
Indeksy kratek tablicy Karnaugha tworzone są w następujący sposób:
- Wiersze i kolumny numerujemy przy pomocy binarnego kodu Graya.
- Wektorem odpowiadającym danej kratce jest wektor powstały po 'sklejeniu' binarnego numeru wiersza z binarnym numerem kolumny (Tabele 1,2 - to nie są tablice Karnaugha!)
 |
 |
| Tabela 1 - Indeksy kratek w systemie binarnym | Tabela 2 - Indeksy kratek w systemie dziesiętnym |
[edytuj] Wartości w kratkach
Każda kratka tablicy odpowiada jednemu, konkretnemu wektorowi zmiennych binarnych. W kratkach zapisywane są wartości funkcji dla odpowiadających im wektorów. Przykład tablicy Karnaugh podany zostanie w następnym akapicie.
[edytuj] Przykład minimalizacji
Weźmy funkcję:
f(x1,x2,x3,x4) = Σ[2,3,6,7,8,10,11,15,(0,13)]
Tablica prawdy dla funkcji f wygląda następująco:
-
# x1 x2 x3 x4 f 0 0 0 0 0 - 1 0 0 0 1 0 2 0 0 1 0 1 3 0 0 1 1 1 4 0 1 0 0 0 5 0 1 0 1 0 6 0 1 1 0 1 7 0 1 1 1 1 8 1 0 0 0 1 9 1 0 0 1 0 10 1 0 1 0 1 11 1 0 1 1 1 12 1 1 0 0 0 13 1 1 0 1 - 14 1 1 1 0 0 15 1 1 1 1 1
Tworzymy tablicę Karnaugh przypisując zmienne x1, x2 wierszom a zmienne x3, x4 kolumnom. Następnie sklejamy ze sobą jak największe grupy jedynek i kresek tak, by każda jedynka z tablicy znalazła się choć raz w jednej z grup. Niektóre grupy będą po prostu pojedynczymi kratkami - w nich znajdują się jedynki których nie można skleić wg poniższych reguł:
- sklejamy kratki bezpośrednio stykające się ze sobą np.: 2-3-6-7 lub 13-15; przy czym traktujemy brzegi tablicy Karnaugh jako stykające się ze sobą np.: 3-11 lub 0-2-8-10.
- sklejony obszar musi być prostokątem o bokach będących potęgami 2; należy pamiętać że brzegi stykają się ze sobą, dlatego sklejone np. cztery rogi tablicy tworzą kwadrat o boku 2
Przykładami tabel uzyskanych wg. powyższego przepisu są tabele 3 i 4. Warto zauważyć, że kratka 13 (kreska nie obwiedziona żadnym kolorem) nie musi być w żadnej grupie, a jej włączenie spowodowałoby niepotrzebny przyrost ilości grup.
 |
 |
|
Tabela 3 - Nieoptymalna |
Tabela 4 - Nieoptymalna |
Obydwa przedstawione wyżej sposoby sklejania są nieoptymalne. Żeby otrzymać optymalną tablicą należy wybierć najmniejszą liczbę jak największych grup pokrywającą wszystkie jedynki. W tabeli 3 było zbyt dużo grup, a w tabeli 4 obszary czerwone były niepotrzebne bo te same jedynki zawierały się w innych sklejonych obszarach. Tablicą optymalną jest tablica 5.
Tabela 5 - Optymalna
Formułą minimalną, równoważną funkcji pierwotnej jest suma iloczynów odpowiadających wybranym grupom. Owe iloczyny są implikantami tej funkcji. W przypadku funkcji f formuła minimalna odczytana z tabeli 5 zapisuje się tak (kolorami oznaczono którą grupę pokrywa dany implikant):
f(x1,x2,x3,x4) = (¬x1 ∧ x3) ∨ (¬x2 ∧ ¬x4) ∨ (x3 ∧ x4)
[edytuj] Sklejanie "na skos"
Gdy istnieją grupy jednoelementowe, które stykają się ze sobą rogami (nie mogą zostać sklejone w konwencjonalny sposób), jest możliwość zminimalizowania funkcji za pomocą funktorów XOR i XNOR.
