Analisi e Sintesi di circuiti
sequenziali
Definizione
Uscite combinatorie
Porte logiche
combinatorie
Uscite di memoria
Elementi
di memoria
• Una macchina sequenziale é un
sistema nel quale, detto
• I(t) l'insieme degli ingressi in t,
O(t) l'insieme delle uscite in t, e
M(t) una funzione di
• I(t-1),
I(t-2)...(i=1,..n)
detta
memoria, si ha:
• oi(t)=F(I(t),M(t)) , oiO
Ingress i esterni
Automi a stati finiti
0
1
1
Q0
Q1
0
0,1
Q2
Q2
Un automa a stati finiti é una
quintupla (Q,S,d,q0, F) dove:
•Q e' un insieme finito di stati,
•e' un alfabeto finito di simboli,
•q0 e' lo stato iniziale, F  Q e' il set
di stati finali, e
• e' la funzione di transizione
QxS --> Q
(QxS e' il prodotto cartesiano, ovvero
l'insieme delle coppie q,a ); d(q,a)
rappresenta uno stato raggiunto
dall'automa, per ogni ogni stato di
partenza q e simbolo di ingresso a.
Esempio: distributore di bibite
•
•
•
•
•
•
•
Ogni bibita costa 30c
Accetta monete da 20 e da 10
Non dà resto
Cosa deve memorizzare il circuito in ogni “stato”?
L’ammontare ricevuto
Quanti stati diversi della memoria?
0c, 10c, 20c,≥30c  4 stati
Automa:
•
•
•
•
4 stati, S0, S1, S2, S3
Alfabeto di Input: 0c, 10c, 20c
Alfabeto di output: 0 bibite, 1 bibita
Stato iniziale: S0
Stato 0:
M=0
Input=10c
Stato 0:
M=0
Input=20c
Stato 1:
M=10
Stato 2:
M=20
20c
Input=10c
Stato 0:
M=0
Input=20c
Stato 1:
M=10
10c
Stato 3:
M≥30
Stato 2:
M=20
10c o 20c
20c
Input=10c
Stato 0:
M=0
Input=20c
Stato 1:
M=10
10c
Stato 3:
M≥30
Stato 2:
M=20
10c o 20c
Output=bibita
Input=0
20c
Input=10c
Stato 0:
M=0
Input=20c
Stato 1:
M=10
10c
Stato 3:
M≥30
Stato 2:
M=20
10c o 20c
Input=0
Output=bibita
Funzione di transizione
Input=0
Input=10c
Stato 0:
M=0
20c
Stato 1:
M=10
10c
Stato 3:
M≥30
Stato 2:
M=20
Input=20c
Input=0
Output=bibita
10c o 20c
d: QxIQ
d(S0,0)=S0
d(S0,10)=S1
d(S0,20)=S2
d(S1,0)=S1
d(S1,10)=S2
d(S1,20)=S3
d(S2,0)=S2
d(S2,10)=S3
d(S2,20)=S3
d(S3,0)=S0
Rappresentazione tabellare
• Alternativamente,
un
automa
si
può
rappresentare mediante una tabella delle
Latransizioni,
tabella è esattamente
o stati futuri: la funzione d(QxI)
•
Stato 0
Input=10
Stato 1
Input=20
Stato 2
Input=0
Stato 0
Stato 1
Stato 2
Stato 3
Stato 1
Stato 2
Stato 3
Stato 3
Stato 2
Stato 3
-
-
Stato 0
Macchine di Moore
• DEF Una macchina di Moore é una sestupla (Q,S,D,d,l,q0) dove D é un
alfabeto di output, e l é una funzione di transizione l : Q  D, che associa
un simbolo di output ad ogni stato. Per ogni stato, l(qi)=aj, ajD.
• Un automa deterministico a stati finiti può essere visto come un caso speciale
di macchina di Moore dove D=(0,1) e l(qi)=1 se qiF.
• Notare che nelle macchine con output non occorre una distinzione fra stati di
accettazione e non.
q2,b
d
c
q0,a
c
d
d
c
q1,a
S  c,d 
D  a,b
Macchine di Mealy
• DEF Una macchina di Mealy é una sestupla
(Q,S,D,d,l,q0) , dove l é un mapping da
• QxS->D, ovvero l(qi,bk)=aj, bkS, ajD.
d,a
c,a
d,a
q0
c,b
q2
d,b
c,a
q1
Equivalenza fra macchine di
Moore e Mealy
• Teorema. Se M1= (Q,S,D,d,l,q0) é una macchina di Moore,
allora esiste una macchina di Mealy equivalente M2.
• Dimostrazione. sia M2=(Q,S,D,d,l',q0) e definiamo:
l'(q,a)=l(d(q,a))
• Allora, M2 è equivalente a M1 e segue le stesse transizioni,
emettendo ad ogni transizione l'output associato allo stato di
arrivo in M1.
Equivalenza Mealy Moore
• Teorema. Se M1= (Q,S,D,d,l,q0) é una macchina di Mealy, allora esiste una
macchina di Moore equivalente M2.
• Dimostrazione. sia M2=(QxD,S,D,d',l',(q0 b0)), dove b0 é un qualsiasi
carattere di D. Gli stati M2 sono coppie rappresentate da stati di M1 e simboli
di D. Definiamo
d'((q, b),a) = (d(q,a), l(q,a)) e l'((q,b))=b
• I due automi sono equivalenti, infatti le transizioni di M2 da uno stato all'altro
sono determinate solo dal primo elemento della coppia che identifica lo stato,
e dal valore dell'input. Ovvero, da uno stato (q, b), quando si riceve il simbolo
a, si transita in uno stato (q', c) il cui primo elemento rappresenta lo stato in
cui transita M1 quando da q riceve a ed il cui secondo elemento rappresenta
l'output che , nella macchina di Mealy, avrebbe assunto l'output transitando in
quello stato dallo stato q a fronte di un certo input a.
Minimizzazione degli ASF
• Poiché, come vedremo, un automa é un modello
astratto di una macchina sequenziale, é intuitivo
il fatto che sia conveniente minimizzare un
automa, ovvero trovare un automa equivalente
che abbia il minimo numero di stati. Ridurre il
numero di stati infatti equivale a ridurre il
numero di componenti di memoria nel circuito
corrispondente.
Distinguibilità
• Sia dato un automa di Moore M (Q,S,D,d,l,q0).
Due stati p e q si dicono distinguibili in una
macchina di Moore se gli output associati a p e
q sono diversi, o se per qualche sequenza di
simboli a1a2..an ricevuti a partire da p e q, si
transita in due stati p' e q' caratterizzati da
output diversi.
Esempio 1
• Gli stati q0 e q1 sono indistinguibili
d,a
d,a
q0
c,a q2
c,b
d,b
c,a
q1
Esempio 2
• (q3,q4) (q0,q2)
d,a
q2
d,a
q0
d,b
c,b
d,b
q3
c,a
q1
c,b
d,b
c,a
q4
c,a
Passo 1; tabella triangolare
• Si traccia, a partire dall'automa o dalla sua tabella degli
stati futuri, una tabella triangolare che permetta, ai suoi
incroci, di indicare il risultato del confronto di ogni
possibile coppia di stati.
q1
q2
q3
q4
q0
q1
q2
q3
Passo 2: marcatura delle celle
• Si esaminano una dopo l'altra tutte le possibili coppie di righe della
tabella degli stati futuri, inserendo nel corrispondente incrocio della
tabella triangolare:
– una X se in almeno una colonna risultano specificate uscite
diverse
– la denominazione della coppia di stati futuri individuati colonna
per colonna se in tutte le colonne le uscite risultano uguali.
– non si scrive nulla nel caso in cui le indicazioni di stato futuro
siano identiche o coincidano con la denominazione della coppia
di stati presa in esame
d,a
q2
d,a
q0
d,b
c,b
d,b
q3
c,a
q1
c,b
d,b
c,a
c,a
q4
q1
q2
q3
q4
x
3,4
x
x
x
x
x
x
x

q1
q2
q3
q0
Osservazioni
Le caselle con X individuano stati distinguibili
sulla base di un solo simbolo di ingresso, oppure
del simbolo di uscita.
Le caselle con indicazione di una o pi coppie di
stati futuri indicano stati indistinguibili per
sequenze di ingresso di lunghezza 1. Per questi
stati, la decisione deve essere rimandata.
Le caselle vuote (o col pallino) viceversa
individuano stati indistinguibili per sequenze di
ingresso di lunghezza qualsiasi.
Passo 3 : marcatura progressiva delle
celle “sospese”
• Ogni qual volta si marca una casella (qi,qj) con una X o con un
, si verifica se qualcuna delle caselle precedentemente
esaminate contiene la coppia (qi,qj) , e eventualmente, si
aggiorna la marcatura di quella casella
q1
q2
q3
q4
x
x
3,4
x
x
x
x
x
x
x

q1
q2
q3
q0

x
x
x
x
x
x
x

Passo 4: classi di indistinguibilità
• Procedendo da destra verso sinistra si esaminano una dopo l'altra le colonne
della tabella triangolare contenente caselle con il pallino e si costruisce un
corrispondente sottoinsieme S con la denominazione della colonna stessa e
delle righe relative
• Si controllano via via i sottoinsiemi che risultano contenuti in sottoinsiemi
individuati. Questi sottoinsiemi prendono il nome di classi di
indistinguibilità. Es: S1: q0,q2 e S2: q3, q4
• Si costruisce la tabella degli stati futuri minima (o il grafo) copiando solo le
righe della tabella di partenza che corrispondono al primo stato di ciascuna
classe di indistinguibilità, e correggendo di conseguenza le indicazioni dello
stato futuro.
Esempio
d,a
q2
d,a
q0
d,b
c,b
d,b
q3
c,a
q1
c,b
d,b
d,a
c,a
q4
c,a
c,a
q’0
d,b
c,b
d,b
q’3
q1
c,a
Esempio: Semplificare e costruire l’automa
di Moore corrispondente
0/0
0/1
1/1
s0
s1
1/0
0/0
1/1
s2
Tabella triangolare
S1
S0,S2
x
x
S2
S0
S1
S1
Automa di Mealy Minimizzato
0/1
0/0
1/1
S0=S2
S1
1/0
Mealy-to-Moore
Stati dell’automa di Moore: (S0,0) (S0,1) (S1,0) (S1,1)
Funzione di output:
lmoore((Si,ok))= lmealy( ok) , okD)
lmoore(S0,0)=0 lmoore(S0,1)=1
lmoore(S1,0)=0 lmoore(S1,1)=1
Funzione di transizione:
dmoore((S0,0),0)=(S0,0) dmoore((S0,0),1)=(S1,1)
dmoore((S0,1),0)=(S0,0) dmoore((S0,1),1)=(S1,1)
dmoore((S1,0),0)=(S1,1) dmoore((S1,0),1)=(S1,1)
dmoore((S1,1),0)=(S0,0) dmoore((S1,1),1)=(S1,1)
dmoore((Si,ok),ij)=(dmealy(Si,ij),lmealy(Si,ij))
okD e ijS
indistinguibili
Automa di Moore equivalente
0
0
1
S0,0
S1,1
1