Metoda Karnaugha

Metoda Karnaugha (wym. spolszczona karˈnofa), metoda Karnaugh (wym. ang. ˈkɑː(ɹ)nɔː^[1][2]) – 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.

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.

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.

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.

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.

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.

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.

• algorytm ekspansji
• implikant funkcji boolowskiej
• metoda Espresso

• 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.