Esercizio 17riconoscitore della sequenza 1001 di Mealy e codifica 1-hot (tema d'esame giugno 2026)

---

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 →, Verificare reti logiche e automi con PythonPython serve a controllare i propri conti: tabelle di verità con itertools.product, minimizzazione con sympy (SOPform/POSform con mintermini e don't care), equivalenza di due espressioni con satisfiable(Not(Equivalent(...))), simulazione di una macchina a stati con un dizionario (stato, ingresso) $\to$ (stato futuro, uscita) confrontata con una definizione indipendente, somma in complemento a 2 con rilevazione dell'overflow. Non sostituisce il metodo da sapere a mano (mappe di Karnaugh, tabelle degli stati) ma evita errori di calcolo.Verificare reti logiche e automi con Python →.

a) Diagramma degli stati

Lo stato riassume quanta parte della sequenza $1001$ è stata riconosciuta alla fine degli ingressi ricevuti, tenendo conto della sovrapposizione (se l'ingresso sbagliato non azzera, si torna al più lungo prefisso di $1001$ che è anche suffisso di ciò che si è visto).

• $R_0$: nessun prefisso utile (stato iniziale);
• $R_1$: l'ultimo bit è $1$ (prefisso "$1$");
• $R_2$: ultimi bit $10$ (prefisso "$10$");
• $R_3$: ultimi bit $100$ (prefisso "$100$").

Transizioni (ingresso $A$), motivate:

• $R_0$: $A=0\to R_0$ (nessun progresso); $A=1\to R_1$;
• $R_1$ (visto $1$): $A=0\to R_2$ ($10$); $A=1\to R_1$ (ultimi bit $11$: il solo prefisso utile è l'ultimo $1$);
• $R_2$ (visto $10$): $A=0\to R_3$ ($100$); $A=1\to R_1$ (ultimi $101$: suffisso utile "$1$", non "$10$" perché $101$ non finisce con $10$);
• $R_3$ (visto $100$): $A=0\to R_0$ ($1000$: nessun prefisso: l'ultimo $0$ non inizia nulla); $A=1\to R_1$ con $F=1$: la sequenza $1001$ è completa e l'ultimo $1$ può essere l'inizio di una nuova sequenza (sovrapposizione), quindi si va in $R_1$ e non in $R_0$.

L'uscita è su una freccia (macchina di Mealy): $F=1$ solo nella transizione $R_3\xrightarrow{1}R_1$, nello stesso ciclo in cui arriva l'ultimo bit.

b) Tabella di transizione degli stati e delle uscite

(stato futuro / $F$)

I 4 stati sono tutti diversi (nessuna coppia è equivalente: $R_3$ è l'unico con una uscita $1$; $R_1$, $R_2$ hanno stati futuri diversi). Con la codifica binaria minima servono $\lceil\log_24\rceil=2$ flip-flop, per esempio con $R_0=00,R_1=01,R_2=11,R_3=10$ (Gray).

Verifica. Sequenza di ingresso $0,1,0,0,1,0,0,1,1,0,0,1$: stati (dopo ogni ingresso) $R_0,R_1,R_2,R_3,R_1,R_2,R_3,R_1,R_1,R_2,R_3,R_1$ e uscita $F=0,0,0,0,1,0,0,1,0,0,0,1$: la sequenza è riconosciuta ai bit 5, 8 e 12; tra i bit 2–5 e 5–8 le due occorrenze si sovrappongono nel bit $1$ condiviso ($\dots1001001\dots$). La macchina è stata anche confrontata su 2000 sequenze casuali di 40 bit con la definizione "gli ultimi 4 bit sono $1001$": coincide sempre.

c) Codifica 1-hot

Nella codifica 1-hot si usa un flip-flop per stato, con un solo bit a 1: servono 4 bit, uno per $R_0,R_1,R_2,R_3$ (codici $1000,0100,0010,0001$). Con la codifica binaria ne basterebbero 2: la 1-hot usa più flip-flop, ma in genere ha logica più semplice. Per esempio, scrivendo $Q_i$ per il flip-flop dello stato $R_i$: $$D_0=\overline A\,(Q_0+Q_3),\quad D_1=A\,(Q_0+Q_1+Q_2+Q_3)=A,\quad D_2=\overline A\,Q_1,\quad D_3=\overline A\,Q_2,\quad F=A\,Q_3 .$$ Perché: $R_0$ si raggiunge da $R_0$ e da $R_3$ con $A=0$; $R_1$ si raggiunge da ogni stato con $A=1$, quindi $D_1=A$; $R_2$ solo da $R_1$ con $A=0$; $R_3$ solo da $R_2$ con $A=0$; l'uscita è $1$ solo in $R_3$ con $A=1$.

Errori comuni

• Tornare sempre in $R_0$ dopo un ingresso sbagliato (si perdono le sequenze sovrapposte): da $R_1$ con $A=1$ e da $R_2$ con $A=1$ si va in $R_1$, non in $R_0$.
• Dopo il riconoscimento tornare in $R_0$: l'ultimo $1$ può iniziare una nuova sequenza, quindi si va in $R_1$.
• Mettere $F$ nello stato (Moore) invece che sulla transizione: servirebbe uno stato in più e l'uscita arriverebbe un ciclo dopo.
• Confondere il numero di bit della 1-hot (uno per stato: 4) con quello minimo (2).