Sintesi delle reti sequenziali - riconoscitore di sequenza e codifica degli stati

La sintesi è il progetto di una rete sequenziale sincrona a partire da una descrizione a parole. È l'inverso dell'analisi (Analisi delle reti sequenziali - tabella e diagramma degli stati, Mealy e MooreAnalizzare una rete sequenziale sincrona significa ricavare, dal circuito, le equazioni di ingresso dei flip-flop (stato futuro) e dell'uscita, la tabella degli stati ($2^{m+n}$ righe per $m$ FF e $n$ ingressi), il diagramma degli stati (cerchi = stati, frecce = transizioni con ingresso/uscita) e la simulazione temporale. Mealy: uscita funzione di stato e ingresso (scritta sulle frecce, può cambiare tra due fronti di clock); Moore: uscita funzione del solo stato (scritta nel cerchio, cambia solo al fronte). Due stati sono equivalenti se danno le stesse uscite e portano a stati equivalenti: si fondono per ridurre i FF.Analisi delle reti sequenziali - tabella e diagramma degli stati, Mealy e Moore →) e il passo più difficile è il primo: tradurre le specifiche in un diagramma degli stati.

Procedura

1. Ottenere le specifiche (ingressi, uscite, comportamento, stato iniziale).
2. Disegnare il diagramma degli stati.
3. Costruire la tabella degli stati e delle uscite, riducendo gli stati equivalenti.
4. Assegnare una codifica binaria a ogni stato.
5. Scegliere il tipo di flip-flop (qui D positive-edge-triggered).
6. Ricavare le equazioni di ingresso dei flip-flop dagli stati futuri della tabella.
7. Ricavare le equazioni delle uscite.
8. Minimizzare le equazioni (mappe di Karnaugh, Mappe di Karnaugh - implicanti e copertura minimaLa mappa di Karnaugh è la tabella di verità disposta in una griglia con righe e colonne in codice Gray, così che celle adiacenti (anche tra bordi opposti) differiscano in una sola variabile. Si raggruppano gli 1 in rettangoli di $2^k$ celle: ogni gruppo elimina $k$ variabili e dà un prodotto. Implicante primo = gruppo massimo; essenziale = unico a coprire un mintermine; la copertura minima contiene tutti gli essenziali più il minimo di altri primi (può non essere unica). Efficace fino a 4 variabili.Mappe di Karnaugh - implicanti e copertura minima →).
9. Disegnare il circuito e verificarlo con diagramma temporale e transizioni.

Una volta fissata la codifica, il progetto si riduce a due reti combinatorie: una per lo stato futuro, una per l'uscita. Per un D flip-flop lo stato futuro è direttamente l'ingresso $D$.

Il diagramma degli stati

Non esiste un algoritmo: servono pratica e attenzione. Lo stato è la sintesi della storia pregressa che serve a decidere il comportamento futuro: dipende dalla sequenza degli ingressi ricevuti. Conviene descrivere ogni stato a parole, in modo preciso.

Esempi di descrizioni di stato.

• "Il sistema è in $S_1$ se ha ricevuto $X=1$ per gli ultimi tre fronti di clock consecutivi": vi si trova dopo $00111$ o $10101111$, non dopo $00011$ o $011100$.
• "Il sistema è in $S_2$ se ha ricevuto agli ingressi $X_1X_2$, nell'ordine, le combinazioni $00,01,11,10$ (ciascuna ripetuta quante volte si vuole) con $10$ come ultima".

Quanti stati. Ogni transizione potrebbe creare uno stato nuovo; conviene riusare gli stati esistenti quando la loro descrizione vale ancora. Se $S_1$ significa "gli ultimi tre ingressi sono stati $1$" e si riceve ancora $1$ (sequenza $001111$) si può restare in $S_1$, perché non ci sono vincoli sul numero massimo di 1. Si cerca il numero minimo di stati: una buona definizione degli stati lo rende evidente.

Reset. Un sistema sequenziale all'accensione si trova in uno stato indefinito. Prima di operare serve uno stato iniziale noto, imposto da un segnale di reset. Il reset sincrono richiede un fronte di clock per avere effetto: si realizza con una AND in ingresso a ogni D (il reset porta a 0 tutti i flip-flop). Il reset asincrono agisce subito sul flip-flop (VHDL - latch, flip-flop e reset sincrono e asincronoIn VHDL un elemento di memoria si descrive con un process il cui ramo non assegna sempre il segnale: latch D = process(D,C) con if C='1' then Q<=D; flip-flop positive-edge-triggered = process(CLK) con if CLK'event and CLK='1'. Reset asincrono: RST nella sensitivity list e testato per primo (if RST='1' ... elsif fronte); reset sincrono: solo CLK in lista e RST testato dentro al ramo del fronte (serve un fronte per averne effetto). Il testbench di un circuito sincrono ha un process che genera il clock e uno che applica gli ingressi lontano dal fronte attivo.VHDL - latch, flip-flop e reset sincrono e asincrono →). Il reset può anche servire come uscita da uno stato di errore (watchdog).

