Data la seguente tabella degli stati, eseguire l'ottimizzazione e applicare i criteri euristici per la scelta della codifica ottimale da utilizzare per generare la tabella delle transizioni corrispondente. Sintetizzare le funzioni d'uscita corrispondenti. Sintetizzare la funzione di stato prossimo scegliendo il flip-flop da utilizzare.

Il primo passo è quello di ottimizzazione, ossia generare la tabella triangolare per verificare se ci sono compatibilità.
Due stati sono compatibili se hanno uscite compatibili e stati prossimi compatibili.
Le uscite sono compatibili se la loro parte specificata è identica.
(Es: 11 compatibile solo con 11, ma 1- è compatibile sia con 10 che 11 che 1-)

Da questo primo passo gli unici nodi che si possono dire compatibili sono S1 e S2.
I nodi S2 e S3 sono incompatibili in quanto S3 S5 non sono compatibili.
I nodi S0 e S3 sono incompatibili in quanto S1 S5 non sono compatibili.

Ne risulta la seguente tabella:

Ad essa corrisponde il seguente grafo di compatibilità:

Per identificare i gruppi di stati compatibili bisogna seguire la seguente regola:
Si sceglie il sottografo completo di ordine massimo, si elencano i suoi nodi e i nodi citati nei suoi vincoli, si cancellano dal sottografo tutti i nodi che non fanno parte di alcun vincolo.

Nel nostro caso il sottografo completo (ossia avente tutti i collegamenti interni) è formato da S0 S1 S2 e i nodi interessati dai suoi vincoli sono S1 e S3, cancello S0 e S2 perchè non interessati.

Il grafo rimanente ha come unico sottografo completo  S1 S3, il suo vincolo è S0 S2, tale vincolo è già rispettato dal primo sottografo scelto, ossia S0 S1 S2. Cancello dal grafo i nodi S1 e S3 perchè non interessati dai vincoli in considerazione.

Rimangono solo i nodi isolati S4 e S5 che vanno presi singolarmente.

Si delinea quindi un raggruppamento del tipo A={S0,S1,S2} B={S1,S3} C=S4 D=S5. Bisogna controllare che questo raggruppamento rispecchi i vincoli: S3S1 è rispettato perché esiste B, S0S2 è rispettato perché è compreso in A.
Essendo rispettati tutti i vincoli, il raggruppamento è corretto.

Può sorgere il problema di come gestire S1 visto che appartiene a due gruppi, si applicano alcune euristiche che risultano utili al momento della scelta della codifica migliore per gli stati.
Le euristiche suggeriscono di:

• Se un gruppo (ad esempio A) contiene anche un solo nodo con uscita specificata, quella è l'uscita del gruppo.

• Se lo stato prossimo in una data cella appartiene a due o più gruppi, se tra questi gruppi c'è lo stato attuale della riga in considerazione, quello è lo stato prossimo da indicare.

• Se la premessa del punto precedente è vera ma non si può mantenere lo stato attuale, indico uno stato prossimo ammissibile che abbia distanza di hamming minima su quella riga.

Applicando queste euristiche, deriva la seguente tabella degli stati ottimizzata:

Ora bisogna scegliere una codifica per gli stati.
Si applicano i seguenti criteri:

• Si tende a dare codifiche adiacenti a stati che portano allo stesso stato prossimo a fronte del medesimo ingresso.

• Si tende a dare codifiche adiacenti a stati che sono stati prossimi, derivanti da ingressi adiacenti, di uno stesso stato. (Sono le adiacenze orizzontali sulla tabella)

Ad ogni coppia di stati che rispetta uno dei criteri, si attribuisce una marca per ogni loro occorrenza lungo la tabella.
NOTA: Se l'applicazione di un criterio porta ad aggiungere un uguale numero di marche a tutte le coppie esistenti, è possibile tralasciare l'aggiunta di tali marche in quanto non porterebbero ad un vantaggio relativo di qualche coppia su un'altra.

Applicando il primo criterio si ottengono le seguenti marche (divise per colonna considerata):

• AB: 1 + 0 + 0 + 1 = 2

• BC: 1 + 0 + 1 + 1 = 3

• CD: 0 + 0 + 0 + 0 = 0

• DA: 0 + 0 + 0 + 0 = 0

• AC: 1 + 1 + 0 + 1 = 3

• BD: 0 + 0 + 0 + 0 = 0

Applicando il secondo criterio si ottengono le seguenti marche (divise per riga considerata):

• AB: 2 + 2 + 1 + 0 = 5

• BC: 0 + 0 + 0 + 0 = 0

• CD: 0 + 0 + 0 + 0 = 0

• DA: 0 + 0 + 1 + 2 = 3

• AC: 0 + 0 + 0 + 0 = 0

• BD: 0 + 2 + 1 + 0 = 3

Sommando i contributi dei due criteri si ottengono le seguenti marche:

• AB: 7

• BC: 3

• CD: 0

• DA: 3

• AC: 3

• BD: 3

E' utile rappresentare graficamente questa situazione:

