IT

Macchine a stati (Moore e Mealy)

Dal diagramma degli stati alla tabella e alle equazioni dei flip-flop, con un rilevatore di sequenza

Progettazione di un rilevatore di sequenza

Macchina

Diagramma degli stati

Ogni freccia riporta il valore dell'ingresso x che la provoca; in Mealy, anche l'uscita prodotta («ingresso/uscita»). In Moore l'uscita è dentro lo stato, e gli stati con doppio cerchio sono quelli che danno z = 1.

Tabella degli stati

Equazioni con flip-flop D

Simulazione

Ingresso

Che cos'è una macchina a stati

Una macchina a stati finiti è un circuito sequenziale che in ogni istante si trova in uno di un numero limitato di stati. Lo stato riassume tutto ciò che conta del passato. A ogni fronte di clock passa a un nuovo stato, che dipende dallo stato attuale e dagli ingressi. Si costruisce con un registro di flip-flop, che memorizza lo stato, e due blocchi di logica combinatoria: uno calcola lo stato successivo e l'altro le uscite.

È il modo ordinato di progettare qualsiasi automatismo sequenziale: un semaforo, il comando di una porta automatica, un distributore automatico, il protocollo di una porta seriale o le fasi di un ciclo di lavaggio. In un PLC si programma allo stesso modo con GRAFCET o con passi in ladder, e in un microcontrollore con uno switch su una variabile di stato.

Moore e Mealy

MooreMealy
L'uscita dipendeSolo dallo statoDallo stato e dagli ingressi
Dove si disegna l'uscitaDentro ogni statoSu ogni freccia, «ingresso/uscita»
Numero di statiDi solito ne servono alcuni in piùDi solito ne servono meno
RispostaL'uscita cambia al fronte di clock successivoL'uscita cambia appena cambia l'ingresso
UscitaStabile per tutto il ciclo, senza glitchPuò avere glitch se li ha l'ingresso

Confronta i due tipi nel simulatore con la stessa sequenza: il rilevatore di Mealy dà z = 1 nello stesso ciclo in cui arriva l'ultimo bit, quello di Moore un ciclo dopo, quando è già entrato nello stato finale. Se l'uscita di una macchina di Mealy va a un altro circuito sincrono, quel ritardo compare comunque al momento di memorizzarla.

Fasi del progetto

  1. Diagramma degli stati. Si descrive il comportamento: quali stati esistono, in quale si passa con ogni ingresso e quale uscita si produce. In un rilevatore di sequenza, ogni stato significa «ho ricevuto i primi k bit della sequenza».
  2. Tabella degli stati. Lo stesso del diagramma, in forma di tabella: stato attuale e ingresso a sinistra, stato successivo e uscita a destra.
  3. Codifica. Si assegna un codice binario a ogni stato. Con S stati servono ⌈log₂ S⌉ flip-flop. La codifica binaria usa il minimo di flip-flop; la «one-hot» (un flip-flop per stato) ne usa di più ma semplifica molto le equazioni, ed è comune nelle FPGA.
  4. Equazioni. Con flip-flop D, l'ingresso D di ciascuno è direttamente il bit corrispondente dello stato successivo. I codici non usati sono indifferenti e aiutano a semplificare nella mappa di Karnaugh. Con flip-flop JK si usa la tabella di eccitazione invece di copiare lo stato successivo.
  5. Stati inutilizzati. Bisogna verificare dove va la macchina se parte da un codice non usato, per un disturbo o all'accensione, e prevedere un reset che la riporti allo stato iniziale.

Sovrapposizione

Con sovrapposizione, gli ultimi bit di una sequenza rilevata possono essere l'inizio della successiva: cercando 1011 in 1011011, la si rileva due volte. Senza sovrapposizione, dopo ogni rilevamento la macchina ricomincia e ne trova una sola. Per decidere a quale stato tornare quando arriva un bit che non corrisponde, si cerca la parte più lunga di quanto ricevuto che coincide con l'inizio della sequenza; è la stessa idea dell'algoritmo di ricerca testuale KMP.

Esempio: un semaforo

Un semaforo per auto con pulsante pedonale è una macchina di Moore: le luci dipendono solo dallo stato. Un temporizzatore fornisce il segnale «tempo scaduto» e la pressione del pulsante viene memorizzata finché non è servita.

StatoLuci autoLuci pedoniPassa al successivo quando
S0 VerdeVerdeRossoUn pedone ha premuto ed è trascorso il tempo minimo di verde
S1 GialloGialloRossoTempo di giallo scaduto
S2 RossoRossoVerdeTempo di attraversamento scaduto
S3 SgomberoRossoVerde lampeggianteTempo di sgombero scaduto; torna a S0

Quattro stati si codificano con due flip-flop. Le uscite sono funzioni di Q1 e Q0, per esempio verde auto = Q1'·Q0' e rosso pedoni = Q1'.

Vedi anche: latch e flip-flop, mappa di Karnaugh, simulatore di porte logiche e simulatore ladder.