Metoda Karnaugh

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Metoda Karnaugh (czyt. karno) – sposób minimalizacji funkcji boolowskich. Został wynaleziony 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 tablicą lub siatką 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, np. metodę Quine'a-McCluskeya.

Indeksy kratek[edytuj | edytuj kod]

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 Karnaugh 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[edytuj | edytuj kod]

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

W celu minimalizacji funkcji logicznych należy wypełnić siatkę 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ć największe możliwe. Jedno pole może należeć do wielu grup.

Przykład siatki Karnaugha 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"[edytuj | edytuj kod]

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.

Stany nieokreślone[edytuj | edytuj kod]

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.

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ż[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

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