Post on 02-May-2015
transcript
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-1
Capitolo 8: Progetto di Macchine a Stati Finiti
Reti Logiche Contemporary Logic Design
Randy H. KatzUniversity of California, Berkeley
May 1993
Trasparenze tradotte da:Luciano Lavagno
Universita’ di UdineSettembre 1998
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-2
Motivazioni
• Contatori: reti logiche sequenziali in cui stato = uscita
• Generalizzazione a Mcchine a Stati Finiti (FSM): Le uscite sono funzione degli stati (e degli ingressi) Stati futuri sono funzione degli stati e degli ingressi Usate per realizzare circuiti che controllano altri circuiti Logica che “prende le decisioni”
• Applicazione di tecniche di progetto logico sequenziale: Specifiche informali (“a parole”) Trasformazione in specifiche formali di FSM Esempi di progetti
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-3
Riassunto del capitoloConcetto di macchina a stati
• Suddivisione tra unita’ operativa (data path) e di controllo (control unit)
• Campionamento degli ingressi ed aggiornamento delle uscite
Metodo base di progetto
• Sei passi di progetto
Diverse rappresentazioni di Macchine a Stati Finiti
• Diagramma degli stati, ASM, VHDL, ABEL Description Language
Macchine di Moore e di Mealy
• Definizione, esempi di realizzazione
Problemi informali
• Esempi di progetto
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-4
Concetto di Macchina a StatiHardware = Unita’ Operativa (UO) + Unita’ di Controllo (UC)
RegistriUnita’ funzionali combinatorie (p.es. ALU)Bus
FSM che genera sequenze di segnali di controlloInforma l’UO su che cosa fare al prossimo passo
”Burattino"
”Burattinaio chetira i fili"
Bit risultato
Bit controllo
Unita’ di controllo
Unita’ operativa
Stato
Controllied uscite
Risultatied ingressi
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-5
Concetto di Macchina a StatiEsempio: controllore di parita’ dispari
Pari [0]
Disp. [1]
Reset
0
0
1 1
Mette ad 1 l’uscita ogni volta che l’ingresso ha un numero dispari di 1
Diagramma degli stati
St. presentePari Pari Disp. Disp.
Ingresso 0 1 0 1
St. futuroPari Disp. Disp. Pari
Uscita 0 0 1 1
Tabella di transizione simbolica
Uscita 0 0 1 1
St. futuro0 1 1 0
Ingresso 0 1 0 1
St. presente0 0 1 1
Tabella di transizione codificata
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-6
Concetto di Macchina a StatiEsempio: controllore di parita’ dispari
Funzioni di stato futuro e di uscita
NS = PS xor PI; OUT = PS
D
R
Q
Q
Input
CLK PS/Output
\Reset
NS
Realizzazione con FF D
T
R
Q
Q
Input
CLK
Output
\Reset
Realizzazione con FF T
Comportamento nel tempo con ingresso 1 0 0 1 1 0 1 0 1 1 1 0
Clk
Output
Input 1 0 0 1 1 0 1 0 1 1 1 0
1 1 0 1 0 0 1 1 0 1 1 1
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-7
Concetto di Macchina a Stati
Temporizzazione: Quando vengono campionati gli ingressi, calcolato lo stato futuro, aggiornate le uscite?
Durata di uno stato: intervallo tra eventi del clock
• Evento di clock fa cambiare uscite e stato in base agli ingressi
• Necessario soddisfare tempi di setup/hold:
Ingressi devono essere stabili prima dell’evento di clock
• Dopo il tempo di propagazione, si passa allo stato futuro e si stabilizzano le uscite
NOTA: segnali asincroni hanno effetto subito, segnali sincroni hanno effetto al prossimo evento di clock
P.es., abilitazione tri-state: attivo immediatamente azzeramento sincrono contatore: attivo al prossimo evento di clock
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-8
Concetto di Macchina a Stati
Esempio: sistema sincrono attivo sul fronte di salita
Sul fronte di salita vengono campionati gli ingressi e calcolati le uscite e lo stato futuro
Dopo un ritardo di propagazione, le uscite e lo stato futuro sono stabili
Uscite imediate: hanno effetto subito sull’UO possono far cambiare i risultati dell’UO
Uscite ritardate: hanno effetto al prossimo evento di clock ritardi di propagazione devono essere maggiori del tempo di hold
Uscite
Durata stato
Clock
Ingressi
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-9
Concetto di Macchina a StatiMacchine a stati comunicanti
Le due macchine avanzano insieme (“al passo”)
Ingressi/uscite iniziali: X = 0, Y = 0
L’uscita di una macchina e’ l’ingresso di un’altra e viceversa
CLK
FSM 1 X FSM 2
Y
A A B
C D D
FSM 1 FSM 2
X
Y
A [1]
B [0]
Y=0
Y=1
Y=0,1
Y=0
C [0]
D [1]
X=0
X=1
X=0
X=0
X=1
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-10
Metodo base di progettoProcesso a sei passi
1. Capire la specifica
2. Derivare una specifica astratta dell’FSM
3. Minimizzare gli stati
4. Assegnare gli stati
5. Scegliere i tipi di FF per realizzare il registro di stato
6. Realizzare l’FSM
1, 2 descritti adesso; 3, 4, 5 descritti piu’ avanti;4, 5 casi generali del metodo di progetto visto per il contatore
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-11
Metodo base di progettoEsempio: FSM che controlla distributore automatico
Definizione informale e genericafornire gomma da masticare dopo aver ricevuto 150 lire
unica fessura per 50 e 100 lire
non da’ resto
Schema a blocchi
Passo 1. Capire il problema:
FSM distributore automatico
50
100
Reset
Clk
OpenSensore monete
Meccanismo distribuzione
gomma
Disegnare una figura!
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-12
Esempio distributore automatico
Tabulare sequenze di ingresso “tipiche”3 da 50 lire1 da 50 lire, 1 da 100 lire1 da 100 lire, 1 da 50 lire2 da 100 lire2 da 50 lire, 100 lire
Disegnare il diagramma degli stati:
Ingressi: 50, 100, reset
Uscita: apri
Passo 2. Trasformare in una specifica formale piu’ adatta
Reset
50
50
50
100
100
50 100
[apri]
[apri] [apri] [apri]
S0
S1 S2
S3 S4 S5 S6
S8
[apri]
S7
100
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-13
Esempio distributore automatico
Passo 3: Minimizzazione degli stati
Reset
50
50
50, 100
[open]
150
0
50
100
100
100
Riutilizzare glistati quandoe’ possibile
Tabella degli stati simbolica
Stato Presente
0
50
100
150
100
0 0 1 1 0 0 1 1 0 0 1 1 X
50
0 1 0 1 0 1 0 1 0 1 0 1 X
Ingressi Stato Futuro
0 50 100 X 50 100 150 X
100 150 150 X
150
Uscita Apri
0 0 0 X 0 0 0 X 0 0 0 X 1
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-14
Esempio distributore automatico
Passo 4: Codifica degli stati
Stato futuroD 1 D 0
0 0 0 1 1 0 X X 0 1 1 0 1 1 X X 1 0 1 1 1 1 X X 1 1 1 1 1 1 X X
Stato presenteQ 1 Q 0
0 0
0 1
1 0
1 1
100
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
50
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Ingressi Uscita Apri
0 0 0 X 0 0 0 X 0 0 0 X 1 1 1 X
Tabella degli stati codificata
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-15
Esempio distributore automaticoPasso 5. Scegliere i FF per la realizzazione
FF D sono i piu’ facili da usare
D1 = Q1 + 100 + Q0 50
D0 = 50 Q0 + Q0 50 + Q1 50 + Q1 100
OPEN = Q1 Q0
8 porte
Mappa per ApriMappa per D0Mappa per D1
Q1 Q0100 50
Q1
Q0
100
Q1 Q0100 50
Q1
Q0
100
Q1 Q0100 50
Q1
Q0
100
50 50 50
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-16
Esempio distributore automatico
Passo 5. Scegliere i FF per la realizzazione
FF J-K
Tabella di transizione codificata trasformata
Stato futuroD 1 D 0
0 0 0 1 1 0 X X 0 1 1 0 1 1 X X 1 0 1 1 1 1 X X 1 1 1 1 1 1 X X
Stato presenteQ 1 Q 0
0 0
0 1
1 0
1 1
D
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
N
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
Ingressi K 1
X X X X X X X X 0 0 0 X 0 0 0 X
K 0
X X X X 0 1 0 X X X X X 0 0 0 X
J 1
0 0 1 X 0 1 1 X X X X X X X X X
J 0
0 1 0 X X X X X 0 1 1 X X X X X
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-17
Esempio distributore automatico
Realizzazione:
J1 = 100 + Q0 50
K1 = 0
J0 = Q0 50 + Q1 100
K0 = Q1 50
7 porte
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-18
Rappresentazioni alternative per FSM
Perche’ i diagrammi degli stati non bastano
Non abbastanza flessibili per grandi FSM
Non adatti per sviluppo graduale della FSM
Non descrivono in modo ovvio un algoritmo: cioe’ una ben specifica sequenza di operazioni basate sui dati di ingresso
algoritmo = sequenza + operazioni sui dati separazione fra controllo e dati
Spostamento graduale verso rappresentazioni simili ad un programma:
• Rappresentazione ad Algorithmic State Machine (ASM)
• Linguaggi di descrizione dell’hardware (Hardware Description Languages, HDL) p.es. VHDL, ABEL
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-19
Rappresentazioni alternative per FSM
Rappresentazione ad Algorithmic State Machine (ASM)
Tre elementi base:
• Stato
• Decisione
• Uscita
FSM e’ esattamente in uno stato alla volta
Singolo ingresso in uno stato
Unico cammino di uscita da uno stato per ogni combinazione degli ingressi
Uscite attive alte (.H) o basse (.L) immediate (I) o ritardate (fino al clock successivo)
Cammino di ingresso nello stato
Nomedello stato
Codice dello stato
Stato
Blocco ASM
Lista uscite assoc. allo stato
Condizione
Lista uscite condizionali
Output Box
Uscite adaltri blocchi ASM
Condizione
* ***
T F
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-20
Rappresentazioni alternative per FSM
Rappresentazione ad ASM
Condizioni:l’ordine non ha effetto sul risultato finale
Blocchi ASM equivalenti: A passa a B se (I0 • I1) altrimenti passa a C
A 010
I0
I1
T
T
F
F
B C
A 010
I0
T
T
F
F
B C
I1
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-21
Rappresentazioni alternative per FSM
Esempio: controllo di parita’
Lista di uscita vuota implica Z inattivo
Z attivo nello stato Dispari
Ingresso X, uscita Z
Ingr.FTFT
Statopresente
PariPari
Disp.Disp.
StatofuturoPari
Disp.Disp.Pari
Uscita——AA
Tabella degli stati simbolica
Ingr.0101
Statopresente
0011
Statofuturo
0110
Uscita0011
Tabella degli stati codificata
Seguire i cammini perderivare le tabelle ditransizione degli stati
Seguire i cammini perderivare le tabelle ditransizione degli stati
Pari
Dispari
H. Z
X
X
0
1
F
T
T F
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-22
Rappresentazioni alternative per FSM
ASM per distributore automatico
0
150
H.Apri
100
Reset
00
1 1
T
T
F
50 F
T
F
100
100
10
T
50 F
T
F
50
100
01
T 50
F T
F
0
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-23
Rappresentazioni alternative per FSMLinguaggi di descrizione dell’hardware: VHDL
ENTITY parity_checker IS PORT ( x, clk: IN BIT; z: OUT BIT);END parity_checker;
ARCHITECTURE behavioral OF parity_checker IS BEGIN main: BLOCK (clk = ‘1’ and not clk’STABLE)
TYPE state IS (Even, Odd); SIGNAL state_register: state := Even;
BEGIN state_even: BLOCK ((state_register = Even) AND GUARD) BEGIN state_register <= Odd WHEN x = ‘1’ ELSE Even END BLOCK state_even;
BEGIN state_odd: BLOCK ((state_register = Odd) AND GUARD) BEGIN state_register <= Even WHEN x = ‘1’ ELSE Odd; END BLOCK state_odd;
z <= ‘0’ WHEN state_register = Even ELSE ‘1’ WHEN state_register = Odd; END BLOCK main;END behavioral;
Descrizione dell’interfaccia
Realizzazione FSM
Espressione di controllo
Decisione stato futuro
Decisione uscite
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-24
Rappresentazioni alternative per FSMLinguaggi di descrizione dell’hardware: ABEL
module paritytitle 'odd parity checker state machine'u1 device 'p22v10';
"Input Pins clk, X, RESET pin 1, 2, 3;
"Output Pins Q, Z pin 21, 22;
Q, Z istype 'pos,reg';
"State registersSREG = [Q, Z];S0 = [0, 0]; " even number of 0'sS1 = [1, 1]; " odd number of 0's
equations [Q.ar, Z.ar] = RESET; "Reset to state S0
state_diagram SREGstate S0: if X then S1 else S0;state S1: if X then S0 else S1;
test_vectors ([clk, RESET, X] -> [SREG]) [0,1,.X.] -> [S0]; [.C.,0,1] -> [S1]; [.C.,0,1] -> [S0]; [.C.,0,1] -> [S1]; [.C.,0,0] -> [S1]; [.C.,0,1] -> [S0]; [.C.,0,1] -> [S1]; [.C.,0,0] -> [S1]; [.C.,0,0] -> [S1]; [.C.,0,0] -> [S1];end parity;
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-25
Metodo progetto per macchine di Moore e MealyDefinizioni
Macchina di Mealy
Le uscite dipendono dastati ed ingressi
Cambiamenti in ingressocausano cambiamenti
immediati in uscita
Alcuni segnalisono asincroni
Macchina di Moore
Le uscite dipendonosolo dagli stati
Cambiamenti in uscitasincronizzati con
il clock
Registro di stato Clock
Reazione di stato
Logicacombinatoriaper uscite estato futuro
X Ingressi
i Z Uscite
k
Clock
Reazione di stato
Logicacombinatoria
per stato futuro(ingressi dei
flipflop)
Registro di stato
Logica combinat. per uscite
Z Uscite
k
X Ingressi
i
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-26
Macchine di Moore e di MealyDiagrammi degli stati equivalenti
Uscite associatecon lo stato
Uscite associate con la transizione
Reset/0
50/0
50/0
50 +100/1150
0
50
100
100/0
100/1
(50 100 + Reset)/0
Reset/0
Reset/1
50 100/0
50 100/0
Macchinadi Moore Reset
N
N
50 + 100
[1]
150
0
50
100
D
[0]
[0]
[0]
D
50 100 + Reset
Reset
Reset
50 100
50 100
Macchinadi Mealy
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-27
Macchine di Moore e di MealyStati o transizioni?
Una macchina di Mealy in genere ha meno stati di una di Moore a parita’ di sequenza di uscita
ASMequivalenti
Stesso comportamento ingresso/uscita
Diverso numero di stati
1
1
0
1
2
0
0
[0]
[0]
[1]
1/0
0
1
0/0
0/0
1/1
1
0
S0
S1
IN
IN
S2
IN
10
01
00
H.OUT
S0
S1
IN
IN
1
0
H.OUT
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-28
Macchine di Moore e di MealyComportamento nel tempo delle macchine di Moore
De-progettate questo circuito:
Ingresso XUscita ZStato A, B = Z
Due metodi per de-progettazione:
• Ad hoc: provare combinazioni di ingresso per derivare tabella di transizione
• Formale: derivare le transizioni analizzando il circuito
JCK R
Q
Q
FFa
JCK R
Q
Q
FFb
X
X
X
X
\Reset
\Reset
A
Z
\A
\A\B
\B
Clk
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-29
Macchine di Moore e di Mealy
De-progettazione ad hoc
Comportamento in risposta alla sequenza 1 0 1 0 1 0:
Tabella di transizione degli
stati parziale
A 0
0
1
1
B 0 1 0 1
X 0 1 0 1 01 0 1
A+ ? 1 0 ? 1 0 1 1
B+ ? 1 0 ? 0 1 1 0
Z 0 0 1 1 0 0 1 1
X = 1 AB = 00
X = 0 AB = 1 1
X = 1 AB = 1 1
X = 0 AB = 10
X = 1 AB = 10
X = 0 AB = 01
X = 0 AB = 00
Reset AB = 00
100
X
Clk
A
Z
\Reset
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-30
Macchine di Moore e di MealyDe-progettazione formale
Derivare la tabella di transizione dalle funzioni di stato futuro in ingresso ai flipflop e dalle funzioni di uscita!
Ja = XJb = X
Ka = X • BKb = X xor A
Z = B
Funzioni di eccitazione del FF J-K:
A+ = Ja • A + Ka • A = X • A + (X + B) • AB+ = Jb • B + Kb • B = X • B + (X • A + X • A) • B
Mappe di Karnaugh delle funzioni di stato futuro:
Stato 00, Ingresso 0 -> Stato 00Stato 01, Ingresso 1 -> Stato 01
A+
B+
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-31
Macchine di Moore e di MealyASM completa per la macchina di Moore da identificare
Nota: tutte le uscite sono associate con gli statiNon ci sono uscite dipendenti dagli ingressi (macchina di Moore)
S 0 00
X
H. Z
S 1 01
X
S 3 1 1
S 2 10
H. Z
X
X
0 1
1 0
0
1
0 1
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-32
Macchine di Moore e di MealyDe-progettate questa macchina di Mealy
Ingresso X, Uscita Z, Stato A, B
Il registro di stato ha un FF D ed un FF J-K
D
C R
Q
Q
J C K R
Q
Q
X
X
X
Clk
A
A
A
B
B
B
Z
\Reset \Reset
\ A
\ A
\ X
\ X
\ X \ B
DA
DA
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-33
Macchine di Moore e di MealyMetodo ad hoc
Comportamento nel tempo con sequenza di ingresso 101011:
Notate lealee su Z!
Uscite valideal fronte di
discesasuccessivodel clock
Tabella ditransizione
parziale basatasulle forme
d’onda
A 0
0
1
1
B 0 1 0 1
X 0 1 0 1 0 1 0 1
A+ 0 0 ? 1 ? 0 1 ?
B+ 1 0 ? 1 ? 1 0 ?
Z 0 0 ? 0 ? 1 1 ?
Reset AB =00
Z =0
X =1 AB =00
Z =0
X =0 AB =00
Z =0
X =1 AB =01
Z =0
X =1 AB =10
Z =1
X =0 AB =1 1
Z =1
X =1 AB =01
Z =0
X
Clk
A
B
Z
\Reset
100
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-34
Macchine di Moore e di MealyMetodo formale
A+ = B • (A + X) = A • B + B • X
B+ = Jb • B + Kb • B = (A xor X) • B + X • B
= A • B • X + A • B • X + B • X
Z = A • X + B • XTransizioni ed uscite mancanti:
Stato 01, Ingr. 0 -> Stato 01, Uscita 1Stato 10, Ingr. 0 -> Stato 00, Uscita 0Stato 11, Ingr. 1 -> Stato 11, Uscita 1A+
Z
B+
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-35
Macchine di Moore e di MealyASM per la macchina di Mealy da identificare
S0 = 00, S1 = 01, S2 = 10, S3 = 11
Nota: alcune uscite dipendono dalle transizioni, altre dagli stati (macchina di Mealy)
S 0 00
X
H. Z S 1 01
S 2 10
X
H. Z
H. Z
S 3 1 1
X X
0
1
0
0 1
1
0 1
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-36
Macchine di Moore e di MealyVariante macchina di Moore
(anche detta macchina di Mealy sincrona)
Uscite e stati memorizzati: “risponde” dopo un ciclo di clock (Moore) ma non ci sono alee sulle uscite!
Registro di stato Clock
Clock
Logicacombinatoria
per uscitee stato futuro
Reazione di stato
X Ingressi
i Z Uscite
k
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-37
Macchine di Moore e di MealyMacchina di Mealy
Uscite non memorizzate: “risponde” immediatamente (Mealy) ma puo’ avere alee sulle uscite!
Registro di stato Clock
Logicacombinatoria
per uscitee stato futuro
Reazione di stato
X Ingressi
i Z Uscite
k
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-38
Specifiche informali di FSMTraduzione di specifiche informali in specifiche formali
Quattro esempi:
• Riconoscitore di stringa finita
• Contatore con decisioni complesse
• Controllore di semaforo
• Serratura a combinazione numerica
Useremo diagrammi degli stati ed ASM
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-39
Specifiche informali di FSMRiconoscitore di stringa finita
Un riconoscitore di stringa finita ha un ingresso (X) ed una uscita (Z).L’uscita e’ attiva quando e’ stata vista la sequenza …010…in ingresso, purche’ non sia mai stata vista la sequenza 100.
Passo 1. Capire il problema
Esempi di comportamenti ingresso/uscita:
X: 00101010010…Z: 000010101000…
X: 11011010010…Z: 000000001000…
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-40
Specifiche informali di FSM
Riconoscitore di stringa finita
Passo 2. Disegnare diagramma degli stati/ASM per le due stringhe che vanno riconosciute, cioe’ 010 ed 100.
Diagramma degli stati di MooreReset manda la FSM nello stato S0
Produce 1 in uscita
Rimane per sempre nello stato
S0 [0]
S1 [0]
S2 [0]
S3 [1]
S4 [0]
S5 [0]
S6 [0]
Reset
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-41
Specifiche informali di FSMRiconoscitore di stringa finita
Condizioni di uscita da S3: ho riconosciuto …010 se il prossimo ingresso e’ 0, ho visto …0100 (stato S6)! se il prossimo ingresso e’ 1, ho visto …0101 = …01 (stato S2)
S0 [0]
S1 [0]
S2 [0]
S3 [1]
S4 [0]
S5 [0]
S6 [0]
Reset
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-42
Specifiche informali di FSMRiconoscitore di stringa finita
Condizioni di uscita da S1: riconosce stringhe del tipo …0 (nessun 1) torna ad S1 se l’ingresso e’ 0
Condizioni di uscita da S4: riconosce stringhe del tipo …1 (nessuno 0) torna ad S4 se l’ingresso e’ 1
S0 [0]
S1 [0]
S2 [0]
S3 [1]
S4 [0]
S5 [0]
S6 [0]
Reset
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-43
Specifiche informali di FSMRiconoscitore di stringa finita
S2, S5 mancano ancora di alcune transizioni
S2 = …01; se il prossimo ingresso e’ 1, potrebbe essere l’inizio di (01)1(00), cioe’ esattamente del caso di S4!
S5 = …10; se il prossimo ingresso e’ 1, potrebbe essere l’inizio di (10)1(0), cioe’ esattamente del caso di S2!
Diagramma deglistati finale
S0 [0]
S1 [0]
S2 [0]
S3 [1]
S4 [0]
S5 [0]
S6 [0]
Reset
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-44
Specifiche informali di FSMRiconoscitore di stringa finita
module stringtitle '010/100 string recognizer state machine Josephine Engineer, Itty Bity Machines, Inc.'u1 device 'p22v10';
"Input Pins clk, X, RESET pin 1, 2, 3;
"Output Pins Q0, Q1, Q2, Z pin 19, 20, 21, 22;
Q0, Q1, Q2, Z istype 'pos,reg';
"State registersSREG = [Q0, Q1, Q2, Z];S0 = [0,0,0,0]; " Reset stateS1 = [0,0,1,0]; " strings of the form ...0S2 = [0,1,0,0]; " strings of the form ...01S3 = [0,1,1,1]; " strings of the form ...010S4 = [1,0,0,0]; " strings of the form ...1S5 = [1,0,1,0]; " strings of the form ...10S6 = [1,1,0,0]; " strings of the form ...100
equations [Q0.ar, Q1.ar, Q2.ar, Z.ar] = RESET; "Reset to S0
state_diagram SREGstate S0: if X then S4 else S1;state S1: if X then S2 else S1;state S2: if X then S4 else S3;state S3: if X then S2 else S6;state S4: if X then S4 else S5;state S5: if X then S2 else S6;state S6: goto S6; test_vectors ([clk, RESET, X] -> [Z]) [0,1,.X.] -> [0]; [.C.,0,0] -> [0]; [.C.,0,0] -> [0]; [.C.,0,1] -> [0]; [.C.,0,0] -> [1]; [.C.,0,1] -> [0]; [.C.,0,0] -> [1]; [.C.,0,1] -> [0]; [.C.,0,0] -> [1]; [.C.,0,0] -> [0]; [.C.,0,1] -> [0]; [.C.,0,0] -> [0];end string;
Descrizione ABEL
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-45
Specifiche informali di FSMRiconoscitore di stringa finita
Riassunto del procedimento:
• Scrivere esempi di sequenze di ingresso ed uscita per capire la specifica
• Scrivere le sequenze degli stati delle stringhe da riconoscere
• Aggiungere transizioni mancanti, riutilizzando stati il piu’ possibile
• Verificare il comportamento ingresso/uscita del diagramma degli stati per verificare che si comporti come specificato
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-46
Specifiche informali di FSMContatore complesso
Un contatore sincrono a 3 bit ha un ingresso M che ne controllail modo di funzionamento:
• Quando M = 0 il contatore conta in avanti in binario puro. • Quando M = 1 il contatore conta in avanti in codice Gray.
Binario: 000, 001, 010, 011, 100, 101, 110, 111Gray: 000, 001, 011, 010, 110, 111, 101, 100
Esempio di comportamento corretto di ingresso/uscita:
Ingresso di modo M0011100
Stato presente000001010110111101110
Stato futuro (Z2 Z1 Z0)001010110111101110111
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-47
Specifiche informali di FSMContatore complesso
Uno stato per ogni combinazione di uscitaAggiungere gli archi opportuni in base al modo
S 0 000
S 1 001 H. Z 0
M
S 3 01 1 H. Z 1 H. Z 0
H. Z 1
S 2 010
M M
S 6 1 10 H. Z 2 H. Z 1
H. Z 2 H. Z 1 H. Z 0
S 4 100
M
H. Z 2
H. Z 2 H. Z 0
M
S 5 101
M
S 7 1 1 1
0 1
0 1
0
1
0
1 0
1
0 1
ResetS0
[000]
S1 [001]
S2 [010]
S3 [011]
S4 [100]
S5 [101]
S6 [110]
S7 [111]
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-48
Specifiche informali di FSMContatore complesso
module countertitle 'combination binary/gray code upcounter Josephine Engineer, Itty Bity Machines, Inc.'u1 device 'p22v10';
"Input Pins clk, M, RESET pin 1, 2, 3;
"Output Pins Z0, Z1, Z2 pin 19, 20, 21;
Z0, Z1, Z2 istype 'pos,reg';
"State registersSREG = [Z0, Z1, Z2];S0 = [0,0,0];S1 = [0,0,1];S2 = [0,1,0];S3 = [0,1,1];S4 = [1,0,0];S5 = [1,0,1];S6 = [1,1,0];S7 = [1,1,1];
equations [Z0.ar, Z1.ar, Z2.ar] = RESET; "Reset to state S0
state_diagram SREGstate S0: goto S1;state S1: if M then S3 else S2;state S2: if M then S6 else S3;state S3: if M then S2 else S4;state S4: if M then S0 else S5;state S5: if M then S4 else S6;state S6: goto S7;state S7: if M then S5 else S0; test_vectors ([clk, RESET, M] -> [Z0, Z1, Z2]) [0,1,.X.] -> [0,0,0]; [.C.,0,0] -> [0,0,1]; [.C.,0,0] -> [0,1,0]; [.C.,0,1] -> [1,1,0]; [.C.,0,1] -> [1,1,1]; [.C.,0,1] -> [1,0,1]; [.C.,0,0] -> [1,1,0]; [.C.,0,0] -> [1,1,1];end counter;
Descrizione ABEL
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-49
Specifiche informali di FSMControllore di semaforo
Una strada di grande traffico incrocia una strada secondaria.Il sensore C segnala la presenza di un’auto sulla strada secondariaSe non ci sono veicoli sulla strada secondaria, il semaforo rimaneverde per la strada principale.Se c’e’ un veicolo sulla strada secondaria, il semaforo passa da verdea giallo a rosso per la strada principale, permettendo al semaforodi diventare verde per la strada secondaria.Il semaforo rimane verde per la strada secondaria finche’ ci sonoveicoli, ma con un tempo massimo prefissato.Quando una di queste due condizioni e’ soddisfatta, il semaforodiventa giallo e poi rosso per la strada secondaria, permettendo alsemaforo di diventare verde per la strada principale.Anche se ci sono veicoli sulla strada secondaria, la strada principaleha un intervallo minimo prefissato con il semaforo verde.
Supponete di avere un temporizzatore che genera un’uscita TSdopo un breve intervallo di tempo ed una TL dopo un lungo intervallodi tempo, in risposta ad un segnale di partenza ST.Usate TS per temporizzare il giallo e TL per il verde.
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-50
Specifiche informali di FSMControllore di semaforo
Figura dell’incrocio:
Principale
Principale
Secondaria
Secondaria
HL
HL
FL
FL
C
C
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-51
Specifiche informali di FSMControllore di semaforo
• Tabella degli ingressi e delle uscite:
Segnale di ingressoresetCTSTL
Segnale di uscitaHG, HY, HRFG, FY, FRST
Descrizioneporta la FSM nello stato inizialepresenza veicolo su strada secondariafine intervallo di tempo brevefine intervallo di tempo corto
Descrizioneattiva luce verde/gialla/rossa principaleattiva luce verde/gialla/rossa secondariainizio intervallo breve o lungo
• Tabella degli stati (alcune uscite ne implicano altre)
StatoS0S1S2S3
DescrizioneVerde principale (rosso secondaria)Giallo principale (rosso secondaria)Verde secondaria (rosso principale)Giallo secondaria (rosso principale)
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-52
Specifiche informali di FSMControllore di semaforo
Completamento di ASM:
Iniziare con sequenza e uscite di base:
S 0 S 3
S 1 S 2
H.HG H.FR
H.HR H.FY
H.HR H.FG
H.HY H.FR
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-53
Specifiche informali di FSMControllore di semaforo
Decidere condizioni di uscita per S0: Veicolo in attesa E fine dell’intervallo lungo: C • TL
Frammenti equivalenti di ASM
S 0 S 0
H.HG H.FR
H.HG H.FR
TL TL • C
H.ST C
H.ST S 1
H.HY H.FR
S 1
H.HY H.FR
0
0
1
1
0
1
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-54
Specifiche informali di FSMControllore di semaforo
Transizione da S1 ad S2: Attivare ST uscendo da S0 Restare in S1 finche’ TS e’ attivato Stesso comportamento per la transizione da S3 ad S4
S 1
H.HY H.FR
TS
H.ST
S 2
H.HR H.FG
0 1
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-55
Specifiche informali di FSMControllore di semaforo
Condizione di uscita per S2: nessun veicolo OPPURE fine dell’intervallo lungo
ASM completa per il controllore di semaforo
S 0 S 3
H.HG H.FR H.ST
H.HR H.FY
TS TL • C
H.ST H.ST
S 1 S 2
H.HY H.FR
H.ST H.HR H.FG
TS TL + C
0 0 1
1
1 0
1
0
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-56
Specifiche informali di FSMControllore di semaforo
Confrontate con il diagramma degli stati:
Vantaggi di ASM:
• Permette di concentrarsi su cammino e condizioni peruscire da uno stato
• Condizione di uscita costruita passo per passo, e poitrasformata in una condizione logica
• E’ piu’ facile capire una specifica algoritmica
S0: HG
S1: HY
S2: FG
S3: FY
Reset
TL + C
S0TL•C/ST
TS
S1 S3
S2
TS/ST
TS/ST
TL + C/ST
TS
TL • C
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-57
Specifiche informali di FSMControllore di semaforo
module traffictitle 'traffic light FSM'u1 device 'p22v10';
"Input Pins clk, C, RESET, TS, TL pin 1, 2, 3, 4, 5;
"Output Pins Q0, Q1, HG, HY, HR, FG, FY, FR, ST pin 14, 15, 16, 17, 18, 19, 20, 21, 22;
Q0, Q1 istype 'pos,reg'; ST, HG, HY, HR, FG, FY, FR istype 'pos,com'; "State registersSREG = [Q0, Q1];S0 = [ 0, 0];S1 = [ 0, 1];S2 = [ 1, 0];S3 = [ 1, 1];
equations [Q0.ar, Q1.ar] = RESET; HG = !Q0 & !Q1;
HY = !Q0 & Q1; HR = (Q0 & !Q1) # (Q0 & Q1); FG = Q0 & !Q1; FY = Q0 & Q1; FR = (!Q0 & !Q1) # (!Q0 & Q1); state_diagram SREGstate S0: if (TL & C) then S1 with ST = 1 else S0 with ST = 0state S1: if TS then S2 with ST = 1 else S1 with ST = 0state S2: if (TL # !C) then S3 with ST = 1 else S2 with ST = 0state S3: if TS then S0 with ST = 1 else S3 with ST = 0 test_vectors ([clk,RESET, C, TS, TL]->[SREG,HG,HY,HR,FG,FY,FR,ST]) [.X., 1,.X.,.X.,.X.]->[ S0, 1, 0, 0, 0, 0, 1, 0]; [.C., 0, 0, 0, 0]->[ S0, 1, 0, 0, 0, 0, 1, 0]; [.C., 0, 1, 0, 1]->[ S1, 0, 1, 0, 0, 0, 1, 0]; [.C., 0, 1, 0, 0]->[ S1, 0, 1, 0, 0, 0, 1, 0]; [.C., 0, 1, 1, 0]->[ S2, 0, 0, 1, 1, 0, 0, 0]; [.C., 0, 1, 0, 0]->[ S2, 0, 0, 1, 1, 0, 0, 0]; [.C., 0, 1, 0, 1]->[ S3, 0, 0, 1, 0, 1, 0, 0]; [.C., 0, 1, 1, 0]->[ S0, 1, 0, 0, 0, 0, 1, 0];end traffic;
Descrizione ABEL
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-58
Specifiche informali di FSMSerratura a combinazione numerica
Una serratura seriale a 3 bit controlla l’ingresso di una stanza. Gli ingressi sono: RESET, ENTER ed un interruttore a 2 posizioniKEY-IN per il bit di codice.La serratura genera l’uscita UNLOCK (sblocca) quando il codice introdotto corrisponde alla combinazione interna.Una luce di ERROR si illumina se il codice non corrisponde alla combinazione.La sequenza corretta e’: (1) premi RESET, (2) introduci il bit di codice, (3) premi ENTER, ripeti (2) e (3) per altre 2 volte. La specifica e’ incompleta: • come viene definita la combinazione? • quando viene accesa ERROR esattamente?
Fate supposizioni ragionevoli: • combinazione memorizzata in un registro oppure pre-definita
nella logica di stato futuro • attivare ERROR subito, appena identificato un errore, oppure
aspettare la fine del codice
In questo caso: combinazione in un registro e segnalazione di errorealla fine del codice
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-59
Specifiche informali di FSMSerratura a combinazione numerica
Capire il problema: disegnare lo schema a blocchi...
Combinazioneinterna
Dati dall’operatore
Ingressi:ResetEnterKey-InL0, L1, L2
Uscite:UnlockError
UNLOCK
ERROR
RESET
ENTER
KEY -IN
L 0
L 1
L 2
Combination Lock FSM
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-60
Specifiche informali di FSMSerratura a combinazione numerica
Enumerazione degli stati:
quali sequenze portano all’apertura della porta? le condizioni di errore saranno verificate in un secondo tempo …
Stato iniziale START piu’ tre stati di confronto COMP
Entra in START quando c’e’ RESET
Esce da START quando ENTER e’ stato premuto
Continua se Key-In e’ uguale ad L0
ST ART
Reset
Enter
COMP0
KI = L 0
N
Y
1
0
0
1
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-61
Specifiche informali di FSMSerratura a combinazione numerica
Cammino persbloccare:
Attendere cheEnter sia stato
premuto
Confrontare Key-In
COMP0
N KI = L 0
Y IDLE0
Enter
COMP1
N
Y
KI = L 1
IDLE1
COMP2
Enter
N KI = L 2
Y DONE
H.Unlock
Reset
ST ART
1
0
0
1
0
1
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-62
Specifiche informali di FSMSerratura a combinazione numerica
Adesso consideriamo gli errori: Dovremmo seguire la stessa sequenza del cammino che finisce con UNLOCK, eccetto per l’attivazione di ERROR alla fine
Errore in COMP0 va ad IDLE0'
Errore in COMP1 va ad IDLE1'
Errore in COMP2 va ad ERROR3
IDLE0'
Enter
ERROR1
IDLE1'
Enter
ERROR2
ERROR3
H.Error
Reset
ST ART
0 0 0
1 1 1
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-63
Specifiche informali di FSMSerratura a combinazione numerica
Diagramma degli statiequivalente
Reset
Reset + Enter
Reset • Enter
Start
Comp0
KI = L0 KI ° L0
Enter
Enter
Enter
Enter
Idle0 Idle0'
Comp1 Error1
KI ° L1KI = L1Enter
Enter
EnterEnter
Idle1 Idle1'
Comp2 Error2
KI ° L2KI = L2
Done [Unlock]
Error3 [Error]
Reset
Reset Reset
Reset
StartStart
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-64
Specifiche informali di FSMSerratura a combinazione numerica
module locktitle 'comb. lock FSM'u1 device 'p22v10';
"Input Pinsclk, RESET, ENTER, L0, L1, L2, KI pin 1, 2, 3, 4, 5, 6, 7;
"Output PinsQ0, Q1, Q2, Q3, UNLOCK, ERROR pin 16, 17, 18, 19, 14, 15;
Q0, Q1, Q2, Q3 istype 'pos,reg';UNLOCK, ERROR istype 'pos,com'; "State registersSREG = [Q0, Q1, Q2, Q3];START = [ 0, 0, 0, 0];COMP0 = [ 0, 0, 0, 1];IDLE0 = [ 0, 0, 1, 0];COMP1 = [ 0, 0, 1, 1];IDLE1 = [ 0, 1, 0, 0];COMP2 = [ 0, 1, 0, 1];DONE = [ 0, 1, 1, 0];IDLE0p = [ 0, 1, 1, 1];ERROR1 = [ 1, 0, 0, 0];IDLE1p = [ 1, 0, 0, 1];ERROR2 = [ 1, 0, 1, 0];ERROR3 = [ 1, 0, 1, 1];
equations [Q0.ar, Q1.ar, Q2.ar, Q3.ar] = RESET; UNLOCK = !Q0 & Q1 & Q2 & !Q3;"asserted in DONE ERROR = Q0 & !Q1 & Q2 & Q3; "asserted in ERROR3 state_diagram SREGstate START: if (RESET # !ENTER) then START else COMP0; state COMP0: if (KI == L0) then IDLE0 else IDLE0p;state IDLE0: if (!ENTER) then IDLE0 else COMP1;state COMP1: if (KI == L1) then IDLE1 else IDLE1p;state IDLE1: if (!ENTER) then IDLE1 else COMP2;state COMP2: if (KI == L2) then DONE else ERROR3;state DONE: if (!RESET) then DONE else START;state IDLE0p:if (!ENTER) then IDLE0p else ERROR1;state ERROR1:goto IDLE1p;state IDLE1p:if (!ENTER) then IDLE1p else ERROR2;state ERROR2:goto ERROR3;state ERROR3:if (!RESET) then ERROR3 else START; test_vectors end lock;
Descrizione ABEL
Reti LogicheMacchine a Stati Finiti
© R.H. Katz 8-65
Riassunto del capitoloComportamento fondamentale nel tempo di una FSM
• quando gli ingressi vengono campionati, e quando gli stati e le uscite cambiano e si stabilizzano
• Macchine di Moore e Mealy (sincrone ed asincrone) uscite = F(stato) oppure uscite = F(stato, ingressi)
Primi due passi della procedura (in sei passi) per la sintesi di FSM
• capire il problema
• derivare una rappresentazione astratta della FSM
Rappresentazioni astratte di FSM
• diagrammi degli stati, ASM, linguaggi di descrizione dell’hardware
Specifiche informali
• capire il comportamento ingresso/uscita; disegnare schemi
• tracciare gli stati per l’”obiettivo”; aggiungere le condizioni di errore
• riutilizzare gli stati se possibile