Macchine sequenziali

Dal circuito combinatorio al sequenziale

(addizionatore)

Adder

M

ai

bi

si

ci+1ci

Stato = carryInizialmente, c0=0

memorizza carry

Dal circuito combinatorio al sequenziale

(comparatore)

Comp.

M

ai

bi

za,i

memorizza stato

zb,iza,i-1

zb,i-1

Circuito sequenziale(schema di principio)

Comp.

M

x1

xj Yi-1,1

Yi-1,k

memorizza stato

zh

z1

Yi,1

Yi,k

Definizione

• Una Macchina Sequenziale è una quintupla MS=(I,S,O, )– I Alfabeto di Ingresso

• I={i1,..,im}

– S Insieme degli Stati• S={s1,..,sn}

– O Alfabeto d'Uscita• O={o1,..,oq}

Funzione dello stato successivo : S x I S

– Funzione di uscita : S x I O (Mealy) : S O (Moore)

Rappresentazioni

• Per rappresentare le funzioni ed si possono usare – Diagramma degli stati– Tabella degli stati/uscite ( di transizione)– Algorithm State Machine (ASM)– Matrice di connessione*

* Non la usiamo

Diagramma degli Stati

• Il Diagramma degli stati è un grafo orientato etichettato G(V,A,L)– Vertici V = Insieme dei nodi

• Ogni nodo rappresenta uno stato

– Archi A - Insieme degli archi• Ogni arco rappresenta le transizioni di stato

– L = Insieme delle etichette

Esempio diagramma stati

s1 s2

i/o

s1/o1 s2/o2

i

Mealy

Moore

Tabelle degli stati/uscite

• MACCHINA DI MEALYMatrice |S| righe per |I| colonne. L’elemento in posizione h,k contiene il prossimo stato e l’uscita nel caso in cui lo stato corrente sia h e l’ingresso sia il k-esimo

• MACCHINA DI MOOREMatrice |S| x |I|+1. L’elemento in posizione h,k contiene il prossimo stato nel caso in cui lo stato corrente sia h e l’ingresso sia il k-esimo L’elemento h,|I|+1 contiene l’uscita nel caso in cui lo stato sia h

  i1 i2 ------- ik ------ im

s1

s2

::sh

:::sn

    ---

    ---

    ------

::::ik,sh)/(ik,sh)

    

Macchina di Mealy

Macchina di Moore

  i1 i2 ------ ik ------ im

s1

  sh

  sn

   ---

   --- 

   ---------

:::(ik, sh)

    :::sh)

   

Algorithm State Machine 

Trasformazione del grafo in ASM: caso Mealy

x/TT

s

d

s

d

s

d1d2

i1..il/T1 il+1...im/T2

s

T1 T2

d1 d2

test

s

d1dm

i1/T1 im/Tm

s

T1 Tm

d1 dm

d1

casei1 im

Algorithm State Machine 

Trasformazione del grafo in ASM: caso Moore

x

s

d/T

s

d/T

s

d1/T1d2/T2

i1..il il+1...im

s

d1/T1 d2/T2

test

s

dm/Tm

i1im

s

d1/T1 dm/Tm

d1/T1

casei1

im

Flip/Flop S-R(rappresentazione diagramma degli stati)

• Ingresso: Set – Reset (S-R) – solo uno dei due ingressi può essere pari ad uno.

• Stati: 0, 1

0 1

10

01

00,10

00,01

Flip/Flop S-R(rappresentazione tabella di transizione)

Ingressi

S-R

Stato attuale

Stato succ.

Uscita

0 0 0 0 0

0 0 1 1 1

0 1 0 0 0

0 1 1 0 1

1 0 0 1 0

1 0 1 1 1

Flip/Flop S-R(rappresentazione ASM)

Riconoscitore di sequenza

• Macchina che riconosca la sequenza di lettere ciao

• I={a,b,..,z}– Per comodità indichiamo con il simbolo di negazione

su una lettera tutte le lettere di I tranne la lettera stessa; se più simboli attivano la stessa transizione allora si userà un solo arco con l’elenco di tali simboli

• O={si,no}

Diagramma degli stati (Moore)

1/no 2/no 3/no 4/no 5/sic i a o

cc

c,i

1: aspetto c2: aspetto i3: aspetto a , 4: aspetto o; 5: parola completa

c c,a

c

c,o

c

c

Diagramma degli stati (Mealy)

1: attesa c2: attesa i3: attesa a4: attesa o

1 2 3

4

c/no i/no

a/noo/si

c

no c/no

c,i/no c/noc,a/no

c/no

Contatore UP-DOWN modulo 4

0 1

23

U

U

U

U D

D

D

D

Classificazione macchine sequenziali

Dipendendo dalla struttura della macchina stessa e dalle caratteristiche delle sequenze di ingresso, le macchine sequenziali si possono distinguere in:

•  SINCRONE•  ASINCRONE•  SINCRONE IMPULSIVE•  ASINCRONE IMPULSIVE

Considerazioni sulle macchine sequenziali

• Le macchine sincrone non si possono realizzare.

• Ci focalizzeremo solo sulle impulsive.

• I flip/flop, che utilizzeremo nel seguito, vengono ricavati dalle macchine asincrone, per mancanza di tempo non li potremmo progettare.