valerioditommaso.dev

Le Macchine a Stati Finiti (FSM <- Finite State Machine) sono il modello matematico utilizzato per descrivere sistemi dotati di memoria, capaci di eseguire algoritmi e utili alla progettazione ad alto livello di Reti Logiche Sequenziali.

Come abbiamo già detto nella definizione dei concetti chiave delle Reti Logiche Sequenziali ci sono due tipi di FSM: Sincrone e Asincrone.

La definizione formale di una FSM Sincrona:

Per descrivere matematicamente una FSM viene utilizzata una tupla di sei elementi.

$M = \langle S, X, Z, \delta, \lambda, s_0 \rangle$

Analizziamo il contenuto di questa tupla in ordine di intuitività:

$X$ <--- L’Alfabeto di ingresso - è l’elenco di tutte le possibili combinazioni di bit per ogni ingresso. La sua dimensione varia in base al numero di ingressi, se ci sono $n$ ingressi, allora la dimensione di $X$ sarà di $2^n$ .
$Z$ <--- L’Alfabeto di uscita - è l’elenco di tutte le possibili combinazioni di bit che le variabili di uscita possono avere. La sua dimensione varia in base al numero di uscite, se ci sono $n$ uscite, allora la dimensione di $Z$ è $2^n$ .
$S$ <--- L’Insieme degli Stati - è l’elenco di tutte le possibili combinazioni di bit che uno stato può assumere. Uno stato è come se fosse una memoria, ma non una che salva dati, ma più come memoria che ci dice a che punto è il sistema, come un segnalibro.
$s_0$ <--- Stato Iniziale - è lo stato di default nonché anche il primo appena avviata la FSM.
Le funzioni $\delta$ e $\lambda$ - che lavorano in parallelo e che fanno calcoli molti simili a seconda della FSM specifica (Moore o Mealy):
- $\delta$ <--- Funzione di Stato Prossimo - è una funzione che contiene le condizioni logiche necessarie a determinare il prossimo stato (Stato Attuale + Input). Infatti se di base c’è un $s_0$ di default al fine di permettere la prima esecuzione della FSM, nelle seguenti esecuzioni si ha la necessità di ottenere gli stati delle future esecuzioni. Essendo nel campo di FSM sincrone, a determinare il passaggio sequenziale alla prossima esecuzione è il clock, che scatterà ogni tot tempo, contato con $k$ . Ebbene l’output della funzione $\delta$ diventa $s_{k+1}$ , quindi lo stato che descrive il passato della macchina alla prossima esecuzione.
- $\lambda$ <--- Funzione di Uscita - è una funzione che contiene le condizioni logiche necessarie a restituire l’output presente del sistema. Le condizioni sono generalmente legate allo Stato Attuale (+Input se è Mealy).

Grafi di Transizione di Stato:

Una FSM può essere rappresentata graficamente attraverso dei disegni chiamati Grafi di Transizione di Stato. In questi grafi:

I Nodi (cerchi) <--- Rappresentano gli stati.
Gli Archi (frecce) <--- Rappresentano la transizione da uno stato ad un altro in base all’input in ingresso del circuito in quell’istante di esecuzione della FSM. Queste transizioni rappresentano dunque la funzione $\delta$ nel caso della FSM di Moore, e le funzioni $\delta$ e $\lambda$ nel caso della FSM di Mealy.

Esempio grafico di un Grafo di Transizione di Stato generico:

Macchina di Moore:

Esempio di Grafo con FSM di Moore: Schermata del 2025-12-31 19-13-36.png I nomi delle variabili sono imprecisi e discostati dalla parte descritta sotto.

Nella FSM di Moore, nel grafo possiamo osservare:

Nei Cerchi —> 2 valori: $s_k/z_k$ $s_{k} / z_{k}$
- Gli Stati $s_k$ come variabili (non è necessario saperne il valore).
- L’Output $z_k$ del sistema (riportato come valore numerico).
Negli Archi —> Riportato l’Input $x_k$ del sistema come condizione per passare allo stato prossimo (riportato come valore numerico).

