Analisi delle reti sequenziali - tabella e diagramma degli stati, Mealy e Moore

L'analisi parte da un circuito sequenziale sincrono (flip-flop e porte, Elementi di memoria - latch SR, latch D e flip-flop DUn circuito sequenziale ha uscite che dipendono da ingressi e stato (memoria); è un circuito combinatorio con elementi di memoria in retroazione; stato presente = uscite dei FF, stato futuro = ingressi dei FF. Sincrono (clock) o asincrono. Latch SR (NOR): S=1,R=0 set; S=0,R=1 reset; 00 memoria; 11 proibito. Latch D: C=1 trasparente (Q=D), C=0 memoria, sensibile al livello. Flip-flop D edge-triggered = due latch D in cascata (master-slave) con clock opposti: cambia solo sul fronte attivo e non è trasparente. Si assume D flip-flop positive-edge-triggered.Elementi di memoria - latch SR, latch D e flip-flop D →) e ne ricava il comportamento. È l'operazione inversa della sintesi (Sintesi delle reti sequenziali - riconoscitore di sequenza e codifica degli statiSintesi di una rete sequenziale sincrona: specifiche $\to$ diagramma degli stati $\to$ tabella (riduzione degli stati equivalenti) $\to$ codifica binaria degli stati $\to$ scelta del FF (D PET) $\to$ equazioni di ingresso dei FF e delle uscite $\to$ minimizzazione $\to$ circuito e verifica. Lo stato riassume la parte di storia utile; per i riconoscitori si ha uno stato per ogni prefisso riconosciuto, riusando gli stati (sovrapposizioni). Reset: stato iniziale noto. Codifica Gray (numero minimo di FF) vs 1-hot (un FF per stato, logica più semplice): per il riconoscitore 1101 Gray costa circa la metà.Sintesi delle reti sequenziali - riconoscitore di sequenza e codifica degli stati →). Versione sintetica con Mealy e Moore: Reti sequenziali e automi a stati finitiModello di una rete sequenziale sincrona (stato in flip-flop, logica di stato prossimo e di uscita); automi di Moore e di Mealy; procedimento di sintesi con esempio svolto di un riconoscitore della sequenza 11.Reti sequenziali e automi a stati finiti →.

Strategia di analisi

Si descrive l'evoluzione di stato futuro e uscite in funzione di ingressi e stato presente:

1. equazioni di ingresso dei flip-flop: calcolano lo stato futuro (per un D flip-flop, $A(t+1)=D_A(t)$). Il pedice indica la variabile di stato; le equazioni contengono variabili di stato e ingressi;
2. equazioni dell'uscita;
3. tabella degli stati: per ogni combinazione di stato presente e ingressi dà stato futuro e uscita;
4. diagramma degli stati: gli stessi dati in forma grafica;
5. simulazione (diagramma temporale) per verificare il funzionamento.

Tabella degli stati. Con $m$ flip-flop (variabili di stato) e $n$ ingressi la tabella ha $2^{m+n}$ righe, con $m+n$ colonne per stato presente e ingressi, $m$ per lo stato futuro e le colonne delle uscite. Si costruisce elencando tutte le combinazioni di stato presente e ingressi, calcolando lo stato futuro dalle equazioni di ingresso e l'uscita dall'equazione di uscita. Una forma alternativa, la tabella bidimensionale degli stati, ha una riga per stato e colonne separate per ogni valore dell'ingresso (stato futuro/uscita).

Diagramma degli stati. Gli stati sono cerchi; le transizioni sono frecce da uno stato all'altro, una per ogni combinazione degli ingressi; accanto alla freccia si scrive ingresso/uscita (separati da una barra). Il diagramma dà un'interpretazione più intuitiva, la tabella una più sistematica. Un segnale di reset porta il circuito in uno stato iniziale noto (indicato con una freccia entrante).

Mealy e Moore

• Modello di Mealy: le uscite dipendono dallo stato presente e dagli ingressi. Sul diagramma l'uscita è accanto a ogni freccia (ingresso/uscita).
• Modello di Moore: le uscite dipendono solo dallo stato presente. L'uscita si scrive dentro il cerchio dello stato; sulle frecce c'è solo l'ingresso.

Differenze pratiche:

• Una macchina di Mealy può avere meno stati e meno logica, e reagisce più in fretta a un cambio di ingresso: l'uscita può cambiare anche tra due fronti di clock, non appena cambia l'ingresso (ne dipende combinatoriamente).
• In una macchina di Moore l'uscita dipende dallo stato, memorizzato in flip-flop che cambiano solo sul fronte attivo: l'uscita cambia solo ai fronti di clock ed è più stabile; di norma richiede uno stato in più per ottenere lo stesso riconoscimento.

