074 075

⁷⁴ ^

‘a

przschodniości relacji niesprzecznoś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.

BEP, SCPS, 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ę modna 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 zamknlętości 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. W 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

mm mmi \Minao'	»»	» t r	1 t > l
• i	C (	{ - r	Dl(-
11	( 1	i t i	Elit
11	A 1	t - i	A * * -
i»	- 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, ualeiy sprawdzić, czy spełniony jest warunek zamknięcia wyselekcjonowanej rodziny ..W 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, DBF, BCDE, ABE

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

*^ Zwróóey uwagę, że w przypadku rozłącznych zbiorów itauów nlesprzecznych otrzymane zbiory tworzą poszukiwaną rodzinę 1 znika konieczność selskoji.

mm amSi ■—jomtun	A t	M f	I t I E	1 B f
1 •	l E	l - F	»:» E -	t P -
t i	£ A	1 C 1	Elit	1 CC
i i	i ł	( - t	Alt-	A A -
i i .	- F	4 A A	II 4 1	- i A .

Rys. 3.8. Tablica do sprawdzania sarnimi fala rodziny Zbiorów (przykład 3.5)

bstitowt	A t	F	I t I E	A I
«•	( E	F.	1 t t -	t -
11	E A	»	Elit	Et
11	A t	(	Ali-	A -
11	- F	A	E A A A	- A

	' N	n	<i	u
(At) «t	t/\	*A	«/i	f/o
	*r-	r/o	i/\	« un <f/l
(kk) r	^fA	0	i/\	t/\
(«) i	r/-	tA	Ol LU 5/1	*un 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-5

Pozostają więc tylko sprawdzić; 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 DE, 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

AG, F, BCDE, AE

z których kaZdy będzie odpowiadał nowemu stanowi' minimalnego układu sekwencyjnego .

Ostatnim etapem minimalizacji liczby stanów układu sekwencyjnego Jest konstrukcja nowej tablicy pnżejść/wyjść. V naszym przypadku na podstawie tablic z rys. 3.4 i 3*9 otrzymujemy tablicę przejść/wyjść układu minimalnego daną na rys. 3-10.    4+

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, 3»11.'

Tablica trójkątna do wyznaczania zbiorów stanów nlesprzecznych przedstawiona jest na rys. 3.12. Na Jej podstawie wypisujemy pary i tworzymy większe zbiory stanów nlesprzecznych, jak to pokazano w tablicy na rys.3-13.