Metoda Karnaugh

1  Metoda Karnaugh.    Powszechnie uważa się, iż układ o mniejszej liczbie elementów jest tańszy i bardziej  niezawodny, a spośród dwóch układów o takiej samej liczbie elementów logicznych lepszy  jest ten, który operuje mniejszą liczbą sygnałów (mniejsza ilość wejść). Tak więc niezależnie  od zastosowanych dalej elementów schematu logicznego, bardzo ważnym etapem syntezy jest  poszukiwanie takiej postaci funkcji, w której występuje minimalna liczba zmiennych lub ich  negacji. Proces poszukiwania tej postaci minimalnej nosi nazwę minimalizacji funkcji i opiera  się na następujących regułach sklejania:  B x B x B A x A Ax = + + = + ) )( ( _ _     w których A i B to zmienne lub funkcje przełączające. Reguły te można przedstawić  następująco: suma lub iloczyn dwóch wyrażeń różniących się między sobą tylko na jednej  pozycji – znakiem negacji, mogą być zastąpione jednym wyrażeniem, bez litery stanowiącej  różnicę, np.:    1 1 _ 2 2 1 _ 2 1 2 1 1 ) ( x x x x x x x x x = ⋅ = + = +    lub    3 _ 2 3 _ 2 1 3 _ 2 _ 1 ) )( ( x x x x x x x x + = + + + +     Wyrażenia podlegające sklejaniu nazywane są wyrażeniami sąsiednimi.   W wyniku sklejania uzyskuje się wyrażenia, które już nie są postaciami kanonicznymi, ale  zachowują postać sumy iloczynów oraz iloczynu sum. Wyrażenia tego typu przyjęto nazywać  postacią normalną sumy i postacią normalną iloczynu.   W przypadku gdy funkcja jest złożona, wielu zmiennych wyszukiwanie wyrażeń sąsiednich i  sklejanie w sposób analityczny jest bardzo uciążliwe. Istnieją metody upraszczające  procedurę minimalizacji. Jedną z nich jest metoda tablic Karnaugh (zwana również metodą  Veitcha).  Metoda ta ułatwia sklejanie przez takie usytuowanie na płaszczyźnie wyrażeń postaci  kanonicznej, aby wyrażenia sąsiednie były umieszczone blisko siebie, a więc były sąsiednimi  również w sensie geometrycznym. Tablica do której wprowadzamy wartości logiczne funkcji  jest prostokątna i zawiera 2n pól. Każda kratka tablicy odpowiada jednej kombinacji wartości  zmiennych wejściowych. Kod tych kombinacji jest dobrany tak, aby sąsiednie kratki różniły  się wartością jedynie jednej zmiennej, a wiec by odpowiadały im sąsiednie wyrażenia. Kod o  takich właśnie własnościach nosi nazwę kody Gray’a. Do opisanej tym kodem tablicy wpisuje  się symbole, odpowiadające wartościom funkcji dla odpowiednich kombinacji zmiennych  wejściowych. Przykłady tablic Karnaugh dla dwóch, trzech, czterech oraz pięciu zmiennych  przedstawia poniższy rysunek. Baczną uwagę należy zwrócić na specyficzną numerację  ... zobacz całą notatkę