Macchine a stati finiti

Una macchina a stati finiti (FSM: Finite State Machine) è un modello matematico che descrive una macchina che esegue algoritmi ed è dotata di memoria.

Per rappresentare una macchina a stati finiti si visualizzerà l’evoluzione del circuito con una sequenza di stati, dove uno di questi sarà lo stato presente.

Nella realizzazione di una FSM si attua una rete combinatoria dove si inserisce in input:

• I bit di ingressi.
• Lo stato presente.
• Un registro di attualizzazione dello stato.

Alla fine otterremmo gli output e lo stato futuro.

Una FSM (sincrona) si definisce nella seguente tupla:

$$\mathcal{M}=⟨S,X,Z,\lambda ,\delta ,s_0⟩$$

Dove:

• $S=\{s_0,\dots ,s_n\}$ è l’insieme degli stati finiti, con $s_0$ che è lo stato iniziale.
• $X=\{x_0,\dots ,x_m\}$ è l’alfabeto di ingresso.
• $Z=\{z_0,\dots ,z_p\}$ è l’alfabeto di uscita.
• $\delta$ e $\lambda$ sono due funzioni che calcolano rispettivamente lo stato prossimo (la funzione $\delta$) e l’output (la funzione $\lambda$).
  • Nelle macchine di Mealy:
    • La funzione $\delta$ calcolerà lo stato prossimo $s_{k+1}=\delta (x_k,s_k)$
    • La funzione $\lambda$ calcolerà l’output $z_k=\lambda (x_k,s_k)$
  • Nelle macchine di Moore:
    • La funzione $\delta$ calcolerà lo stato prossimo $s_{k+1}=\delta (x_k,s_k)$
    • La funzione $\lambda$ calcolerà l’output $z_k=\lambda (s_k)$

Gli elementi $s_k\in S,x_k\in X,z_k\in Z$ e $k$ è l’istante.

Grafi di transizione

Una FSM si può rappresentare tramite i grafi di transizione dello stato. Questa rappresentazione sfrutta i nodi per descrivere gli stati, mentre sfrutta gli archi per delineare una trasizione da uno stato al successivo in base all’input in ingresso.

Macchine di Mealy

Nelle macchine di Mealy l’output e lo stato prossimo vengono calcolati dai bit in ingresso e dallo stato presente. Quindi in questa FSM l’output sarà $z_k=\lambda (x_k,s_k)$.

Nella rappresentazione grafica, nelle transizioni vengono appuntati input e output (sottoforma di “input/output”), mentre nei nodi c’è solamente lo stato.

Esiste anche una forma tabellare per rappresentare la macchina di Mealy.

	0	1
$s_0$	$s_0$ / 1	$s_1$ / 0
$s_1$	$s_1$ / 1	$s_2$ / 0
$s_2$	$s_2$ / 0	$s_3$ / 1
$s_3$	$s_3$ / 1	$s_0$ / 1

Macchine di Moore

Nelle macchine di Moore lo stato prossimo viene calcolato dai bit in ingresso e dallo stato presente, mentre l’output viene calcolato solamente dallo stato presente. Quindi in questa FSM l’output sarà $z_k=\lambda (s_k)$.

Nella rappresentazione grafica, nelle transizioni viene appuntato solamente l’input, e nel nodo c’è sia lo stato che l’output.

Esiste anche una forma tabellare per rappresentare la macchina di Moore.

	0	1	Uscita
$s_0$	$s_0$	$s_1$	1
$s_1$	$s_1$	$s_2$	0
$s_2$	$s_2$	$s_3$	0
$s_3$	$s_3$	$s_0$	1

Macchina di Mealy vs macchina di Moore

Nella tabella riportata di sotto ci sono le principali differenze tra la macchina di Mealy e la macchina di Moore.

	Mealy	Moore
Come viene generato l’output?	Dipende dallo stato e dagli input	Dipende esclusivamente dallo stato
Dove si scrive l’output?	Sulla transizione	Nello stato
Quando reagisce?	Quando viene dato l’input	Dopo la transizione
Numero di stati	Generalmente ne usa di meno rispetto alla macchina di Moore	Spesso richiede più stati

Da Moore a Mealy

Per passare da una macchina di Moore a una macchina di Mealy basta aggiungere l’output appartenente a uno stato nelle transizioni che partono da esso.

Example

Da Mealy a Moore

Per passare da una macchina di Mealy a una macchina di Moore bisogna, per ogni stato, creare tanti stati quante sono le transizioni con output diverso che puntano allo stato e inserire negli stati l’output della transizione da cui sono stati generati.

Example

Example

Example