Minimizzazione degli Stati in una macchina a stati finiti

Reti Logiche
Sintesi di reti sequenziali sincrone
Procedimento:
Minimizzazione
degli Stati in una
macchina a stati finiti
Specifiche
Diagramma degli stati
Tabella degli stati
Minimizzazione degli stati
Codifica degli stati
Tabella delle transizioni
Scelta elementi di memoria
Tabella delle eccitazioni
Sintesi delle reti combinatorie (next state - output)
Macchina a Stati Finiti
Macchina a Stati Finiti
M: <S,I,O,δ,λ ,s0>
S: insieme degli stati
A
B
C
0
B/0
A/1
B/0
1
C/1
C/0
A/0
0
B
A
B
A
B
C
1
C
C
C
Out
0
1
1
I: alfabeto di ingresso
insieme di tutti i possibili simboli di ingresso
O: alfabeto di uscita
A
1/0
δ: SxI → S
λ: funzione di uscita
λ: SxI → O (macchina di Mealy)
s0: stato iniziale
0/1
1/1
δ: funzione di stato prossimo
λ: S → O
0/0
(macchina di Moore)
1
A/0
0
B
0
1
1/0
C
C/1
0/0
0
1
Mealy
Moore
B/1
Motivazione
Obiettivo
Elementi di memoria necessari per memorizzare
lo stato:
N ≥ log2|S|
Individuazione di una
macchina minima equivalente
Possono esistere stati ridondanti
Eliminazione degli stati non raggiungibili (dallo stato iniziale)
Eliminazione ridondanza
Identificazione
Diminuzione del numero di elementi di memoria
Stati equivalenti (per le macchine completamente specificate)
Reti combinatorie più semplici
Stati compatibili (per le macchine non completamente
specificate)
Definizioni
Stato Irragiungibile
Dati:
Non esiste alcuna sequenza di transizione che
porti dallo stato iniziale (I) allo stato considerato
(Q)
I : sequenza di ingresso {i1, i2, i3, ..., iN}
U : sequenza di uscita associata a I
si , sj due stati generici
Gli stati si e sj sono indistinguibili (si ~ sj) se:
I
Q
Lo stato Q
è irragiungibile
I
Q
U = L(si,I) = U' = L(sj,I) ∀ I
cioè se per qualunque sequenza di ingresso le uscite generate partendo da si e da
A
C
B
A
C
B
sj sono le stesse
Proprietà:
Riflessiva: si ~ si
Simmetrica:si ~ sj ⇔ sj ~ si
Transitiva: si ~ sj ∧ si ~ sk ⇒ si ~ sk
Partizione degli stati
Eliminazione di stati
~ è una relazione di equivalenza
Due stati indistinguibili sono equivalenti e
possono essere sostituiti da un singolo stato
induce una partizione sull'insieme S
P = {p0 , p1 , ... , pr}
S1 ~ S2
S1
due stati si e sj appartengono allo stesso blocco pk se e solo se si ~ sj
S2
una macchina a stati finiti è minima se non ha stati
distinti equivalenti
M: <S,I,O,δ,λ ,s0> ⇒ M': <P,I,O,δ',λ' ,p0>
S4 ~ S5
S5 ~ S6
S3
S6
S5
S4
S6
S2
S1'
S3
S3
S4'
S4”
P: partizione indotta su S dalla relazione ~
Regola di Paull-Unger
Regola di Paull-Unger
Definizione di indistinguibilità
Si devono considerare tutte le sequenze di ingresso
Difficile applicabilità
Regola di Paull-Unger
Due stati si e sj sono indistinguibili se e solo se:
λ(si , i) = λ(sj , i) ∀ i ∈ I (le uscite sono uguali per tutti i simboli di ingresso)
δ(si , i) ~ δ(sj , i) ∀ i ∈ I (gli stati successivi sono indistinguibili per tutti i simboli di
ingresso)
La regola è ricorsiva
Dopo aver esaminato tutte le coppie di stati, per ogni si e sj
si ~ sj
perché esiste almeno un ingresso per cui le uscite sono diverse
perché esiste un ingresso che porta a stati successivi distinguibili
oppure
si ~ sj perché per ogni ingresso dipendono da:
coppie di cui è stata provata la indistinguibilità
la coppia in esame (si , sj)
oppure
Dipendono da un'altra coppia di stati di cui non si è ancora provata la distinguibilità
Iterare finché tutte le coppie di stati non sono risolte
Esempio
S0
S1
S2
S3
S4
0
S3/0
S4/0
S0/1
S1/1
S0/1
1
S1/1
S1/1
S2/1
S2/0
S2/0
Regola di Paull-Unger
Le relazioni di indistinguibilità si identificano con la Tabella delle
Implicazioni
S0 e S1 hanno la stessa uscita
se gli stati successivi sono indistinguibili, S0~S1
Mette in relazione ogni coppia di stati
S3 e S4 hanno la stessa uscita
se gli stati successivi sono indistinguibili, S3~S4
È triangolare e manca della diagonale principale (simmetria e riflessività)
Ogni elemento della tabella contiene:
L'indistinguibilità tra S0 e S1 dipende da quella tra S3 e S4 (e viceversa).
Possiamo concludere che:
S0~S1 e S3~S4
macchina equivalente
S01'
S2'
S34'
[ (S0,S1)
S01'
;
S2
S2'
;
(S3,S4)
Il simbolo di equivalenza (~) o di non equivalenza (X)
oppure
La coppia di stati a cui si rimanda la verifica se non è ancora possibile decidere
S34' ]
0
1
S34'/0 S01'/1
S01'/1 S2'/1
S01'/1 S2'/0
S1
S2
S3
S0
Se è marcata come equivalente: non è richiesta altra verifica
Se si rimanda a un'altra coppia Sp , Sq
se Sp , Sq sono equivalenti, Si , Sj sono equivalenti
se Sp , Sq sono non equivalenti, Si , Sj sono non equivalenti
se Sp , Sq dipendono da un'altra coppia, ripetere il procedimento iterativamente
L'analisi termina quando ulteriori eliminazioni non sono possibili
Le coppie rimanenti sono equivalenti
~
X
S1
X
S2
Regola di Paull-Unger - esempio
Regola di Paull-Unger
Per ogni coppia di stati Si , Sj
X
X
S1 , S2
a
b
c
d
e
f
g
0
g/0
c/0
e/1
b/0
g/0
d/1
a/1
1
e/1
a/1
g/0
e/1
a/1
f/0
g/0
b
c
d
e
f
g
cg ae
X
X
bg bc ae
X
bg ae
~
cg
X
X
X
de fg
X
X
X
X
ae
a
b
c
d
X
X
e
Analisi delle coppie di stati:
a-b: c-g è indistinguibile se lo è a-e → a~b
a-d: b-g è distinguibile → a~d
b-d: b-c è distinguibile → b~d
b-e: c-g è indistinguibile se lo è a-e → b~e
e-d: b-g è distinguibile → e~d
c-f: d-e è indistinguibile se lo è b-g → f~c
c-g: a-e è indistinguibile → g~c
f-g: a-d è indistinguibile se lo è b-g → g~f
ad
f
Regola di Paull-Unger - esempio
a
b
c
d
e
f
g
0
g/0
c/0
e/1
b/0
g/0
d/1
a/1
1
e/1
a/1
g/0
e/1
a/1
f/0
g/0
b
c
d
e
f
g
~
X
X
~
X
X
a
X
X
~
X
X
b
X
X
X
~
c
X
X
X
d
X
X
e
X
f
Regola di Paull-Unger - esempio
a
b
c
d
e
f
g
0
g/0
c/0
e/1
b/0
g/0
d/1
a/1
1
e/1
a/1
g/0
e/1
a/1
f/0
g/0
b
c
d
e
f
g
~
X
X
~
X
X
a
X
X
~
X
X
b
X
X
X
~
c
X
X
X
d
X
X
e
Analisi delle coppie di stati:
Stati equivalenti:
a-b: c-g è indistinguibile se lo è a-e → a~b
a-d: b-g è distinguibile → a~d
b-d: b-c è distinguibile → b~d
b-e: c-g è indistinguibile se lo è a-e → b~e
e-d: b-g è distinguibile → e~d
c-f: d-e è indistinguibile se lo è b-g → f~c
c-g: a-e è indistinguibile → g~c
f-g: a-d è indistinguibile se lo è b-g → g~f
S0: {a,b,e}
S1: {c,g}
S2: {d}
S3: {f}
Regola di Paull-Unger – esempio 2
a
b
c
d
e
f
g
0
g/00
g/00
d/10
c/10
g/00
f/10
a/01
1
c/01
d/01
a/11
b/11
f/01
e/11
f/11
b
c
d
e
f
g
cd
X
X
cf
X
X
a
X
X
df
X
X
b
ab
X
ae df
X
c
X
be cf
X
d
Nuova tabella degli stati:
S0
S1
S2
S3
0
S1/0
S0/1
S0/0
S2/1
1
S0/1
S1/0
S0/1
S3/0
Regola di Paull-Unger
Per una FSM completamente specificata,
l'agoritmo di Paull-Unger
X
X
e
X
f
Determina in maniera esatta la FSM minima
equivalente
La partizione in classi di stati equivalenti è unica
b
c
d
e
f
g
~
X
X
~
X
X
a
X
X
~
X
X
b
~
X
~
X
c
X
~
X
d
X
X
e
X
f
X
f
Macchine non completamente specificate
Macchine non completamente specificate
La compatibilità è una relazione meno forte di quella di
indistinguibilità:
Per alcune configurazioni di ingressi e stato
corrente non sono specificate le uscite e/o lo stato
futuro
Non vale la proprietà transitiva
esempio
S0
S1
S2
Definizione
si e sj sono compatibili (si ≈ sj) se
0
S2/1
S2/x
S2/0
1
S0/x
S0/1
S0/x
S0 ≈ S1 S1 ≈ S2 S0 ≈ S2
Regola di Paull-Unger estesa:
assunti come stati iniziali danno luogo a sequenze di uscita
identiche, a meno di condizioni di indifferenza, per ogni
possibile sequenza di ingresso
gli stati si e sj sono compatibili se e solo se:
λ(si , i) = λ(sj , i) ∀ i ∈ I ovunque sono entrambi specificati
δ(si , i) ≈ δ(sj , i) ∀ i ∈ I ovunque sono entrambi specificati
La definizione è ricorsiva
Regola di Paull-Unger estesa
Regola di Paull-Unger estesa
Anche le relazioni di compatibilità si identificano con la Tabella
delle Implicazioni
Ogni elemento della tabella contiene:
a
b
c
d
e
0
e/0
d/0
e/x
a/1
a/x
1
a/0
b/0
c/x
a/1
b/x
b
c
d
e
de
≈
X
ab
de
X
ad
ae ac
ae bc
ab
a
b
c
d
X se in almeno una colonna vi sono uscite diverse (stati incompatibili)
Si Sj se le uscite sono tutte uguali ma i nomi degli stati futuri (Si , Sj) sono diversi e
non coincidono con quelli della coppia di stati in esame
Si devono verificare i vincoli che discendono
dall'imposizione delle uscite non specificate
≈ altrimenti (stati compatibili)
esempio:
b≈e se si scelgono entrambe le uscite nello stato e pari a 0,
in questo caso però d≈e
e viceversa
Regola di Paull-Unger estesa
a
b
c
d
e
0
e/0
d/0
e/x
a/1
a/x
1
a/0
b/0
c/x
a/1
b/x
b
c
d
e
non può essere eliminato anche
se a≈c perché nello stato c
l'uscita non è specificata
(quindi non è detto che sia a~c)
de
≈
X
ab
de
X
ad
ae ac
ae bc
ab
a
b
c
d
Regola di Paull-Unger estesa
a
b
c
d
e
0
e/0
d/0
e/x
a/1
a/x
1
a/0
b/0
c/x
a/1
b/x
b
c
d
e
de
≈
X
ab
de
X
ad
ae ac
ae bc
ab
a
b
c
d
Vincoli:
a≈b: se d≈e
a≈e: se a≈b
b≈c: se d≈e
b≈e: se a≈d → b≈e
c≈d: se a≈e , a≈c
c≈e: se a≈e , b≈c
d≈e: se a≈b
Grafo di compatibilità
Regola di Paull-Unger estesa
a
b
c
d
e
0
e/0
d/0
e/x
a/1
a/x
1
a/0
b/0
c/x
a/1
b/x
b
c
d
e
de
≈
X
ab
de
X
X
ae ac
ae bc
ab
a
b
c
d
I nodi corrispondono agli stati
I nodi ni e nj sono collegati se gli stati corrispondenti sono compatibili
I nodi ni e nj sono collegati se la loro compatibilità dipende dalla compatibilità
del loro stato successivo
Vincoli:
a≈b: se d≈e
a≈e: se a≈b
b≈c: se d≈e
b≈e: se a≈d → b≈e
c≈d: se a≈e , a≈c
c≈e: se a≈e , b≈c
d≈e: se a≈b
Su ogni arco sono riportati i vincoli sulla compatibilità degli stati successivi
b
c
d
e
de
≈
X
ab
a
a
ab
de
X
ad
b
de
e
ae ac
ae bc
c
ab
d
b
ae
bc
ab
d
ae
ac
de
c
Grafo di compatibilità
Grafo di compatibilità
I nodi corrispondono agli stati
Classe di compatibilità
Insieme di stati a coppie compatibili
I nodi ni e nj sono collegati se gli stati corrispondenti sono compatibili
È un poligono completo sul grafo di compatibilità
I nodi ni e nj sono collegati se la loro compatibilità dipende dalla compatibilità
Le classi di compatibilità non sono necessariamente disgiunte
del loro stato successivo
Su ogni arco sono riportati i vincoli sulla compatibilità degli stati successivi
Esempi di classi di compatibilità:
a
ab
la compatibilità tra due stati (nodi)
sussiste solo se tutti i vincoli
vengono accettati e utilizzati
de
e
b
ae
bc
ab
d
de
c
ae
ac
a
ab
a,b,c
a,c,e
c,d,e
a,b
c,e
...
de
e
b
ae
bc
ab
d
de
c
ae
ac
Grafo di compatibilità
Grafo di compatibilità
Insieme chiuso di classi di compatibilità
Classe di massima compatibilità
Insieme di classi di compatibilità i cui vincoli sono contenuti in almeno una classe
dell'insieme
Classe di compatibilità non contenuta in nessuna altra classe
Sul grafo è un poligono completo non contenuto in nessun altro poligono
Garantito che tutti i vincoli siano rispettati
a
de
e
Esempi di classi di massima compatibilità:
a,b,c
a,c,e
c,d,e
a
ab
de
e
b
ae
bc
ab
d
ae
ac
de
c
ae
ab
bc
d ae
ac
b
de
c
c
NO: il vincolo ae non è contenuto
in nessuna classe di compatibilità
e
ab
a
a
de
e
b
ae
bc
ab
d ae
ac
ae
bc
c
de
c
OK
c
Grafo di compatibilità
Minimizzazione Stati
Copertura della Tabella degli Stati
Trovare il più piccolo insieme chiuso di classi di compatibilità che copre
l'insieme di stati su cui la macchina è definita
Insieme di classi di compatibilità per cui ogni stato della Tabella degli Stati è
contenuto in almeno una classe di compatibilità
L'insieme di tutte le classi di massima compatibilità è chiuso e copre l'insieme
degli stati della macchina
a
ab
Esempi:
de
e
{{a,b,c} , {a,c,e} , {c,d,e}}
{{a,b} , {b,c} , {a,c,e} , {c,d,e}}
Se si associa uno stato ad ogni classe di massima compatibilità si ottiene una
nuova macchina con un numero di stati
b
ae
bc
ab
d
de
Possibilmente minore di quello di partenza
c
ae
ac
Non necessariamente minimo
Algoritmo
Esempio copertura
a
ab
de
e
b
ae
bc
ab
d
ae
ac
de
b
ae
bc
d ae
ac
c
a
e
ab
de
a
ab
e
ae
bc
c
de
c
c
Copertura ammissibile:
A={a,b,c} B={a,c,e} C={c,d,e}
Non minima
Condivisione di stati tra diverse classi
1. Inizializzare una lista L vuota
2. Finchè il grafo non è vuoto:
a. Individuare e ordinare le classi di massima compatibilità presenti sul grafo per
dimensione
b. Individuare la classe di compatibilità massima di dimensione massima presente sul
grafo
c. Inserire nella lista L tutti i vincoli presenti nella classe di compatibilità considerata
d. Eliminare dalla lista L e dal grafo i vincoli soddisfatti dalla classe considerata
Classi di massima compatibilità non disgiunte
non è possibile realizzare la macchina minima associando un nuovo stato a una classe
il num. di classi di max compatibilità è un limite superiore al numero di stati della macchina
minima
Libertà di assegnamento per le condizioni non specificate
la macchina minima non è unica
Algoritmi euristici
e. Eliminare dal grafo tutti i nodi (ed i relativi archi) appartenenti alla classe di
compatibilità considerata che non appartengono a nessun vincolo presente nella
lista L e/o nel grafo
3. Le classi così individuate formano una partizione di compatibilità (insieme di
classi di compatibilità chiuso)
Algoritmo - Esempio
a
ab
de
e
b
ae
bc
ab
d
de
a
de
b
ae
bc
ab
d
c
ae
ac
a
ab
e
ae
ac
a
de
e
e
b
ae
de
c
Algoritmo - Esempio
e
grafo
de
d
d
c
L = {de}
d
L = {de}
classi di massima compatibilità: abc ace cde
classe selezionata: abc
vincoli nella classe selezionata: de
Copertura individuata: {abc , de}
Algoritmo – Esempio 2
Algoritmo - Esempio
a
b
c
d
e
0
e/0
d/0
e/x
a/1
a/x
1
a/0
b/0
c/x
a/1
b/x
S0
S1
0
S1/0
S0/1
1
S0/0
S0/1
a
b
c
d
e
f
00
b/0
b/0
f/1
f/x
-/x
-/x
01
c/x
-/x
a/0
e/1
e/1
b/0
10
-/x
e/1
b/x
-/x
e/1
b/0
11
d/0
d/0
e/1
a/0
d/0
-/x
b
c
d
e
f
≈
X
bf ce
ce
bc
X
bf ad
≈
X
X
X
ab
ad
X
X
a
b
c
d
e
b e f sono incompatibili ⇒ a e d sono incompatibili
b e f sono incompatibili ⇒ b e d sono incompatibili
Copertura individuata: {abc , de}
S1 = {de}
S0 = {abc}
b e c sono incompatibili ⇒ a e f sono incompatibili
c e e sono incompatibili ⇒ a e e sono incompatibili
a e e sono incompatibili ⇒ d e e sono incompatibili
Algoritmo – Esempio 2
a
b
c
d
e
f
00
b/0
b/0
f/1
f/x
-/x
-/x
01
c/x
-/x
a/0
e/1
e/1
b/0
10
-/x
e/1
b/x
-/x
e/1
b/0
11
d/0
d/0
e/1
a/0
d/0
-/x
b
c
d
e
f
Algoritmo – Esempio 2
≈
X
X
X
X
X
X
≈
X
X
X
ab
X
X
X
a
b
c
d
e
a
b
c
d
e
f
00
b/0
b/0
f/1
f/x
-/x
-/x
01
c/x
-/x
a/0
e/1
e/1
b/0
10
-/x
e/1
b/x
-/x
e/1
b/0
11
d/0
d/0
e/1
a/0
d/0
-/x
b
c
d
e
f
≈
X
X
X
X
X
X
≈
X
X
X
ab
X
X
X
a
b
c
d
e
10
S1/1
S1/1
S0/0
-/x
11
S3/0
S3/0
S1/1
S0/0
b e f sono incompatibili ⇒ a e d sono incompatibili
b e f sono incompatibili ⇒ b e d sono incompatibili
a
b e c sono incompatibili ⇒ a e f sono incompatibili
f
c e e sono incompatibili ⇒ a e e sono incompatibili
e
c
a e e sono incompatibili ⇒ d e e sono incompatibili
d
Algoritmo – Esempio 2
Algoritmo – Esempio 2
a
b
c
d
e
f
00
b/0
b/0
f/1
f/x
-/x
-/x
01
c/x
-/x
a/0
e/1
e/1
b/0
10
-/x
e/1
b/x
-/x
e/1
b/0
11
d/0
d/0
e/1
a/0
d/0
-/x
Copertura individuata: {ab , be , cf , d}
S0 = {ab}
S1 = {be}
S2 = {cf}
S3 = {d}
S0
S1
S2
S3
00
S0/0
S1/0
S2/1
S2/x
01
S2/x
S1/1
S0/0
S1/1
b
ab
10
S1/1
S1/1
S0/0
-/x
11
S3/0
S3/0
S1/1
S0/0
Le classi non sono disgiunte: lo stato b
appartiene sia a S0 che a S1
Al momento della realizzazione della
macchina minima si deve stabilire la
corrispondenza ogni volta che b compare
come “prossimo stato”
a
b
c
d
e
f
00
b/0
b/0
f/1
f/x
-/x
-/x
01
c/x
-/x
a/0
e/1
e/1
b/0
10
-/x
e/1
b/x
-/x
e/1
b/0
11
d/0
d/0
e/1
a/0
d/0
-/x
Copertura individuata: {ab , be , cf , d}
S0 = {ab}
S1 = {be}
S2 = {cf}
S3 = {d}
S0
S1
S2
S3
00
S0/0
S1/0
S2/1
S2/x
01
S2/x
S1/1
S0/0
S1/1
Codifica degli stati
Numero di codifiche possibili:
(2S ) S!
Codifica degli stati
Codifica di lunghezza minima
Sintesi a due livelli delle funzioni δ e λ
N
Flip-flop di tipo D
per 3 stati, codificati con 2 bit, si hanno 24 possibili codifiche
per 4 stati, codificati con 2 bit, si hanno 24 possibili codifiche
per 5 stati, codificati con 3 bit, si hanno 6720 possibili codifiche
per 6 stati, codificati con 3 bit, si hanno 20160 possibili codifiche
per 7 stati, codificati con 3 bit, si hanno 40320 possibili codifiche
per 8 stati, codificati con 3 bit, si hanno 40320 possibili codifiche
per 9 stati, codificati con 4 bit, si hanno 4151347200 possibili codifiche
Analisi esaustiva non praticabile
metodi euristici
Codifica degli stati
Rules of thumb
Stati si e sj che a parità di ingressi hanno gli stessi stati prossimi:
codifiche adiacenti
semplificazione di δ
Stati si e sj che a parità di ingressi hanno le stesse uscite:
codifiche adiacenti
semplificazione di λ
Stati sj e sk tali che sj = δ(si , ia) e sk = δ(si , ib) con Hamming(ia , ib)=1
codifiche adiacenti
semplificazione di δ
Obiettivo: minimizzare la logica combinatoria