Wykład XIV
Asynchroniczne układy
sekwencyjne –
kodowanie tablic przejść-wyjść
Piotr Kawalec
Wykład XIV - 1
Technika cyfrowa
Plan wykładu
Wyścigi w automatach
asynchronicznych
Zasady kodowania
automatów asynchronicznych
Zastosowanie rachunku podziałów do kodowania automatów asynchronicznych Piotr Kawalec
Wykład XIV - 2
Wyścigi w automatach asynchronicznych
Wyścigami w automatach asynchronicznych nazywamy zjawisko istnienia różnych dróg przejść ze stanu niestabilnego do stanu stabilnego
Wyścigi mogą wystąpić w układzie tylko wtedy gdy przełączenie automatu wymaga zmiany stanu co najmniej dwóch elementów pamięci
Wyścigiem krytycznym nazywamy zjawisko możliwości przejścia automatu ze stanu niestabilnego do różnych stanów stabilnych
Piotr Kawalec
Wykład XIV - 3
Wyścigi w automatach asynchronicznych
Wyścigi krytyczne w automatach asynchronicznych muszą być zawsze usuwane !!!
Wyścigiem niekrytycznym nazywamy zjawisko przejścia automatu ze stanu niestabilnego różnymi drogami do odpowiadającego mu stanu stabilnego
Wyścigi niekrytyczne nie prowadzą do błędnego działania układu, a więc nie muszą być usuwane Piotr Kawalec
Wykład XIV - 4
Wyścigi w automatach asynchronicznych
Jeżeli w kolumnie tablicy przejść odpowiadającej aktualnemu stanowi wejść występują dwa lub więcej stany stabilne to grozi wyścig krytyczny
Jeżeli w kolumnie tablicy przejść odpowiadającej aktualnemu stanowi wejść jest tylko jeden stan stabilny,to może wystąpić tylko wyścig niekrytyczny
Warunkiem wystarczającym uniknięcia wyścigów jest takie zakodowanie automatu, aby przy każdej zmianie stanu zmieniał się stan tylko jednego elementu pamięci (graficzna metoda hipersześcianów) Piotr Kawalec
Wykład XIV - 5
Kodowanie z zastosowaniem rachunku podziałów
Podstawowym warunkiem jaki musi spełnić kod przyjęty do kodowania automatu asynchronicznego jest zlikwidowanie wyścigów krytycznych
Zastosowanie rachunku podziałów pozwala nie tylko usunąć wyścigi lecz również uzyskiwać układy o minimalnej złożoności
Ta metoda kodowania dopuszcza równoczesną zmianę stanu kilku elementów pamięci Piotr Kawalec
Wykład XIV - 6
Kodowanie z zastosowaniem rachunku podziałów
W metodzie tej wykorzystuje się następujące twierdzenie
Twierdzenie 1
Jeśli dla każdego x ⊂
⊂
i
X i każdej pary stanów sk, sm
S, takich, że δ(sk, xi) = δ(sm, xi) = sm , kody stanów sk, sm mają część wspólną, która nie występuje w kodzie żadnego s
≠
r takiego, że δ(sr, xi) = sn
sm, to kodowanie
nie powoduje wyścigów krytycznych
Piotr Kawalec
Wykład XIV - 7
Kodowanie z zastosowaniem rachunku podziałów
Poprawne kodowanie można uzyskać, wybierając podziały tak, aby zawsze istniał podział, w którym pary stanów (sk, sm) i (sr , sn) należą do różnych bloków
Wyrażenia sk, sm - sr , sn nakazujące umieszczenie różnych par stanów w różnych blokach podziału określającego kod, nazywamy warunkami elementarnymi
Piotr Kawalec
Wykład XIV - 8
Przykład kodowania
Zakodować tablicę przejść
x
δ(1,x )=3 ; δ(3,x )=3; δ(2,x )=2
3
3
3
s
x1
x2
x3
x4
kody stanów 1 i 3 muszą różnić
1
1
1
3
2
się od kodu 2
τ = (2, 13)
2
1
1
2
2
2
3
1
1
3
3
δ(1,x )=2 ; δ(2,x )=2; δ(3,x )=3
4
4
4
kody stanów 1 i 2 muszą różnić
się od kodu 3
τ = (3, 12)
3
x
Q1Q2
x1
x2
x3
x4
(1) 00
00
00
01
10
Zakodowana
(2) 10
00
00
10
10
tablica przejść
11
--
--
--
--
(3) 01
00
00
01
01
Piotr Kawalec
Wykład XIV - 9
Technika cyfrowa Określenia związane z kodowaniem
Rodziną końcową Tk nazywamy zbiór podziałów prawidłowych spełniający warunki
Î iloczyn tych podziałów daje podział zerowy Î kodowanie zgodne z podziałami Tk nie powoduje wyścigów krytycznych
Optymalną rodziną końcową Tk opt nazywamy rodzinę końcową zapewniającą przy kodowaniu: Î najprostszą postać funkcji przejść Î najprostszą postać funkcji wyjść
Wyznaczanie Tk opt spośród Tk realizowane jest analogicznie jak dla automatów synchronicznych Piotr Kawalec
Wykład XIV - 10
Technika cyfrowa Kodowanie z zastosowaniem rachunku podziałów
Podziałem wewnętrznym π(xi) nazywamy podział, którego bloki zawierają stany o identycznych xi -
następnikach
Twierdzenie 2
Jeżeli każdy z dwóch dowolnych bloków każdego podziału wewnętrznego π(xi) zawarty jest w dwóch różnych blokach jakiegoś podziału prawidłowego ze zbioru podziałów o zerowym iloczynie, to zbiór ten tworzy rodzinę końcową Tk i może być wzięty do kodowania
Piotr Kawalec
Wykład XIV - 11
Technika cyfrowa Kodowanie z zastosowaniem rachunku podziałów
Zgodnie z twierdzeniem 2 do kodowania należy brać podziały wewnętrzne (jeśli są podziałami prawidłowymi), albo podziały prawidłowe większe od wewnętrznych
Twierdzenie 2 narzuca warunek silniejszy od twierdzenia 1
Przykład Wyznaczyć podziały do kodowania x
π
s
x
(x )={134, 2}; π(x )=τ ; π(x )=τ
1
x2
x3
x4
2
3
13
4
14
1
4
1
3
4
podziały τ oraz τ nie zapewniają
13
14
2
4
2
2
2
separacji bloków podziału π(x )
2
3
4
1
3
2
warunek separacji 134 -2 należy rozbić 4
4
1
2
4
na warunki elementarne 13-2 oraz 14-2
Piotr Kawalec
Wykład XIV - 12
Technika cyfrowa Etapy kodowania z zastosowaniem rachunku podziałów
Wypisać podziały wewnętrzne i spośród nich albo podziałów prawidłowych większych od wewnętrznych wyznaczyć podziały do kodowania
Z wypisanych podziałów utworzyć rodziny końcowe
Spośród rodzin końcowych wyznaczyć rodzinę optymalną uwzględniając zarówno uproszczenie funkcji przejść jak i funkcji wyjść
Zakodować tablice przejść, dookreślając stany występujące na drogach przejść
Dla określonej struktury układu wyznaczyć funkcje wzbudzeń
Narysować schemat ideowy układu
Piotr Kawalec
Wykład XIV - 13