Automi a stati finiti
Una classe importante di sistemi dinamici è quella costituita dagli automi ed in particolare dagli
automi a stati finiti. Tali sistemi si rilevano adatti a descrivere un gran numero di problemi di varia
natura.
Def: Un automa è un sistema dinamico, discreto ed invariante in cui gli insiemi dei
valori di ingresso e di uscita sono finiti.
Un automa finito è un automa con l'insieme degli stati finito.
Si definisce AUTOMA FINITO la quintupla (X, Y, Q, f, g) dove
X è l'insieme dei possibili valori degli ingressi X={ x1, x2, …xn}
Y è l'insieme dei possibili valori delle uscite Y= { y1,y2,…ym}
Q è l'insieme degli stati Q= { q1,q2,…qk}
f è la funzione di transizione, che permette di ottenere lo stato successivo all’istante t+1 in base alla
conoscenza dello stato attuale all’istante t e del valore di ingresso: q t+1=f (q t, x t)
g è la funzione di trasformazione di uscita, che permette di determinare l'uscita attuale in base alla
conoscenza dello stato attuale e dal valore di ingresso: y t = g(q t, xt )
I tre insiemi X, Y, Q sono finiti.
Le transizioni avvengono in modo discreto e l’avanzamento del tempo è descritto con t ,t+1,t+2 …
L'automa descritto come sopra in cui la funzione g dipende sia dallo stato che dall'ingresso è detto
automa di Mealy (sistema improprio).
Si definisce automa di Moore (sistema proprio) un automa in cui la funzione di uscita dipende
solo dallo stato y t=g(q t).
MODI DI DESCRIZIONE DEGLI AUTOMI
Le proprietà degli automi sono descrivibili con:
1) Tavole di transizione e di trasformazione di uscita
2) Grafi di transizione
q0
q1
q2
stato di arrivo per stato di arrivo per
input=0
input=1
q0
q0
q0
0
1
1
Q0
Q1
Q2
Q2
0
0,1
Esempio: sia X={0,1}, Y={a,b}, Q={q0, q1, q2}
0,1
automa
a,b
la tabella di transizione unita a quella di uscita potrebbe avere la forma seguente:
X 0
1
Q
q0 q1/a q1/b
q1 q1/b q2/a
q2 q2/a q0/b
Per l'automa di Mealy questo esempio il grafo di transizione associato è il seguente:
La tavola di transizione è una tabella con tante righe e tante colonne quanti sono rispettivamente
gli elementi degli insiemi Q e X.
L'elemento della tabella che compare all'incrocio della riga j e della colonna k è da intendersi così:
a) l'automa si trova attualmente nello stato j-esimo
b) ha come attuale ingresso quello che compare scritto in cima alla colonna k-esima
c) a seguito dell'ingresso passa allo stato che leggiamo all'incrocio.
stato di partenza
Un grafo di transizione è una rappresentazione grafica
con tanti nodi quanti sono gli stati di un automa, connessi
da archi orientati che rappresentano le transizioni da uno
stato all'altro a seguito di un particolare ingresso.
Per l'automa di Mealy su ogni arco è anche indicata la
corrispondente uscita.
Per l'automa di Moore, in cui l'uscita è funzione del solo
stato interno, questa viene segnata all'interno di ogni
cerchio.
q1
q3
q0
Stessa cosa per la tabella di uscita, solo che all’incrocio tra riga e colonna si individua l’uscita
corrispondente.
Per comodità di rappresentazione è possibile in certi casi rappresentare le due tabelle con un’unica
tabella.
0/a
0/b
q0
q1
1/b
1/b
1/a
q2
0/a
Le funzioni di transizione e di trasformazione o d’uscita sono rappresentate dalla tabella o dal grafo.
Un esempio di automa di Moore è descritto dal grafo e dalla tabella seguenti con gli insiemi X,Y,Q
così definiti X={0,1}; Y={0,1}; Q={q0,q1,q2,q3}
X
0
1
0
Q
q0/0
q2/0
q0
q2/0 q3/0
q1
q3/0
1
1
0
q2
q1/0
q3
q1/1 q2/1
0
q3/1
f ‘ (<qi, yj>, xk)=< f(qi,xk), g(qi, xk) >.
Per esempio consideriamo lo stato di Moore q1R (sintesi della rappresentazione <q1,R> e l’ingresso
Mp:
f ‘ (q1R, Mp)=<f(q1,Mp), g(q1,Mp)> = < q1, R > = q1R
Con lo stesso procedimento si ottengono tutte le altre transizioni (vedi figura).
Mp
Mg
Automa di Moore
q1/0
1
q1R
q2R
Quando alcuni elementi della tavola di transizione sono vuoti ciò significa che non sono stati
previsti tutti i possibili ingressi per ogni stato; l'automa non è completamente definito.
Mg
Mp
Mg
Mp
q0B
Mg
Mg
DA MEALY A MOORE
Diciamo che un automa di Moore simula un automa di Mealy se ne rispetta il comportamento
ingresso-uscita. Data quindi una sequenza di ingresso possibile si ottiene la stessa sequenza di
uscita.
In un automa di Moore l’uscita dipende solo dallo stato. Per determinare gli stati di un automa di
Moore a partire da quello di Mealy si considerano innanzi tutto le combinazioni fatte tra gli stati e le
uscite di quest’ultimo. Si ottiene l’insieme di stati Q’ = QxY , prodotto cartesiano dell’insieme Q
per l’insieme Y.
Questo porta in generale ad una individuazione di un numero di stati ridondante in quanto alcune
delle combinazioni stato-uscita ottenute non si verificano mai.
Minimizzazione di automi.
Consideriamo il seguente automa di Mealy caratterizzato da tre stati Q=(q0,q1,q2), due valori di
ingresso X=(Mp,Mg), e tre valori di uscita Y=(B,R,A). In pratica un distributore di biglietti che
fornisce il biglietto B introducendo in sequenza, senza ordine di inserimento, due monete una
piccola Mp ed una grande Mg .
Gli altri due valori di uscita sono A, ancora monete ed R, restituzione della moneta doppia inserita.
L’essenza di un sistema a stati finiti non è tanto la forma della sua rappresentazione o il numero degli stati, ma altresì il
fatto che ad una certa sequenza di ingresso corrisponde una data sequenza di uscita. Può, così, accadere che un sistema a
stati finiti, pur avendo le stesse corrispondenze tra ingressi e uscite, possa avere più rappresentazioni caratterizzate da
un diverso numero di elementi dell’insieme di stato.
Data una rappresentazione (U, X, f, x0, F) di un sistema a stati finiti, quindi, può essere utile in pratica determinare una
rappresentazione dello stesso sistema caratterizzata da un numero di elementi di stato inferiore o addirittura minima.
Mp
q1A
Mp
q2A
A tale proposito, è importante dare la seguente definizione.
Mp/R
Mp/A
q1
Mp/B
q0
Mg/B
Definizione (Equivalenza tra stati)
q2
Mg/R
Mg/A
Si ottengono le seguenti combinazioni degli stati con le uscite, dove sono indicate tra parentesi
quelle inesistenti.
(q1 B) q0 B (q2 B)
q1 R (q0 R) q2 R
q1 A (q0 A) q2 A
Quando l’automa entra nello stato q1 l’uscita può essere o il valore A o il valore R; pertanto q1 B
viene eliminato ecc.
Determinati gli stati si devono descrivere le transizioni (funzione f ). A tale scopo sia qi uno stato
dell’automa di Mealy e yi una uscita; allora la coppia <qi, yj> è uno stato di Moore.
Applicando un ingresso xk si vuole determinare f ‘ (<qi, yj >, xk). Considerando le funzioni f e g
del corrispondente automa di Mealy attraverso il grafo o le tabelle di transizione e di uscita si ha:
Sia S un sistema a stati finiti rappresentato dalla quintupla (U, X, f, x0, F). Due stati x, y ⊂ X si
dicono equivalenti rispetto ad F se a partire da essi il sistema, soggetto alla stessa sequenza di
ingresso, esibisce la stessa sequenza di uscita in F, ovvero
f ( x, u ) = w ⇔ f ( y , u ) = w ,
u ∈U
Grazie alla equivalenza dei loro comportamenti ingresso-uscita, due o più stati equivalenti possono essere rimpiazzati
da un unico stato aggregato. E’ possibile, dunque, ridurre il numero di stati del sistema considerato sostituendo a due o
più stati equivalenti i corrispondenti stati aggregati. Pertanto, si può stabilire che:
Una rappresentazione (U, X, f, x0, F) di un sistema a stati finiti S ha il minor numero di stati rispetto a tutte le altre
rappresentazioni di S se non contiene stati equivalenti. Quando questo accade la rappresentazione si dice minima.
Esempio 5.2.1 Si consideri il riconoscitore di stringa rappresentato dal diagramma in Fig. 5.2, che riceve in ingresso
una sequenza di simboli appartenenti all’insieme {1,2,3} e deve riconoscere la stringa 123. Si può facilmente vedere
dal grafo che gli stati x2 e x3 sono equivalenti in quanto a partire da essi il sistema soggetto allo stesso simbolo di
ingresso si porta nello stesso stato finale, f(x2 , s) = f(x3, s), s= 1, 2, o 3.
Quindi riassumendo
DEF Sia dato un automa di Moore M (Q,Σ,∆
Σ,∆,δ,λ
Due stati p e q si dicono distinguibili in una
Σ,∆ δ,λ,q0).
δ,λ
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.
Se tutte le possibili coppie p q in M sono distinguibili, allora M non può essere minimizzato, ma se viceversa M
contiene collezioni di stati non distinguibili, allora possiamo eliminare le ridondanze prelevando un solo stato per ogni
gruppo di stati non distinguibili, ed eliminando gli altri.
1
2
1
x1
3
x12
x123
Raggiungibilità e controllabilità
1
3
3
Un altro importante aspetto dei sistemi dinamici ed in particolare di quelli a stato finito sono le
cosiddette proprietà di raggiungibilità e controllabilità. In particolare, è importante ai fini
dell’automazione stabilire se è possibile, attraverso una opportuna sequenza di ingresso,
raggiungere i vari stati di un sistema a partire da un dato stato iniziale.
Questo problema è noto come raggiungibilità. La possibilità, invece, di controllare i vari stati di un
sistema, mediante opportuni ingressi, ad uno stato finale desiderato è detto controllabilità.
Fig. 5.2 Grafo di transizione del riconoscitore di stringhe
Entrambi questi problemi sono fortemente legati alle altre proprietà di un sistema dinamico, come la rappresentazione in
forma minima e meritano di essere trattate in dettaglio, almeno nel caso dei sistemi a stato finito. Quanto riportato in
seguito, può comunque essere generalizzato attraverso opportuni sviluppi matematici anche al caso dei sistemi a stato
vettore.
2
2
2
x3
x2
3
3
2
1
Pertanto è possibile sostituire agli stati equivalenti x2 e x3 un unico stato aggregato x23 senza cambiare la
corrispondenza tra sequenze di ingresso e sequenze di uscita del sistema. Si ottiene, così, la seguente rappresentazione
alternativa, che non avendo altri stati equivalenti è anche una rappresentazione minima del riconoscitore considerato.
1
2
3
x12
x123
1
3
Raggiungibilità. Uno stato y si dice raggiungibile in k > 0 passi, a partire dallo stato x, se esiste una sequenza di
ingresso u[0,k] tale che:
ϕ ( x, k , u[0, k ] ) = y ;
1
x1
Definizioni
(*)
ovvero se esiste una sequenza di ingresso che porta il sistema dallo stato x allo stato y attraverso k rami del grafo di
transizione.
2
Controllabilità. In modo simile, si dice che lo stato x è controllabile in k passi allo stato y se esiste una sequenza di
ingresso u[0,k] tale che (*) è verificata.
3
3
x23
2
Fig. 5.3 Rappresentazione equivalente del riconoscitore di stringhe
L’insieme degli stati raggiungibili in k passi a partire da un dato stato y viene indicato con XR (k,y).
Uno stato x si dice raggiungibile dallo stato y se esiste un k ≥ 0 tale che x ∈ XR (k,y); l’insieme di tali stati si indica
semplicemente con XR(y).
Un sistema (U, X, f, x0, F) si dice (completamente) raggiungibile se XR(y) = X, per ogni
y∈ X .
Esempio 5.3.1. Si consideri il sistema a stati finiti definito dal grafo di transizione di Fig. 5.5 dove sono stati omessi per
semplicità gli ingressi che producono le varie transizioni.
Il circuito sequenziale basilare é il Flip Flop, un circuito in grado di memorizzare un bit di
informazione. Il Flip Flop prende anche il nome di bistabile, poiché può trovarsi in due stati stabili:
lo stato in cui ha memorizzato un 1 e quello in cui ha memorizzato uno 0.
x3
x4
x2
Circuiti di memorizzazione elementari: i Flip Flop
Il primo tipo di FF che analizziamo é il FF di tipo Set Reset.
S
Q
R
Q
x1
Fig. 5.5
Si ha:
0,0 0,1
XR (0,x1) = x1, ovvero che l’insieme di stati raggiungibili da x1 in 0 passi è costituito da x1 solamente;
1,0 0,0
XR (1,x1) = x1, x4 ovvero che l’insieme di stati raggiungibili da x1 in 1 passo è costituito da x1 ed x4;
1,0
XR (2,x1) = x3, x1.
Q=1
Q=0
0,1
Pertanto, l’insieme degli stati raggiungibili da x1, ovvero XR(x1), è
costituito da tutti gli stati del sistema.
Set(t)
1
0
1
0
0
L’insieme degli stati controllabili allo stato y viene indicato con XC(k,y). Uno stato x si dice controllabile allo stato y se
esiste un k ≥ 0 tale che x ∈ X C ( k , y ) ; l’insieme degli stati controllabili allo stato y si indica con XC (y).
Reset(t)
U scita Q(t)
Q(t-1) (imm utata)
1
1
0
0
1
0
non amm essa
Un ulteriore tipo di FF é il Toggle
Un sistema (U, X, f, x0, F) si dice (completamente) controllabile se XC(y) = X, per ogni
T(t)
Esempio 5.3.2. Si consideri il sistema a stati finiti definito dal grafo di transizione di Fig. 5.2.1.
Investigando la controllabilità del sistema considerato, è immediato osservare che il sistema è completamente
controllabile ad x1. Infatti, si ha:
T
XC (1,x1) = x4 ;
Q(t)
0
Q(t-1)
1
Q(t-1) (toggle)
XC (2, x1) = x1, x3 ;
1
e così via.
0
E’ facile notare che vale il seguente principio di dualità. Se uno stato xi è raggiungibile (in k
passi) dallo stato xj , allora xj è controllabile (in k passi) allo stato xi .
Q1
Q=1
Q0
Q=0
1
0
Fig. 3.5 Schema di funzionamento del FlipFlop di tipo T
Come si vede, il Toggle commuta a fronte di un ingresso uguale ad 1, mentre resta nello stato di partenza a fronte di un
input basso.
Si noti che i FF di tipo D e T possono essere ottenuti da FF di tipo JK, come mostrato in figura.
4
J
D
possibili
combinazioni corrispondenti
valori corrispondenti
degli input e degli stati in delle
funzioni
di delle uscite in t
eccitazione dei FF in t
t
(nel caso di FF JK)
Qn-1...Q0 Im...I0
Jn-1 Kn-1......J0 K0
Yk..Y0
=
K
=
K
Fig. 3.6 Schema di equivalenza tra Flip-Flop di tipo D, T e J-K
Analisi di circuiti sequenziali
dato lo schema circuitale di circuito sequenziale, descriverne il funzionamento.
Il funzionamento di un circuito sequenziale va descritto in termini di un automa a stati finiti.
Dato lo schema circuitale, dapprima dobbiamo identificare gli elementi di memoria che vi sono inclusi. In ogni istante,
la memoria del sistema, ovvero il valore binario memorizzato nei FF, indica lo stato in cui il sistema si trova. Per ogni
possibile stato e possibile combinazione degli input, da un esame della parte combinatoria del circuito possiamo
determinare i valori delle uscite e il successivo stato in cui il sistema transiterà.
Di seguito descriveremo la procedura generale, riferendoci per semplicità ad un esempio concreto, mostrato in figura.
X0
Do
X1
valori stati futuri, ovvero nuovi
valori
che
saranno
memorizzati in t+1
Qn-1...Q0
La prima colonna contiene tante righe quante sono le possibili combinazioni degli ingressi (m) e dei FF (n), ovvero
2m+n . La seconda colonna va riempita, per ogni ingresso di ogni FF (JK, D, SR, o T) tenendo conto delle EB ricavate
al passo 3. La terza colonna va anch'essa riempita usando le EB ricavate al passo 3. La quarta colonna deve contenere i
valori delle transizioni che ciascun FFi effettuerà, sul successivo fronte di clock, in base al valore Qi precedentemente
memorizzato ed ai valori dei propri input JiKi. La colonna va riempita, singolarmente per ogni Qi(t+1), in base ai
corrispondenti valori degli input JiKi (t) (o Di, Ti, ecc) e Qi(t), letti sulla riga corrispondente. Ad esempio, se sulla riga
j-esima della tabella si legge, per il FFk, Jk=0 Kk=0 (colonna 2) e Qk=1 (colonna 1), il futuro valore di Qk sarà 0 e
pertanto si inserisce uno 0 nell'elemento k-esimo della riga j-esima della quarta colonna.
J
T
Si traccia una tabella degli stati futuri, così composta:
Y
CK
D1
Per quanto riguarda l'esempio di figura 3.6.1, la tabella sarebbe in teoria piuttosto laboriosa da scrivere, perché ci sono 3
input e 2 FF, per un totale di 5 variabili booleane nella prima colonna, che darebbero luogo a 32 combinazioni. Tuttavia
possiamo osservare che D0 e D1 non dipendono da Q0 e Q1, e che la colonna degli stati futuri può essere riempita solo
in base ai valori di D0 e D1 (in un FF di tipo D le uscite Qi "seguono" gli ingressi applicati). Quindi possiamo
descrivere la tabella in termini modulari.
Il modulo essenziale della tabella é il seguente:
X2X1X0(t)
000
001
010
011
100
101
110
111
D1D0(t)
00
00
00
01
00
00
10
11
Q1Q0(t+1)
00
00
00
01
00
00
10
11
Indichiamo ora con le lettere A, B e C rispettivamente la prima, seconda e terza colonna della tabella sopra. La tabella
completa sarà la seguente:
Figura 3.9 Esempio di circuito sequenziale
Q1Q0X2X1X0 (t)
00 A
01 A
10 A
11 A
3.6.1 Procedura di analisi di circuiti sequenziali
Ogni cella della tabella sopra si intende composta di 8 righe. Ad esempio, la cella 00A equivale alla sequenza di celle:
1
00000
00001
00010
00011
00100
00101
00110
00111
X2
CK
2
3
Si esaminano gli elementi di memoria del circuito, ovvero i FF. I possibili stati del circuito sono rappresentati dalle
possibili combinazioni di valori memorizzabili nei FF, e disponibili sulle uscite Qi. Per n FF, avremo 2n
combinazioni, e 2n stati.
Si assegna un simbolo di stato ad ogni combinazione di memoria. Per l'esempio di figura 3.6.1, abbiamo 2 FF, e 4
possibili valori memorizzati su Q1 e Q0: 00,01,10,11. Possiamo ad esempio assegnare la seguente codifica:
S0→00, S1→ 01, S2 →10, S3 →11
Si analizza la parte combinatoria del circuito e si ricavano le espressioni booleane per ciascun ingresso di ciascun
FF contenuto nel circuito, dette anche funzioni di eccitazione dei FF, nonché le EB delle uscite.
Per l'esempio di figura 3.6.1 avremo le seguenti EB:
D0 = X0X1
D1 = X1X2
Y = Q0Q1
5
D1D0(t)
B
B
B
B
Y(t)
0
1
1
1
Q1Q0 (t+1)
C
C
C
C
A partire dalle colonne 1, 3 e 4 della tabella degli stati futuri, si ricava l'automa, o la sua rappresentazione tabellare :
000
S0/0
S0/0
S0/0
S0/0
S0
S1
S2
S3
6
001
S0/0
S0/0
S0/0
S0/0
010
S0/0
S0/0
S0/0
S0/0
011
S1/1
S1/1
S1/1
S1/1
100
S0/0
S0/0
S0/0
S0/0
101
S0/0
S0/0
S0/0
S0/0
110
S2/1
S2/1
S2/1
S2/1
111
S3/1
S3/1
S3/1
S3/1
Si procede (se applicabile) alla minimizzazione dell'automa
Gli stati possono essere suddivisi in due insiemi, {S0} con uscita =0, e {S1,S2,S3} con uscita =1. La tabella
triangolare é:
S1
S2
S3
X
X
X
S0
S1
S2
Tutti gli stati nell'insieme {S1,S2,S3} sono indistinguibili, perché, come emerge dalla tabella delle transizioni, a
fronte degli stessi input transitano negli stessi stati.
7
Si disegna quindi l'automa minimizzato del circuito.
000,001..
011,110,111
011,110,111
S'0
Y=0
S'1
Y=1
000,001,
...
Fig. 3.10 Automa minimizzato
Circuiti sequenziali notevoli
I seguenti tipi di circuiti sequenziali notevoli verranno analizzati a lezione e esercitazione.
Applicazioni:
Riconoscimento di una sequenza di ingresso (vedere sul sito del corso i moltissimi esercizi di esame di questo tipo)
Memorizzazione e trasferimento di dati (vedere esercizi di esame)
Contatori (vedere Fummi et al. paragrafo 5.4)
Contatori Asincroni
Contatori con numeri di MOD>2N
Contatore Asincroni alla rovescia
Contatori Sincroni
Contatori paralleli alla rovescia e bidirezionali UP-DOWN
© Copyright 2024 ExpyDoc
