Sintesi Sequenziale Sincrona
Macchine Non Completamente Specificate
Mariagiovanna Sami
20072007-08
Macchine non completamente specificate
‰
‰
Sono macchine in cui per alcune configurazioni degli
ingressi e dello stato presente non sono specificati gli
stati prossimi e/o le configurazioni d'uscita.
La prima fase della sintesi (creazione del diagramma
degli stati) non differisce in modo sostanziale da quella
per macchine completamente specificate, salvo il fatto
che per uno o più stati presenti:
Per uno o più simboli d’ingresso possono non esistere archi in
uscita (se Nsi è il numero dei simboli di uscita, il numero degli
archi in uscita da ogni stato è ≤ Nsi)
¾ Per una macchina di Mealy: a uno o più archi può non essere
associato un simbolo di uscita
¾ Per una macchina di Moore: a uno o più stati può non essere
associato un simbolo di uscita
¾
-2-
20072007-08
Macchine non completamente specificate
Si consideri la seguente specifica:
‰ Una macchina di Mealy ha un ingresso X e un’uscita z; la
macchina è dotata di stato iniziale;
‰ Sull’ingresso arrivano con continuità sequenze di quattro
bit che codificano cifre decimali, ognuna trasmessa a
partire dal bit più significativo;
‰ In corrispondenza dei primi tre bit della cifra, l’uscita
vale 0; all’arriva della quarta cifra, l’uscita passa al
valore 1 se e solo se il valore è compreso fra 3 e 8.
-3-
20072007-08
Macchine non completamente specificate
‰
‰
A partire dallo stato di reset,
sia il simbolo 0 sia il simbolo 1
sono ammissibili – si tratta,
ricordiamo, del bit più
significativo.
I due stati in cui ci si porta sono
diversi (occorre mantenere
memoria del valore
rappresentato!); si introducono
quindi gli stati S1 ed S2.
S0
0/0
S1
-4-
1/0
S2
20072007-08
Macchine non completamente specificate
‰
Per il secondo bit di ingresso a partire da S2 è ammissibile
solo il valore 0: le configurazioni “11--” non
corrispondono infatti a cifre decimali,
indipendentemente dai bit meno significativi. Si estende
di conseguenza il diagramma
S0
0/0
Per comodità, entro
ogni stato si indica il
frammento di codifica
che si è raggiunta
(ordinato col bit più
significativo a sinistra)
S1
0
0/0
1/0
1/0
S2
1
0/0
S3
00
S4
01
S5
10
-5-
20072007-08
Macchine non completamente specificate
‰
Per il terzo bit di ingresso a
partire da S5 è ammissibile solo
il valore 0: le configurazioni
“101-” non corrispondono
infatti a cifre decimali,
indipendentemente dal bit
meno significativo. Si estende
di conseguenza il diagramma
S0
0/0
1/0
S1
0
0/0
S2
1/0
1
0/0
S3
S4
00
0/0
S5
01
1/0
0/0
10
1/0
0/0
S6
000
-6-
S7
001
S8
S9
010
011
S10
100
20072007-08
Macchine non completamente specificate
‰
‰
Infine, dagli ultimi cinque stati introdotti sono possibili
ambedue le transizioni – sia ingresso 0 sia ingresso 1
portano a codifiche decimali corrette – e ci si riporta in
S0, associando l’uscita 1 alle transizioni che completano
le codifiche da 0011 a 1000
Si completa di conseguenza il diagramma degli stati, e se
ne estrae la tabella degli stati.
-7-
20072007-08
Macchine non completamente specificate
S0
0/0
1/0
S1
0
0/0
S2
1/0
1
0/0
S3
S4
00
1/0
S6
S7
000
0/0
S0
0000
S0
S0
0010
10
0/0
1/0
S0
0011
S0
0100
S10
011
010
1/1 0/1
0/0
S9
S8
001
1/0 0/0
0001
S5
01
0/0
1/1
100
1/1
0/1
S0
0101
-8-
S0
0110
1/0
0/1
S0
0111
S0
1000
S0
1001
20072007-08
Macchine non completamente specificate
x
‰
‰
Si vede che per i due stati S2
ed S5, in corrispondenza
dell’ingresso 0, sia lo stato
prossimo sia l’uscita sono non
specificati.
Si pone il problema della
riduzione del numero degli
stati.
0
1
So
S1/0
S2/0
S1
S3/0
S4/0
S2
S5/0
-/-
S3
S6/0
S7/0
S4
S8/0
S9/0
S5
S10/0
-/-
S6
S0/0
S0/0
S7
S0/0
S0/1
S8
S0/1
S0/1
S9
S0/1
S0/1
S10
S0/1
S0/0
st
-9-
St+1,z
20072007-08
Macchine non completamente specificate
‰
‰
‰
Il metodo di riduzione è simile a quello per macchine
completamente specificate ma si basa sulla proprietà di
compatibilità tra stati, invece che su quella di
indistinguibilità.
La riduzione del numero degli stati in macchine non
completamente specificata è ricondotta alla
individuazione di una macchina minima che copra (sia
compatibile con) quella data;
Occorre introdurre innanzitutto alcuni concetti
fondamentali.
- 10 -
20072007-08
Macchine non completamente specificate:
sequenza di ingresso applicabile e stati compatibili
Data una macchina non completamente specificata:
‰
‰
una sequenza di ingresso I = i1, i2, …, ik si dice applicabile a partire
da uno stato si se e solo se la funzione stato prossimo δ è
specificata per ogni simbolo d'ingresso della sequenza, tranne al
più l'ultimo
Due stati si e sj di una macchina M si dicono compatibili se
–
–
–
‰
partendo da si e da sj
applicando ogni possibile sequenza di ingresso Iα
applicabile da ambedue gli stati si ottengono sequenze d'uscita
identiche ovunque siano ambedue specificate
La compatibilità tra si e sj si indica con: si ∨ sj
- 11 -
20072007-08
Macchine non completamente specificate:
compatibilità
‰
‰
‰
La compatibilità è una relazione meno forte di quella di
indistinguibilità
Non vale la proprietà transitiva cioè se si∨ sj e sj∨ sk può
non essere si∨ sk. Quindi la compatibilità non è una
relazione di equivalenza
Nel seguente esempio, è si∨ sj e sj∨ sk ma !si∨ sk. :
si - sequenza di uscita:
0
0
-
1
-
-
1
. . .
sj - sequenza di uscita:
0
0
1
-
-
1
1
. . .
sk - sequenza di uscita:
0
0
-
0
-
1
1
. . .
valori d'uscita diversi
- 12 -
20072007-08
Riduzione del numero degli stati:
stati compatibili
‰
‰
Il metodo di Paull - Unger è stata estesa per trattare il caso
delle macchine non completamente specificate
Due stati sono compatibili se e solo se per ogni simbolo di
ingresso iα valgono le seguenti relazioni:
1. λ ( si, iα ) = λ (sj, iα ) ove i valori di uscita siano ambedue
specificati; se uno o entrambi non sono specificati
l'uguaglianza si ritiene soddisfatta
2. δ ( si, iα ) ∨ δ ( sj, iα ) ove gli stati prossimi siano ambedue
specificati; se uno o entrambi non sono specificati la
compatibilità si ritiene soddisfatta
- 13 -
20072007-08
Riduzione del numero degli stati:
compatibilità e metodo di Paull-Unger
‰
Poiché gli insiemi S e I hanno cardinalità finita, l’analisi di
tutte le coppie di stati può portare ad una delle tre
condizioni
1. si ∨ sj
–
–
Se i simboli d'uscita sono diversi e/o
Se gli stati prossimi sono già stati verificati come non compatibili
2. si ∨ sj
–
–
Se i simboli d'uscita sono uguali e
Se gli stati prossimi sono ordinatamente identici o se la circolarità del
vincolo si risolve sui due stati stessi (si ∨ sjÖ si ∨ sj)
3. Si genera un insieme di coppie di stati che devono essere
compatibili affinché la coppia in oggetto sia compatibile
(compatibilità condizionate)
- 14 -
20072007-08
Riduzione del numero degli stati:
tabella delle implicazioni
‰
‰
Le relazioni di compatibilità si identificano con la Tabella delle
Implicazioni che viene costruita come nel caso della indistinguibilità
L’analisi della tabella consente di propagare le incompatibilità, ma
non di risolvere i vincoli di compatibilità condizionata. Quindi al
termine dell’analisi, ogni elemento contiene:
–
–
–
‰
‰
Il simbolo di non compatibilità, se gli stati corrispondenti non sono compatibili
Il simbolo di compatibilità, se gli stati corrispondenti sono compatibili
Le coppie di stati che devono essere compatibili affinché la coppia in oggetto
sia compatibile (vincoli)
Poiché la relazione di compatibilità non è transitiva, non si può
concludere che tutte le compatibilità sono soddisfatte. I vincoli
vanno mantenuti per la costruzione delle classi di compatibilità
Le classi di compatibilità si costruiscono esaminando il grafo delle
compatibilità, che riporta le compatibilità condizionate e quelle
incondizionate
- 15 -
20072007-08
Riduzione del numero degli stati: Esempio
Tabella degli stati
Tabella delle implicazioni
b
a
b
c
d
e
0
e/0
d/0
e/a/1
a/-
1
a/0
b/0
c/a/1
b/-
Grafo delle compatibilità
de
a
c
∨
d
x
x
e
ab
ad
a
b
d,e
a,b
de
ae
ac
ae
bc
c
- 16 -
b
e
a,e
b,c
d,e
a,b
ab
d
a,e
a,c
c
d
20072007-08
Riduzione del numero degli stati:
classi di compatibilità
‰
Classe di compatibilità:
–
–
–
‰
Insieme di stati tutti fra di loro a due a due compatibili
Sul grafo di compatibilità una classe di compatibilità è
rappresentata da un sottografo completo (ogni nodo del
sottografo è collegato da un arco a ogni altro nodo dello stesso
sottografo)
le classi di compatibilità non generano una partizione tra gli
stati (non sono disgiunte): uno stato può appartenere a più di
una classe!
Classe massima di compatibilità:
–
–
Classe di compatibilità non contenuta in nessun’altra classe
Una classe massima di compatibilità è individuata sul grafo da
un sottografo completo non interamente contenuto in nessun
altro sottografo completo più grande
- 17 -
20072007-08
Riduzione del numero degli stati:
classi di compatibilità - esempio
a
d,e
a,b
b
e
a,e
b,c
d,e
a,b
d
‰
c
Classi di compatibilità:
–
‰
a,e
a,c
ab, ac, ae, bc, ce, cd, de, abc, aec, dec
Classi massime di compatibilità:
–
abc, aec, dec
- 18 -
20072007-08
Riduzione del numero degli stati:
Insieme chiuso di classi di compatibilità
‰
Insieme chiuso di classi di compatibilità:
Per ogni classe dell’insieme deve valere la seguente relazione:
per ogni simbolo di ingresso l’insieme degli stati futuri relativi agli stati
della classe è contenuto in una stessa classe dell’insieme (cioè tutti i
vincoli sono rispettati: può eventualmente essere contenuto in più
classi diverse)
–
–
Insieme (abc), (ed): chiuso
‰
‰
da (abc) con 0 vado in (ed), con 1 in (abc): OK
da (ed) con 0 vado in (a), con 1 in (ab): OK
Insieme (ab), (ced): NON chiuso
‰
‰
a
d,e
a,b
a,e
b,c
d
a,e
a,c
b
e
d,e
a,b
d,e
a,b
b
e
da (ab) con 0 vado in (ed), con 1 in (ab): OK
da (ced) con 0 vado in (e) e (a): KO, con 1 in
(c) e (ab): KO
a
a,e
b,c
d,e
a,b
c
d
- 19 -
a,e
a,c
c
20072007-08
Riduzione del numero degli stati:
copertura della macchina
‰
‰
Data una macchina M e il suo insieme di classi di compatibilità, si
dice che la macchina M’ il cui insieme degli stati è costituito da un
insieme chiuso delle classi di compatibilità di M (che include tutti gli
stati di M) copre M
Per costruzione, il comportamento di M’ è compatibile con quello di
M e cioè,
–
–
‰
Partendo da un qualsiasi stato di M, ne esiste uno in M’ tale che
Per ogni sequenza di ingresso applicabile a entrambi, le sequenze di
uscita sono identiche ogni volta che l’uscita di M è specificata
Il problema della minimizzazione del numero di stati di una
macchina non completamente specificata equivale quindi a trovare il
più piccolo insieme chiuso di classi di compatibilità che coprono tutti
gli stati della macchina
- 20 -
20072007-08
Riduzione del numero degli stati:
copertura e minimizzazione
‰
‰
‰
‰
L'insieme di tutte le classi massima di compatibilità è chiuso e copre
l’insieme S degli stati
Associando un nuovo stato ad una classe massima di compatibilità si
ottiene una nuova macchina con un numero di stati possibilmente
minore di quello della macchina di partenza, ma non
necessariamente minimo
Il numero di classi di massima compatibilità è il limite superiore al
numero degli stati della macchina minima; si può identificare a volte
una macchina di costo minore non utilizzando classi massime
In genere, la macchina minima non è unica. Gli algoritmi esaustivi
per identificare la macchina minima partono tutti dall’insieme delle
classi massime di compatibilità
- 21 -
20072007-08
Riduzione del numero degli stati:
ricerca delle classi massime di compatibilità
‰
‰
‰
La definizione delle classi massime di compatibilità può
avvenire individuando direttamente sul grafo tutti i più
grandi sottografi completi
Esistono diversi algoritmi specifici per l’individuazione di
tutte le classi massime di compatibilità che utilizzano la
tabella delle implicazioni considerando tutte e sole le
incompatibilità;
Qui si considera solo una soluzione “intuitiva” (a occhio)
- 22 -
20072007-08
Classi massime di compatibilità
a a
a
d,e
a,b
d,e
a,b
b
e
e
a,e
b,c
d,e
a,b
d
•
a,e
a,c
b
e
a,e; b,c
a,e; b,c
a,b
c
d,e
d
a,e;a,c
c c
c
Classi massime di compatibilità:
• {a,b,c}
• {a,c,e}
• {c,d,e}
•
Una copertura ammissibile è data dall’insieme delle classi massime di
compatibilità: tale copertura non è necessariamente minima
- 23 -
20072007-08
Riduzione del numero degli stati: ricerca di
una copertura minimale
‰
‰
‰
La mancanza di disgiunzione tra le classi di massima
compatibilità non consente di definire metodi esatti per
la minimizzazione.
Nel caso ora visto, l’uso di classi massime porta a una
macchina con tre stati; le tre classi non sono disgiunte,
quindi si pone il problema volta per volta
dell’attribuzione a una o all’altra classe degli stati
condivisi.
Si considerino ora le classi {a,b,c} massima) e {d,e} (non
massima): utilizzandole si soddisfano tutti i vincoli e si
ottiene una macchina di costo minore
- 24 -
20072007-08
Riduzione del numero degli stati: costruzione
della tabella degli stati della macchina ridotta
‰
Una volta identificata la copertura tramite le classi di compatibilità, la
costruzione della tabella degli stati della macchina ridotta avviene nel modo
seguente
–
Gli stati della macchina ridotta sono le classi di compatibilità
–
Per ogni classe di compatibilità, se per almeno uno degli stati della classe di
compatibilità lo stato prossimo è specificato, allora la classe di compatibilità
che lo contiene sarà lo stato prossimo della macchina ridotta. Poichè
l’insieme delle classi che costituiscono la copertura può essere non disgiunto,
uno stato della macchina originaria può essere presente in più classi di
copertura. Nella costruzione della tabella degli stati della macchina ridotta è
arbitrario scegliere la classe cui appartiene.
–
Se, per almeno uno degli stati originari che costituiscono lo stato prossimo
della macchina ridotta, l’uscita è specificata, allora questa uscita sarà
l’uscita associata allo stato prossimo nella macchina ridotta. In ogni altro
caso si mantengono le condizioni non specificate
- 25 -
20072007-08
Tabella degli stati della macchina ridotta
Esempio
‰
Sulla base di:
–
–
‰
Tabella degli stati della macchina iniziale
Insieme chiuso delle classi di compatibilità
Si determina la nuova tabella degli stati corrispondente
alla macchina ridotta
Tabella degli stati
a
b
c
d
e
0
e/0
d/0
e/a/1
a/-
1
a/0
b/0
c/a/1
b/-
Tabella degli stati ridotta
s0 = {a,b,c}
s1 = {d,e}
- 26 -
s0
0
s1/0
1
s0/0
s1
s0/1
s0/1
20072007-08