Reti sequenziali e automi a stati finiti

In questa pagina 4

In questa pagina 3

Modello

Una rete sequenziale sincrona è fatta di:

un registro di stato di $k$ flip-flop D (vedi Latch e flip-flop), che può ricordare fino a $2^k$ stati;
una rete combinatoria di stato prossimo: dagli ingressi $X$ e dallo stato attuale $S$ calcola $S' = \delta(S, X)$ ;
una rete combinatoria di uscita $Z$ .

A ogni fronte del clock lo stato diventa $S'$ . Il comportamento si descrive con un automa a stati finiti (diagramma degli stati: un nodo per stato, un arco per ogni transizione etichettato con l'ingresso).

Tipo	Uscita	Conseguenza
Moore	dipende solo dallo stato: $Z = \lambda(S)$	uscita stabile per tutto il ciclo, cambia solo dopo il fronte
Mealy	dipende da stato e ingressi: $Z = \lambda(S, X)$	di solito servono meno stati, ma l'uscita risente subito degli ingressi

L'Unità di controllo cablata di un processore è un automa di questo tipo: lo stato è la fase dell'istruzione, le uscite sono i segnali di controllo.

Sintesi: procedimento

Diagramma degli stati dalla specifica.
Tabella degli stati (stato attuale, ingresso → stato prossimo, uscita).
Codifica degli stati in binario ( $k = \lceil \log_2 N \rceil$ flip-flop per $N$ stati).
Tabella di verità delle funzioni di stato prossimo e di uscita, semplificazione con le mappe di Karnaugh.
Disegno: flip-flop + reti combinatorie.

Esempio: riconoscere due 1 consecutivi

Ingresso seriale $X$ (un bit per ciclo), uscita $Z = 1$ quando gli ultimi due bit ricevuti sono entrambi 1. Automa di Moore:

Stato	Significato	$Z$	$X = 0$	$X = 1$
$S_0$	ultimo bit 0 (o inizio)	0	$S_0$	$S_1$
$S_1$	ultimo bit 1, il precedente no	0	$S_0$	$S_2$
$S_2$	ultimi due bit 1	1	$S_0$	$S_2$

Codifica con due flip-flop $Q_1Q_0$ : $S_0 = 00$ , $S_1 = 01$ , $S_2 = 10$ (11 non usato, indifferenza).

$Q_1$	$Q_0$	$X$	$Q_1'$	$Q_0'$
0	0	0	0	0
0	0	1	0	1
0	1	0	0	0
0	1	1	1	0
1	0	0	0	0
1	0	1	1	0

Semplificando (le righe con $Q_1Q_0 = 11$ sono indifferenze):

$Q_1' = X(Q_1 + Q_0) \qquad Q_0' = X\,\overline{Q_1}\,\overline{Q_0} \qquad Z = Q_1$

Prova con l'ingresso 0 1 1 1 0: stati $S_0 \to S_0 \to S_1 \to S_2 \to S_2 \to S_0$ , uscite (lette nello stato raggiunto) 0, 0, 1, 1, 0: l'uscita vale 1 dopo il secondo e il terzo 1 consecutivo ✓.

Errori tipici

In un automa di Moore, mettere l'uscita sugli archi invece che negli stati (è un automa di Mealy).
Dimenticare di specificare la transizione per ogni valore dell'ingresso in ogni stato.

Versione ripasso

Modello

Registro di stato di $k$ flip-flop D (Latch e flip-flop) più rete di stato prossimo $S' = \delta(S, X)$ e rete di uscita; lo stato cambia a ogni fronte del clock.

Moore: $Z = \lambda(S)$ , uscita stabile per tutto il ciclo. Mealy: $Z = \lambda(S, X)$ , meno stati ma sensibile subito agli ingressi.
L'Unità di controllo cablata è un automa (stato = fase, uscite = segnali).

Sintesi

Diagramma degli stati, tabella degli stati, codifica con $k = \lceil \log_2 N \rceil$ flip-flop, tabelle di verità e semplificazione (mappe di Karnaugh), circuito.

Esempio: due 1 consecutivi (Moore)

$S_0$ (ultimo bit 0) $Z = 0$ , $S_1$ (un 1) $Z = 0$ , $S_2$ (due 1) $Z = 1$ ; con $X = 0$ si va in $S_0$ , con $X = 1$ : $S_0 \to S_1 \to S_2 \to S_2$ . Codifica $S_0 = 00$ , $S_1 = 01$ , $S_2 = 10$ (11 indifferenza): $Q_1' = X(Q_1 + Q_0) \qquad Q_0' = X\,\overline{Q_1}\,\overline{Q_0} \qquad Z = Q_1$ Ingresso 0 1 1 1 0: stati $S_0 \to S_0 \to S_1 \to S_2 \to S_2 \to S_0$ , uscite 0, 0, 1, 1, 0.

Errori tipici: in Moore l'uscita è negli stati, non sugli archi; specificare la transizione per ogni ingresso in ogni stato.

Esercizi su questo argomento

Esercizio 32 · riconoscitore di sequenza con automa di Mealy

Reti sequenziali e automi a stati finiti

Modello

Sintesi: procedimento

Esempio: riconoscere due 1 consecutivi

Errori tipici

Modello

Sintesi

Esempio: due 1 consecutivi (Moore)

Esercizi su questo argomento

Teoria collegata