Riconoscitore di sequenza

Un riconoscitore di sequenza rivela che una certa sequenza è comparsa in ingresso, indipendentemente da ciò che è successo prima. Esempio: ingresso $X$, uscita $Z$; riconoscere $1101$ (le sequenze possono sovrapporsi); $Z=1$ quando si è presentata la sequenza $110$ e $X=1$; $Z=0$ altrimenti.

Passo 1: Mealy o Moore? L'uscita dipende dallo stato (aver visto $110$) e dall'ingresso ($X=1$): con Mealy si segnala il riconoscimento nell'istante dell'ultimo bit, senza aspettare un ciclo. È più conveniente (Moore è possibile, con uno stato in più).

Passo 2: stati. Si parte dallo stato iniziale $S_1$ ("nessun simbolo riconosciuto") e si aggiungono stati lungo la sequenza giusta:

• $S_2$: riconosciuto il primo bit ($1$);
• $S_3$: riconosciuti i primi due ($11$);
• $S_4$: riconosciuti i primi tre ($110$);
• da $S_4$ con $X=1$: sequenza completa, $Z=1$.

Poi si completano tutte le altre transizioni, chiedendosi dove porta ogni ingresso sbagliato, riusando la più lunga parte finale della sequenza già riconosciuta (la regola della sovrapposizione):

• $S_1$, $X=0$: resta in $S_1$;
• $S_2$ ($1$), $X=0$: ricevuto $10$, nessun prefisso utile $\Rightarrow$ $S_1$;
• $S_3$ ($11$), $X=1$: ricevuto $111$, restano gli ultimi $11$ $\Rightarrow$ $S_3$;
• $S_4$ ($110$), $X=0$: ricevuto $1100$, nessun prefisso $\Rightarrow$ $S_1$;
• $S_4$, $X=1$ (sequenza riconosciuta, $Z=1$): l'ultimo $1$ può essere l'inizio di una nuova sequenza $\Rightarrow$ $S_2$.

Tabella degli stati e delle uscite (stato futuro / uscita $Z$):

(8 combinazioni stato-ingresso. Il reset porta in $S_1$.)

Codifica degli stati

Per rappresentare $m$ stati servono $n=\lceil\log_2m\rceil$ bit ($2^n\ge m$). Le scelte possibili sono molte; meno bit (meno flip-flop) non vuol dire sempre costo minore: conta anche la rete combinatoria. L'ottimizzazione della codifica è un problema complesso, risolto con metodi euristici. Si confrontano due codifiche.

• Codice Gray: numero minimo di bit; facilita il riempimento delle mappe di Karnaugh. $S_1=00,\ S_2=01,\ S_3=11,\ S_4=10$.
• Codifica 1-hot: un flip-flop per stato, un solo 1 nella codifica; più FF ma di solito logica più semplice, perché la logica per entrare in ogni stato è indipendente dalle altre: $S_1=1000,\ S_2=0100,\ S_3=0010,\ S_4=0001$.

Gray (2 flip-flop $A,B$)

Dalla tabella con le codifiche, per ogni bit di stato futuro si riempie una mappa nelle variabili $(A,B,X)$.

