TC Moduł 3

From Studia Informatyczne

Grafika:TC_M3_Slajd1.png Minimalizacja funkcji boolowskich metodą tablic Karnaugha.

Grafika:TC_M3_Slajd2.png 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.

Grafika:TC_M3_Slajd3.png 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).

Grafika:TC_M3_Slajd4.png 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 \overline{x}+Ax=A

Grafika:TC_M3_Slajd5.png Dla uzyskania efektu sąsiedztwa współrzędne pól opisuje się tzw. kodem Gray’a.

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

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

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

Grafika:TC_M3_Slajd9.png Oraz stosujemy tę metodę do funkcji z poprzedniego przykładu.

Grafika:TC_M3_Slajd10.png 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.

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

Grafika:TC_M3_Slajd12.png 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.


Grafika:TC_M3_Slajd13.png Pojęcie implikantu można zinterpretować na tablicy Karnaugha.

Grafika:TC_M3_Slajd14.png Omówimy teraz zapis funkcji boolowskiej w kanonicznej formie sumacyjnej oraz kanonicznej formie iloczynowej.

Grafika:TC_M3_Slajd15.png 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.

Grafika:TC_M3_Slajd16.png 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.

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

Grafika:TC_M3_Slajd18.png Kolejne plansze ilustrują sposób tworzenia takich realizacji.

Grafika:TC_M3_Slajd19.png

Grafika:TC_M3_Slajd20.png

Grafika:TC_M3_Slajd21.png

Grafika:TC_M3_Slajd22.png Oto bardziej skomplikowany przykład realizacji iloczynowej.

Grafika:TC_M3_Slajd23.png 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 \bar b + bd + \bar b c
y_2=c+\bar a bd
y_3=bc+a \bar c d + a \bar b \bar c

Realizacja tych wyrażeń wymaga zastosowania 7 bramek AND i 3 bramek OR.


Grafika:TC_M3_Slajd24.png 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=\bar b c + \bar a bd + abd + a \bar b \bar c
y_2=\bar b c + \bar a bd + bc
y_3=abd + a \bar b \bar 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.