Macchine a stati finiti

Architetture degli Elaboratori I, Laboratorio - Corso di Laurea in Informatica, A.A. 2015-2016

Turno A (Cognomi A-F, N. Basilico)

Turno B (Cognomi G-Z, M. Re)

 Esercizio 1
• Si realizzi una macchina di Moore in grado di riconoscere le stringhe 010 e 101
– La macchina riceve in input un bit per volta
– Quando la macchina riconosce una delle due stringhe dà output 1 altrimenti 0

• Suggerimento: si codifichi l’insieme degli stati come

rendendo quindi la macchina in grado di riconoscere una qualsiasi sequenza di

3 bit. Si associ poi un’uscita pari a 1 solo agli stati corrispondenti alle stringhe
010 e 101
 Esercizio 1
• Costruiamo il grafo delle transizioni:
0

1 1
0

1
0 0
1

0 1
0 0 1 0

1 Interpretazione: stato
come registro a
scorrimento verso destra
 Esercizio 1
• Tabella delle transizioni:
 Esercizio 1
• Codifica degli stati:

Stato corrente
Stato prossimo
 Esercizio 1
• Codifica degli stati:

Stato corrente
Stato prossimo
 Esercizio
Funzione di uscita
 Esercizio 1
Funzione di stato prossimo

NOTA: nella rappresentazione

esterna del circuito le posizioni di
C’è qualche somiglianza con il registro a scorrimento che
ingress (stato corrente) e uscite
abbiamo già visto? Ragioniamo sul fatto che il procedimento
(stato prossimo) sono scambiate
meccanico non è l’unico modo per progettare un circuito che
lavora come una macchina a stati finiti.
Esercizio 1

Stato corrente su 3 bit

 Esercizio 2
• Costruire un circuito che simuli lo stato di acceso/spento di un dispositivo. Il
circuito dovrà presentare un singolo bottone on/off col quale passare dallo
stato acceso a lo stato spento e vice versa.
 Esercizio 2
• Costruire un circuito che simuli lo stato di acceso/spento di un dispositivo. Il
circuito dovrà presentare un singolo bottone on/off col quale passare dallo
stato acceso a lo stato spento e vice versa.
bottone premuto
bottone non premuto bottone non premuto
on off

bottone premuto

• Stato di 1 bit: S=1 on, S=0 off

• Input: bottone premuto = 1, bottone non premuto = 0

Lo stato prossimo è lo
XOR tra stato
corrente e input
Esercizio 2

L’uscita coincide con lo stato

Funzione di stato prossimo

Esercizio 2
 Esercizio 2
• Si usi il circuito on/off all’interno di un altro circuito che realizzi un indicatore di
livello (si veda schema con esempio di funzionamento)
 Esercizio 2
• Si usi il circuito on/off all’interno di un altro circuito che realizzi un indicatore di
livello (si veda schema con esempio di funzionamento)

Circuito on/off (con tunnel)

 Esercizio 2
• Si usi il circuito on/off all’interno di un altro circuito che realizzi un indicatore di
livello (si veda schema e esempio di funzionamento)

Singolo led

Input:
[on] accendo/spengo il circuito
[+] aumento il livello
[-] diminuisco il livello
 Esercizio 2
• Si usi il circuito on/off all’interno di un altro circuito che realizzi un indicatore di
livello (si veda schema e esempio di funzionamento)

Indicatore grafico di livello

(matrice led)
 Esercizio 2
• Si usi il circuito on/off all’interno di un altro circuito che realizzi un indicatore di
livello (si veda schema e esempio di funzionamento)

Macchina a stati finiti (?)

 Esercizio 2
• Attenzione! In questo caso il procedimento “meccanico” di progettazione di una MSF
non è la via più facilmente implementabile (anche se comunque percorribile)

• Anziché seguire meccanicamente il procedimento cerchiamo di ragionare con questi

componenti logisim che, essendo già disponibili, possono facilitarci il compito:

shifter
counter
 Esercizio 2
• Counter

decrement
valore di inizializzazione valore corrente (stato)
count

clock Asynchronous clear

Ad ogni rising edge (o falling edge se specificato negli attributi) cambia il suo stato in questo modo:
• se count = 1 e decrement = 0, incrementa il valore corrente di 1
• se count = 1 e decrement = 1, decrementa il valore corrente di 1
• negli attributi ha un valore massimo settabile (Maximum Value)
• negli attributi può indicare cosa fare una volta oltrepassato il valore massimo: stay at value, wrap
around (ciclico)
 Esercizio 2
• Shifter

valore da shiftare
valore shiftato
Distanza
(di quante posizioni shiftare)
Direzione dello shift (sinistra o
destra, settabile negli attributi)

Counter e shifter possono essere utili all’implementazione dell’indicatore di livello

(si veda demo …)
 Esercizio 2
• Soluzione
 Esercizio 2
• Soluzione

Input del circuito: +, - e on riceveranno i segnali dai corrispettivi pulsanti, mentre

ck lo riceverà dalla sorrgente di clock
 Esercizio 2
• Soluzione

Se (+ OR –) è a 1 allora dovrò incrementare il contatore se – è a 0 oppure decrementare il

contatore se – è a 1; se on è 0 (stato di spento) resetto in modo asincrono il contatore
settando a 1 (on negato) il bit di asynchronous clear
 Esercizio 2
• Soluzione

Il contatore tiene traccia del livello corrente (ad esempio, se il suo valore è 5 allora accenderò i primi 5
led nella matrice dal basso verso l’alto). Voglio 16 livelli più il livello 0: [0 16]. Il counter avrà quindi 5
bit e un max value impostato a 16 con “action on overflow” settata a “stay at value” (se il livello è
massimo e premo + non resetto ma tengo livello massimo)
 Esercizio 2
• Soluzione

Se il livello è k, allora devo produrre una stringa di 16 bit in cui i k LSD sono 1 e i (16-k)
MSD sono a 0. Shifto di k posti una stringa di 17 bit tutti settati a 1 e la complemento. (Ne
servono 17 perché una stringa di n bit può essere shiftata al più di (n-1) posti.)
 Esercizio 2
• Soluzione

Prendo solo i 16 bit che mi servono e li mando in uscita

 Esercizio 2
• Soluzione

Il counter è, di fatto, una macchina a stati

finiti (già pronta in logisim) il cui stato e
uscita sono il valore corrente (che in questo Quello che abbiamo fatto è stato modificare la funzione
esercizio abbiamo chiamato “livello”) e le cui d’uscita di questa macchina a stati finiti in modo da
transizioni incrementano/decrementano il trasformare il valore del counter in una corrispondente
livello a seconda degli input che diamo. stringa di bit da visualizzare su matrice led.
 Esercizio 3
• Costruire una macchina a stati finiti (di Moore) con due ingressi, e , che
fornisca 1 quando negli ultimi 3 istanti di tempo si è verificata la seguente
condizione: