Technika cyfrowa
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
Technika cyfrowa
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
Technika cyfrowa
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
Technika cyfrowa
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
Technika cyfrowa
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
Technika cyfrowa
Kodowanie z zastosowaniem rachunku
podziałów
W metodzie tej wykorzystuje się następujące
twierdzenie
Twierdzenie 1
Jeśli dla każdego xi �" 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 sr takiego, że �(sr, xi) =sn `" sm, to kodowanie
nie powoduje wyścigów krytycznych
Piotr Kawalec Wykład XIV - 7
Technika cyfrowa
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
Technika cyfrowa
Przykład kodowania
Zakodować tablicę przejść
x
�(1,x3)=3 ; �(3,x3)=3; �(2,x3)=2
s x1 x2 x3 x4
kody stanów 1 i 3 muszą różnić
1 1 1 3 2
się od kodu 2 �2 = (2, 13)
2 1 1 2 2
3 1 1 3 3
�(1,x4)=2 ; �(2,x4)=2; �(3,x4)=3
kody stanów 1 i 2 muszą różnić
się od kodu 3 �3 = (3, 12)
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
Ą(x2)={134, 2}; Ą(x3)=�13 ; Ą(x4)=�14
s x1 x2 x3 x4
podziały �13 oraz �14 nie zapewniają
14134
24222 separacji bloków podziału Ą(x2)
34132
warunek separacji 134 -2 należy rozbić
44124
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