Piotr Kawalec

Wykład VIII - 1

Wykład VIII

Synteza układów

sekwencyjnych

Technika cyfrowa

Piotr Kawalec

Wykład VIII - 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 VIII - 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 VIII - 4

Technika cyfrowa

Struktury automatów z pamięcią



struktura automatu Mealy’ego

X

S

Y





Piotr Kawalec

Wykład VIII - 5

Technika cyfrowa

Struktury automatów z pamięcią



struktura automatu Moore’a

X

S

Y





Piotr Kawalec

Wykład VIII - 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 VIII - 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 VIII - 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

s

v

i kolumny

odpowiadającej literze wejściowej

x

w

podana

jest
wartość funkcji



w punkcie <

x

w

,

s

v

>

oznaczona



(

x

w

,

s

v

) mająca sens stanu następnego

s

v

’

.

x

s

x

w

s

v

s

v

’

Piotr Kawalec

Wykład VIII - 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

s

v

i kolumny

odpowiadającej literze wejściowej

x

w

podana

jest
wartość funkcji



w punkcie <

x

w

,

s

v

>

oznaczona



(

x

w

,

s

v

) mająca sens litery wyjściowej

y

i

.

x

s

x

w

s

v

y

i

Piotr Kawalec

Wykład VIII -
10

Technika cyfrowa

Tablice wyjść automatu



tablice wyjść automatu Moore’a

dla automatu Moore’a tablica wyjść zamienia

się
w kolumnę wyjść

s

v

x

s

y

i

y





często tablice te buduje się jako jedną tablicę

przejść-wyjść

Piotr Kawalec

Wykład VIII -
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 VIII -
12

Technika cyfrowa

Zasady opisu grafów



graf automatu Mealy’ego



graf automatu Moore’a

s

1

s

2

x/

y

(x, s

1

) =

s

2

(x, s

1

) =

y

s

1

s

2

(x, s

1

) =

s

2

(s

1

) = y

0

(s

2

) = y

1

x

y

0

y

1

Piotr Kawalec

Wykład VIII -
13

Technika cyfrowa

SYNTEZA UKŁ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 VIII -
14

Technika cyfrowa

Przykłady tworzenia tablic przejść -
wyjść



Przykład 1-

zbudować tablicę przejść - wyjść

licznika
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