Technika cyfrowa egzamin poprawka

Metoda Quine'a-McCluskeya

Pierwszą metodą, jaką chcę tutaj omówić jest metoda Quine'a-McCluskeya. Chociaż z początku jest to dość skomplikowana metoda, okazuje się, że łatwo jest nie tylko używać jej ręcznie, ale przede wszystkim zaimplementować ją na komputerze. Jest to metoda, która może być stosowana do funkcji o dużej liczbie zmiennych, ponieważ druga z metod, metoda tablic Karnaugh, jest ciężka do używania, jeśli mamy funkcję więcej niż czterech zmiennych.

Aby przeprowadzić przykładową minimalizację metodą Quine'a-McCluskeya wprowadźmy pojęcie iloczynów pełnych.

Iloczynem pełnym nazywamy logiczny iloczyn wszystkich zmiennych funkcji, w którym zmienne są zanegowane lub nie. Przykładowo, jeśli funkcja jest czterech zmiennych w, x, y, z, iloczyn pełny to na przykład w~xy~z.

Iloczyny pełne układa się w kolejności. Wyznaczają ją liczby dwójkowe odpowiadające iloczynowi. Zmienna zanegowana jest wartością zero, zmienna niezanegowana jest wartością 1. Poprzednio wymieniony iloczyn pełny ma wartość 1010, czyli dziesięć. Jest to dziesiąty w kolejności iloczyn pełny czterech zmiennych.

Funkcję logiczną zawierającą iloczyny pełne można zapisać skrótowo jako sumę kolejnych iloczynów pełnych:

f(w,x,y,z) = Σ(5,7,8,9,10,11,13,15)

Oznacza to, że funkcja jest sumą iloczynów pełnych o konkretnych numerach.

Zminimalizujmy tę funkcję metodą Quine'a-McCluskeya.

W pierwszym kroku wypisujemy numery iloczynów pełnych w czterech (bo 4 zmienne) grupach, które to różnią się między sobą ilością jedynek.

8 1000 - jedna jedynka

5 0101 - dwie jedynki

9 1001 - dwie jedynki

101010 - dwie jedynki

7 0111 - trzy jedynki

11 1011 - trzy jedynki

13 1101 - trzy jedynki

15 1111 - cztery jedynki

Teraz kolejnym krokiem jest iteracja. Porównujemy pomiędzy sobą każdy z każdym elementy z sąsiednich grup. Jeśli elementy różnią się tylko na jednej pozycji, należy "skleić" je ze sobą i w miejscu, gdzie się różniły stawia się kreseczkę. Oczywiście jest to wykorzystanie jednego z podstawowych praw logicznych, mianowicie xy + x~y = x.

W kolejnym kroku przepisujemy tabelę tak, by elementy w poszczególnych grupach znów różniły się tylko o jedną jedynkę.

W naszym przykładzie będzie to wyglądało tak:

8-9 100-

8-10 10-0

5-7 01-1

5-13 -101

9-11 10-1

9-13 1-01

10-11 101-

7-15 -111

11-15 1-11

13-15 11-1

Iterujemy poprzedni krok tak, aby uzyskać kombinację, która nie da się już uprościć. W naszym przypadku dzieje się tak już w trzecim kroku. Inne kombinacje dają te same wyniki.

8-9-10-1110--

5-7-43-15 -1-1

9-11-13-15 1-1-

Kiedy już dojdziemy do takiego rezultatu, musimy odczytać wynik. W tym celu należy stworzyć tak zwaną siatkę Quine'a-McCluskeya.

	5	7	8	9	10	11	13	15		Rozw.
8-9-10-11			x	x	x	x			10--	w~x
5-7-13-15	x	x					x	x	-1-1	bd
9-11-13-15				x		x	x	x	1--1	ad

Ostatnia kolumna jest odpowiednikiem przedostatniej, tylko zapisanej jako zmienne.

Teraz należy wybrać takie elementy, aby "pokryć" wszystkie iloczyny pełne. Optymalnym wyborem będzie u nas:

	5	7	8	9	10	11	13	15		Rozw.
8-9-10-11			xx	xx	xx	xx			10--	w~x
5-7-13-15	xx	xx					xx	xx	-1-1	xz
9-11-13-15				x		x	x	x	1--1	wz

Zatem nasza zminimalizowana funkcja będzie miała postać

f(w,x,y,z) = w~x + xz.

Oczywiście rozwiązaniem jest także

f(w,x,y,z) = w~x + xz + wz,

jednak jak widać jest to funkcja o większym współczynniku skomplikowania.

Ta część minimalizacji metodą Quine'a-McCluskeya opiera się na następującym fakcie. Każde połączenie sum logicznych czy iloczynów logicznych takich jak x1x2~x3+ x1x2x3 = x1x2 są tak zwanymi IMPLIKANTAMI. Dlatego można zapisać każdą funkcję logiczną sztucznie jako sumę iloczynów pełnych, rozszerzając poszczególne elementy tak jak to podano wyżej. Wprowadza się także definicję implikantu prostego, który jest implikantem pewnej formuły, i jednocześnie jest najprostszy pod względem skomplikowania.

Jeśli zatem mamy implikanty proste odpowiadające naszej funkcji, to suma niektórych lub wszystkich z nich jest równoważna wyjściowej funkcji. Wyboru dokonuje się w ten sposób, aby możliwa była reprezentacja każdego z iloczynów pełnych poprzez jeden z implikantów, tak jak to robiliśmy w drugiej części metody Quine'a-McCluskeya. Oczywiście, musimy wybrać tak, by liczba wykorzystanych implikantów nie była wysoka, ściślej - by była to możliwie najmniejsza ilość. Wszystko oczywiście po to, by zminimalizowana funkcja posiadała jak najmniejszy współczynnik skomplikowania.