Impara › Argomento 11
Macchine a stati di Moore e di Mealy: progetto completo
7 min di lettura · Team bitGateLab
Una macchina a stati finiti (FSM) è un circuito sequenziale che "ricorda" a che punto di un processo si trova. Semafori, serrature a combinazione, controllori di ascensori e ricevitori di comunicazione seriale sono macchine a stati. Qui vedrai i due modelli classici, Moore e Mealy, e seguirai un progetto completo dalla descrizione a parole fino alle equazioni dei flip-flop, con un riconoscitore della sequenza 101.
Parti di una macchina a stati
Ogni FSM sincrona ha tre blocchi:
- Registro di stato: n flip-flop (quasi sempre di tipo D) che memorizzano lo stato attuale; bastano per un massimo di 2n stati.
- Logica dello stato successivo: combinatoria; calcola il prossimo stato a partire dallo stato attuale e dagli ingressi.
- Logica di uscita: combinatoria; calcola le uscite.
La differenza tra i due modelli sta nell'ultimo blocco:
- Moore: le uscite dipendono soltanto dallo stato attuale. Si scrivono dentro il cerchio di ogni stato (per esempio S3/1).
- Mealy: le uscite dipendono dallo stato e dagli ingressi. Si scrivono sulle frecce (ingresso/uscita, per esempio 1/1).
Il problema: riconoscitore della sequenza 101
Un ingresso seriale X arriva sincronizzato con il clock, un bit per ciclo. L'uscita Z deve valere 1 ogni volta che gli ultimi tre bit ricevuti sono 1, 0, 1. È ammessa la sovrapposizione: nella stringa 10101 ci sono due riconoscimenti, perché l'ultimo 1 della prima sequenza è il primo della successiva.
Il primo passo è decidere che cosa deve ricordare la macchina. Ogni stato rappresenta "quanta parte della sequenza ho già visto":
- S0: non ho ancora nulla di utile.
- S1: l'ultimo bit è stato 1.
- S2: gli ultimi bit sono stati 1, 0.
- S3: ho appena ricevuto 1, 0, 1 (Z = 1).
Diagramma e tabella degli stati (Moore)
Per ogni stato e per ogni valore di X chiediti: con questo nuovo bit, qual è il suffisso più lungo che coincide con l'inizio di 101? Quel suffisso definisce lo stato successivo.
| Stato attuale | X = 0 | X = 1 | Z |
|---|---|---|---|
| S0 | S0 | S1 | 0 |
| S1 | S2 | S1 | 0 |
| S2 | S0 | S3 | 0 |
| S3 | S2 | S1 | 1 |
Fai attenzione a due transizioni che si sbagliano spesso. In S1 arriva un altro 1: la stringa termina con 11, e l'ultimo 1 vale ancora come inizio, quindi la macchina resta in S1. In S3 arriva uno 0: la stringa termina con 1010, il cui suffisso 10 coincide con l'inizio di 101, quindi va in S2 e non in S0. È questo a rendere possibile la sovrapposizione.
Assegnazione degli stati ed equazioni
Con 4 stati bastano 2 flip-flop D (Q1 Q0). L'assegnazione più diretta è quella binaria: S0 = 00, S1 = 01, S2 = 10, S3 = 11. Con i flip-flop D la tabella di eccitazione è banale, perché D = Q+.
| Q1 | Q0 | X | Q1+ = D1 | Q0+ = D0 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
Semplificazione:
- D0 vale 1 esattamente nelle righe con X = 1, quindi D0 = X. Ha senso: in questa assegnazione Q0 = 1 significa "l'ultimo bit è stato 1".
- D1 = Σm(2, 5, 6) con le variabili nell'ordine Q1 Q0 X. I mintermini 2 (010) e 6 (110) sono adiacenti e formano Q0·X. Il 5 (101) non ha vicini a 1 e resta da solo: Q1·Q0·X. D1 = Q0·X + Q1·Q0·X.
- L'uscita di Moore dipende soltanto dallo stato: Z = Q1·Q0.
Il circuito risulta composto da 2 flip-flop D, una AND a 2 ingressi per Z e, per D1, una AND a 2, una AND a 3 e una OR a 2 (più gli invertitori di Q0 e X).
Verifica con una sequenza di prova
Ingresso X = 1 0 1 0 1 1 0 1, partendo da S0. Stato dopo ogni fronte:
| Fronte | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| X | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| Stato | S1 | S2 | S3 | S2 | S3 | S1 | S2 | S3 |
| Z | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
Ci sono tre riconoscimenti: nei bit da 1 a 3, da 3 a 5 (sovrapposizione) e da 6 a 8. Verifica il fronte 4 con le equazioni: stato S3 = 11 e X = 0, D1 = 1·1 + 1·0·0 = 1 e D0 = 0, stato successivo 10 = S2. Coincide.
La versione di Mealy
In Mealy l'uscita è associata alla transizione, quindi lo stato S3 è superfluo: il riconoscimento avviene "all'arrivo dell'1 mentre ci si trova in S2". Con tre stati A (nulla), B (ultimo bit 1) e C (ultimi bit 1, 0):
| Stato | X = 0 | X = 1 |
|---|---|---|
| A | A / 0 | B / 0 |
| B | C / 0 | B / 0 |
| C | A / 0 | B / 1 |
Servono comunque 2 flip-flop, ma l'uscita Z = 1 compare nello stesso ciclo in cui arriva l'ultimo 1, un ciclo prima rispetto alla versione di Moore.
Errori comuni
- Mandare in S0 tutte le transizioni che "falliscono", senza controllare quale parte della sequenza è ancora utile; così si perdono i riconoscimenti con sovrapposizione.
- Scrivere le uscite sulle frecce in una macchina di Moore o dentro gli stati in una di Mealy.
- Dimenticare le combinazioni di flip-flop non usate (per esempio, il codice 11 nella versione di Mealy): bisogna decidere dove vanno oppure segnarle come X e verificare che la macchina rientri nella sequenza.
- Leggere l'uscita di una macchina di Mealy in un momento qualsiasi: va campionata subito prima del fronte, quando l'ingresso è ormai stabile.
- Cambiare l'ingresso X proprio sul fronte del clock mentre si prova la macchina.
Provalo nel simulatore
Una volta ottenute le equazioni, costruire il riconoscitore richiede pochi minuti e il cronogramma ti permette di verificare ogni transizione.
- Inserisci due flip-flop D con lo stesso clock; chiama le loro uscite Q1 e Q0.
- Collega l'ingresso X direttamente a D0.
- Costruisci D1 = Q0·X + Q1·Q0·X con due invertitori, due AND e una OR, e collegalo a D1.
- Collega una AND di Q1 e Q0 a un indicatore per Z.
- Cambia X prima di ogni fronte seguendo la sequenza 1 0 1 0 1 1 0 1 e osserva nel cronogramma che Z si accende dopo i fronti 3, 5 e 8.
Esercizi
- Con sovrapposizione, quante volte la macchina riconosce 101 nella stringa 1010101?
Risposta
Tre volte: nei bit da 1 a 3, da 3 a 5 e da 5 a 7.
- Rifai la tabella di Moore del riconoscitore di 101 senza sovrapposizione (dopo un riconoscimento si ricomincia da zero).
Risposta
Cambia solo la riga S3: con X = 0 va in S0 e con X = 1 va in S1. Le altre righe restano uguali.
- Con l'assegnazione della versione di Mealy A = 00, B = 01, C = 10, ricava Z.
Risposta
Z = 1 solo nello stato C con X = 1: Z = Q1·Q0·X. Se il codice 11 non compare mai lo si può segnare come X e resta Z = Q1·X.
- Quanti flip-flop servono come minimo a una macchina con 9 stati?
Risposta
4, perché 23 = 8 non basta e 24 = 16 sì.
Per ripassare i flip-flop che formano il registro di stato consulta latch e flip-flop.