Rotation of�

164

4. Kontynuować wyszukiwanie grup obejmujących 2^K pól z jedynką lub kreską (dla kolejnych k, k =    3,4...), dopuszczając częściowe

zachodzenie grup na siebie, aż do “nakrycia” wszystkich pól zawierających jedynki.

i. Znając lokalizację grup w tablicy, zbudować wyrażenie logiczne opisujące rozważaną funkcję.

Jeżeli na którymś etapie występuje kilka możliwości połączenia lależy je wszystkie przeanalizować, przy czym dojść można do kilku ■'óżnych postaci końcowych, spośród których należy wybrać postać minimalną.

W przykładzie 3.3 (rys. 3.5 a^ ) wystąpiła powyższa sytuacja;! uzyskano tam dwie równoważne, w sensie liczby literałów, minimalne NPSl funkcji. Podobna sytuacja występuje w przypadku funkcji z rys. 3.15 a. Jeśli nie są określone dodatkowe kryteria, w obu przypadkach wybrać! można dowolną z dwu minimalnych postaci funkcji.

Opisany wyżej algorytm wyznaczania minimalnej NPS funkcji, można łatwo zaadaptować do przypadku wyznaczania minimalnej NPI funkcji -należy wszystkie słowa "jedynka" zastąpić słowami "zero" (algorytm wówczas operuje na zerach i kreskach w tablicy).

Opisaną wyżej kolejność wyznaczania grup można odwrócić, zaczynając] od generowania grup największych, jednakże trzeba wówczas sprawdzić, czy któraś z grup większych nie została całkowicie pokryta przez niezbędne grupy mniejsze. Przypadek taki przedstwiono na rys. 3. 15 b, na którym występuje grupa 5 obejmująca cztery pola z jedynkami, lecz wszystkie one wchodzą do niezbędnych grup 1    ,    2    ,    3    ,    4

zawierających po dwie jedynki. Grupa 5 jest zatem zbędna. Minimalna NPS funkcji jest wypisana obok tabeli na rys. 3.15 b.

Na zakończenie. powtórzmy jeszcze raz, że ogólna zasada minimalizacji funkcji metodą tablic Karnauhga polega na "nakryciu” wszystkich jej jedynek (albo wszystkich jej zer) przy pomocy jak najmniejszej liczby jak największych grup. W tym celu wykorzystać można również kreski w tablicy, zaś pewne jedynki (pewne zera) mogą być włączone do więcej niż jednej grupy.

Metoda minimalizacji za pomocą tablic Karnaugha jest prosta i skuteczna przy niewielkiej liczbie zmiennych - w praktyce dla funkcji do pięciu, najwyżej sześciu zmiennych. Powyżej tej granicy wyszukiwanie pól sąsiednich w tablicy staje się kłopotliwe i metoda przestaje bj użyteczna. Należy wówczas zastosować inne metody, a w przypadku szczególnie dużej liczby zmiennych - metody komputerowe.

^X3^X^ 2\	00	01	3’ ł	10	2 / 1 2 3’ y = XjX3 ♦ xlX2x3 ♦ XjX2x4 lub 1 2 3” y - x1x3 * xjx2x3 + x2x3x4
00	0	0 _	' 0	V
01	0	f‘[	co	0
11	f 1	U	0	0
10	l^1		0	0
	“ \ y 1 3”				dwie minimalne NPS

grupa 5 jest zbędna

1    2    3

*2*3*4 ^{+ X}2^X3^X4 ^{+ X}1^X2^X4 ⁺ 4

⁺ *1^X2^X3

Rys. 3.15. Przykłady minimalizacji funkcji 3.4.2. Metoda Quine’a-McCluskey'a

Metoda ta może być stosowana do funkcji dowolnej liczby zmiennych, ^a w praktyce - gdy liczba zmiennych jest większa lub równa sześć. Ponieważ, jak już zaznaczono w rozdz. 3.4.1, w przypadku funkcji "iększej liczby zmiennych z reguły stosuje się - jako bardziej zwarty -^2aPis tych funkcji w postaci dziesiętnej (typu (3.31) lub (3.32)), dlatego też przedstawimy ten wariant metody Quine'a-McCluskey’a. który °Peruje na dziesiętnej reprezentacji funkcji. W literaturze, np. ^1.16,1), znaleźć można również . opis innego wariantu metody °Perującego na binarnym zapisie funkcji.