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