• $D_A=1$ per $(A,B,X)=011,110,111$: $D_A=BX+AB$;
• $D_B=1$ per $001,011,101,111$, cioè esattamente per $X=1$: $D_B=X$;
• $Z=1$ solo per $101$: $Z=A\overline B\,X$.

Costo (numero di ingressi delle porte, senza contare gli inverter sugli ingressi): $D_A$: 2 AND a 2 ingressi più OR a 2 $=6$; $D_B$: nessuna porta; $Z$: AND a 3 ingressi $=3$. Rete combinatoria $=9$; due flip-flop (un D flip-flop PET costa $\approx14$ ingressi) $=28$; totale $37$.

1-hot (4 flip-flop $Q_1\dots Q_4$)

Si legge direttamente la tabella: $S_1$ si raggiunge da $S_1,S_2,S_4$ con $X=0$; $S_2$ da $S_1,S_4$ con $X=1$; $S_3$ da $S_2,S_3$ con $X=1$; $S_4$ da $S_3$ con $X=0$. $$D_1=\overline X\,(Q_1+Q_2+Q_4),\ D_2=X(Q_1+Q_4),\ D_3=X(Q_2+Q_3),\ D_4=\overline X\,Q_3,\ Z=XQ_4 .$$ Costo della rete combinatoria $5+4+4+2+2=17$ (senza l'inverter di $X$); quattro flip-flop $=56$; totale $\approx73$. (Il valore esatto dipende dalla convenzione di conteggio degli inverter, ma la conclusione non cambia.) Il reset deve poi mettere a 1 il solo $Q_1$, più complesso che azzerare tutti i bit.

Conclusione: con la codifica Gray si spende circa la metà; la 1-hot può però dare un progetto più facile da scrivere, più affidabile e a volte più veloce.

Entrambe le realizzazioni riproducono la tabella per tutte le $8$ combinazioni stato-ingresso (controllo fatto una per una).

Verifica

Si applicano ingressi diversi e si controlla che a ogni fronte il circuito faccia le transizioni previste, partendo da un reset. Per circuiti piccoli si percorrono tutte le combinazioni stato-ingresso (qui 8), il che richiede più transizioni, perché bisogna ripassare più volte sugli stessi stati. Una sequenza di ingresso che le copre tutte, dopo il reset in $S_1$: $$X=0,1,1,1,0,1,0,1,1,0,0$$ produce gli stati $S_1,S_1,S_2,S_3,S_3,S_4,S_2,S_1,S_2,S_3,S_4,S_1$ e l'uscita $Z=1$ solo all'ingresso di posizione 6 (l'ultimo bit di $1101$ nella sottosequenza $...0\,1\,1\,1\,0\,1$). Con ingresso $0,1,1,0,1,1,0,1,0,1,1,0,1$ l'uscita vale $1$ in tre punti (posizioni 5, 8, 13), anche quando le sequenze si sovrappongono. Per circuiti più grandi non si possono provare tutte le sequenze: si scelgono vettori di test significativi (la verifica è un'attività molto complessa che qui non si affronta).

Versione di Moore

Con Moore l'uscita sta nello stato, quindi serve uno stato in più che significhi "riconosciuto": $R_0$ (nessun prefisso), $R_1$ ($1$), $R_2$ ($11$), $R_3$ ($110$), $R_4$ ($1101$, uscita 1). Transizioni (ingresso $0$ / ingresso $1$):

Da $R_4$ con $X=1$ si va in $R_2$: l'ultima parte della sequenza ricevuta ($\dots1101\,1$) termina con $11$, che è il prefisso riconosciuto da $R_2$. L'uscita compare un ciclo dopo l'ultimo bit (appena lo stato diventa $R_4$), mentre nella macchina di Mealy compare nell'istante dell'ultimo bit.

Errori comuni

• Dimenticare di completare tutte le transizioni (per ogni stato, ogni valore dell'ingresso).
• Tornare sempre allo stato iniziale dopo un errore: se la sequenza ammette sovrapposizioni si deve tornare al prefisso più lungo ancora valido.
• Usare Moore e aspettarsi l'uscita nello stesso ciclo di Mealy.
• Scegliere la codifica solo sul numero di FF: conta anche la logica combinatoria.
• Non prevedere lo stato iniziale/reset.