Nella Macchina di Moore:

L’Output presente $z_k$ dipende dallo stato attuale: $z_k = \lambda(s_k)$ Lo Stato Prossimo $s_{k+1}$ dipende dallo stato attuale + input: $s_{k+1} = \delta(s_k, x_k)$

Qual’è la logica per leggere i Grafi nelle FSM di Moore:

Osservare il Cerchio $s_k/z_k$ .
Calcolare l’Output $z_k = \lambda(s_k)$ .
Individuare l’Input $x_k$ sopra l’Arco.
Usare l’Arco come freccia per spostarsi sullo Stato Successivo e calcolare $s_{k+1} = \delta(s_k, x_k)$ .

Macchina di Mealy:

Esempio di Grafo con FSM di Mealy: Pasted image 20251231191419.png I nomi delle variabili sono imprecisi e discostati dalla parte descritta sotto.

Nelle FSM di Mealy, nel grafo possiamo vedere gli:

Nei Cerchi —> Gli Stati $s_k$ come variabili (non è necessario saperne il valore).
Negli Archi —> 2 valori: $x_k/z_k$ $x_{k} / z_{k}$
- Riportato l’Input $x_k$ del sistema come condizione per passare allo stato prossimo. (riportato come valore numerico).
- L’Output $z_k$ del sistema (riportato come valore numerico).

Nella Macchina di Mealy:

L’Output presente $z_k$ dipende dallo stato attuale+ input: $z_k = \lambda(s_k, x_k)$ Lo Stato Prossimo $s_{k+1}$ dipende dallo stato attuale + input: $s_{k+1} = \delta(s_k, x_k)$ In questa FSM Output e Stato Prossimo chiedono gli stessi valori per essere calcolati.

Qual’è la logica per leggere i Grafi nelle FSM di Mealy:

Osservare lo stato attuale nel Cerchio $s_k$ .
Osservare l’Arco.
Osservare la notazione dell’Output $z_k$ successivo a quella dell’Input $x_k$ , che ci dice di calcolare l’Output
Calcolare l’Output $z_k = \lambda(s_k, x_k)$ .
Poi usare l’Arco come freccia (ignorando la notazione dell’Output) per spostarsi sullo Stato Successivo e calcolare $s_{k+1} = \delta(s_k, x_k)$ .

Rappresentare le FSM con delle Tabelle:

Tra FSM di Moore e Mealy cambia di poco il modo con il quale vengono strutturate le tabelle.

Tabelle per FSM di Moore:

Ipotizziamo una FSM di Moore: Pasted image 20260101221109.png

Adesso creiamo la tabella composta da:

Le Colonne che indicano nelle prime 2 gli ingressi ( $0$ o $1$ ) e nell’ultima l’Output.
Le Righe che indicano lo stato in cui si trova il sistema.

Dunque nelle celle in cui si incrociano queste Righe e Colonne andiamo a inserire prima quali sono gli ingressi e l’output in un determinato stato.

La Tabella corrispondente alla FSM sopra:

	$0$	$1$	$Output$
$s_0$	$s_0$	$s_1$	$1$
$s_1$	$s_2$	$s_1$	$0$
$s_2$	$s_0$	$s_0$	$0$

Tabelle per FSM di Mealy:

Ipotizziamo una FSM di Mealy: Pasted image 20260101224151.png

Adesso creiamo una tabella composta da:

Le Colonne che indicano gli ingressi ( $0$ e $1$ ).
Le Righe che indicano lo stato in cui si trova il sistema.

È possibile notare che la differenza con le FSM di Moore è l’assenza di una colonna per gli Output, ma questo è del tutto naturale essendo che anche nei Grafi le FSM di Mealy hanno l’Output rappresentato affianco all’input, quindi anche nelle tabelle, input e output vengono rappresentati insieme.