Ormai siamo un pò Off Topic rispetto al titolo, ma va bene
Consideriamo proprio il primo esempio sull'algoritmo del partizionamento nella slide Reti Logiche 6: Macchine sequenziali, riporto anche l'immagine in questo _link_.
http://oi60.tinypic.com/oupav6.jpgPer prima cosa, per ogni ingresso bisogna confrontare gli stati rispetto alle uscite, questa prima analisi corrisponde alla prima tabella.
Si parte da considerare che F sia "presumibilmente" pari proprio all'insieme degli stati Q e poi lo si suddivide man mano quando si rilevano le incompatibilità. Ciò equivale a dire che all'inizio si considera proprio l'insieme (1,2,3,4,5,6).
Nell'esempio si parte dal considerare le incompatibilità per l'ingresso sia i1 (ovviamente negli esercizi d'esame ci ritroveremo sempre ad avere a che fare solo valori binari, cioè con 0 e 1 come ingressi e uscite, ma il concetto è lo stesso.)
Se l'ingresso è 1, si vede dalla tabella degli stati che 1,3,5,7 danno come uscita u1, mentre 2,4,6 danno come uscita u2. Come appunto è riportato nell'esempio, se i=i1 -> u1:[1,3,5,7] , u2:[2,4,6].
Ciò vuol dire che bisogna effettuare la partizione dell'insieme (1,2,3,4,5,6) nei due insiemi (1,3,5,7) e (2,4,6). Da ora in poi questi due insiemi andranno trattati e controllati separatamente.
Nella seconda riga si controlla cosa accade sull'insieme (1,3,5,7) se l'ingresso è i2. In tal caso, tutti gli stati in esame presentano la stessa uscita u2, infatti si scrive u2:[1,3,5,7], quindi non ci sono incompatibilità e in questo caso non si deve intervenire.
Nella terza riga si controlla cosa accade all'insieme (2,4,6) quando l'ingresso è i2. In questo caso, gli stati 2 e 4 danno come uscita u1, mentre 6 dà come uscita u2, cioè si scrive u1:[2,4] , u2:[6]. Di conseguenza, si partiziona l'insieme (2,4,6) negli insiemi (2,4) e (6).
In questo semplice esempio non ci sono altri elementi da esaminare per quanto riguarda l'analisi delle uscite. Finora abbiamo ricavato gli insiemi (1,3,5,7),(2,4),(6).
Si passa ora all'analisi degli stati seguenti (cioè alla seconda tabella).
Anche in questo caso si fa la valutazione al variare degli ingressi.
Ricordiamo la definizione ricorsiva degli stati equivalenti: "Due stati sono fra loro equivalenti se, per qualunque ingresso, forniscono le stesse uscite e producono stati a loro volta equivalenti".
Nell'esempio parte valutando cosa accade all'insieme (1,3,5,7) quando l'ingresso è i1 e quindi indica con una freccia gli stati seguenti per ogni stato di tale insieme per l'ingresso i1.
Dobbiamo cioè controllare la tabella degli stati: se lo stato 1 riceve in ingresso i1, passa allo stato 2; se lo stato 3 riceve in ingresso i1, passa allo stato 1; se lo stato 5 riceve in ingresso i1, passa allo stato 4; se lo stato 7 riceve in ingresso i1, passa allo stato 5.
Ovvero, se i=i1 :[1,3,5,7] --> (2,1,4,5).
Individuati gli stati seguenti, si controlla se essi sono compatibili rispetto agli insiemi ricavati prima. Notiamo che 2 e 1 non sono compatibili, infatti sono contenuti in insiemi separati [cioè (1,3,5,7) e (2,4) ]; di conseguenza, per la definizione di stati equivalenti, gli stati 1 e 3, da cui derivano, non possono essere equivalenti. Lo stesso discorso vale per 4 e 5, quindi neanche 5 e 7 sono equivalenti. Gli stati 2 e 4, invece, sono fra loro compatibili [ perchè avevamo trovato l'insieme (2,4)] quindi 1 e 5 sono compatibili ; stesso discorso vale per 1 e 5, quindi i corrispondenti 3 e 7 sono compatibili.
In pratica, come scritto nella tabella, si ricava che:[2,4] (1,5) --> (1,5), (3,7). Cioè, il fatto che si debbano partizionare gli stati seguenti (2,1,4,5) in (2,4) (1,5), comporta che si vada a partizionare (1,3,5,7) in (1,5),(3,7).
Nella riga successiva dell'esempio, esamina cosa succede all'insieme (2,4) per l'ingresso i1, ottenendo (2,4) --> (4,2) , ovvero 2 porta a 4, mentre 4 porta a 2. In questo caso non si deve fare niente, l'insieme ottenuto è uguale al precedente, quindi gli stati 2 e 4 hanno lo stesso funzionamento per l'ingresso i1.
Nell'ultima riga, controlla gli stati successivi di (2,4) quando l'ingresso è i2. In tal caso, (2,4) ->(7,3), cioè 2 porta allo stato 7, mentre 4 allo stato 3. Si è ricavato prima che 3 e 7 sono compatibili, infatti si era trovato l'insieme (3,7), quindi non ci sono incompatibilità.
L'esempio non lo riporta, ma si sarebbero anche potuti controllare (1,5) e (3,7) con ingresso i2.
Alla fine si è quindi ottenuto che la Famiglia è costituita da (1,5), (3,7), (2,4), (6), ovvero 1 e 5 sono equivalenti fra loro, così come 3 e 7, 2 e 4, mentre 6 non è equivalente con nessuno.
Si può quindi passare da una macchina a 6 stati ad una equivalente a 4 stati.
Preferiti: 0
