048 049

48

48

	Vi^Ti	^rt *i *i	*1^TI^TJ	1, Tj «j	X, X,
Vi	X	X
		X			X
‘1*1			X	X
X,*J				X	X

	*l**«**ł		T,vr2«j
*»**«	X	X
			X

Rys. 2.3. Tablice lmplikantów (a) 1 implieentów (b) do przykładu 2.2

prostymi. W tablicy wpisuje się znak (np. x), gdy Jedynka-"danego impli-kantu pokrywa Jedynkę odpowiedniego składnika ZNPS (Jak widać z tablicy na rys. 2.3a zachodzi to wtedy, gdy iloczyn będący implikantam prostym Jest fragmentem danego składnika ZNPS).

Z tablicy wynika, że istnieją w danym przypadku dwa zespoły implikaa-tów prostych pokrywających Jedynki funkcji. Ponieważ w obu przypadkach uzyskuje się tak samo złożony zapis, oba te przypadki są równorzędnymi postaciami minimalnymi funkcji.

Są to

y = x^x₂ + x^x₂ + Zglj -

lub

y = x₁x₂ + x₁x₂ + x₁x_J

W świetle tego rozwiązania warto wrócić do prób rozwiązania tego zadania przeprowadzonego na początku przykładu 2.2. Widać teraz, że pierwsza próba nie prowadziła do postaci minimalnej, bo nie przeprowadzono wszystkich możliwych sklejeń, w drugiej przeprowadzono co prawda wszystkie możliwe sklejenia, ale nie potrafiliśmy wyeliminować zbędnych ięplik^ntów, a w trzeciej próbie przypadkowo uzyskaliśmy postać minimalną.

Analogicznie, gdy postacią końcową funkcji ma być minimalna KPI, postacią wyjściową-funkcji Jest ZNPI

y = (x₁+x₂+x₅nx₁+x₂+5j)(x₁+x₂+x₃)

Możliwe Jest tylko Jedno sklejenie, po wykonaniu którego otrzymujemy y = (x₁+x₂)(x₁+x₂+ij)

Na rys. 2.3b przedstawiono tablicę implieentów, z której wynika,że powyższa postać nie zawiera implieentów zbędnych i Jest minimalna.    tt

Minimalizacja czyli wykonanie wszystkich możliwych sklejeń Jak i eliminacja zbędnych lmplikantów (implieentów)- Jest łatwa, ale uciążliwa. Poniżej wprowadzimy pewną modyfikację pozwalającą na bardziej mechaniczne jej wykonywanie 1 ułatwiającą przygotowanie programu minimalizacji na maszynę cyfrową.

V metodzie Qjine'a-Mc Cluskey'a minimalizację przeprowadza się następująco;

1.    Wszystkie składniki ZNPS (czynniO ZNPI) danej funkcji wypisuje się w

postaci kolumny liczb dwójkowych pisząc 0(1) zamiast oraz 1(0) zamiast x^.

2.    Porządkuje się otrzymaną kolumnę liczb dwójkowych według rośnącej liczby Jedynek.

3.    W uporządkowanej kolumnie wydziela się grupy liczb o 0,1,2,3, itd. Jedynkach.

4.    Tworzy się następną kolumnę liczb dwójkowych, która Jest rezultatem sklejeń liczb w kolumnie poprzedniej (pamiętamy, że liczba jest umownym zapisem iloczynu (sumy)), przy czym:

-    skleja się tylko liczby należące do sąsiednich grup;

- sklejane liczby mogą się różnić tylko na jednej pozycji;

- wynik sklejenia jest liczbą, w której w miejsce różniących się cyfr wpisuje się kreskę (np. sklejając 1001 i 1011 otrzymujemy 10-1);

-    liczby biorące udział w sklejaniu oznacza się (np. v);

-    każda liczba może brać udział w sklejaniu dowolną ilość razy;

-    należy wyczerpać wszystkie możliwości sklejeń;

-    wyniki sklejeń między poszczególnymi grupami tworzą nowe grupy;

-    wyników powtarzających się nie wpisujemy.

5.    Każdą następną kolumnę tworzymy z poprzedniej według tych samych zasad uwzględniając dodatkowo, że warunkiem dalszych sklejeń, jest występowanie kresek na tych samych pozycjach.

6.    Proces sklejania kończy się, gdy w ostatnio otrzymanej kolumnie nie moż na Już przeprowadzić żadnych sklejeń.

7.    Liczbami (ze wszystkich kolumn), które nie podlegały sklejeniom, opisujemy wiersze tablicy lmplikantów (implieentów), gdyż odpowiadają one implikantom (implicentom) prostym, liczbami odpowiadającymi składnikom ZNPS (czynnikom ZNPI) opisujemy kolumny tej tablicy.

8.    Przy pomocy tak opisanej tablicy eliminujemy zbędne implikanty (impli-centy), a pozostałe przekształcamy do jawnej postaci według zasady (1.10) (1.14).

Przykład 2.4

Zminimalizować funkcję    '

y = x₁x₂x^x_ił + x₁x₂5j5_Jf + x^x₂x^ + x^x₂x^ + x₁x₂x_Jx_ił + x^x₂xjx^+

+ x„x~x-.x

12 3 4

Postępując wg podanych zasad otrzymujemy kolejne kolumny (rys. 2.4a) i tablicę implikantów (rys. 2.4b), na podstawie której otrzymujemy postać minimalną

y = x₁x₂x_J + 5ć₁XjX₄ + x₁x_Jx₄ + x₁x₂x^    ^    **

Podczas minimalizacji funkcji niepełnie określonych, przy poszukiwaniu ■ espołu implikantów (implieentów) prostych, należy, co Jest oczywiste, uwzględniać składniki ZNPS (czynniki ZNPI), przy których funkcja jest nie-