Reti sequenziali: registri, contatori e macchine a stati finiti
Registri e registri a scorrimento, LFSR, contatori sincroni e asincroni, macchine di Moore e di Mealy, progetto completo di un riconoscitore di sequenza, codifiche e reset.
Con i flip-flop si costruiscono le reti sequenziali: circuiti la cui uscita dipende non solo dagli ingressi attuali ma dalla storia passata, riassunta in uno stato. Registri, contatori, controllori di protocolli, l’unità di controllo di un processore sono tutti reti sequenziali sincrone. In questa lezione vediamo registri e contatori e il metodo generale per progettare una macchina a stati finiti, con un esempio completo.
Registri e registri a scorrimento
Un registro di 
bit è fatto di flip-flop D con lo stesso clock: a ogni fronte memorizza una parola. Collegando l’uscita di ogni flip-flop all’ingresso del successivo si ottiene un registro a scorrimento: a ogni fronte i bit avanzano di una posizione. Serve a convertire dati da paralleli a seriali e viceversa (è il cuore di UART, SPI e di tutte le trasmissioni seriali), a ritardare un segnale di un numero preciso di cicli, a generare sequenze pseudo-casuali (con una retroazione tramite porte XOR, il LFSR, usato per i codici del GPS e per il collaudo dei chip).
I contatori
Un contatore binario sincrono a bit è un registro il cui ingresso è il valore attuale più 1: conta da 0 a 
e ricomincia. Il bit meno significativo cambia a ogni fronte, il successivo ogni due, e così via: ogni bit divide la frequenza per due. Un contatore modulo N si azzera quando raggiunge 
: per contare i secondi di un orologio servono 6 bit (
).
I contatori asincroni (a propagazione), in cui ogni flip-flop riceve come clock l’uscita del precedente, usano meno logica ma i bit non cambiano insieme: per un istante il contatore attraversa valori sbagliati. Nei progetti moderni si usano quasi sempre contatori sincroni.
Le macchine a stati finiti
Una macchina a stati finiti (FSM) è descritta da:
- un insieme finito di stati, memorizzati in un registro;
- una funzione di stato futuro, che dallo stato attuale e dagli ingressi calcola lo stato successivo (logica combinatoria);
- una funzione di uscita.
Nella macchina di Moore l’uscita dipende solo dallo stato; in quella di Mealy dipende anche dagli ingressi. Le Moore sono più semplici da verificare e hanno uscite stabili per tutto il ciclo; le Mealy reagiscono un ciclo prima e spesso richiedono meno stati.
Un esempio completo: riconoscere la sequenza 101
Si vuole un circuito con un ingresso seriale 
, un bit per ciclo di clock, e un’uscita 
che vale 1 quando gli ultimi tre bit ricevuti sono 1, 0, 1 (anche sovrapposti: in 10101 la sequenza compare due volte).
1. Il diagramma degli stati. Ogni stato ricorda quanta parte della sequenza è già arrivata:
: niente di utile;
: l’ultimo bit era 1;
: gli ultimi due erano 1, 0;
: gli ultimi tre erano 1, 0, 1, l’uscita vale 1 (macchina di Moore).
Le transizioni si ricavano chiedendosi, per ogni stato e ogni ingresso, qual è il prefisso più lungo della sequenza che coincide con la fine di ciò che è stato ricevuto. Per esempio in (ultimi bit 101) un 0 dà …1010, che termina con 10: si va in , non in .
2. La tabella degli stati.
| Stato |  |  | |
|---|---|---|---|
| | | 0 |
| | | 0 |
| | | 0 |
| | | 1 |
3. La codifica. Quattro stati richiedono 2 flip-flop. Con la codifica binaria 
, 
, 
, 
(bit 
), dalla tabella si ricavano le funzioni dello stato futuro e si semplificano con le mappe di Karnaugh:
![\[ q_0^+ = x,\qquad q_1^+ = \overline{x}\,q_0 + x\,q_1\,\overline{q_0},\qquad z = q_1q_0 \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-b31ff243107da8a6bfed112997bd3a4e_l3.png "Rendered by QuickLaTeX.com")
Si verifica riga per riga: per esempio da (
) con : 
, 
, cioè 
, corretto. (Qui 
ha un significato semplice: 
ricorda l’ultimo bit ricevuto.)
4. Il circuito. Due flip-flop D, le porte che realizzano 
e 
, una porta AND per l’uscita.
Altre codifiche sono possibili: la one-hot usa un flip-flop per stato (4 qui), con logica più semplice e veloce; è la scelta abituale nelle FPGA, dove i flip-flop abbondano. Gli strumenti di sintesi scelgono la codifica da soli, a partire dalla descrizione in un linguaggio di descrizione dell’hardware.
Il reset
Ogni macchina a stati deve partire da uno stato noto: all’accensione il contenuto dei flip-flop è casuale. Un segnale di reset porta il registro di stato nello stato iniziale. Se il reset è asincrono, il suo rilascio va comunque sincronizzato con il clock (con lo stesso sincronizzatore visto per la metastabilità), altrimenti flip-flop diversi potrebbero uscire dal reset in cicli diversi e la macchina partirebbe da uno stato non previsto.
