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*5 . 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 podT 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 1 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.
Wyszukiwarka
Podobne podstrony:
074 075 74 ^ ‘a przschodniości relacji niesprzeczności. Proces ten przedstawiony Jest na rys. 3>6
OMiUP t1 Gorski 9 Obraz sprężania wielostopniowego w układzie T—s przedstawiony jest na rys. 3.8. Ry
P1100243 rotacji przedstawiono jest na rys. 24.1 (jądro a) i ten typ obejmuje wszystkie o parzystej
Wa&St Hydr20 W l ii i nulu
3.1.1. Zespół łożyska Schemat komory badawczej przedstawiono jest na Rys 9. Czop badanego łożyska (p
7 Konstrukcja przetwornika piezoelektrycznego typu "sandwich", przedstawiona jest na rys.
/ Zadanie 10 Zrealizować układ sterowania klimatyzatora. Cykl pracy układu przedstawiony jest na rys
Pętla while przedstawiona jest na rys. 27. W środku obramowania umieszcza się progr am, który wymaga
Analogowocyfrowy przetwornik I Schemat blokowy analogowo-cyfrowego przetwornika l_ przedstawiony jes
WYTYCZNE PROJEKTOWANIA ULIC- 1.4.4. Schemat węzła typu WC przedstawiony jest na rys. 9.2. Dostosowan
OMiUP t1 Gorski24 Budowa filtra przedstawiona jest na rys. 4.24. Wkład filtrujący 6 złożony jest z p
amat urz kr064 Układ stosowany przy omawianej modulacji przedstawiony jest na rys. 5-15. Zwykle stos
225 (4) 225 warstw, wartość €rain(k) powinna maleć. Typowy przebieg eniin(&) przedstawiony jest
więcej podobnych podstron