FSM: Macchine a Stati Finiti -...
53
FSM: Macchine a Stati Finiti
Transcript of FSM: Macchine a Stati Finiti -...
FSM: Macchine a Stati Finiti
Sommario
• Introduzione• Automi di Mealy• Automi di Moore • Esempi
Introduzione• Metodo per descrivere macchine di tipo
sequenziale• Molto utile per la descrizione di Unità di controllo• Rappresento evoluzione circuito come una
sequenza di stati• Sono in uno STATO PRESENTE ed evolverò in
uno STATO FUTURO• La loro realizzazione fisica consiste in una rete
per il calcolo delle USCITE e dello STATO FUTURO a partire da ingressi e STATO PRESENTE ed un registro di attualizzazionedello stato
Introduzione
STATO FUTURO
R
CalcoloUscite
eStato
Futuro
INGRESSI
STATO PRESENTE
USCITE
Registro di attualizzazione dello
stato
Introduzione
• Il registro che attualizza lo stato è quello che permette evoluzione tra stato presente e stato futuro
• Campiona stato futuro che diventerà (al colpo di clock successivo) il nuovo stato presente!!
Introduzione
• Si rappresenta un circuito sequenziale come un insieme di STATI raggiungibili
• Per ogni stato si descrivono le TRANSIZIONI da e per esso
• Per ogni stato si indicano gli INGRESSI del circuito
• Per ogni stato si indicano le USCITE del circuito
Introduzione
• Si può utilizzare una RAPPRESENTAZIONE GRAFICA per descrivere L’EVOLUZIONE degli STATI
• Si utilizza un GRAFO State TransitionDiagram (STD)
• Stati Nodi (“pallozzi”)• Transizioni Vertici (“frecce”)• In gergo si parla di “Pallogramma”
Introduzione
• Esempio di Pallogramma (1 INGRESSO A)
a0
b0
c1
d1
A=0
A=0
A=0
A=0 A=1
A=1
A=1A=1
Introduzione
• Nell’esempio precedente dentro gli stati sono indicate il nome dello STATO ed il valore delle USCITE
• Lungo le transizioni sono indicati i valori assunti dagli INGRESSI
Sommario
• Introduzione• Automi di Mealy• Automi di Moore • Esempi
Automi di Mealy
• Chiamati anche macchine di Mealy• Le USCITE DIPENDONO da STAT0
PRESENTE ed INGRESSINome
STATO
INGRESSI
USCITE
Automi di Mealy
• Molto veloci perché variazioni degli ingressi vengono subito riconosciute producendo le nuove uscite
• Richiedono un numero di stati inferiore• Ritardi diversi sugli ingressi potrebbero
causare uscite SPURIE
Automi di Mealy
R
CalcoloUscite
eStato
Futuro
INGRESSI
STATO PRESENTE Yi
USCITE
STATO FUTURO Fi
Sommario
• Introduzione• Automi di Mealy• Automi di Moore• Esempi
Automi di Moore
• Chiamati anche Macchine di Moore• USCITE DIPENDONO SOLO da STATO
NomeSTATO
USCITE
Automi di Moore
• Richiedono + stati per riconoscere gli ingressi e proporre le corrette uscite
• Sono potenzialmente + lente (rispetto a Mealy)
• Si ha maggiore controllo sull’evoluzione della macchina
• Risultano più facilmente testabili e modificabili
Automi di Moore
CalcoloStato Futuro
R
CalcoloUscite
INGRESSI
STATO PRESENTE Yi
USCITE
STATO FUTURO Fi
Sommario
• Introduzione• Automi di Mealy• Automi di Moore • Esempi
Esempi
• Vedremo sempre macchine di Moore• Vedremo esempi di FSM Semplici• Per il primo vedremo un progetto completo• Per il secondo arriveremo alla definizione
delle funzioni logiche• Per il terzo progetto completo• 2 Esercizi da completare a casa
Esempio 1
• Progettare circuito che riconosca che il valore logico dell’ingresso X al momento attuale è uguale al valore a quello nel periodo di clock precedente.
• In questo caso l’uscita è pari a 1
Esempio 1
X
U
CalcoloStato Futuro
R
CalcoloUscite
FiYi
Macchina di Moore
Esempio 1
• Definiamo uno stato iniziale a con uscita pari a ‘0’ (Stato POR Power-On Reset)
• Se ingresso T=‘0’ vado in stato b se è ‘1’ vado in c con uscita a ‘0’
a0
c0
b0
X=0 X=1
Esempio 1
• In b se X=‘0’ (stesso valore di prima) vado in d con uscita pari a ‘1’. Se X=1 vado in c. In questo modo se ricevo un altro 1 riconosco la sequenza
• In c se X=‘1’ (stesso valore di prima) vado in e con uscita pari a ‘1’. Se X=1 vado in b.
Esempio 1
• Diagramma degli Stati:a0
c0
b0
X=0 X=1
e1
d1
X=0X=1
X=0
X=1
Esempio 1
• In d se ricevo uno ‘0’ rimango nello stesso stato. Se X=‘1’ devo cambiare stato
• Se ritornassi in b ed al clock successivo avessi ancora X=‘1’ andrei in c con uscita a ‘0’ mentre dovrebbe essere ad ‘1’
• Lo stesso succede per e (ovviamente con valori di X duali)
Esempio 1
• Allora se sono in d con X=‘1’ devo andare in c
• Se sono in e con X=‘1’ devo andare in b
Esempio 1
• Diagramma degli Stati Completoa0
c0
b0
X=0 X=1
e1
d1
X=0X=1
X=0
X=1
X=0 X=1
X=0X=1
Esempio 1
• Abbiamo identificato 5 STATI• Intero superiore di log25=3 • Per realizzare tale circuito ci vogliono 3
FLIP-FLOP
Esempio 1: Funzione generazione Stato Futuro
Stato Ingresso Stato Futuro Stato Y2 Y1 Y0
a 0 b a 0 0 0
a 1 c b 0 0 1
b 0 d c 0 1 0
b 1 c d 0 1 1
c 1 e e 1 1 0
c 0 b
d 0 d
d 1 c
e 1 e
e 0 b
ASSEGNAZIONE dello STATO
Esempio 1: Stato Futuro• Tabella di verità
Y2 Y1 Y0 X F2 F1 F0
a 0 0 0 0 0 0 1 ba 0 0 0 1 0 1 0 cb 0 0 1 0 0 1 1 db 0 0 1 1 0 1 0 cc 0 1 0 0 0 0 1 bc 0 1 0 1 1 1 0 ed 0 1 1 0 0 1 1 dd 0 1 1 1 0 1 0 c- 1 0 0 0 - - - -- 1 0 0 1 - - - -- 1 0 1 0 - - - -- 1 0 1 1 - - - -e 1 1 0 0 0 0 1 be 1 1 0 1 1 1 0 e- 1 1 1 0 - - - -- 1 1 1 1 - - - -
Don’t CareValori di cui non ho
specifiche sul valore che devono
assumere
Esempio 1: Stato Futuro
03
07
-15
-11
12
16
-14
-10
01
05
013
-9
10
14
112
-8
Y2 Y1
Y0 X 00 01 11 10
00
01
11
10
13
17
-15
-11
12
16
-14
-10
11
15
113
-9
00
04
012
-8
Y2 Y1
Y0 X 00 01 11 10
00
01
11
10
03
07
-15
-11
02
06
-14
-10
01
15
113
-9
00
04
-12
-8
Y2 Y1
Y0 X 00 01 11 10
00
01
11
10
F0 = X’
F2 = XY0’Y1
F1 = Y0+X
In fase di copertura
attribuisco ai don’t care i valori più consoni
(a proprio piacere)
Esempio 1: Stato Futuro
• Circuito Generazione stato futuro
Esempio 1: Funzione generazione delle uscite
• Macchina di Moore: uscita dipende solo dallo stato presente
• Tabella di Verità:Stato Y2 Y1 Y0 U
a 0 0 0 0b 0 0 1 0c 0 1 0 0d 0 1 1 1- 1 0 0 -- 1 0 1 -e 1 1 0 1- 1 1 1 -
Esempio 1: Uscite
01
13
-7
-5
00
02
16
-4
Y2 Y1
Y0 00 01 11 10
0
1
U = Y2Y1Y0’ + Y2’Y1Y0
Esempio 1: Circuito Finale
Esempio 1: Considerazioni aggiuntive
• Alcuni stati non erano “coperti” (don’t care)• Se per errore la macchina entra in uno di
questi (ad esempio allo start-up), non si conosce comportamento uscite
• Si rischia anche di non uscire da stato di errore
• In quei casi sarebbe stato meglio fissare lo stato futuro ad a
• Rifare per esercizio
Ulteriore Considerazione
• Alcuni segnali devono essere presi negati• Per quelli relativi a stato presente si
possono evitare le porte NOT• Basta prendere le uscite negate fornite dai
FLIP-FLOP di attualizzazione
Esempio 2
• Circuito che riconosca la sequenza in ingresso: “010”
• Ingresso è segnale X• Quando viene riconosciuta l’uscita U deve
essere portata ad ‘1’ (‘0’ altrimenti) • Arriveremo a definire diagramma stati e
assegnazione stati ed uscite• Completare per esercizio
Esempio 2
• Partiamo da stato iniziale A con U=‘0’• Se X=‘1’ rimango in A se X=‘0’ posso
andare in un nuovo stato (B)
A
0
X=‘1’
X=‘0’
B
Esempio 2
• Da B se ricevo X=‘1’ posso avanzare in un nuovo stato (C) [Ho riconusciuto “01”]
• Se X=‘0’ posso rimanere in B in modo da rilevare subito un nuovo ingresso ad ‘1’
A
0
X=‘1’X=‘0’
B
0C
0
X=‘0’
X=‘1’
Esempio 2
• Da C se X=‘0’ vado in D che avrà uscita U=‘1’ [Sequenza “010”]
• Se in C X=‘1’ devo andare in A (non un B)
D
1
X=‘0’
A
0
X=‘1’X=‘0’
B
0C
0 X=‘1’
C
0
X=‘0’
X=‘1’
Esempio 2
• Da D se X=‘0’ posso andare direttamentrein B in modo da poter identificare un nuova sequenza “010”
• Se X=‘1’ posso andare in C infatti ho identificato già una nuova sequenza “01”. Infatti lo ‘0’ deriva da C D ed ora ho ‘1’. Se arriva un altro ‘0’ identifico ancora una sequenza corretta “010”
Esempio 2
• Diagramma degli Stati finale
X=‘1’D
1
X=‘0’
A
0
X=‘1’X=‘0’
B
0C
0 X=‘1’
C
0
X=‘0’
X=‘1’
X=‘0’
4 STATI
2 FLIP-FLOP
Esempio 2: Stato FuturoStato Ingresso Stato Futuro Stato Y1 Y0
A 0 B A 0 0 A 1 A B 0 1B 0 B C 1 0B 1 C D 1 1C 0 D C 1 AD 0 BD 1 C
ASSEGNAZIONE dello STATO
Esempio 2: Stato Futuro
• Tabella di veritàY1 Y0 X F1 F0
A 0 0 0 0 1 BA 0 0 1 0 0 AB 0 1 0 0 1 BB 0 1 1 1 0 CC 1 0 0 1 1 DC 1 0 1 0 0 AD 1 1 0 0 1 BD 1 1 1 1 0 C
Esempio 2: Uscita
• Tabella di verità
Stato Y1 Y0 U
A 0 0 0B 0 1 0C 1 0 0
D 1 1 1
Esempio 2
• Completare l’esercizio ricavando le funzioni logiche per lo stato futuro e le uscite
• Utilizzare le mappe di Karnaugh• Disegnare il circuito risultante
Esempio 3
• Progettare contatore modulo 8• Usare flip-flop tipo D!!!!• Stato Futuro Uscita (Macchina Moore)• Non è necessario ricavare il pallogramma• Parto da tavola di verità• Completare disegnando circuito
Esempio 3
• Tavola di verità
Y2 Y1 Y0 F2 F1 F0
0 0 0 0 0 10 0 1 0 1 00 1 0 0 1 10 1 1 1 0 01 0 0 1 0 11 0 1 1 1 01 1 0 1 1 11 1 1 0 0 0
Esempio 3
• Mappe di Karnaugh
01
13
07
15
00
02
16
14
Y2 Y1
Y0 00 01 11 10
0
1 11
03
07
15
00
12
16
04
Y2 Y1
Y0 00 01 11 10
0
1
01
03
07
05
10
12
16
14
Y2 Y1
Y0 00 01 11 10
0
1 00 YF =
1010101 YYYYYYF ⊕=+=21202102 YYYYYYYF ++=
Esercizio 1 (x casa)
• Progettare un circuito che riconosca la sequenza: “11111111”
• Se si è riconosciuta allora U=‘1’• Ricavare diagramma degli stati• Ricavare funzione logica per stati futuri• Ricavare funzione logica per uscita• Disegnare il circuito finale
Esercizio 2
• Progettare circuito sequenziale che riconosca che ingresso ha variato il suo valore e ponga uscita U=‘1’
• Esempio: @ t=1 X=‘0’@ t=2 X=‘1’ U=‘1’
• Si ipotizzi di partire da uno stato iniziale A corrispondente ad avere ricevuto uno ‘0’ (ovvero NO STATO POR)
Esercizio 2 (x casa)
• Ricavare Diagramma degli Stati• Ricavere le funzioni logiche per Stato
Futuro ed Uscita• Disegnare schema del circuito finale
