Piotr Kawalec

Wykład VI - 1

Wykład VI

Kodowanie automatów

asynchronicznych

Technika cyfrowa

Piotr Kawalec

Wykład VI - 2

Technika cyfrowa

Kodowanie tablic przejść-wyjść



Kodowanie automatów asynchronicznych

polega,

podobnie jak w automatach

synchronicznych, na

przyporządkowaniu

stanom wewnętrznym s stanów elementów
pamięciowych

Q

1

,...,

Q

k



Kodowanie automatów asynchronicznych jest

procesem bardzo ważnym, bowiem

niewłaściwe

zakodowanie może prowadzić

do błędnego działania

układu

Piotr Kawalec

Wykład VI - 3

Technika cyfrowa

Wyścigi w automatach
asynchronicznych

x

Q

1

Q

2

x

1

x

2

x

3

x

4

00

1

3

01

2

1

11

1

3

10

2

2



Dla litery wejściowej x

2

przy przejściu ze stanu 1 do 1

konieczna jest zmiana obu elementów pamięci

Q

1

Q

2

= 00  11



Ze względu na różne czasy propagacji sygnałów możliwe

są

następujące drogi przejścia

 Q

1

Q

2

= 00 

01

 11

układ trafi i pozostanie w

stanie

2

 Q

1

Q

2

= 00  10  11

układ może trafić do stanu

1

Piotr Kawalec

Wykład VI - 4

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 VI - 5

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 VI - 6

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 VI - 7

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 VI - 8

Technika cyfrowa

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

s

k

,

s

m



S,

takich, że

(s

k

, x

i

) = (s

m

, x

i

) = s

m

,

kody

stanów

s

k

,

s

m

mają część wspólną, która nie

występuje w kodzie

żadnego

s

r

takiego, że

(s

r

,

x

i

) = s

n

 s

m

,

to kodowanie nie powoduje

wyścigów krytycznych

Piotr Kawalec

Wykład VI - 9

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 (s

k

, s

m

) i (s

r

, s

n

)

należą do różnych bloków



Wyrażenia s

k

, s

m

- s

r

, s

n

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 VI - 10

Technika cyfrowa

Przykład kodowania



Zakodować tablicę przejść

x

s

x

1

x

2

x

3

x

4

1

1

1

3

2

2

1

1

2

2

3

1

1

3

3

x

Q

1

Q

2

x

1

x

2

x

3

x

4

(1) 00 00 00 01 10
(2) 10 00 00 10 10

11 --

--

--

--

(3) 01 00 00 01 01

(1,x

3

)=3 ; (3,x

3

)=3; (2,x

3

)=2

kody stanów 1 i 3 muszą różnić
się od kodu 2



2

= (2, 13)

(1,x

4

)=2 ; (2,x

4

)=2; (3,x

4

)=3

kody stanów 1 i 2 muszą różnić
się od kodu 3



3

= (3, 12)

Zakodowana
tablica przejść

Piotr Kawalec

Wykład VI - 11

Technika cyfrowa

Określenia związane z kodowaniem



Rodziną końcową T

k

nazywamy zbiór podziałów

prawidłowych spełniający warunki



iloczyn tych podziałów daje podział zerowy



kodowanie zgodne z podziałami T

k

nie

powoduje

wyścigów krytycznych



Optymalną rodziną końcową T

k opt

nazywamy

rodzinę

końcową zapewniającą przy

kodowaniu:



najprostszą postać funkcji przejść



najprostszą postać funkcji wyjść



Wyznaczanie

T

k opt

spośród

T

k

realizowane jest

analogicznie jak dla automatów

synchronicznych

Piotr Kawalec

Wykład VI - 12

Technika cyfrowa

Kodowanie z zastosowaniem rachunku
podziałów



Podziałem wewnętrznym (x

i

)

nazywamy

podział,

którego bloki zawierają stany o

identycznych

x

i

-

następnikach

Twierdzenie 2

Jeżeli każdy z dwóch dowolnych bloków każdego

podziału wewnętrznego

(x

i

)

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ą

T

k

i może być wzięty do

kodowania

Piotr Kawalec

Wykład VI - 13

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

1

x

2

x

3

x

4

1

4

1

3

4

2

4

2

2

2

3

4

1

3

2

4

4

1

2

4

(x

2

)={134, 2}; (x

3

)=

13

; (x

4

)=

14

podziały



13

oraz



14

nie zapewniają

separacji bloków podziału

(x

2

)

warunek separacji 134 -2 należy
rozbić na warunki elementarne 13-
2 oraz 14-2

Piotr Kawalec

Wykład VI - 14

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