fsm: macchine a stati finiti -...
TRANSCRIPT
![Page 1: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/1.jpg)
1
FSM: Macchine a Stati Finiti
Sommario
• Introduzione
• Automi di Mealy
• Automi di Moore
• Esempi
![Page 2: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/2.jpg)
2
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
• 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 attualizzazione dello stato
![Page 3: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/3.jpg)
3
Introduzione
STATO FUTURO
R
CalcoloUscite
eStato
Futuro
INGRESSI
STATO PRESENTE
USCITE
Registro di attualizzazione dello
stato
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
![Page 4: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/4.jpg)
4
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
![Page 5: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/5.jpg)
5
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
![Page 6: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/6.jpg)
6
Automi di Mealy
• Chiamati anche macchine di Mealy
• Le USCITE DIPENDONO da STAT0 PRESENTE ed INGRESSI
Nome 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
![Page 7: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/7.jpg)
7
Automi di Mealy
R
CalcoloUscite
eStato
Futuro
INGRESSI
STATO PRESENTE Yi
USCITE
STATO FUTURO Fi
Sommario
• Introduzione
• Automi di Mealy
• Automi di Moore
• Esempi
![Page 8: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/8.jpg)
8
Automi di Moore
• Chiamati anche Macchine di Moore
• USCITE DIPENDONO SOLO da STATONome
STATO
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
![Page 9: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/9.jpg)
9
Automi di Moore
CalcoloStato Futuro
R
CalcoloUscite
INGRESSI
STATO PRESENTE Yi
USCITE
STATO FUTURO Fi
Sommario
• Introduzione
• Automi di Mealy
• Automi di Moore
• Esempi
![Page 10: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/10.jpg)
10
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
• 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
![Page 11: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/11.jpg)
11
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
![Page 12: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/12.jpg)
12
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
![Page 13: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/13.jpg)
13
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
![Page 14: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/14.jpg)
14
Esempio 1
• Diagramma degli Stati Completo
a0
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
![Page 15: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/15.jpg)
15
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
![Page 16: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/16.jpg)
16
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
013
-9
00
04
112
-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+Y2’X+Y2X’ = Y0 + X + Y2
In fase di copertura
attribuisco ai don’t care i valori più consoni
Esempio 1: Stato Futuro
• Circuito Generazione stato futuro
Y0Y1Y2
X F0
F1
F2
![Page 17: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/17.jpg)
17
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 0
b 0 0 1 0
c 0 1 0 0
d 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
U
Y0Y1Y2
![Page 18: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/18.jpg)
18
Esempio 1: Circuito Finale
U
X
CLK
F0
F1
F2
Y0
Y1
Y2
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
![Page 19: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/19.jpg)
19
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
![Page 20: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/20.jpg)
20
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’
![Page 21: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/21.jpg)
21
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
![Page 22: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/22.jpg)
22
Esempio 2: Stato Futuro
Stato Ingresso Stato Futuro Stato Y1 Y0
A 0 B A 0 0
A 1 A B 0 1
B 0 B C 1 0
B 1 C D 1 1
C 0 D
C 1 A
D 0 B
D 1 C
ASSEGNAZIONE dello STATO
Esempio 2: Stato Futuro
• Tabella di veritàY1 Y0 X F 1 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
![Page 23: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/23.jpg)
23
Esempio 2: Uscita
• Tabella di verità
Stato Y1 Y0 U
A 0 0 0
B 0 1 0
C 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
![Page 24: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/24.jpg)
24
Esercizio 1
• 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)
![Page 25: FSM: Macchine a Stati Finiti - corsiadistanza.polito.itcorsiadistanza.polito.it/corsi/pdf/05EKDN/pdf/FSM.pdf · 2 Sommario • Introduzione • Automi di Mealy • Automi di Moore](https://reader033.vdocumenti.com/reader033/viewer/2022052319/5a78791f7f8b9a7b698b9341/html5/thumbnails/25.jpg)
25
Esercizio 2
• Ricavare Diagramma degli Stati
• Ricavere le funzioni logiche per Stato Futuro ed Uscita
• Disegnare schema del circuito finale