072 073

72

) 'j/ł* zamknięta,

5’ zawierała minimalną ilość zbiór "w stanów niesprzecznych przy spełnle:.; u w*runk'w 1) i 2),

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

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

Łowimy, że rodzina Rj 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 Tje R^.

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

Cały proces poszukiwania zbiorów niesprzecznych, 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 Uealy'ego zadanego tablicą na rys. 3.4.

M II 11 l»

	^E/t	v<	~h
»/•	^E/1	Vt	^E/-
»/o	*/\	^6/(	Vi
^E/o	D/-	^6/ł	Vi
	C/-	-/,	V-
*h	»/«	^6/t	^kA
'/1	Vt	6/-	^F/o

Proces minimalizacji rozpoczynamy od wyznaczenia zbiorów stanów niesprzecznych. C tym celu musimy zbadać nie sprzeczność wszystkich możliwych stanów. Najwygodniej jest dokonać tego korzystając z tablicy trójkątnej (rys. 3-5a), 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,

Rys. 3*4. Tabela przejść/ /wyjść do przykładu 3.5

b)    Jeżeli dana para stanów jest niesprzeczna, 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-eznoscl tych stanów następnych; Jest to tzw. niesprzeczność warunkowa, i.tody w odpowiednią kratkę wpisujemy te pary różnych stanów następnych. Wypeł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-lejne 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 niesprzecznych (przykład 3-5)

r) -

i) if

0)    *r,X, w t)

1) k)

KDUMNA

Rys. 3.6. Tworzenie zbiorów stanów niesprzecznych (przykład 3.5). Przekreślone pary stanów weszły przynajmniej raz w skład większych zbiorów

es»

warunek niesprzeczności 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. V kratce o współrzędnych E,<ł występują warunki CA i AF. Ponieważ para stanów CA jest sprzeczna, warunek nie-sprzecznoścl BIG Jest niespełniony 1 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 niesprzecznych.

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.

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