Architettura degli Elaboratori I

Testo delle Prove e Soluzioni

II Prova di Esonero A

Esercizio 1 (20 punti)

Analizzare il circuito sequenziale in figura, seguendo la procedura di analisi illustrata a lezione, e derivare l’automa a stati finiti che ne descrive il comportamento. In figura, due linee intersecanti ( ) sono effettivamente collegate solo se sull’intersezione è apposto un cerchio nero. Consiglio: fate attenzione al verso ( è )dei segnali, che in figura è esplicitamente indicato solo per il clock!

Esercizio 2 (10 punti)

Dimostrare, usando un linguaggio chiaro e formale, l’equivalenza fra macchine di Mealey e Moore, e viceversa.

II Prova di Esonero B

Esercizio 1 (20 punti)

Progettare un circuito sequenziale con tre uscite Q2Q1Q0, che emetta la sequenza ciclica: 000è 111è 101è 110è 001è 010è 000…..

Si segua la procedura di sintesi vista a lezione.

Esercizio 2 (10 punti)

Si descriva, usando un linguaggio chiaro e formale, il metodo di minimizzazione di un automa a stati finiti con output.

Soluzione Esercizio 1 compito A

(la spiegazione che segue tiene conto di errori comuni rilevati durante la correzione dei compiti)

Si ricavano le espressioni booleane degli ingressi di Set e Reset dei 3 FF

Si ricava la tabella degli stati futuri, riempiendo le 3 colonne centrali sulla base delle espressioni booleane sopra ricavate, e determinando poi gli stati futuri per le uscite dei tre FF.

Q2Q1Q0(t)	S2R2	S1R1	S0R0	Q2Q1Q0(t+1)
000 001 010 011 100 101 110 111	10 00 01 00 10 00 01 00	10 10 01 01 10 10 11 01	10 01 00 00 10 01 10 10	111 010 000 001 111 110 001 101

Si tratta dunque di un contatore della sequenza: 000è 111è 101è 110è 001è 010è 000…..gli stati 011 e 100 non compaiono nella sequenza. Se, per errore, il contatore si trova in uno di questi stati, viene "forzato" nuovamente nella sequenza di conteggio al successivo fronte di clock.

Notare che un contatore NON PUO’ ESSERE minimizzato: ogni stato corrisponde ad un conteggio diverso (cioè un output diverso) e dunque, tutti gli stati sono distinguibili.

Soluzione esercizio 1 compito B

Il compito B richiedeva di seguire la procedura inversa rispetto a quella del compito A.

La tabella degli stati futuri è la stessa dell’esercizio sopra, ma in questo caso le colonne da riempire sono le 3 centrali, sulla base della prima e della quinta colonna (S(t)è S(t+1))

Dalla tabella, si ricavano le espressioni booleane dei segnali SR dei 3 FF, ed infine lo schema circuitale, che è mostrato nel testo dell’esercizio 1 del compito A.

Si noti che in questo caso è tuttavia possibile utilizzare i "dont’care" e di conseguenza semplificare il circuito, sfruttando la presenza di stati non permessi.

La tabella che segue suppone che gli stati esterni alla sequenza non possano essere raggiunti ( le righe corrispondenti sono dunque riempite con "X"). Una strategia alternativa consiste nel forzare la transizione da stati non permessi ad uno stato della sequenza, ad esempio "000".

La tabella contiene delle "X" anche in corrispondenza delle colonne Si e Ri, laddove una certa commutazione del FF corrispondente possa essere ottenuta in più modi. Infatti:

0è 0 si ottiene applicando SR= 0,0 oppure 0,1 è 0X

1è 1 " SR= 0,0 oppure 1,0 è X0

Q2Q1Q0(t)	S2R2	S1R1	S0R0	Q2Q1Q0(t+1)
000 001 010 011 100 101 110 111	10 0X 01 XX XX X0 01 X0	10 10 01 XX XX 10 11 01	10 01 0X XX XX 01 10 X0	111 010 000 XXX XXX 110 001 101

La tabella è stata costruita utilizzando FF SR con porte NOR. Il comportamento di un FF con porte NAND (il cui simbolo grafico include due palline di inversione sugli ingressi S e R) è complementare.

Si noti che ,in un contatore, l’input è rappresentato dal clock, e l’output coincide con le uscite dei FF. E’ possibile costruire un automa nel quale la codifica degli stati non coincida con la sequenza da contare, ma un tale automa avrà bisogno di circuiteria aggiuntiva per generare gli output richiesti. Questa soluzione non è consigliabile.