1.2
I modelli di
comportamento
dei sistemi digitali
12 ottobre 2000
Comportamento combinatorio o sequenziale?
1
Il processo di elaborazione
astrazione
b) Il modello del blocco e la relazione ingresso/uscita
i(t)  I
(alfabeto di ingresso)
P
u(t)  U
(alfabeto di uscita)
U(t) = P(t, i(t))
a) L’interazione uomo/macchina
Dati
MACCHINA
Risultati
12 ottobre 2000
2
Esempio di comportamento di un sistema digitale
u=
i
dato
9
25
49
risultato
3
5
7
t
L’uscita all’istante t è funzione dell’ingresso in quell’istante
L’uscita u(t) non dipende da i() con  < t
L’uscita non risente della storia passata degli ingressi
Il sistema non ha memoria
possiamo scrivere:
u = P(i)
u(t) = P(i(t)) oppure
Questo comportamento è detto: combinatorio
Questo comportamento può essere descritto da una tabella della verità
Le reti logiche che realizzano questo tipo di comportamento
si chiamano: reti logiche combinatorie
12 ottobre 2000
3
La macchina combinatoria
Un sistema digitale in cui l’uscita dipende solo dal valore
contemporaneo dell’ingresso è detto macchina combinatoria.
U(t) = f (I(t))
In una macchina combinatoria, Se I è l’insieme delle
informazioni in ingresso e U è l’insieme delle informazioni in
uscita il comportamento della macchina è descritto mediante
la funzione
F: I U
La funzione F può essere assegnata mediante una tabella che associa a
ogni simbolo di ingresso il corrispondente simbolo in uscita
12 ottobre 2000
4
Un altro esempio di macchina combinatoria:
il campanello
Tabella del comportamento
i: Pulsante
u = F(i)
12 ottobre 2000
Premuto
Rilasciato
u: Suoneria
Suono
Nessun Suono
5
Altro esempio di comportamento
V
G
R
u(t) = P(t)
t
• Il sistema non ha ingressi ma deve tener conto dello scorrere del tempo
• Il tempo deve essere discretizzato (cioè suddiviso in intervalli Tn)
• Il sistema ha memoria: deve sapere quanti intervalli di tempo sono passati, quindi deve
saper contare
• Il valore del conteggio riassume la storia passata del sistema
• Il riassunto della storia passata (o memoria del sistema) si chiama anche:
stato interno presente del sistema
• L’uscita u(Tn) dipende dallo stato interno nello stesso intervallo Tn
Questo comportamento è detto: sequenziale sincrono
• sequenziale significa “con stato interno che influenza l’uscita”
• sincrono significa che lo stato interno può cambiare solo in
determinati istanti di tempo (quelli che separano Tn da Tn+1)
Le reti logiche che realizzano questo tipo di comportamento
si chiamano: reti logiche sequenziali sincrone
12 ottobre 2000
6
Approfondiamo l’esempio: u(tn) = P(s( tn))
V
T0
t0
G
T1
t1
T2
t2
T3
t3
R
T4
V
T5
t5
T7
T6
t6
t7
T8
t8
T9
t
t9
• Il semaforo resta verde per 60 sec, giallo per 20 sec e rosso per 60 sec, poi torna verde;
quindi ha un comportamento periodico con periodo 140 sec.
• Se dividiamo il tempo in intervalli di durata T = 20 sec, allora il semaforo resta verde in
T0, T1, T2 , giallo in T3 e rosso in T4, T5, T6 , poi torna verde
• Si ha che u(tn+7) = u(tn): l’uscita è periodica con periodo 7 T
• Allora possiamo dire quanto segue:
• l’uscita dipende dall’intervallo Ti in cui ci troviamo
• l’intervallo in cui ci troviamo identifica lo stato interno presente s
• lo stato interno si ripete con periodo 7 T;
• se associamo uno “stato interno” a ciascuno dei 7 intervalli T in cui è suddiviso il
periodo di funzionamento del semaforo, allora possiamo far corrispondere a ogni stato
interno un suo valore dell’uscita: u = P(s)
• dunque possiamo dire che in questa macchina sequenziale sincrona l’uscita è una
funzione combinatoria dello stato presente
12 ottobre 2000
7
Ecco la tabella che associa l’uscita allo stato interno presente
V
T0
t0
Stato presente:
Stato
presente
A
B
C
D
E
F
G
12 ottobre 2000
T1
t1
A
uscita
verde
verde
verde
giallo
rosso
rosso
rosso
G
T2
t2
B
T3
R
T4
t3
C
T5
t5
D
E
V
t6
F
T7
T6
t7
G
T8
t8
T9
t
t9
A
Questa è una corrispondenza tra un
insieme finito di simboli di ingresso
( i sette valori dello stato interno) e un
insieme finito di simboli di uscita ( i tre
colori);
se chiamiamo S l’insieme dei sette stati
e U l’insieme dei valori possibili
dell’uscita, e se chiamiamo F la
corrispondenza tra S e U, allora
possiamo scrivere:
F: S  U
8
E’ sufficiente assegnare la funzione F: S  U per
descrivere il funzionamento del semaforo?
V
T0
t0
Stato
presente
A
B
C
D
E
F
G
T1
t1
Stato
futuro
B
C
D
E
F
G
A
G
T2
t2
T3
t3
R
T4
V
T5
t5
t6
t7
T8
t8
T9
t
t9
No, perché non abbiamo ancora detto come viene
aggiornato lo stato presente che rappresenta la
memoria del sistema; la stato presente ci dice a
che punto siamo del ciclo; dunque deve essere
aggiornato ad ogni istante di clock.
La tabella di fianco ci dice, per ogni stato qual è
il successivo. Se ad ogni istante di clock
facciamo passare lo stato presente dal valore
della colonna di sinistra al valore della colonna
di destra, allora otteniamo il corretto
funzionamento del nostro semaforo
La tabella descrive la funzione G: S  S
12 ottobre 2000
T7
T6
9
Conclusione: il comportamento del semaforo è
descritto dalle due funzioni F: S  U e G: S  S
V
T0
t0
Stato
presente
A
B
C
D
E
F
G
uscita
verde
verde
verde
giallo
rosso
rosso
rosso
F: S  U
12 ottobre 2000
G
T1
t1
T2
t2
Stato
presente
R
T3
T4
t3
V
T5
t5
T7
T6
t6
t7
t8
Stato
futuro
A
B
C
D
E
F
G
G: S  S
B
C
D
E
F
G
A
T8
s
t
T9
t9
F
u
G
s*
T
F e G sono due blocchi combinatori
T è l’intervallo tra due aggiornamenti
successivi dello stato interno
10
Le tabelle che descrivono le due funzioni F e G si
possono raggruppare in un’unica tabella detta
Tabella di Flusso
V
T0
t0
G
T1
t1
T2
t2
Stato
presente
A
B
C
D
E
F
G
12 ottobre 2000
T3
R
T4
t3
T5
t5
Stato
futuro
B
C
D
E
F
G
A
G: S  S
V
T7
T6
t6
t7
T8
t8
T9
t
t9
uscita
verde
verde
verde
giallo
rosso
rosso
rosso
F: S  U
11
Il sistema di elaborazione che controlla il semaforo
Il comportamento del semaforo è specificato dalle funzioni F: S  U e G: S  S
z1
clock
•
•
•
•
•
rete
sequenziale
sincrona
z2
z3
Il sistema di elaborazione che dobbiamo progettare è un sistema BINARIO; è
cioè un sistema in grado di trattare solamente variabili binarie.
Quindi è necessario che tutti le informazioni trattate (gli insiemi S e U) siano
tradotte in sequenze di zeri e uni.
Questa operazione è detta “codifica”
dobbiamo dunque codificare gli stati con variabili binarie che chiameremo
“variabili di stato interno”
dobbiamo codificare i simboli di uscita con “variabili binarie di uscita”
12 ottobre 2000
12
Codifica degli stati e delle uscite
V
T0
t0
G
T1
t1
T2
t2
T3
t3
R
T4
V
T5
t5
T7
T6
t6
t7
T8
t8
T9
t
t9
•Per codificare 7 informazioni sono necessarie 3 variabili binarie
•La codifica è arbitraria
•Le uscite sono codificate in modo ridondante (basterebbero anche due bit)
Codifica
Stato
A
B
C
D
E
F
G
12 ottobre 2000
y2 y1 y0
000
001
010
011
100
101
110
Uscita
Codifica
z3 z2 z1
Acceso verde
100
Acceso giallo
010
Acceso rosso
001
13
La tabella delle transizioni
•Se si applica alla tabella di flusso la codifica degli stati e delle uscite si ottiene una
nuova tabella detta tabella delle transizioni
•La tabella delle transizioni esprime in forma binaria le funzioni F e G!!
•Le funzioni F e G sono combinatorie
Stato
presente
Stato
presente
y2 y1 y0
A
B
C
D
E
F
G
000
001
010
011
100
101
110
Stato
futuro
Uscita
001
010
011
100
101
110
000
100
100
100
010
001
001
001
G: S  S
z3 z2 z1
F: S  U
Per poter realizzare le sei funzioni Y2 Y1 Y0 e z3 z2 z1
è necessario studiare l’algebra di comutazione
12 ottobre 2000
Si pone ora il problema
di progettare
le 6 reti combinatorie
che realizzano
le sei funzioni binarie
Y2 Y1 Y0 e
z3 z2 z1
Si noti che le variabili di stato
presente si indicano con y
minuscola
mentre le variabilidi stato futuro
(uscite della rete G)
si indicano con la Y maiuscola
14
La rete logica sequenziale sincrona
che controlla il semaforo
uscita u
z1
z2
Rete
logica
combinatoria
s(tn+1) = S(tn)
y2
y1
y0
stato presente s
12 ottobre 2000
T
T
T
z3
u = F(s)
Y2
Y1
Y0
stato futuro S = G(s)
15
Una importante e comoda tecnica di
descrizione del comportamento di una
macchina sequenziale:
il grafo degli stati
Disegnamo a titolo di esempio
il grafo degli stati del semaforo
12 ottobre 2000
16
Il grafo degli stati del semaforo
A,V
B,V
C,V
D,G
G,R
F,R
E,R
• Ogni nodo rappresenta uno stato
• All’interno di ogni nodo sono indicati i simboli dello stato e dell’uscita
• Ogni ramo rappresenta la transizione da stato presente a stato futuro
• Dal grafo è possibile ricavare le funzioni F e G, e quindi la T. d. F.
• Le transizioni avvengono in corrispondenza degli impulsi di clock
12 ottobre 2000
17
Come cambia il d.d.s. se aggiungiamo al semaforo un ingresso binario che, quando è attivo,
fa diventare rosso il semaforo al prossimo impulso di clock? Successivamente, il semaforo
dovrà tornare verde al primo impulso di clock in cui questo ingresso non sarà attivo.
Soluzione 1
0
0
A,V
B,V
C,V
1
0
0
1
1
0
G,R
H,R
1
1
1
0
0
1
F,R
D,G
1
0
E,R
Analizzare attentamente, quindi ricavare
12 ottobre 2000la tabella di flusso e la tabella delle transizioni
18
Soluzione 2:
Con riferimento alla Soluzione 1, gli stati G e H sono indistinguibili tra loro in
quanto hanno la stessa uscita e per ogni configurazione di ingresso hanno lo
stesso stato futuro; quindi possono essere sostituiti da un solo stato (soluzione 2)
S0,V
0
1
0
0
S1,V
S2,V
0
1
1
1
S3,G
S6,R
1
0
-
S5,R
12 ottobre 2000
0
S4,R
19
Altri esempi di comportamento
istruzione
risultato
istruzione operando
CPU
operando
risultato
Il risultato
dipende anche dalle
istruzioni e dai dati
precedenti
•
•
•
•
•
t
u(t) = P(t, i(t))
Il sistema ha ingressi esterni oltre allo stato interno
Il sistema ha memoria: il risultato dipende anche da istruzioni e dati precedenti
L’attività precedente viene riassunta nello stato interno del sistema
Il tempo viene discretizzato (cioè suddiviso in intervalli Tn)
L’uscita u(Tn) dipende dallo stato interno e dagli ingressi nello stesso intervallo
Tn
Questo comportamento è analogo a quello del lucido precedente,
quindi anche la CPU è una rete logica sequenziale sincrona
12 ottobre 2000
20
Anche i processori si comportano
come specificato dal loro dds
BUS
Fase di fetch
Fase di execute
CPU
o
clock Processore
Il processore usa il periodo del clock come “unità di misura” del tempo.
La durata della fase di execute dipende dall’istruzione che la fase di
12 ottobre 2000
21
fetch ha reperito in memoria.
Generalità sulle macchine
sequenziali
Nei prossimi lucidi verranno
generalizzati gli esempi di
descrizione e struttura di R.S. visti
nei lucidi precedenti
12 ottobre 2000
22
Macchine sequenziali
•
Le macchine sequenziali sono modelli matematici che descrivono sistemi digitali in cui il
valore della grandezza presente in uscita non dipende solamente dal valore contemporaneo
dell’ingresso, ma dipende anche dai valori assunti dall’ingresso nel passato; le macchine
sequenziali descrivono dunque sistemi dotati di memoria
•
le macchine sequenziali si suddividono in:
– Macchine sequenziali sincrone
– Macchine sequenziali asincrone
•
Nelle macchine sequenziali sincrone il tempo viene suddiviso in intervalli elementari di
durata costante T e vengono considerati solamente gli istanti di tempo ti che delimitano
detti intervalli. Gli intervalli elementari possono essere contati ed è quindi possibile
misurare il tempo. Pertanto nelle macchine sequenziali sincrone il valore dell’uscita può
dipendere sia dalla sequenza dei valori in ingresso, sia dalla relativa durata
•
Nelle macchine sequenziali asincrone non viene fissata una base dei tempi di riferimento;
pertanto le macchine S.A. non sono in grado di tener conto della durata dei valori in
ingresso; il valore dell’uscita dipende dalla sequenza dei valori in ingresso, ma non può
dipendere dalla relativa durata.
12 ottobre 2000
23
Un esempio di sistema digitale con memoria che
non ha bisogno di misurare la durata degli intervalli di tempo
•
Il comportamento di una lampada da tavolo che si accende e si spegne
premendo un pulsante è riconducibile al modello delle Macchine Sequenziali
Asincrone: lo stato della lampada non dipende dalla posizione del pulsante
(premuto o rilasciato), né dalla durata degli intervalli di tempo in cui il
pulsante è stato premuto o rilasciato; dipende invece dal numero di volte in
cui il pulsante è stato premuto nel passato, dipende cioè solamente dalla
sequenza con cui è cambiato lo stato del pulsante (i. e. il valore dell’ingresso)
u(t) = P(i(t-))
0
12 ottobre 2000
• Le variazioni dell’uscita (lampadina) sono
dovute a variazioni dell’ingresso (pulsante)
• Il valore dell’uscita non dipende dalla durata
delle configurazioni di ingresso, quindi non
dipende
dal valore di t, ma dipende solo dalla sequenza
con cui è variato l’ingresso
• Nelle M.S.A. la storia passata è rappresentata
solo dalla sequenza con cui è variato l’ingresso,
e non dalla durata di ogni configurazione di
24
ingresso
Esempi di sistemi digitali con memoria
in cui è necessario (o opportuno) misurare la durata degli
intervalli di tempo
u(t) = P(t)
colore
Le variazioni
dell’uscita sono
dovute al trascorrere
del tempo
t
istruzione
operando
u(t) = P(t, i(t-))
0
istruzione operando
CPU
risultato
Dipende anche dalle
istruzioni e dai dati
precedenti
risultato
t
• La storia passata è rappresentata dal tempo trascorso, dalla sequenza con cui sono
variati gli ingressi e dalla loro durata
• Il comportamento di questi sistemi è riconducibile al modello delle Macchine Sequenziali Sincrone
• Al fine di misurare la durata degli intervalli di tempo, il tempo viene discretizzato cioè viene suddiviso
in intervallini di durata costante T (vedi diapositiva n. 7)
• T rappresenta l’unità di misura del tempo
12 ottobre 2000
25
Macchine digitali e
reti logiche
• Un modello matematico che descrive un sistema capace di
elaborare grandezze discrete si chiama anche macchina
digitale
• E’ possibile realizzare reti logiche che si comportano come
una macchina digitale assegnata passando attraverso un
procedimento di codifica binaria delle grandezze discrete
elaborate dalla macchina data
• Si viene così a definire una corrispondenza tra macchina
digitale e rete logica
12 ottobre 2000
26
La macchina digitale e la rete logica
i(t)  I
(alfabeto di ingresso)
u(t)  U
(alfabeto di uscita)
Macchina digitale
• Ingressi e uscite sono simboli appartenenti a un alfabeto assegnato
• Si può descrivere la M.D. con il diagramma degli stati e con la tabella di flusso
X[0..(n-1)]
(var. di ingresso)
Z[0..(n-1)]
(var. di uscita)
Rete logica
• Ingressi e uscite sono: vettori di variabili binarie con cui gli alfabeti di cui
sopra sono codificati
• è necessario codificare anche gli stati interni
• l’andamento delle variabili binarie z in funzione delle x e delle eventuali
variabili di stato interno è descritto dalla tabella delle transizioni
• Si ottiene la rete logica ad essa associata sintetizzando le variabili di uscita e
le variabili di stato futuro indicate dalla T.d.T.
12 ottobre 2000
27
Il modello delle M.S.S.
la discretizzazione del tempo e le funzioni F,G
i(tn)
u(t) = P(t, i(t-))
0
u(tn)
F
u(tn ) = P (i ,i(t0),i(t1), …., i(tn-1), i(tn))
s(tn+1)
u(tn ) = F(s(tn),i(tn))
s(tn+1) = G(s(tn),i(tn))
Ti : intervalli
di durata T
ti : istanti
s(tn)
stato interno: il riassunto
della “storia passata”
T0
t0
T1
t1
12 ottobre 2000
T2
t2
T3
t3
G
Tn-1
Tn
tn
Ritardo
T
Tn+1
tn+1
s(t0) = i
28
Il modello delle M.S.A.
la retroazione diretta dello stato interno (T=0)
u(t) = P(t, i(t-))
0
i(t)
u(t)
F
u(t ) = F(s(t),i(t))
S(t) = G(s(t),i(t))
S(t)
stato interno: il riassunto
della “storia passata”
s(t0) = stato iniziale
• s(t): stato interno presente
• S(t): stato interno futuro
• La variazione di i (ingresso) si ripercuote immediatamente
s(t)
sullo stato interno
• Il modello non riesce a misurare la durata delle configurazioni di ingresso
• Il modello riesce a ricordare la sequenza delle configurazioni di ingresso
12 ottobre 2000
G
Ritardo
T=0
29
Astrazione di un modello per M.S.S. e M.S.A.
Le variabili discrete sS, iI, uU e le funzioni F e G
La funzione F:
S x I U
La funzione G:
S x I S
S
I
S
I
U
12 ottobre 2000
S
30
Il modello astratto della macchina sequenziale
Sistema matematico
i
u
M = {I, U, S, F, G}
F
formato da 3 INSIEMI
I: i1, i2, …, in alfabeto di ingresso
U: u1, u2, …, um alfabeto di uscita
S: s1, s2, …, sk insieme degli stati
s*
da 2 FUNZIONI
G
F : S  I  U funzione di uscita
s
G : S  I  S funzione di aggiornamento
dello stato interno
e da una MEMORIA
che mantiene il “vecchio stato” s
memoria
fino a quando non è necessario
sostituirlo con il “nuovo stato” s*
(il prossimo istante di clock nelle reti SINCRONE)
12 ottobre 2000
31
Macchine sequenziali e
automi a stati finiti
Il comportamento complessivo di un sistema digitale
è descritto dal sistema matematico
M = {I,U,S,F,G}
formato da 3 INSIEMI
• I: alfabeto di ingresso
• U: alfabeto di uscita
• S: insieme degli stati interni
e da 2 FUNZIONI
•F: funzione di uscita
• G: funzione di aggiornamento dello stato interno
L’insieme di 5 elementi M è detto Automa a Stati Finiti
• Nelle macchine sequenziali sincrone lo stato interno viene aggiornato in tutti gli
istanti ti , e l’uscita viene aggiornata tutte le volte che cambia la configurazione di
ingresso o lo stato interno
• Nelle macchine sequenziali asincrone uscita stato interno e uscita vengono
aggiornati ad ogni cambiamento della configurazione di ingresso o dello stato
interno
12 ottobre 2000
32
Descrizione del comportamento
con tabella di flusso
insieme
degli
stati
ingresso
s1
s2
..
..
stato
presente
sj
..
..
sk
i1
i2
..
..
..
..
….
….
….
..
..
..
..
…. sp,uq ….
..
..
..
..
..
..
..
..
….
ii
..
..
….
….
….
..
..
in
alfabeto
d’ingresso
..
..
..
..
…. ….
stato futuro, uscita
12 ottobre 2000
33
Descrizione con grafo degli stati
Per ogni stato e
per ogni valore di ingresso lecito si
devono individuare
stato futuro e valore dell’uscita
S1
Sp
i 1 , um
Sj
ii, uq
in, un
Sk
12 ottobre 2000
S2
34
Classificazione dei comportamenti e quindi del
grafo degli stati delle Macchine Sequenziali
i1, u1
1: una variazione di ingresso
determina (al più) una
variazione di uscita
i2, u2
i2, u2
a
b
i1, u1
2: una variazione di ingresso
determina un numero limitato
di variazioni di uscita
3: una variazione di ingresso
determina continue
variazioni di uscita
12 ottobre 2000
a
i2, u1
a
i2, u3
i2, u2
i2, u2
b
b
i2, u3
g
i2, u3
g
35
Esempio di comportamento 1:
una lampada da tavolo
u: lampadina
U : {spenta, accesa}
rilasciato,spenta
premuto,accesa
premuto,
accesa
a
b
premuto, spenta
rilasciato,
accesa
rilasciato, accesa
rilasciato,
spenta
i: pulsante
I : {rilasciato,premuto}
12 ottobre 2000
d
premuto,
spenta
g
• Questo comportamento può essere
convenientemente realizzato con una R.S.A.
• E’ comunque possibile realizzare questo
comportamento con una R.S.S.
36
La macchina sequenziale asincrona
Per ottenere il comportamento 1 (al più una variazione dell’uscita a
fronte di una variazione dell’ingresso) è sufficiente progettare la
macchina in modo che lo stato d’arrivo non vari in corrispondenza del
nuovo ingresso:
se s j = G( s i, i) allora s j = G( s j, i)