Esempio di conteggio. Un sistema con un ingresso deve portare l'uscita a 1 quando riconosce la sequenza $01$: servono 2 stati in Mealy e 3 stati in Moore (il terzo è lo stato "ho riconosciuto $01$", che ha l'uscita nel cerchio).

Esempio 1: una rete di Moore

Circuito con due D flip-flop $A,B$, ingresso $X$, uscita $Y$, reset a $AB=00$: $$D_A=X+B,\qquad D_B=X\,\overline A,\qquad Y=\overline A+B .$$

Tabella degli stati (8 righe):

L'uscita $Y$ non dipende da $X$ (compare solo nello stato): è una macchina di Moore. Diagramma degli stati (uscita nel cerchio):

• stato $00/1$: con $X=0$ resta in $00$; con $X=1$ va in $11$;
• stato $11/1$: con $X=0$ e con $X=1$ va in $10$;
• stato $10/0$: con $X=0$ va in $00$; con $X=1$ resta in $10$;
• stato $01/1$: con $X=0$ va in $10$; con $X=1$ va in $11$.

Partendo dal reset $00$ lo stato $01$ non è raggiungibile.

Simulazione con ingresso $X=1,0,0,1,1,0,1,0$ (un valore per ciclo, reset iniziale a $00$):

L'uscita $Y$ del ciclo $t$ è determinata dallo stato presente.

Esempio 2: una rete di Mealy

Due D flip-flop $A,B$, ingresso $X$, uscita $Y$, reset a $00$: $$D_A=B,\qquad D_B=\overline{X\oplus A},\qquad Y=A\oplus B\oplus X .$$

Qui $Y$ dipende anche da $X$ per ogni stato: macchina di Mealy. Diagramma (frecce X/Y): $00\xrightarrow{0/0}01$, $00\xrightarrow{1/1}00$, $01\xrightarrow{0/1}11$, $01\xrightarrow{1/0}10$, $10\xrightarrow{0/1}00$, $10\xrightarrow{1/0}01$, $11\xrightarrow{0/0}10$, $11\xrightarrow{1/1}11$.

Con ingresso $X=1,1,0,1,0,0,1$ dal reset: stati $00,00,00,01,10,00,01$ e uscite $Y=1,1,0,0,1,0,0$.

Si può usare lo stesso diagramma per dare un nome simbolico agli stati: $S_0=00$, $S_1=01$, $S_2=10$, $S_3=11$; la sua descrizione VHDL è nell'esempio di VHDL - macchine a stati finiti e testbench sequenzialeUna macchina a stati finiti (FSM) si descrive in VHDL, in stile behavioral, con un tipo enumerato per gli stati e tre process: (1) registro di stato con reset (asincrono) e aggiornamento state<=next_state sul fronte; (2) stato futuro come funzione combinatoria di stato e ingresso (case state, default next_state<=state); (3) uscita come funzione combinatoria di stato (Moore) o di stato e ingresso (Mealy). Il testbench ha il process del clock e il process degli ingressi (reset iniziale, sequenza di test che percorre tutti gli stati).VHDL - macchine a stati finiti e testbench sequenziale →.

Stati equivalenti

Due stati sono equivalenti se, per ogni valore dell'ingresso, producono la stessa uscita e portano a stati futuri uguali o equivalenti. Stati equivalenti si possono fondere, ottenendo un circuito più semplice con meno stati e meno flip-flop. La riduzione non porta sempre a un costo minore: il costo dipende anche dalla rete combinatoria, non solo dai flip-flop.

Esempio (Mealy, ingresso $x$, uscita 1 quando $x$ passa da 1 a 0):

$S_1$ e $S_2$ hanno le stesse uscite ($1$ per $x=0$, $0$ per $x=1$) e stesse destinazioni ($S_0$ per $x=0$; $S_2$ per $x=1$, che a sua volta si fonde con $S_1$): sono equivalenti. Fondendoli in un unico stato $S_{12}$ si ha una macchina a 2 stati ($S_0$: ultimo ingresso 0; $S_{12}$: ultimo ingresso 1), cioè 1 flip-flop invece di 2. Il metodo sistematico è il raffinamento di partizioni: si parte raggruppando gli stati con la stessa riga di uscite e si separano quelli che con lo stesso ingresso vanno in gruppi diversi, finché la partizione non cambia più.

Errori comuni

• Dire che una macchina è di Mealy solo perché "ha un ingresso": conta se l'uscita dipende dall'ingresso.
• Scrivere l'uscita di una macchina di Moore sulle frecce (va nel cerchio).
• Dimenticare che una macchina di Mealy può cambiare uscita anche tra due fronti di clock.
• Leggere lo stato futuro come stato presente nella simulazione (si aggiorna al fronte successivo).
• Non verificare con il reset gli stati raggiungibili e non raggiungibili.