Podręcznik

Mimo swoich niedoskonałości metoda Karnaugha jest najczęściej wykładaną metoda minimalizacji funkcji boolowskich. Paradoksalnie to co jest jej wadą – prostota – jest jednocześnie jej zaletą, gdyż można szybko ją „opanować” i stosować w obliczeniach ręcznych. Należy jednak pamiętać, że w praktyce projektowania inżynierskiego metoda tablic Karnaugha jest absolutnie nieprzydatna, gdyż zakres jej zastosowań kończy się na funkcjach 6 – 7 argumentów, a typowe zadania praktyczne operują funkcjami o kilkudziesięciu argumentach.

Rys. 2.8. Zasada sklejania

W metodzie Karnaugha każda kratka odpowiedniej tablicy (zwanej tablicą Karnaugha) odpowiada wektorowi zmiennych binarnych. Można więc powiedzieć, że ciąg wartości tych zmiennych tworzy adres kratki. Kratki są ponumerowane w taki sposób, że numer i jest liczbą dziesiętną odpowiadającą kombinacji zmiennych (wektorowi zero-jedynkowemu) traktowanej jako liczba dwójkowa. W poszczególnych kratkach wpisane są wartości funkcji, tj. 0 lub 1 przyjmowanej przez funkcję dla tej kombinacji lub symbol „–”, jeżeli funkcja nie jest określona (rys. 2.8). W tablicy Karnaugha różniącym się tylko o negację pełnym iloczynom przyporządkowane są leżące obok siebie pola tablicy (sąsiednie kratki), które się łączy (skleja) odpowiednią pętelką. Korzysta się z faktu, że dla dowolnego $A,A\bar{x}+Ax=A$.

Dla uzyskania efektu sąsiedztwa współrzędne pól opisuje się tzw. kodem Gray’a. Kod Gray’a jest takim ciągiem wektorów binarnych, w którym każde dwa sąsiednie wektory różnią się wyłącznie na jednej pozycji. Przykłady kodu Gray’a dla dwóch i trzech zmiennych podane są w tabl. 2.10.

Tablica 2.10

Minimalizacja metodą Karnaugha polega na wykonaniu dwóch czynności:

1. wpisanie funkcji do tablicy,
2. zakreślanie pętelek i kojarzenie z nimi iloczy­nów zmiennych prostych i zanegowanych.

Wpisywanie funkcji do tablicy Kar­naugha ułatwia numeracja kratek. Na rys. 2.9 podajemy przykłady tablic Karnaugha z ponu­merowanymi kratkami według naturalnego kodu binarnego (NKB), odpowiednikami. Wzorce tych tablic ułatwiają znajdowanie kratek odpowiadających wektorom w tablicy prawdy.

Rys.  2.9. Przykłady tablic z ponumerowanymi kratkami

Niestety zakreślanie pętelek i kojarzenie z nimi odpowiednich iloczynów jest trudniejsze. Omawiamy ten proces na bardziej skomplikowanym przykładzie (rys. 2.10), w którym dla poszczególnych kopii tablicy Karnaugha trzech zmiennych zaznaczamy pola odpowiadające pojedynczym zmiennym (prostym i zanegowanym). Pokrywanie się tych pól określa odpowiedni iloczyn zmiennych prostych

Rys. 2.10. Ilustracja minimalizacji funkcji boolowskiej

Minimalizacja funkcji za pomocą tablic Karnaugha sprowadza się do wykonania czynności opisanych w następującym algorytmie.

Algorytm 2.1

1) Wpisujemy funkcję do tablicy Karnaugha.

2) Zakreślamy pętelki.

a) Pętelki zakreślamy wokół grup sąsiadujących kratek zawierających „1” albo „1” i „–” (kreski).

b) Liczba kratek objętych pętelka musi wynosić: 1, 2, 4, …,2^k.

c) Staramy się objąć pętelką jak największą liczbę kratek.

3) Pętelki zakreślamy tak długo, aż każda „1” będzie objęta co najmniej jedną pętelką, pamiętając o tym aby pokryć wszystkie „1” możliwie minimalną liczbą pętelek.

4) Z każdą pętelką kojarzymy iloczyn zmiennych prostych lub zanegowanych. Suma tych iloczynów, to minimalne wyrażenie boolowskie danej funkcji.

Przykład 2.4 posłuży teraz do wprowadzenia jednego z najważniejszych pojęć minimalizacji jakim jest implikant.

Na przykład ${\bar{x}}_1x_3x_4$ jest implikantem funkcji f, bo zbiór wektorów reprezentowanych przez ten implikant: 0111 oraz 0011 nie zawiera żadnego wektora (mintermu), dla którego wartość funkcji jest 0. Są to bowiem mintermy, które w naturalnym kodzie binarnym odpowiadają liczbom 7 i 12, i jak widać z zapisu funkcji  f = S[0, 5, 6, 7, 10, (2, 3, 11, 12)], nie należną one do zbioru wektorów „zerowych” tej funkcji.

Pojęcie implikantu można zinterpretować na tablicy Karnaugha. W tablicy 2.16 zakreślono dwie pętelki. Mniejsza odpowiada implikantowi ${\bar{x}}_1x_3x_4$. Nie może to być implikant prosty, gdyż pętelkę tę można powiększyć. Większej pętelce odpowiada implikant prosty ${\bar{x}}_1x_3$, w którym nie można już usunąć żadnego literału.

Tablica 2.16

W dotychczasowych przykładach minimalizowane były pojedyncze funkcje boolowskie, dla których – w celu uzyskania rozwiązania z minimalnym kosztem – two­rzo­ne były wyłącznie implikanty proste. W ogól­nym przypadku minimalizacji zespołów funkcji boolowskich tworzenie minimalnego rozwiązania wyłącznie na podstawie impli­kantów prostych nie zawsze prowadzi do najlepszego rezultatu końcowego. Problem sygnalizuje przykład 2.8.

Przykład sugeruje, że w realizacji zespołu funkcji stosowanie minimalnej sumy implikantów prostych nie zawsze prowadzi do rozwiązania z minimalnym kosztem. Kolejny przykład ilustruje w jaki sposób należy dobierać implikanty zespołu funkcji, aby uzyskać rozwiązanie z minimalnym kosztem.