Lo stato viene aggiornato con il ritardo della rete G
Una volta aggiornato, lo stato resta stabile e immutato
fino all’arrivo della prossima configurazione di ingresso
(infatti lo stato futuro resta uguale allo stato presente)
Macchine di questo tipo sono dette asincrone perché il loro
comportamento dipende dal verificarsi di “eventi” (le variazioni
degli ingressi) e non dal trascorrere del tempo.
12 ottobre 2000
37
Esempio di comportamento 2: una lavapiatti
stop
Immissione acqua
Riposo
Riscaldamento
start
Controllo
Timer
Scarico
acqua
Getti
Detersivo
& getti
Immissione acqua
Scarico
acqua
I cambiamenti di stato avvengono quando il timer segnala che è scaduto il tempo
previsto per la fase del ciclo associato allo stato presente.
12 ottobre 2000
38
Esempio di comportamento n. 3: il semaforo
colore
•
•
•
•
•
u(tn) = P(tn)
Le variazioni
dell’uscita (colore)
sono dovute al
t
trascorrere del tempo
Il grafo degli stati del semaforo corrisponde al comportamento 3 indicato nel lucido 32 (il
semaforo passa ciclicamente e con continuità per più stati senza che vi siano ingressi che
cambiano)
Il grafo degli stati del semaforo è stato visto a lezione
Questo comportamento può essere realizzato solamente con una rete sequenziale sincrona,
cioè con una rete che cambia stato solo in corrispondenza degli istanti ti
Se si realizzasse il grafo del semaforo secondo il modello delle R.S.A. (cioè con
retroazione diretta dello stato futuro sullo stato presente, lo stato interno e le uscite
oscillerebbero e quindi non assumerebbero mai un valore stabile e definito. Saremmo
dunque in presenza di un funzionamento erroneo
Il d.d.s. del semaforo è un esempio di grafo degli stati di un generatore di forme d’onda
periodiche. Se il periodo della forma d’onda è T = k * Tck, allora solitamente si avrà:


numero degli stati nel dds = k
(tn - tn-1) = Tck
12 ottobre 2000
39
La macchina sequenziale sincrona
Nei comportamenti 2 e 3 (definiti nel lucido 15) si hanno variazioni di uscita e
stato anche con ingresso costante. Tali variazioni quindi non possono che essere
dovute al trascorrere del tempo.
La macchina deve allora essere in grado di misurare il trascorrere del tempo.
Ciò viene ottenuto inserendo un ritardo costante, Tck, sul ramo di retroazione
della funzione G
Questo ritardo, solitamente chiamato “periodo di clock”, diventa l’unità di
misura del tempo della macchina
Macchine di questo tipo sono dette sincrone perché il loro comportamento
dipende sia dal trascorrere del tempo sia dal verificarsi di “eventi”.
Nelle macchine sincrone con ingressi sincroni la “durata” di un simbolo di uscita
è sempre un multiplo di Tck . Per ottenere una durata pari a k Tck occorrono k
transizioni di stato
12 ottobre 2000
40
Analisi e sintesi di
reti logiche sequenziali
12 ottobre 2000
41
Modello formale di ogni rete
che riceve e fornisce segnali binari
1: Schema logico (struttura)
x1(t)
x2(t)
z1(t)
z2(t)
x3(t)
Rete logica
zm(t)
xn(t)
2: Espressioni (comportamento)
12 ottobre 2000
xi(t), zj(t)  B0,1
zj(t) = Fj (t, x1(t) , x2(t), …, xn(t)) per j=1,..,m
42
IL CASO GENERALE
di rete logica sequenziale
ingresso i
x1
x2
xn
uscita u
z1
z2
Rete
logica
combinatoria
zm
u = F(i,s)
s(t+Dt) = S(t)
yk
Yk
ritardo
y2
y1
stato presente s
12 ottobre 2000
ritardo
ritardo
Y2
Y1
stato futuro S = G(i,s)
43
Dalla macchina sequenziale sincrona
alla rete sequenziale sincrona (1/2)
la discretizzazione del tempo e le funzioni F,G e il ritardo sulla retroazione
u(tn ) = P (i ,i(t0),i(t1), …., i(tn-1), i(tn))
i(tn)
u(tn)
F
u(tn ) = F(s(tn),i(tn))
s(tn+1) = G(s(tn),i(tn))
T0
t0
T1
t1
T2
t2
T3
t3
Tn-1
Tn
tn
• Ti : iesimo periodo di clock (periodo = T)
• ti : iesimo istante di clock (ti - ti-1 = T)
• In corrispondenza degli istanti di clock ti
lo stato interno si aggiorna e quindi rimane
stabile per tutto il periodo Ti fino a ti+1
12 ottobre 2000
s(tn+1)
Tn+1
G
tn+1
stato interno:
il riassunto
della
“storia
passata”
Stato futuro
s(tn)
Ritardo
T
s(t0) = i
44
Dalla macchina sequenziale sincrona
alla rete sequenziale sincrona (2/2):
Una realizzazione della rete sequenziale sincrona
i
x1
xn
y1
Rete
combinatoria
yk
• Il ritardo sulla
retroazione viene
realizzato con una
“rete logica” detta
Flip Flop D (FF-D)
• Ci vuole un FF-D
per ogni variabile di
stato
Q
Q
j
z1
zm
Y1
k
Yk
D
D
z i n = F i (x 1,.., x n , y 1 ,.., y k)n per i = 1, .. , m
y i n+1 = Y i n = G i (x 1,.., x n , y 1 ,.., y k)n per i = 1, .. , k
12 ottobre 2000
45
Il flip-flop come elemento di ritardo
D
Q
Q n+1 = D n
equazione
caratteristica
del FF “D”
Q’
clock C
(n-1) . T0
n . T0
(n+1) .T0
ingresso D
D n-1
Dn
D n+1
uscita Q
Q n-1
Qn
Q n+1
12 ottobre 2000
46
Vincolo per il corretto funzionamento di
una rete sequenziale sincrona
Fronte
di salita
del clock
t
T 0  R + RC + SU
SU: tempo max. di set up dei FF
RC: tempo max. di risposta della rete comb.
R: tempo max. di risposta dei FF
Campionamento dei Di
12 ottobre 2000
47
I problemi di sintesi e di analisi
per le reti sequenziali sincrone
SINTESI - Dato un comportamento di tipo 1, 2 o 3 (lucido 32),
individuare:
 la più “opportuna” frequenza del clock,
 il n° minimo di stati
 la “migliore” realizzazione delle reti di uscita e di
aggiornamento dello stato interno
ANALISI - Dato uno schema logico con gate e flip-flop sincroni,
individuare:
 il grafo degli stati
 una descrizione “a parole” del comportamento
12 ottobre 2000
48
Procedimento di sintesi di R.S.S.:
dalla DESCRIZIONE A PAROLE alla RETE LOGICA
Si può passare da una descrizione a parole del funzionamento di una macchina sequenziale sincrona alla
R.S.S. corrispondente eseguendo in sequenza i seguenti passi:
1 - si costruisce il diagramma degli stati
2 - si ricava la tabella di flusso
3 - si individua la tabella di flusso minima (cioè la tabella col numero minimo di stati)
4 - si codificano gli stati con variabili binarie (variabili di stato)
5 - si ricava la tabella delle transizioni
6 - si disegnano le mappe di Karnaugh o le t.d.v. delle variabili di stato e di uscita (funzioni F e G)
7 - si scrivono le espressioni di costo minimo dello stato futuro e delle uscite (sintesi di F e G)
8 - si disegna lo schema logico inserendo un FF-D sul ramo di retroazione di ogni variabile di stato
9 - si individua la massima frequenza di clock compatibile con il corretto funzionamente della rete
10 - si realizza il circuito con FF-D e operatori elementari, oppure con dispositivi programmabili
Il passo 3 e la minimizzazione nel passo 7 non sono strettamente necessari; se effettuati portano alla
sintesi minima della R.S.S. con FF-D; è sempre possibile, ma ormai in disuso, utilizzare altri tipi di flip
flop al posto dei FF-D
Sono ormai di uso comune strumenti di sintesi logica automatica che consentono di passare direttamente
dal diagramma degli stati al file di configurazione di circuiti logici programmabili (es. FPGA)
12 ottobre 2000
49
Procedimento di analisi di R.S.S.:
dalla RETE LOGICA alla DESCRIZIONE A PAROLE
•
Si può passare dallo schema logico di una R.S.S. (con ritardi sulla retroazione realizzati con FF-D)
alla descrizione a parole del suo comportamento eseguendo in sequenza i seguenti passi:
1 - si scrivono le espressioni di G ed F, cioè le espressioni delle variabili di stato stato futuro (ingressi D
dei FF) e delle uscite
2 - si esegue l’analisi delle espressioni di G e F (si disegnano cioè le mappe di Karnaugh o le t.d.v.
delle variabili di stato futuro e di uscita)
3 - si ricava la tabella delle transizioni (t.d.t)
4 - si assegna un nome simbolico ad ogni configurazione delle variabili di stato interno presente (una
configurazione, cioè uno stato per ogni riga della t.d.t.)
5 - si ricava la tabella di flusso (t.d.f.)
6 - si disegna il diagramma degli stati (d.d.s.)
7 - si descrive a parole il funzionamento della macchina sequenziale sincrona a cui corrisponde il d.d.s.
disegnato aiutandosi eventualmente con forme d’onda
• I passi 4 e 5 sono opzionali
• Sono ormai diffusi simulatori logici per Personal Computer che costruiscono l’andamento nel tempo
delle variabili di uscita di una R.S.S. in funzione di pattern di ingresso scelti dall’operatore.
• Il simulatore può essere utilizzato sia in fase di sintesi di una R.S.S. per verificarne il corretto
funzionamneto, sia in analisi per individuare il comportamento di una R.S.S. assegnata
12 ottobre 2000
50
Riepilogo sulla classificazione
delle macchine digitali
e sul loro comportamento nel tempo
Forme d’onda di riferimento
12 ottobre 2000
51
Classificazione delle macchine
Macchina
Comp.
Evento
combinatoria
1
nuovo ingresso i
asincrona
1
nuovo ingresso i
sincrona
2, 3
Uscita
Stato
u = F(i)
non occorre
lo stato
u = F(s,i)
s*=G(s,i)
aggiorn. immediato
= F(s*,i) s*=G(s*,i)
intervallo n-esimo
aggiorn. alla fine °
un = F(sn,in) s*n=G(sn,in)
sn+1= s*n
°
Un “orologio” esterno (clock) suddivide il tempo in intervalli tutti eguali, durante i
quali ingresso, uscita e stato sono per ipotesi costanti. L’aggiornamento dello stato
avviene nell’istante che delimita due intervalli consecutivi (istante di sincronismo).
12 ottobre 2000
52
La macchina combinatoria
tn
tn+1
ingresso
i
j
k
uscita
F(i)
F(j)
F(k)
ritardo p
p : intervallo di tempo impiegato per il calcolo di F
12 ottobre 2000
53
La macchina asincrona
p : intervallo di tempo impiegato per il calcolo di F e di G
tn
ingresso
j
stato presente
s
i
s*
uscita
F(j,s)
stato futuro
s = G(j,s)
12 ottobre 2000
tn+1
F(i,s)
= F(i,s*)
s* = G(i,s) = G(i,s*)
ritardo p
54
Un esempio di macchina asincrona:
la lampada da tavolo
rilasciato,spenta
premuto,accesa
premuto,
spenta
a
b
premuto, spenta
rilasciato,
accesa
rilasciato, accesa
rilasciato,
spenta
d
pulsante i  I:{rilasciato,premuto}
lampadina u U:{spenta, accesa}
Questa macchina ha
un comportamento di “tipo 1”
12 ottobre 2000
a
b
g
d
premuto,
accesa
rilasciato
a , spenta
g, accesa
g , accesa
a , spenta
g
premuto
b , spenta
b , accesa
d , accesa
d , spenta
55
La macchina sincrona
T0 : intervallo di tempo in cui la macchina non modifica il suo stato
tn
tn+1= tn + T0
ingresso
i n-1
in
i n+1
stato presente
s n-1
sn
s n+1
uscita
F(in,sn)
stato futuro
G(in,sn)
ritardo p
p : intervallo di tempo impiegato dal calcolo di F e di G 56
12 ottobre 2000
Una macchina sincrona di tipo 2:
la lavapiatti
stop
Immis.
acqua
Riposo
t1
Riscaldamento
start
t2
t7
Scarico
acqua
Controllo
start/stop
durata
fase
Timer
12 ottobre 2000
tempo
scaduto
Detersivo
& getti
t6
Getti
t3
t5
Immis.
acqua
t4
Scarico
acqua
I cambiamenti di stato avvengono quando il timer segnala che è scaduto
il tempo di attesa richiesto per la fase associata allo stato 57
presente.
Una macchina sincrona di tipo 3:
il processore
BUS
Fase di fetch
Fase di execute
CPU
o
clock Processore
La macchina usa il periodo del clock come “unità di misura” del tempo.
La durata della fase di execute dipende dall’istruzione che la fase di
12 ottobre 2000
58
fetch ha reperito in memoria.
1.3
La proprietà di
decomposizione
12 ottobre 2000
59
Decomposizione
Una macchina sequenziale M con N stati può essere decomposta in
due macchine più semplici M1 e M2, rispettivamente con N1 e N2
stati (N1 < N, N2 < N, N1  N2  N).
La proprietà di decomposizione in sottomacchine vale fino a
quando si arriva ad identificare un componente primitivo.
M
M1
i
F
u
M2
12 ottobre 2000
60
Il Controllo ed il Percorso dei dati
richiesta notifica
controllo
comandi
dato
12 ottobre 2000
stato
percorso dei dati
risultato
61
il Percorso dei dati: Elaborazione e I/O
Elaborazione
Input
Output
controllo
richiesta
dato
controllo
protocollo
di
ingresso
12 ottobre 2000
controllo
operandi
operazioni
risultati
notifica
protocollo risultato
di
uscita
62
il Controllo: Programma ed Interprete
Elaborazione
richiesta
dato
Input
memoria
istruzioni
controllo
Output
controllo
interprete
controllo
protocollo
di
ingresso
operandi
operazioni
risultati
protocollo risultato
di
uscita
12 ottobre 2000
notifica
63
Regole “elementari” di decomposizione
a) in serie
u=M2(M1(i))
M1
i
M2
u
b) in parallelo
M1
u1
M2
u2
i
c) in retroazione
i
M1
s
M2
12 ottobre 2000
u
Deve operare prima il blocco a
sinistra, poi quello a destra.
{
u1=M1(i)
u2 =M2(i)
I due blocchi operano
contemporaneamente.
u=M1(i, s)
s=M2(u)
u=M1(i, M2(u))
È necessario che l’anello completi
un calcolo prima di avviarne
uno
64
nuovo.