Metoda Karnaugha

Metoda Karnaugha (wym. spolszczona karˈnofa), metoda Karnaugh (wym. ang. ˈkɑː(ɹ)nɔː) – sposób minimalizacji funkcji boolowskich. Został wynaleziony w 1950 roku przez Maurice'a Karnaugh. 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 mapą lub siatką Karnaugha, wówczas znalezienie minimalnej formuły odbywa się na drodze intuicyjnej. W celu minimalizacji funkcji o większej liczbie wejść stosuje się metody komputerowe, na przykład metodę Quine’a-McCluskeya.

Indeksy kratek

W siatce Karnaugha część zmiennych binarnych przypisana jest wierszom, a część kolumnom. Indeksy i kolumny numerowane są przy pomocy kodu Graya. Wektorem odpowiadającym danej kratce jest wektor powstały po „sklejeniu” binarnego numeru wiersza z binarnym numerem kolumny.

Sposób wypełniania siatki Karnaugha wartościami funkcji czterech zmiennych F(A,B,C,D)

Dzięki zastosowaniu kodu Graya możliwe jest znalezienie w wizualny sposób pól sąsiednich logicznie, czyli różniących się wartością dokładnie jednej zmiennej. Przy większej liczbie zmiennych staje się to jednak trudniejsze.

Sąsiedztwa logiczne w siatce pięciu zmiennych

Minimalizacja funkcji logicznych

Przykład dwóch poprawnych grup dla siatki pięciu zmiennych

W celu minimalizacji funkcji logicznych należy wypełnić mapę Karnaugha wartościami (1 lub 0) odpowiadającymi wartościom funkcji dla wartości argumentów opisujących dane pole w tablicy. Następnie grupuje się pola o wybranej wartości (1 aby uzyskać funkcję minimalną w postaci sumy, 0 dla postaci iloczynu). Grupy muszą mieć kształt prostokąta o długościach boków będących potęgami dwójki (przy czym może on przechodzić przez krawędź tablicy, a dla liczby zmiennych powyżej 4 nie musi być spójny, a jedynie łączyć pola sąsiednie logicznie). W celu uzyskania postaci minimalnej, grupy powinny być możliwie największe. Jedno pole może należeć do wielu grup.

Przykład siatki Karnaugha dla czterech zmiennych z zaznaczonymi grupami zarówno zer, jak i jedynek. Poniżej zapisano uzyskaną postać minimalną funkcji w postaci sumy i iloczynu

W każdej uzyskanej grupie część wartości zmiennych będzie wspólna dla wszystkich pól i to z nich powstaje wyrażenie odpowiadające danej grupie. Jeżeli pogrupowane zostały jedynki, wyrażenie dla pojedynczej grupy będzie miało postać iloczynu zmiennych, które, jeżeli w danej grupie przyjmują wartość 1, będą występowały w postaci prostej, jeżeli 0 – w postaci zanegowanej (zmienne przyjmujące w danej grupie różne wartości są pomijane); funkcja końcowa będzie sumą tych iloczynów. Jeżeli utworzono grupy zer, wyrażenie dla danej grupy będzie sumą zmiennych w postaci zanegowanej, jeżeli w danej grupie mają wartość 1, prostej, jeśli 0; wynik będzie iloczynem takich sum. Tak więc im grupa jest większa, od tym mniejszej liczby zmiennych zależy.

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.

Funkcja podobna do powyższej, jednak teraz dla wartości 15 funkcja jest nieokreślona. Pozwoliło to na powiększenie grupy czerwonej i całkowite usunięcie zielonej przy jednoczesnej eliminacji hazardu

Stany nieokreślone

Jeżeli dana funkcja logiczna dla danej kombinacji wartości argumentów nie jest określona (tzn. wartość, jaką przyjmie dla niej funkcja, nie jest istotna), odpowiednie pole może (ale nie musi) zostać wcielone do którejś z grup w celu jej powiększenia.

Zobacz też

• algorytm ekspansji
• implikant funkcji boolowskiej
• metoda Espresso

Bibliografia

• Halina Kamionka-Mikuła, Henryk Małysiak, Bolesław Pochopień: Synteza i analiza układów cyfrowych. Gliwice: Wydawnictwo Pracowni Komputerowej Jacka Skalmierskiego, 2009, s. 72–77. ISBN 978-83-60716-40-3.