074 075

przechodnlości relacji alesprzeczności. Proces ten przedstawiony jest na rys. 3.6.

W wyniku tej operacji i ewentualnego dołączenia stanów nlesprzecznych tylko z sobą, otrzymujemy następujące zbiory stanów nlesprzecznych.

.. DE?, BCDB, AG, ABE    i

Hależy teraz z tych zbiorów wyselekcjonować rodzinę, która spełnia podane wcześniej warunki*⁵ . Zastosujemy w tym celu metodę prób i błędów (Inną metodę można znaleźć np. w-[17 str. 96]) . Metoda prób polega na wyborze minimalnej Ilości zbiorów, które łącznie pokrywają zbiór stanów układu zadanego, a następnie sprawdzaniu zamkniętoścl i próbach usuwania stanów z poszczególnych zbiorów.

Zacznijmy od wyboru minimalnej liczby zbiorów pokrywających wszystkie stany układu sekwencyjnego. V tym celu podkreślimy wszystkie stany występujące tylko Jeden raz w wypisanych wyżej zbiorach. Mamy

DE?, BCDE, AG, ABE

Zbiory z podkreślonymi elementami muszą wejść do szukanej rodziny ze

ajNMWil	A (	»ir	» t > (
1 I 1 1	C ( I l	t - t t t t	D 1 ( -(Alt
1 «	A 1	A - t	Ali-
1 1	- r	A A A	I A A A

Rys. 3*7. tablica do sprawdzania zamknięcia rodziny zbiorów (przykład 3.5)

względu na warunek pokrycia. Ponieważ w naszym przypadku pokrywają one wszystkie stany układu minimalizowanego, należy sprawdzić, czy spełniony jest warunek zamknięcia wyselekcjonowanej rodziny.,/® tym celu tworzymy, na pod_T stawie tablicy przejść, tablicę przedstawioną na rys. 3.7*

Z rysunku tego widać, że ze zbioru AG pod wpływem sygnału 01 układ przechodzi do zbioru AE, którego obecnie nie ma w próbnie wybranej rodzinie zbiorów, z czego wynika, że wyselekcjonowana rodzina nie jest zamknięta. Podobnie, zbiór BCDE pod wpływem sygnału 1 0 przechodzi w zbiór AE.

Ze zbiorów badanej rodziny nie można też usunąć elementów tak,aby znikło przejście do zbioru AE, bowiem wtedy rodzina ta przestanie pokrywać zbiór stanów układu zadanego (np. nie można wyeliminować ani A ani G ze zbioru AG).

Jedyne co pozostaje, to dodać do badanej rodziny jeden zbiór. Ponieważ przy badaniu warunku zamknięcia stwierdzono brak podzbioru AE, dołączymy ten zbiór, otrzymując następną próbną rodzinę

AG, DE?, BCDE, ABE

Z tablicy na rys. 3.8 widać, że otrzymana rodzina jest zamknięta. ,

Zwróóay uwagę, ża w przypadku rozłącznych zbiorów stanów nlasprzacznycb otrzymana zbiory tworzą poszukiwaną rodzinę 1 znika koniaoznoód aalakoji.

mm ctamm	A t	M F	t t » C	a a r
i i	t C	t - F	M t -	t t> -
t i	C A	1 C 1	Cl » t	ICC
i i	A ł	( - »	Alt-	A * -
i i .	- F	4 A A	1 A 4 A	- £ A .

Rys. 3.8. Tablica do sprawdzania zamknięcia rodziny Zbiorów (przykład 3.5)

‘SwMMaU*	A 1	F	1 t » t	A 1
«i	C l	F.	Alt-	t -
11	I A	»	CIII	CC
11	A t	«	Alt-	A -
11	- F	A	f A 4 A	- A

	' N	n	<<	u
(Al) «t	t/\	0	«/l	fi/o
	&	0	0	* um i/\
(ku) r	0	0	i/\	i/\
(AC) i	r/-	0	i lh ff/1	kin m

Rys. 3.9. Tablica do sprawdzania ¹ zamknięcia rodziny zbiorów (przykład 3-5)

Rys. 3.10. Tablica przejść/wyjść układu minimalnego z przykładu 3.3

Pozostają więc tylko sprawdzać, czy nie moZna z poszczególnych zbiorów usunąć niektórych elementów, oczywiście nie naruszając spełnienia warunków pokrycia 1 zamknięcia. '

Okazuje się, Ze można ze zbioru DEF usunąć elementy OS, zaś ze zbioru ABE element B. Powstała rodzina spełnia warunek pokrycia, zaś zamknięcie Jest widoczne z tablicy na rys. 3.9.

Ostatecznie dysponujemy rodziną zbiorów stanów nlesprzecznych

Ad, F, BCDE, AE

z których każdy będzie odpowiadał nowemu stanowi- minimalnego układu sekwencyjnego .

Ostatnim etapem minimalizacji liczby 3tanów układu sekwencyjnego Jest konstrukcja nowej tablicy przejść/wyjść. W naszym, przypadku na podstawie tablic z rys. 3«* i 3*9 otrzymujemy tablicę przejść/wyjść układu minimalnego daną na rys. 3-10.    #

Następny przykład będzie dotyczył przypadku minimalizacji liczby stanów układu w pełni określonego. .....

Przykład 3.6

Wyznaczyć układ minimalny Moore'a wykrywający sekwencje 0010 lub 1010 lub 11010.    ■'    ł

Z treści zadania wynika bezpośrednio graf.1 tablica’przejść/wyjść przedstawiona na rys,' -JiH.' ^:

Tablica trójkątna do wyznaczania zbiorów stanów nlesprzecznych przedstawiona Jest narys. 3.12. Na jej podstawie wypisujemy pary i tworzymy większe zbiory stanów nlesprzecznych, jak to pokazano w tablicy na rys.3.13.