048 049

48

		^Tl *! *1	«tT,T}	‘iVł	‘1 *1 ‘1
Vi	X	X
		X			X
			X	X
X,*J				X	X

	‘i **r*i
V‘i	X	;x
*1*^Tl*‘l			X

a)

b) ¹

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

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

' Z tablicy wynika, że istnieją w danym przypadku dwa zespoły lmplikantó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₂ + x₂*j -

lub

y = x^x₂ + x₁x₂ + x₁x_}

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 lmplikantów, a w trzeciej próbie przypadkowo uzyskaliśmy postać minimalną.

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

y s (x₁+x₂+x₅nx₁+x₂+xj)(x₁+x₂+xj)

Możliwe jest tylko jedno sklejenie, po wykonaniu którego otrzymujemy y = (x₁+x₂)(3E₁+5₂+Xj)

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

Minimalizacja czyli wykonanie wszystkich możliwych sklejeń jak i eliminacja zbędnych lmplikantów (impllcentó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ą.

W metodzie Qjine'a-Mc Cluskey'a minimalizację przeprowadza się następująco:

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

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

2.    Porządkuje się otrzymaną kolumnę liczb dwójkowych według rosną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, te 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.

3. Każdą następną kolumnę tworzymy z poprzedniej według tyoh samych zasad uwzględniając dodatkowo, że warunkiem dalszych sklejeń,Jest występowanie krasek 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 (impllcentó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 (impll-centy), a pozostałe przekształcamy do jawnej postaci według zasady (1.10) (1.14).

Przykład 2.4

Zminimalizować funkcję

y o x₁x₂x₅x_ił + x₁x₂x₃x_if + 3E₁x₂x₃x_ł +    *2*3*4 + x^x₂x^ + x₁x₂XjX₄+

+ X₁X₂XjX₄ + X₁X₂XjX₄

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

y = x₁x₂X3 + x₁x₃x₄ + x₁x_Jx₄ +    **

i    '    4

Podczas minimalizacji funkcji niepełnie określonych, przy poszukiwaniu .espolu lmplikantów (Impllcentów) prostych, należy,' co Jest oczywiste, iwzględniać składniki ZNPS (czynniki ZNPI), przy których funkcja jest nie-