E' necessario spezzare qualche lato per ottenere una configurazione adatta alla scelta della codifica.
Ci sono due possibilità: o si spezza il lato AB e si "srotola il quadrato" oppure si spezzano le diagonali.
Siccome la somma delle marche delle diagonali è inferiore a quella del lato AB, sono loro ad essere spezzate.

Si ottiene quindi la seguente codifica:

• A = 00

• B = 01

• D = 10

• C = 11

Si ottiene in questo modo la tabella delle transizioni della macchina a stati finiti:

A questo punto è possibile sintetizzare le funzioni d'uscita della macchina a stati, ossia le reti combinatorie che determinano il valore di ognuno dei bit dell'uscita.
Per fare questo è sufficiente ricavare dalla tabella precedente le due mappe di Karnaugh aventi le codifiche degli ingressi sulle colonne, le codifiche degli stati sulle righe e all'interno delle celle il valore corrispondente del primo o del secondo bit dell'uscita, a seconda che si voglia sintetizzare F1 o F2.

Le due funzioni d'uscita hanno le seguenti mappe di Karnaugh:

• F1 = I1*I2

  S\I	00	01	11	10
  00	0	0	1	0
  01	0	0	1	0
  11	0	0	1	0
  10	0	0	-	0

• F2 = S0'*I1 + S0'*I2' + S1*I1'*I2'

  S\I	00	01	11	10
  00	1	0	1	1
  01	1	0	1	1
  11	1	0	0	0
  10	0	0	-	0

Per sintetizzare la rete combinatoria di stato prossimo invece è necessario scegliere il tipo di flip-flop da utilizzare.

NOTA: La funzione d'uscita non dipende dal tipo di bistabile scelto, mentre la finzione di stato prossimo sì.

NOTA: Se il bistabile scelto è il flip-flop D non serve il calcolo della tabella delle eccitazioni della MSF perchè essa coincide con la tabella delle transizioni in quando tale flip-flop non fa altro che riportare in uscita il dato che riceve in ingresso al colpo di clock successivo.

Se il bistabile scelto non è di tipo D, bisogna considerare la sua tabella delle eccitazioni.
I bistabili che si considerano sono:

• Il flip-flop T: Se l'ingresso è abilitato, inverte il valore dell'uscita, altrimenti lo mantiene.
  E' caratterizzato dalla seguente tabella delle eccitazioni:

  Q	Q*	T
  0	0	0
  0	1	1
  1	0	1
  1	1	0

• Il flip-flop D: Porta in uscita al colpo di clock successivo il dato presente in ingresso.
  E' caratterizzato dalla seguente tabella delle eccitazioni:

  Q	Q*	D
  0	0	0
  0	1	1
  1	0	0
  1	1	1

   

• Il flip-flop SR: Ha due ingressi che servono rispettivamente per porre a 1 e a 0 l'uscita. La configurazione d'ingresso 1 1 va evitata in quanto porta ad un comportamento incontrollato del bistabile.
  E' caratterizzato dalla seguente tabella delle eccitazioni:

  Q	Q*	S	R
  0	0	0	-
  0	1	1	0
  1	0	0	1
  1	1	-	0

• Il flip-flop JK: Si comporta come l'SR ma ha un comportamento definito a fronte della combinazione 1 1 in ingresso. Per tale combinazione inverte le uscite.

  Q	Q*	J	K
  0	0	0	-
  0	1	1	-
  1	0	-	1
  1	1	-	0

Utilizzando le tabelle delle eccitazioni dei bistabili è possibile generare la tabella delle eccitazioni della MSF. Tale tabella è generata a partire dalla tabella delle transizioni della MSF, infatti quest'ultima ha sulle righe i valori dello stato attuale e all'interno delle celle i valori dello stati prossimo. Per generare la tabella delle eccitazioni, si sostituisce nella tabella delle transizioni lo stato prossimo con i valori degli ingressi del bistabile che portano a generare quello stato prossimo a partire da quello stato attuale.

Scegliendo per esempio di realizzare la tabella delle eccitazioni della MSF in considerazione con un flip-flop di tipo T, il risultato è il seguente:

Per ottenere questa tabella da quella delle transizioni non si è fatto altro che eliminare le codifiche degli stati prossimi all'interno delle celle e sostituirle con una nuova codifica di 2 bit. Questa nuova codifica rispecchia il comportamento degli ingressi dei bistabili T necessari a memorizzare lo stato. In particolare, chiamando a e b i due bit della nuova codifica, a=0 sse Q₁=Q₁^* e b=0 sse Q₂=Q₂^* . a=1 e b=1 altrimenti. Dove Q_i^* è l'i-esimo bit dello stato prossimo appena eliminato.

A questo punto è sufficiente ricavare le due mappe di Karnaugh aventi all'interno delle celle l'i-esimo bit degli ingressi ai bistabili appena creati per poter sintetizzare la rete combinatoria di stato prossimo in grado di controllare i bistabili T.

Se si fossero scelti altri tipi di bistabili si sarebbero avute quattro mappe di Karnaugh in quanto gli ingressi da controllare sarebbero stati 4, o due S e due R, oppure due J e due K.

   Calcolatori Elettronici

Boh