Soluzioni esercizi 27-2-00
Prova A
Esercizio 1 (15 punti) Si progettino un sommatore parallelo a n bit ed un sommatore seriale. Sia D il tempo di risposta di una generica porta logica, e sia T l'intervallo fra due colpi di clock.
Sia T
tot il tempo necessario ad eseguire una somma di n bit usando il sommatore parallelo, e sia T'tot il tempo necessario ad eseguire la stessa somma con il sommatore seriale.Determinare formalmente la condizione che rende T
tot=T'tot.
La struttura di un addizionatore parallelo a n bit è descritta, per esempio, nel par. 4.5.4 del Bovet.
Il tempo di risposta di un circuito sommatore realizzato come esposto a lezione e nel citato paragrafo del Bovet dipende dal ritardo di propagazione del bit di riporto attraverso gli n moduli ADDi.
L'equazione del carry per il generico modulo ADDi è:
dove c
i è il riporto calcolato in uscita al modulo, ci-1 è il riporto in ingresso (proveniente dal modulo ADDi-1, ed infine ai e bi sono i bit i-esimi dei registri operandi, il cui contenuto deve essere sommato.Il circuito che realizza l'espressione booleana del carry ha dunque due stadi di porte logiche, ed un tempo di risposta, se D è il ritardo di attraversamento di una singola porta logica, pari a 2D .
Il ritardo complessivo sarà dunque, per n bit: n2D
Un sommatore seriale riceve i due addendi da due registri SISO. Ad ogni passo i, vengono sommati i bit ai e b
i con il carry memorizzato nel passo precedente. Il carry deve essere memorizzato su un FF, che rappresenta la memoria del sistema.La Figura 1 mostra lo schema a blocchi e l'automa del circuito. Lo stato S0 è quello in cui c
i-1 =0, S1 rappresenta lo stato in cui ci-1 =1.L'equazione della uscita Sum
i è la stessa che si ottiene per un sommatore parallelo, comunque la si può ricavare dall'automa in figura.La figura mostra che le parti combinatoria e sequenziale del circuito funzionano in parallelo , cioè, i ritardi si sovrappongono, non si sommano.
Il ritarado di attraversamento del circuito combinatorio deve essere necessariamente minore del ciclo di clock del FF, in modo tale che, ad ogni fronte di clock, sia possibile un aggiornamento dello stato della macchina. Dunque, (e ciò vale per qualsiasi circuito sequenziale sincrono) i tempi di esecuzione del circuito dipendono esclusivamente dal ciclo di clock T del sistema.
Nel caso in esame, viene eseguito un passo della somma ad ogni fronte di clock, dunque, occorrono nT istanti per completare la somma.
La condizione che rende uguali i tempi di esecuzione di una somma aritmetica sui due tipi di sommatore è dunque:
2D =T
Esercizio 2 (15 punti)
Progettate il circuito sequenziale che "riconosce" un numero divisibile per 4. L'automa riceve in ingresso una stringa binaria. Il bit ricevuto nell'istante t, i(t), rappresenta il bit meno significativo della stringa, ovvero: se, fino ad un certo istante, ha ricevuto la stringa S(t-1): 00..111 ed in t riceve uno 0, la stringa complessivamente ricevuta fino a t sarà S(t)= 00…1110.
L'automa deve generare un'uscita pari ad uno se S(t) è divisibile per 4, 0 altrimenti.
Una stringa binaria rappresenta un numero divisibile per 4 se le ultime due cifre sono 00. Il circuito sequenziale relativo può essere rappresentato con un automa di Mealy avente 2 stati, corrispondenti ai 2 possibili valori del bit b(t-1). Il valore corrente del bit b(t) determina l'output.
Si noti che un automa deterministico con output è definito mediante una sestupla, e che uno degli elementi della sestupla è lo stato iniziale, q0. Dunque, occorre fare una ipotesi sullo stato di partenza del sistema, ed una ipotesi "naturale" è che il FF memorizzi, all'inizio della ricezione della sequenza, il valore 0 (dunque non occorre inserire "stati di inizializzazione"!).
La figura mostra solo l'automa.
Lo studente ha a disposizione in rete decine di esempi di esercizi che, dall'automa, mostrano come ricavare il relativo circuito.
Prova B
Esercizio 1(15 punti) Si progetti un circuito combinatorio che riceve in ingresso due segnali di controllo, ADD e SUB, e le uscite di due registri A e B da n bit.
Se SUB=1, viene eseguita la sottrazione in complemento a due. Se ADD=1 viene eseguita la somma. Se ADD=SUB=0, non viene eseguita alcuna operazione.
Un terzo segnale di controllo, WRITE, abilita la scrittura del risultato sul registro A.
Si supponga che i segnali ADD, SUB e WRITE siano opportunamente temporizzati.
La rappresentazione dei numeri in complemento a b (dove b rappresenta la base, che nel caso in esame è 2) è illustrata nel par. 1.3.3 del Bovet, ed è stata illustrata più volte durante le esercitazioni.
Nel paragrafo in questione si mostra come la rappresentazione in complemento all'intervallo (a due, nel caso dell'esercizio) consenta di sostituire una sottrazione con un'operazione di cambiamento di segno seguita da una addizione. Infatti,
A-B= A+(-B)=A+
Lo schema è mostrato in Figura. Si noti che il segnale Sub, collegato con il segnale di input del carry del primo modulo del sommatore, ha l'effetto di sommare 1, come richiesto nella espressione della differenza in complemento a due.
Esercizio 2(15 punti). Progettate il circuito sequenziale che "riconosce" un numero divisibile per 2. L'automa riceve in ingresso una stringa binaria S(t). Il bit ricevuto nell'istante t, b(t), rappresenta il bit meno significativo della stringa, ovvero: se, fino ad un certo istante, ha ricevuto la stringa S(t-1): 00..111 ed in t riceve uno 0, la stringa complessivamente ricevuta fino a t sarà S(t)= 00…1110.
L'output Y(t) dell'automa sarà uguale ad 1 se la stringa è pari, e sarà 0 altrimenti.
L'uscita del circuito sequenziale viene utilizzata per abilitare un'operazione logica fra due registri R1 ed R2. Se Y(t)=1, si esegue R1ANDR2 e si trasferisce il risultato su R3.
Un numero è pari se il bit meno significativo è pari a 0. Poiché il bit meno significativo è quello ricevuto in t, la condizione di parità può essere verificata nell'istante corrente, senza bisogno di circuiti di memoria!
Il bit b(t), banalmente, va utilizzato per abilitare l'una o l'altra delle due operazioni logiche richieste.