Circuiti sommatori
Cosa sono i circuiti sommatori
Un sommatore è una rete che effettua la somma fra due operandi numerici. Se gli ingressi sono espressi su n bit saranno necessari n+1 bit di uscita per eseguire correttamente qualunque somma.
Somma di operandi ad un bit: half-adder
Un half-adder è una rete combinatoria che somma due operandi (a e b) ad un bit e restituisce un risultato (r) ed un riporto (cout), detto carry.
Il riporto vale 0 se la somma di a e b può essere rappresentata su un bit, 1 altrimenti.
In questo caso la rete è quindi caratterizzata dalla seguente tabella di verità
E' facile notare come la colonna cout descrive l’operazione di AND fra a e b, mentre la colonna r descrive l’operazione di XOR fra a e b. Pertanto questa rete combinatoria si può sintetizzare nel seguente modo:
Somma di operandi ad un bit: full-adder
Un full-adder è una rete combinatoria che somma tre operandi (a, b ed un carry di ingresso cin) ad un bit e restituisce un risultato (r) ed un riporto (cout).
La sua tabella di verità è la seguente
E dunque può essere così sintetizzato:
Realizzazione del full-adder in logica statica CMOS
Esistono diversi modi per realizzare un full-adder in logica statica.
Il primo consiste nel collegare fra di loro le porte elementari necessarie (2 porte XOR, 2 porte AND, 1 porta OR) secondo lo schema visto precedentemente. Lo svantaggio principale di questa realizzazione sta nell’elevato numero di transistor necessari a realizzare la rete.
Una tecnica alternativa (complex-gate) consiste nell’esaminare in maniera separata le due uscite della rete, ed in particolare le configurazioni degli ingressi che ne determinano il valore logico alto o basso.
r vale 1 nei seguenti quattro casi:
Nella logica statica è la PUN che si occupa di portare l’uscita a livello logico alto, quindi occorre creare una PUN che preveda quattro diversi percorsi che portano r ad 1:
r vale 0 nei seguenti quattro casi:
Nella logica statica è la PDN che di occupa di portare l’uscita al livello logico basso, quindi occorre creare una PDN che preveda quattro diversi percorsi che portano r a 0:
Mettendo PUN e PDN insieme, una rete che implementa r è la seguente:
Analoghi ragionamenti si possono fare osservando l’uscita della rete Cout ed individuando i percorsi utili. Una rete che implementa il carry di uscita Cout è la seguente
Anche con il complex-gate il numero di transistori rimane molto alto, in quanto servono 16 transistori per realizzare la rete che genera r, 10 transistori per la rete che genera Cout e altri 6 transistori per invertire i tre ingressi (2 transistori ad invert). In totale sono dunque 32 transistori.
E' possibile diminuire il numero di transistori necessari? La risposta è si.
Osserviamo nuovamente la tabella di verità del full-adder e mettiamo in relazione le due uscite:
come si può notare facilmente r è sempre complementare a cout tranne nei casi in cui tutti gli ingressi sono pari ad 1 o sono tutti pari a 0. Possiamo allora esprimere r in funzione di cout:
Inoltre, cout gode della seguente proprietà:
Grazie a queste considerazioni possiamo ottenere delle reti alternative che generano le due uscite:
La rete di sinistra produce cout complementato e lo invia alla rete di destra, che produce il risultato r complementato.
La rete di sinistra è identica a quella analizzata nella soluzione complex-gate, ma si sono complementati tutti gli ingressi, per produrre la negazione di cout in virtù della proprietà precedentemente analizzata. Questo permette di eliminare gli inverter che servono solo per negare gli ingressi a, b e cin. La rete di destra è la diretta implementazione della relazione che esprime r in funzione di cout.
Con questa realizzazione sono necessari 24 transistori più 4 per i due inverter, quindi 28 in totale. Lo svantaggio della rete è che per produrre r è necessario prima attendere che venga calcolato cout.
Somma di operandi ad n bit
Per realizzare sommatori che sommano operandi a n bit si potrebbe scrivere, e poi sintetizzare, la tabella di verità. Ad esempio per operandi a due bit, la tabella è la seguente:
Questa però è più difficile da sintetizzare, rispetto a quella vista per lo half-adder. All’aumentare di n diventa sempre più complesso tirar fuori la rete combinatoria corrispondente e questo approccio deve essere abbandonato.
In alternativa si ricorre alla modularizzare della soluzione: avendo a disposizione il full-adder (che accetta il carry in ingresso), si può effettuare la somma fra i singoli bit dei due operandi, tenendo in considerazione eventuali riporti generati dalla somma dei due bit precedenti.
Ad esempio se si vuole effettuare la somma di operandi a quattro bit, si possono usare quattro full-adder così connessi:
Dove con a0, b0, r0, si sono indicati i bit meno significativi rispettivamante dei due operandi a e b e del risultato r, mentre con a3, b3, r3 si sono indicati i bit più significativi.
Questa soluzione presenta due problemi: il primo è che ci vogliono tanti full-adder, quanti sono i bit che costituiscono gli operandi da sommare (ed ogni full-adder richiede, al minimo, 28 transistori); il secondo è che ogni full-adder della catena deve attendere che il full-adder immediatamente precedente abbia prodotto il carry di uscita, altrimenti non può calcolare il risultato corretto.
In alternativa si può utilizzare una soluzione detta ripple-carry, che sfrutta un solo full-adder e diversi registri.
Ad ogni clock, il full-adder esegue la somma di due bit (un bit di a ed un bit di b) e deposita il risultato parziale nel registro di r. Il risultato completo sarà quindi disponibile dopo n cicli di clock e solo allora la rete sarà pronta ad eseguire una nuova somma. Il registro F necessita di reset, in quanto ogni volta che cambiano gli operandi occorre riportare a 0 il carry di ingresso.
Questa soluzione presenta il vantaggio di usare un solo full-adder ma la sua velocità dipende dal clock che ovviamente non può essere scelto a piacere e deve sottostare a vincoli ben precisi.
Delle due soluzioni non esiste una migliore ed una peggiore, in quanto dipende tutto da n e dalla metrica di confronto. Ad esempio, se confrontiamo le soluzioni dal punto di vista del numero di transistori utilizzati, per n piccolo è sicuramente migliore la soluzione basata sulla catena di full-adder; ad esempio per n = 1 sono necessari i soli transistori per realizzare il full-adder, mentre nella soluzione ripple-carry vanno considerati anche i transistori necessari per realizzare i registri ad 1 bit che conterranno a, b ed r, nonchè il registro F. Al crescere di n, la situazione può ribaltarsi.
Carry look ahead
Le due soluzioni analizzate non possono essere usate per realizzare ALU di processori che richiedono prestazioni elevate. Se prendiamo ad esempio la soluzione basata sulla catena di full-adder e ipotizziamo di voler realizzare una ALU a 64 bit in cui ogni full-adder produce il carry di uscita in 0.5 ns, allora per sommare operandi a 64 bit la rete impiega nel complessivo
64 * 0.5 = 32 ns
Questo permette di avere una frequenza di clock massima pari a
f = 1/32 = 30 Mhz
che ovviamente è irrisoria.
Il collo di bottiglia è rappresentato dal fatto che ogni full-adder deve attendere che sia pronto il carry prodotto dal full-adder precedente. In alternativa si può ricorrere ad una rete che genera tutti i carry in maniera istantanea; questa rete è detta rete CLA. Vediamo con quali ragionamenti è possibile ottenerla.
Per quanto visto, l’espressione che caratterizza il carry prodotto da ogni full-adder della catena dipende dal carry prodotto dal full-adder antecedente ed è
Ci = Ai Bi + Ci-1 (Ai + Bi)
Si possono definire due termini: il termine generatore Gi, detto così perchè, se attivo, il carry di uscita viene portato a 1
Gi = Ai Bi
ed il termine propagatore Pi, detto così perchè se attivo propaga in uscita il carry di ingresso
Pi = Ai + Bi
Si possono caratterizzare entrambe le uscite di un full-adder, in relazione a questi due termini
Ci = Gi + Ci-1 Pi
Si = Pi XOR Ci-1
Si itera adesso la formula di Ci quattro volte:
C0 = G0 + CIN P0
C1 = G1 + P1 G0 + CIN P0 P1
C2 = G2 + P2 G1 + P2 P1 G0 + CIN P0 P1 P2
C3 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0 + CIN P0 P1 P2 P3
Come si vede i quattro carry sono indipendenti fra di loro e dipendono solo dal carry di ingresso CIN. E’ dunque possibile creare una rete che genera i quattro carry tutti insieme (rete CLA) a patto che ci sia una rete (BB) che genera Gi e Pi.
Quindi, una architettura in grado di sommare operandi a quattro bit è la seguente
In genere non si producono reti CLA che sommano operandi a più di quattro bit, in quanto più è alto l’indice del carry e più aumenta il fan-in delle porte AND e OR da usare per implementare la rete CLA stessa. Di tutto ciò ne risente il tempo di propagazione della rete
Il tempo di propagazione cresce (quasi) linearmente per fan-in minori o uguali a quattro, subito dopo esplode esponenzialmente. Se si vogliono sommare operandi a 16, 32, 64, ... bit è possibile seguire due approcci.
Il primo approccio vede il collegamento di più reti CLA-4 in cascata; ad esempio per sommare operandi a 64 bit occorre mettere in cascata 16 reti CLA-4. Questo approccio presenta problemi analoghi a quelli discussi quando si è parlato del collegamento in cascata di più full-adder.
L'altro approccio è quello effettivamente seguito e consiste nel creare una gerarchia di reti CLA-4. Questa soluzione si ottiene sviluppando ulteriormente le relazioni numeriche viste precedentemente; in particolare, nella espressione
C3 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0 + CIN P0 P1 P2 P3
si possono fare due sostituzioni:
P’ = P0 P1 P2 P3
G’ = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0
In questo modo la precedente diviene
C3 = G’+ CIN P’
e si può iterare per produrre C4, C5 e C6.
Con questo metodo si possono creare gerarchie che permettono di sommare operandi a 64 bit
Con questa architettura, se ipotizziamo che ogni livello di CLA impieghi 1 ns per produrre il risultato, la rete totale impiega
1 ns * 3 livelli = 3 ns
contro i
1 ns * 16 CLA = 16 ns
richiesti dalla catena di CLA.
Con 3 ns si possono ottenere processori con frequenza massima di
f = 1 / 3 = 300 MHz
che ovviamente non è ottima, ma sicuramente è molto meglio dei 30 MHz ottenibili concatenando i full-adder.
Effettivamente esistono tante soluzioni che permettono di creare circuiti sommatori che operano su operandi a 64 bit ed il carry look-ahead è solo una di queste.
Compatibile con
Ris. min. 1024x768
© 2008-2010 Alessio Amato