ULOG10, Studia WIT - Informatyka, PUL - Podstawy układów logicznych

[ Pobierz całość w formacie PDF ]
Minimalizacja automatu
Minimalizacja automatu to minimalizacja liczby stanów.
Jest to transformacja automatu o danej tablicy przejść-wyjść na równoważny mu (pod
względem przetwarzania sygnałów cyfrowych) automat o mniejszej liczbie stanów
wewnętrznych.
Jest to prawie zawsze możliwe, gdyż w procesie pierwotnej specyfikacji często
wprowadzane są stany nadmiarowe lub równoważne.
Minimalizacja liczby stanów
x
abcdab cd
S
S1
– S3S4S2– 1 1 1
abcd a bcd
S2
S4 –
–
– 0
–
–
–
ACBCA 0 111
S3
S6 S6 –
– 0
1
– –
S4
– S6S1S5– 0 0 1
BCCA– 0 11–
S5
––2––– 1–
CBCAB 0 001
I
T
P
W
S6
S3 – S2S30 – 0 1
ZPT
Czysty zysk – zamiast trzech przerzutników tylko dwa!
1
Minimalizacja liczby stanów
Kluczem do rozwiązania tego problemu jest:
Relacja zgodności na zbiorze stanów S:
(pary stanów zgodnych)
Maksymalne zbiory stanów zgodnych
(Maksymalne Klasy Zgodności)
Selekcja zbiorów zgodnych spełniających tzw.:
−
warunek pokrycia
−
warunek zamknięcia
I
T
P
W
Wyselekcjonowane w ten sposób zbiory
reprezentują stany automatu minimalnego
ZPT
2
Jak wyznaczać relację zgodności stanów?
Dwa stany wewnętrzne Si, Sj są
zgodne
, jeżeli dla każdego
wejścia v mają one niesprzeczne stany wyjść, a ich stany
następne są takie same lub niesprzeczne.
x
abcdabcd
S
Stany zgodne
warunkowo
1 –342–111
2 4–––0–––
3 66––01 ––
4–61 5–001
Stany zgodne
5 ––2–––1 –
6
3–230–01
Stany sprzeczne
I
T
P
W
Dwa stany wewnętrzne S
i
, S
j
są
zgodne warunkowo
,
jeżeli ich
stany wyjść są niesprzeczne oraz
dla pewnego v
V
ich stany wyjść są sprzeczne.
∈
V para stanów
następnych do S
i
, S
j
(ozn. S
k
, S
l
):
(S
i
, S
j
)
∈
ZPT
≠
(S
k
, S
l
)
3
Stany Si, Sj są
sprzeczne,
jeżeli dla pewnego v
Relacja zgodności
Ze względu na to, że para zgodna warunkowo może
– po dalszej analizie – okazać się parą zgodną albo
sprzeczną w obliczaniu wszystkich par zgodnych
posługujemy się tzw. tablicą trójkątną.
Tablica trójkątna zawiera tyle kratek, ile jest
wszystkich możliwych par stanów. Na przykład dla
automatu o 5 stanach:
I
T
P
W
ZPT
4
Tablica trójkątna
2
3
v
x
4
5
(i,j)
1 2
3
4
Kratki tablicy wypełniamy symbolami:
v
–jeżeli para stanów jest zgodna,
x
–jeżeli para stanów jest sprzeczna, lub
I
T
P
W
(i,j)-paą
(parami stanów następnych), jeżeli jest to
para zgodna warunkowo.
ZPT
5
[ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • emaginacja.xlx.pl

    •