Metoda Karnaugh

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

Metoda Karnaugh to 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

1 Tablica Karnaugh
- 1.1 Indeksy kratek
- 1.2 Wartości w kratkach
2 Przykład minimalizacji
3 Sklejanie "na skos"
4 Zobacz także:

[edytuj] Tablica Karnaugh

[edytuj] Indeksy kratek

Tablicę Karnaugh 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 Karnaugh liczba zmiennych binarnych przypisanych wierszom i liczba zmiennych binarnych przypisana kolumnom powinna różnić się maksymalnie o 1.

Indeksy kratek tablicy Karnaugh 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 Karnaugh!)


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 Kratki 8 i 10 (niebieskie) tworzą jeden obszar, zostały sklejone poprzez brzeg tabeli	Tabela 4 - Nieoptymalna W tym wypadku sklejone przez brzegi tablicy są wszystkie cztery rogi (żółte) oraz kratki 3 i 2 (czerwone u góry) z 11 i 10 (czerwone na dole)

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.