072 073

72

) ’»ył^J zamknięta,

5 zawierała minimalną ilość zbiorów stanów niesprzeeznych przy spełni"!.!u w»runk 'w 1) i 2),

ą) każdy ze zbiorów stanów niesprzeeznych powinien zawierać możliwie mato elementów przy spełnieniu warunków 1), 2) i 3).

l.owimy, że Rj pokrywa zbiór stanów układu zadanego, jeżeli każdy jego st-n występuje przynajmniej w jednym zbiorze T^e R,,

Łowimy, że rodzina R^ jest zamknięta, jeżeli zbiór stanów następnych otrzymanych z dowolnego zbioru T^e R^ za pomocą dowolnego sygnału wejściowego x jesc podzbiorem jednego ze zbiorów T^e R^.

Po wybraniu rodziny stanów niesprzeeznych spełniających wyżej wymienione warunki konstruujemy, przyjmując jako nowe stany - zbiory niesprzeczne, nowy układ sekwencyjny, który pokrywa układ zadany i jest minimalny.

Cały proces poszukiwania zbiorów niesprzeeznych, a następnie rodziny będącej podstawą budowy układu minimalnego oraz konstrukcji układu minimalnego, przedstawiamy na poniższym przykładzie.

Przykład 5.5

Zminimalizować liczbę stanów wewnętrznych układu sekwencyjnego Healy'ego zadanego tablicą na rys. 3.4.

00 II11H

V-	^E/.	V<	~h
»/•	^E/1	Vi	^E/-
»/«	^lA	^6/i	Vi
^E/o	D/_	^6/»	Vi
	C/-	-/,	V-
	»/o	^6/t	^kA
	\A	6/-	^F/o

Proces minimalizacji rozpoczynamy od wyznaczenia zbiorów stanów niesprzeeznych. Z' tym celu musimy zbadać niesprzeczność wszystkich możliwych stanów. Najwygodniej jest dokonać tego korzystając z tablicy trójkątnej (rys. 3.5-a), której kolejne kratki odpowiadaj ą wszystkim możliwym parom stanów. Tablicę tę w oparciu o tablicę przejść/wyjść wypełniamy następująco:

a)    Jeżeli danej parze stanów odpowiadają określone i różne sygnały wyjściowe, to badane stany są sprzeczne i w odpowiednie kratki wpisujemy znak x_f

Rys.    Tabela przejść/

/wyjść do przykładu 3.5

b)    Jeżeli dana para stanów jest niesprzeozna, gdyż sygnały wyjściowe i stany następne są identyczne, o ile są określone, to w odpowiednią kratkę wpisujemy znak V.

c) Jeżeli danej parze stanów odpowiadają identyczne, o ile są określone, sygnały wyjściowe (sygnały wyjściowe niesprzeczne).natomiast niektóre stany następne są określone i różne, wtedy nie możemy od razu stwierdzić nlesprzeczności danej pary stanów. Zależy ona bowiem od niesprze-eznosci tych stanów następnych; Jest to tzw. niesprzeczność warunkowa, l.tody w odpowiednią kratkę wpisujemy te pary różnych stanów następnych, '..ypełniając tablicę z rys. 3.5a według tych reguł otrzymujemy w naszym przykładzie tablicę Jak na rys. 3.5b.

?' następnym etapie sprawdzamy niesprzeczność par stanów wpisanych w to-lsjne kratki tablicy 3.5b. Np. w kratce o współrzędnych A,B znajduje się

Rys. 3.5.

Kolejne etapy poszukiwania zbiorów stanów niesprzeeznych (przykład 3.5)

r) -n tf

M łf,X, w

t)

») K.tfK, KM

k)

KOLUMNA

Rys. 3*6. Tworzenie zbiorów stanów niesprzeeznych (przykład 3-5). Przekreślone pary stanów weszły przynajmniej raz w skład większych zbiorów

o

warunek niesprzeczność! CD. Sprawdzamy teraz zawartość kratki o współrzędnych C_}D. Ponieważ w kratce tej nie występuje znak x oznaczający sprzeczność, zawartość kratki A,B pozostawiamy bez zmian. W kratce o współrzędnych E,<ł występują warunki CA i AF. Ponieważ para stanów CA jest sprzeczna, warunek nie-sprzeczności EG jest niespełniony i w kratkę o współrzędnych E,G wpisujemy znak x.

Przebieganie kolejno wszystkich kratek, w których występują warunki,kontynuujemy tak długo, aż w kolejnym przeglądzie nie wpiszemy znaku x w żadną kratlę.Współrzędne wszystkich kratek nie zawierających znaku x są parami stanów nie-sprzecznych.

W naszym przykładzie tylko jeden warunek (CA) był niespełniony, co pociągnęło za sobą sprzeczność stanów EG, ale nie pociągnęło już za sobą sprzeczności innych stanów. Końcowa tabela pokazana jest na rys. 3.5c.

Na podstawie tej tabeli wypisujemy wszystkie pary stanów niesprzeeznych, łącząc je następnie w zbiory o maksymalnej liczebności, pamiętając o nie-