Rotation of�

166

W opisie prezentowanej tu metody występuje pojęcie tzw. indeksu liczby dziesiętnej.

Definicja 3.14

Indeks liczby dziesiętnej jest to ilość jedynek w odpowiadającej jej liczbie binarnej.

W tabeli 3.2 przedstawiono początkowe liczby dziesiętne posegregowane według indeksów.

Tabela 3.2. Indeksy początkowych liczb dziesiętnych

Indeks	0	1	2	3
Liczby	0	1,2,4,8,	3.5,6.9.10,12.	7,11.13,14,
		16____	17,18.20,24____	19,21,22,25,25,28____

	4	5
	15,
	23,27,29,30____	31____

Metoda Quine’a-McCluskey’a realizowana jest w dwóch etapach:

1.    Etap I ma za cei wyznaczenie wszystkich prostych implikantów - w przypadku szukania minimalnej NPS funkcji albo wszystkich prostych implicentów - w przypadku NPI funkcji.

2.    W Etapie. II,. na bazie wyników Etapu I, generowany jest minimalny zestaw implikantów (minimalny zestaw implicentów) nakrywający wszystkie jedynki (wszystkie zera) funkcji.

A zatem, w przeciwieństwie do metody tablic Karnaugha. dwa zasadnicze etapy minimalizacji funkcji sformułowane w rozdz. 3.3 są tu wyraźnie rozgraniczone - odpowiadają im ściśle dwa etapy metody.

Metoda Quine’a-McCluskey’a zostanie najpierw sformułowana dla NPS f unkcji.

Algorytm dla Etapu I jest następujący: j Dziesiętne reprezentacje zespołów wartości zmiennych dla których

funkcja jest równa jedności lub nieokreślona (a zatem elementy 1 ^M _ "

zbioru F    u F ). należy podzielić na grupy o jednakowych

indeksach i wypisać w pierwszej kolumnie w kolejności zgodnej ze wzrastającą wartością indeksu.

2 Łączeniu podlegają dwie liczby z sąsiednich grup, różniące się o potęgę dwójki, przy czym liczba należąca do grupy o mniejszym indeksie musi być mniejsza. Należy więc kolejne liczby danej grupy (poczynając od grupy pierwszej) porównywać z kolejnymi większymi od nich liczbami sąsiedniej (niżej zapisanej) grupy. W przypadku,gdy porównywane liczby różnią się o 1,2,4,8 ... itd. a więc dają się połączyć, należy je zapisać w następnej kolumnie, przy czym mniejszą na początku, a obok w nawiasie należy wpisać ich różnicę, np. wynikiem połączenia 12 i 14 jest 12,14 (2).

3.    Z kolei, w sposób analogiczny do tego z punktu 2, porównywane są pierwsze liczby w wierszach sąsiednich grup nowo utworzonej kolumny. Wiersze, w których pierwsze liczby różnią się o potęgę dwójki (mniejsza liczba musi być z grupy o mniejszym indeksie) oraz dodatkowo, w których liczby w nawiasach są jednakowe, należy połączyć ze sobą i umieścić w trzeciej kolumnie, wpisując je w porządku rosnącym. Obok, w nawiasie należy wpisać różnicę pochodzącą z poprzedniej kolumny z nawiasów łączonych wierszy oraz bieżącą różnicę pierwszych liczb łączonych aktualnie wierszy, np. wynikiem połączenia 8,9(1) i 12,13,(1) jest 8,9,12,13(1,4).

4.    Powyższa procedura trwa dopóty, dopóki nie skortczą się możliwości łączenia.

Uwaga: W punktach 2,3 i 4 wiersze, które udało się połączyć z innymi należy oznaczyć symbolem "V", natomiast te których nie udało się Połączyć z żadnym innym - symbolem    Wiersze oznaczone symbolem

gwiazdki reprezentują proste implikanty funkcji.

Przykład 3.10 [ 11 ]

Rozpatrzymy funkcję w pełni określoną

(3.53)

y = f(x₁,x₂,x₃,x₄) = £ (4,7,9,10,12,13,14,15)