Esercizio 14circuito sequenziale di Moore con codifica Gray (tema d'esame settembre 2025)

---

Teoria usata: 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 →, 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 →, Mappe di Karnaugh - POS, condizioni di don't care e paritàPer la POS minima si raggruppano gli 0 della mappa, si ottiene la SOP minima di $\overline F$ e si scrive $F$ come prodotto di somme (variabile diretta se vale 0 nel gruppo, negata se vale 1). Le condizioni di don't care (X) sono combinazioni di ingresso che non si presentano o la cui uscita è indifferente: si usano come 1 o come 0 a seconda di quel che allarga i gruppi (mai raggruppamenti fatti solo di X). Le funzioni XOR a più variabili (disparità) e XNOR (parità) hanno mappa a scacchiera: non si semplificano con i gruppi.Mappe di Karnaugh - POS, condizioni di don't care e parità →, Codici binari - BCD, ASCII, Unicode, parità e GrayUn codice binario a $n$ bit distingue $2^n$ elementi. BCD: una cifra decimale ogni 4 bit (1010–1111 non usati; 10 richiede 8 bit, non è il binario del numero). ASCII: 7 bit per 128 caratteri, la cifra ASCII è 011 seguito dal BCD. Unicode/UTF-8: da 1 a 4 byte, compatibile con ASCII. Bit di parità: rileva errori su un numero dispari di bit. Distanza di Hamming = numero di bit diversi. Codice Gray: numeri consecutivi differiscono di un solo bit (sensori di posizione); si costruisce per riflessione o con $g_i=b_i\oplus b_{i+1}$.Codici binari - BCD, ASCII, Unicode, parità e Gray →.

Interpretazione adottata

Il testo ha alcune zone ambigue; si adotta la lettura più naturale e la si dichiara:

• la sequenza $111$ è formata da tre $1$ consecutivi (il primo $1$ che ha alzato $W_1$ conta come il primo dei tre); un $0$ in ingresso azzera il conteggio dei $1$ consecutivi ma $W_1$ resta a 1;
• dopo la sequenza $111$ le uscite sono $W_1=W_2=1$ e restano così finché si presenta un ulteriore $1$ (un $0$ non cambia nulla); con il quarto $1$ si ritorna a $S_0$ ($W_1=W_2=0$).

a) Diagramma degli stati

Servono le informazioni: $W_1$ già alzato o no; quanti $1$ consecutivi sono arrivati (0, 1, 2, 3); se $W_2$ è alzato. Stati (macchina di Moore, uscite $W_1W_2$ nello stato):

Spiegazione: da $S_1$ e da $S_2$ un $0$ interrompe la serie di $1$ consecutivi: lo stato in cui si finisce ($S_4$: $W_1$ resta a 1, conteggio 0) è lo stesso in entrambi i casi; da $S_4$ un nuovo $1$ riparte il conteggio ($S_1$). In $S_3$ ($W_2=1$) uno $0$ non cambia nulla; un $1$ riporta tutto a $0$.

b) Minimizzazione degli stati

Un diagramma ingenuo avrebbe uno stato diverso per ogni via con cui si arriva a "$W_1$ alzato, conteggio 0" (uno raggiungibile da $S_1$ con $K=0$, uno da $S_2$ con $K=0$): hanno la stessa uscita e gli stessi stati futuri, quindi sono equivalenti e si fondono in $S_4$.

Si verifica che i cinque stati restanti non sono equivalenti con il raffinamento di partizioni. Uscite: $S_0$ ($00$), $\{S_1,S_2,S_4\}$ ($10$), $S_3$ ($11$). Dentro $\{S_1,S_2,S_4\}$: con $K=1$, $S_2$ va in $S_3$ (che ha $W_2=1$) mentre $S_1$ e $S_4$ vanno in stati con $W_2=0$: $S_2$ si separa; poi $S_1$ ($K=1\to S_2$) e $S_4$ ($K=1\to S_1$) vanno in stati ora distinti: si separano. Risultano 5 stati distinti.

c) Codifica Gray e numero di flip-flop

Con 5 stati servono $\lceil\log_25\rceil=3$ flip-flop. Codici Gray assegnati in ordine agli stati (si parte da $S_0=000$ con $X_2X_1X_0$): $S_0=000$, $S_1=001$, $S_2=011$, $S_3=010$, $S_4=110$. I tre codici $100,101,111$ sono inutilizzati: don't care. La codifica Gray rende adiacenti sulla mappa gli stati consecutivi.

d) Equazioni

Tabella degli stati futuri (le uscite non dipendono da $K$):

Ingresso del primo flip-flop ($D_0$, bit $X_0$ dello stato futuro). $X_0$ futuro vale $1$ per $(X_2X_1X_0,K)=(000,1),(001,1),(110,1)$, cioè nelle celle $1,3,13$ della mappa in $(X_2,X_1,X_0,K)$; i codici $100,101,111$ sono don't care. Mappa (righe $X_2X_1$, colonne $X_0K$):

Gruppi (usando le X): $\overline{X_1}K$, cioè le celle $1,3,9,11$ (le celle reali $1$ e $3$ più le X $9$ e $11$): $X_1=0$, $K=1$; e $X_2K$, cioè le celle $9,11,13,15$ (la cella reale $13$ più le X): $X_2=1$, $K=1$. Risultato: $$D_0=\overline{X_1}\,K+X_2\,K=K\,(\overline{X_1}+X_2).$$

Uscita $W_1$. Vale $1$ in $S_1,S_2,S_3,S_4$ (codici $001,011,010,110$) e $0$ in $S_0$ ($000$); le altre combinazioni sono don't care:

Gruppi: le celle con $X_0=1$ ($1,3,5,7$, le ultime due sono X): $X_0$; le celle con $X_1=1$ ($2,3,6,7$): $X_1$. Insieme coprono tutti gli $1$. $$W_1=X_0+X_1$$ ($X_2$ non serve: l'unico $0$ è nello stato $000$.) Controllo: $S_4=110\Rightarrow X_1=1\Rightarrow W_1=1$ ✓; $S_0=000\Rightarrow0$ ✓. Anche l'altra uscita risulta $W_2=\overline{X_2}X_1\overline{X_0}$ (solo $S_3=010$ ha $W_2=1$).

Per completezza: $D_1=X_0+X_1\overline K$ e $D_2=X_0\overline K+X_2\overline K=\overline K\,(X_0+X_2)$.

Simulazione di controllo

Ingresso $K=0,1,1,0,1,1,1,1,0,1,0,1,1,1,1$ da $S_0$:

$W_1$ si alza dopo il primo $1$ (stato $S_1$ dal ciclo 2). Lo $0$ del ciclo 3 interrompe la serie $1,1$ (stato $S_4$: $W_1$ resta a 1). I tre $1$ consecutivi dei cicli 4, 5, 6 portano a $S_3$ ($W_1W_2=11$ al ciclo 7: l'uscita di Moore compare dopo il fronte). Il $1$ del ciclo 7 riporta a $S_0$ ($00$ al ciclo 8). Il circuito con le equazioni trovate riproduce la tabella su tutte le $10$ combinazioni (stato, $K$) valide.

Errori comuni

• Dimenticare che $W_1$ resta a 1 anche dopo uno $0$.
• Non fondere gli stati equivalenti (un diagramma con 6–7 stati).
• Non usare i codici inutilizzati come don't care: si perderebbe $D_0=K(\overline{X_1}+X_2)$.
• Assegnare codici non-Gray o non partire da $000$ per $S_0$ (il testo lo richiede).