Image057

W dotychczasowych rozważaniach, dotyczących sposobów zapisu funkcji, funkcje te przyjmowały ściśle określone wartości dla wszystkich 2ⁿ kombinacji n zmiennych niezależnych. Może jednak zdarzyć się przypadek, że fizyczne warunki działania urządzenia nie dopuszczają wystąpienia pewnych kombinacji zmiennych. Wówczas tablica wartości będzie określona częściowo, z pominięciem kombinacji nieokreślonych. Jeśli dana kombinacja zero-jedynkowa nigdy się na wejściu układu nie pojawia, można przyjąć, że dla tej kombinacji wartość funkcji może wynosić równie dobrze 0, jak i 1. Możliwość przyjęcia dowolnej wartości funkcji dla pewnych kombinacji jest bardzo przydatna w procesie minimalizacji. W tablicach, w miejsca, gdzie wartość funkcji może być dowolna, wpisuje się umowny symbol , 0, X.

3.4. Minimalizacja funkcji logicznych

Realizacja funkcji logicznej przedstawionej w postaci kanonicznej nie jest zazwyczaj realizacją najprostszą. Oczywiście, jest możliwe minimalizowanie funkcji logicznych drogą przekształceń algebraicznych. Postacie kanoniczne tych funkcji przekształca się zgodnie z prawami oraz tożsamościami algebry Boole’a tak, aby uzyskać wyrażenie równoważne, ale tańsze według przyjętej funkcji kosztu. Otrzymywane wyrażenia zależą w dużej mierze od umiejętności projektanta.

Istnieje graficzna metoda minimalizacji, powszechnie nazywana metodą tablic Karnaugha [1, 2, 3, 4, 6, 9, 11, 12, 13]. Tablica Karnaugha została przedstawiona w p. 3.3 jako jedno z możliwych przedstawień funkcji logicznej. Obecnie będzie opisane wykorzystanie jej do minimalizacji funkcji logicznej.

Zauważmy, że wypisane przy krawędziach tablicy Karnaugha (rys. 3.7) liczby nie są kolejnymi liczbami dwójkowymi, lecz kolejnymi słowami kodu Graya, a więc kolejne słowa różnią się tylko na jednej pozycji. Kolejność taka jest charakterystyczną właściwością tablicy Karnaugha, wykorzystywaną do przeprowadzania uproszczeń w oparciu o tzw. regułę sklejania:

AX+AX - A (B+X)(B+X) = B

gdzie A i B — zmienne lub funkcje logiczne. A więc zmienną, która w dwóch sąsiednich polach przyjmuje różne wartości można pominąć.

Proces minimalizacji funkcji logicznej za pomocą tablicy Karnaugha składa się z trzech etapów. Etap pierwszy polega na przygotowaniu tablicy dla danej liczby zmiennych i wpisaniu w pola elementarne wartości funkcji. W polach odpowiadających kombinacjom zmiennych, dla których wartość funkcji jest nieokreślona, należy wpisać znak nieokreśloności, np. 0.

Następnie należy narysować obwiednie możliwie największych obszarów obejmujących wyłącznie jedynki (dla postaci sumacyjnej), albo wyłącznie zera (dla postaci iloczynowej), sąsiadujące ze sobą. Rysowanie obwiedni odbywa się według następujących zasad:

— liczba pól elementarnych połączonych ze sobą musi być potęgą dwójki (1, 2, 4, ...,2"),

67