Technika cyfrowa
Wykład IX
Synteza układów sekwencyjnych
Piotr Kawalec Wykład IX - 1
Technika cyfrowa
Plan wykładu
Pojecie układów sekwencyjnych
Rodzaje i struktury automatów
z pamięcią
Metody opisu układów sekwencyjnych
tablice przejść  wyjść
grafy przejść
Piotr Kawalec Wykład IX - 2
Technika cyfrowa
Pojęcie układu sekwencyjnego
Def. Układami sekwencyjnymi nazywamy układy
cyfrowe w których stan wyjścia zależy nie tylko
od aktualnych sygnałów wejściowych lecz również
od stanu wejść w poprzednich chwilach czasowych
Historia działania układu odwzorowywana jest
w postaci stanów jego pamięci.
Modelem matematycznym układu sekwencyjnego
jest automat skończony z pamięcią.
Piotr Kawalec Wykład IX - 3
Technika cyfrowa
Pojęcie automatu skończonego z pamięcią
Def. Automatem skończonym z pamięcią nazywamy
uporzÄ…dkowanÄ… piÄ…tkÄ™
< X, S, Y, ´,  >
gdzie
X - alfabet wejściowy (zbiór stanów wejściowych);
S - alfabet wewnętrzny (zbiór stanów wewnętrznych);
Y - alfabet wyjściowy (zbiór stanów wyjściowych);
´ - funkcja przejść ´ = f(X,S);
 - funkcja wyjść dla automatu Mealy ego  = f(X,S)
dla automatu Moore a  = f(S)
Piotr Kawalec Wykład IX - 4
Technika cyfrowa
Struktury automatów z pamięcią
struktura automatu Mealy ego
X
Y
S
´

Piotr Kawalec Wykład IX - 5
Technika cyfrowa
Struktury automatów z pamięcią
struktura automatu Moore a
X
S Y
´

Piotr Kawalec Wykład IX - 6
Technika cyfrowa
Podział automatów z pamięcią
automaty synchroniczne
automaty w których stan wejść może oddziaływać na
układ pamięciowy w ściśle określonych momentach
wyznaczanych sygnałem na specjalnym wejściu
taktującym (wejściu zegarowym)
automaty asynchroniczne
automaty w których stan wejść wpływa w sposób
ciągły na stan układu pamięciowego
Piotr Kawalec Wykład IX - 7
Technika cyfrowa
Sposoby opisu automatów
opis słowny
wykresy czasowe
tablice przejść i tablice wyjść
grafy stanów układów
Piotr Kawalec Wykład IX - 8
Technika cyfrowa
Tablice przejść automatu
tablice przejść automatów Mealy ego i Moore a
wiersze tablicy odpowiadają stanom wewnętrznym s,
a kolumny literom wejściowym x. Na przecięciu
wiersza odpowiadajÄ…cego stanowi sv i kolumny
odpowiadającej literze wejściowej xw podana jest
wartość funkcji ´ w punkcie < xw , sv > oznaczona
´ (xw , sv ) majÄ…ca sens stanu nastÄ™pnego sv .
x
xw
s
sv
sv
Piotr Kawalec Wykład IX - 9
Technika cyfrowa
Tablice wyjść automatu
tablice wyjść automatu Mealy ego
wiersze tablicy odpowiadają stanom wewnętrznym s,
a kolumny literom wejściowym x. Na przecięciu
wiersza odpowiadajÄ…cego stanowi sv i kolumny
odpowiadającej literze wejściowej xw podana jest
wartość funkcji  w punkcie < xw , sv > oznaczona
(xw , sv ) mająca sens litery wyjściowej yi .
x
xw
s
yi
sv
Piotr Kawalec Wykład IX - 10
Technika cyfrowa
Tablice wyjść automatu
tablice wyjść automatu Moore a
dla automatu Moore a tablica wyjść zamienia się
w kolumnę wyjść
x
y
s
sv yi
´
często tablice te buduje się jako jedną tablicę
przejść-wyjść
Piotr Kawalec Wykład IX - 11
Technika cyfrowa
Graf stanów automatu
jest graficznym odpowiednikiem tablic przejść-wyjść
stany wewnętrzne umieszcza się w wierzchołkach
grafu skierowanego
stany wejść umieszcza się na gałęziach (łukach,
tranzycjach) grafu
umieszczenie stanów wyjść zależy od rodzaju
automatu
dla automatu Mealy ego - na Å‚ukach grafu
dla automatu Moore a - przy wierzchołkach grafu
Piotr Kawalec Wykład IX - 12
Technika cyfrowa
Zasady opisu grafów
graf automatu Mealy ego
x/y
s1 s2
´(x, s1) = s2
(x, s1) = y
graf automatu Moore a
x
s1 s2
´(x, s1) = s2
y1
y0
(s1) = y0
(s2) = y1
Piotr Kawalec Wykład IX - 13
Technika cyfrowa
SYNTEZA UKA
ADÓW SYNCHRONICZNYCH
Zasady tworzenia tablic przejść - wyjść
jeśli znamy liczbę stanów wewnętrznych tablicę
przejść-wyjść możemy utworzyć bezpośrednio
z opisu
w przeciwnym wypadku konieczna jest budowa
grafu stanów automatu
w grafach i tablicach nie wyróżnia się wśród
sygnałów wejściowych stanu zegara, a jedynie
zaznacza się stan wejść automatu w momencie
zmiany stanu sygnału zegarowego
Piotr Kawalec Wykład IX - 14
Technika cyfrowa
Przykłady tworzenia tablic przejść - wyjść
Przykład 1- zbudować tablicę przejść - wyjść licznika
rewersyjnego mod 5 zliczajÄ…cego impulsy zegarowe
Przykład 2 - zbudować tablicę przejść - wyjść układu
wykrywającego w dowolnie długim ciągu binarnym
sekwencje 1100
Przykład 3 - Na wejście układu podawane są kolejno
bit po bicie trzybitowe ciągi o wartościach od 0 do 5.
Na wyjściu ma się pojawić 1 gdy kolejny ciąg zawiera
nieparzystÄ… liczbÄ™ jedynek
Piotr Kawalec Wykład IX - 15