TC Moduł 3

Minimalizacja funkcji boolowskich metodą tablic Karnaugha.

---

Zasygnalizowany w poprzednim wykładzie proces minimalizacji funkcji boolowskich ma ogromne znaczenie w technice cyfrowej. Znaczenie to zostało spotęgowane możliwościami realizacji układów logicznych w strukturach scalonych o złożoności milionów bramek logicznych.

---

Wypracowano wiele metod minimalizacji funkcji boolowskich. Najbardziej znaną i uznawaną za najskuteczniejszą jest metoda ESPRESSO opracowana w latach 80. na Uniwersytecie Kalifornijskim w Berkeley. Ze względu na ograniczony zakres wykładu omówimy wyłącznie metodę tablic Karnaugha oraz metodę ekspansji (przykładową procedurę Espresso).

---

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

---

Na planszy pokazane są przykłady łączenia (sklejania) kratek tablicy Karnaugha.

---

Kolejny przykład ilustruje wykorzystanie zasady łączenia kratek do graficznej minimalizacji funkcji boolowskiej.

---

Wpisywanie funkcji do tablicy Karnaugha ułatwia numeracja kratek. Podajemy przykłady tablic Karnaugha z ponumerowanymi kratkami.

---

Oraz stosujemy tę metodę do funkcji z poprzedniego przykładu.

---

Niestety zakreślanie pętelek i kojarzenie z nimi odpowiednich iloczynów jest trudniejsze. Omawiamy ten proces na bardziej skomplikowanym przykładzie, w którym kolorami zaznaczamy odpowiednie pola tablicy Karnaugha. Pokrywanie się tych pól określa odpowiedni iloczyn zmiennych prostych lub zanegowanych.

---

Na tym przykładzie trenujemy cały proces minimalizacji funkcji metodą tablic Karnaugha.

---

Pojęciem podstawowym w procesie minimalizacji jest pojęcie implikantu. Implikant funkcji boolowskiej $f$ jest to iloczyn literałów (czyli zmiennych prostych lub zanegowanych) o następującej własności: dla wszystkich kombinacji wartości zmiennych, dla których implikant jest równy jedności, również funkcja $f$ jest równa jedności. Prosty implikant jest to implikant, który zmniejszony o dowolny literał przestaje być implikantem.

---

Pojęcie implikantu można zinterpretować na tablicy Karnaugha.

---

Omówimy teraz zapis funkcji boolowskiej w kanonicznej formie sumacyjnej oraz kanonicznej formie iloczynowej.

---

Podajemy ogólny wzór na kanoniczną formę sumacyjną oraz sposób tworzenia tej formy dla przykładowej funkcji. KFS można utworzyć bezpośrednio z tablicy prawdy przez wybranie wierszy, dla których wartość funkcji wynosi 1, utworzenie dla każdego takiego wiersza iloczynu pełnego, oraz utworzenie sumy iloczynów pełnych.

---

Podajemy ogólny wzór na kanoniczną formę iloczynową oraz sposób tworzenia tej formy dla przykładowej funkcji. W tym przypadku synteza funkcji sprowadza się do wybrania wierszy, dla których wartość funkcji wynosi 0, utworzenia dla każdego takiego wiersza sumy pełnej oraz utworzenia iloczynu sum pełnych.

---

Formy kanoniczne są stosowane do uzyskiwania różnych realizacji bramkowych funkcji boolowskich. Są to: realizacja AND-OR, realizacja NAND, realizacja OR-AND, realizacja NOR.

---

Kolejne plansze ilustrują sposób tworzenia takich realizacji.

---

---

---

---

Oto bardziej skomplikowany przykład realizacji iloczynowej.

---

W dotychczasowych przykładach minimalizowane były pojedyncze funkcje boolowskie, dla których – w celu uzyskania rozwiązania z minimalnym kosztem – tworzone były wyłącznie implikanty proste. W ogólnym przypadku minimalizacji zespołów funkcji boolowskich tworzenie minimalnego rozwiązania wyłącznie na podstawie implikantów prostych nie zawsze prowadzi do najlepszego rezultatu końcowego. Problem ilustrujemy następującym przykładem zespołu funkcji: $y_1=\sum (2,3,5,7,8,9,10,11,13,15)$ $y_2=\sum (2,3,5,6,7,10,11,14,15)$ $y_3=\sum (6,7,8,9,13,14,15)$ Po zakreśleniu „pętelek” obejmujących implikanty proste uzyskujemy następujące wyrażenia boolowskie: $y_1=a\overline{b}+bd+\overline{b}c$ $y_2=c+\overline{a}bd$ $y_3=bc+a\overline{c}d+a\overline{b}\overline{c}$ Realizacja tych wyrażeń wymaga zastosowania 7 bramek AND i 3 bramek OR.

---

Znacznie lepszą realizację uzyskamy dokonując minimalizacji w sposób przedstawiony w tablicach na niniejszej planszy. Pętelki w tych tablicach zakreślamy tak, aby uzyskiwać implikanty wspólne dla co najmniej dwóch spośród trzech funkcji. Spełnienie tego warunku wymusza zakreślanie pętelek wokół grup kratek reprezentujących implikanty, które nie są implikantami prostymi. W rezultacie uzyskujemy następujące wyrażenia: $y_1=\overline{b}c+\overline{a}bd+abd+a\overline{b}\overline{c}$ $y_2=\overline{b}c+\overline{a}bd+bc$ $y_3=abd+a\overline{b}\overline{c}+bc$ Realizacja powyższych wyrażeń łącznie, mimo pozornie większego skomplikowania dla poszczególnych funkcji, jest oszczędniejsza niż poprzednio; całość wymaga bowiem zastosowania 5 bramek AND i trzech bramek OR.