Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

Circuiti Addizionatori

Gli addizionatori sono un elemento critico all’interno dei sistemi digitali, sia

perché coinvolti in un vasto numero di operazioni elementari, sia perché spesso

responsabili del massimo ritardo combinatorio presente all’interno del sistema

(in un sistema sincrono, tale ritardo condiziona la massima frequenza operativa

raggiungibile). Per questi motivi, nel corso degli ultimi decenni è stata presenta-

ta un’ampia varietà di soluzioni circuitali per l’operazione di addizione, tuttora

oggetto di ricerca. In questo capitolo vengono analizzati alcuni degli addiziona-

tori più importanti. Per ogni addizionatore, viene presentato lo schema archi-

tetturale ed alcune considerazioni legate alle prestazioni ed al costo realizzativo.

Vari tipi di addizionatori, data la loro importanza, sono descritti in diversi testi,

tra cui [1, 2, 3]. In [16] sono presentate anche molte implementazioni specifiche.

1 Addizionatori binari

Per comprendere la strutturazione dei circuiti addizionatori, è utile enfatizzare il

procedimento elementare tramite il qualche può essere calcolata la somma di due

numeri rappresentati in binario (Figura 1). La figura riporta i passi elementari

Figura 1: Un esempio di addizione tra numeri in rappresentazione binaria.

dell’operazione di somma, procedendo dalla coppia di cifre meno significative,

quelle più a destra, verso le cifre più significative. Ogni coppia di cifre è som-

mata insieme ad un eventuale riporto entrante prodotto dalla coppia di cifre a

destra, producendo a sua volta un bit di somma ed un eventuale bit di riporto

che sarà tenuto in conto nella somma di bit successiva. L’operazione ha una

strutturazione evidentemente iterativa, e pertanto si presta ad una realizza-

zione “bit-sliced”, ovvero ottenuta implementando circuitalmente l’operazione

elementare (somma di due bit più il riporto), ed iterando n volte il circuito per

ottenere la somma ad n bit. 2

Si noti che, a differenza delle generiche coppie di cifre interne, la coppia

più a destra non necessita di ricevere un riporto in ingresso, e richiede quindi

un’operazione di somma più semplice.

Per studiare in dettaglio l’implementazione circuitale dell’addizione, partia-

mo proprio dalla coppia di cifre più a destra. In questo caso, abbiamo bisogno

di una rete che riceva due bit in ingresso (A e B ) e produca due bit in uscita

i i

(S, il bit di somma, e C , il riporto, o carry in uscita). La somma richiesta

out

può essere vista come la funzione logica definita dalla seguente tabella di verità:

A B S C

i i out

0 0 0 0

0 1 1 0

1 0 1 0

1 1 0 1

Tabella 1: Tabella di verità dell’Half-Adder

Dalla tabella si deduce che la funzione somma può essere descritta dalle seguenti

equazioni: S = A ⊕ B (1)

i i

C = A · B (2)

out i i

La rete che implementa questa coppia di operazioni è chiamata Half-Adder

(Figura 2).

Per le coppie di cifre interne occorre tenere in conto anche il riporto entrante

da destra. In altre parole, la cella che implementa l’operazione elementare dovrà

questa volta avere tre ingressi, A , B ed il riporto entrante C . La rete che

i i in

implementa queste operazioni è chiamata Full-Adder e realizza la tabella di

verità riportata sotto (Tabella 2). L’uscita S del Full-Adder è ancora una XOR

dei tre ingressi, mentre l’uscita C è alta se sono contemporaneamente alti

out

almeno due dei tre ingessi (funzione maggioranza).

1 0

Si noti che, assegnando peso 2 = 2 all’uscita C e peso 2 = 1 all’uscita

out

S, il Full-Adder genera la codifica binaria del numero di 1 presenti ingresso. In

altri termini, il valore 2C + S è uguale al numero di ingressi pari ad 1, come

out

si può facilmente verificare dalla tabella. Ad esempio, quando in ingresso si ha

A B C S C

i i in out

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

Tabella 2: Tabella di verità di un Full-Adder.

3

A = 1, B = 0 e C = 1 (due 1 in ingresso), l’uscita sarà C = 1 e S = 0,

i i in out

che può essere letta come il valore 2 in binario. Questa proprietà si interpreta

facilmente osservando l’esempio di somma in Figura 1: il bit di somma S ha

lo stesso peso dei bit sommati A e B , e viene pertanto scritto nella stessa

i i

colonna; il bit C ha invece peso aumentato di 1 e viene sommato insieme alla

out

cifre alla sinistra di quelle correnti A e B . Questa proprietà è vera anche per

i i

l’Half-Adder, sebbene in quel caso siano presenti solo due ingressi, e quindi il

massimo valore codificato dalle due uscite C ed S sarà pari a (10) = 2. In

out 2

molte circostanze, è utile considerare Full-Adder ed Half-Adder come contatori,

sulla base della proprietà appena vista.

Dalla tabella di verità, è possibile notare che le equazioni del Full-Adder

possono essere scritte come:

S = A ⊕ B ⊕ C = (A ⊕ B ) ⊕ C

i i in i i in

e, minimizzando opportunamente la funzione C ,

out

C = A B + A C + B C = A B + C (A + B )

out i i i in i in i i in i i

È facile notare che l’espressione di C può essere riscritta come

out

C = A B +A C +B C = A B +A B C +A B C +A B C +A B C

out i i i in i in i i i i in i i in i i in i i in

per assorbimento, questa espressione diventa

A B + A B C + A B C = A B + C (A ⊕ B )

i i i i in i i in i i in i i

Nella realizzazione del circuito Full-Adder, è spesso utile costruire prima i segnali

P = A ⊕ B

i i

G = A B

i i

Questi segnali possono essere generati da un Half-Adder. Avendo a disposizione

i segnali P e G, per ottenere le uscite del Full-Adder occorre ancora calcolare

S = P ⊕ C in

C = G + C · P

out in

Le operazioni di XOR e AND necessarie per ottenere S e C a partire da P

out

e G possono essere ottenute con un secondo Half-Adder, come mostrato nella

Figura 3. Un Full-Adder può quindi essere realizzato a partire da due Half-

Adder, più una porta OR.

2 Ripple-Carry Adder (RCA)

Il metodo più diretto per realizzare un addizionatore ad n bit è rappresentato

dal Ripple-Carry Adder (RCA), o addizionatore a propagazione del riporto.

Questo circuito richiede n Full-Adder in cascata, ovvero con il riporto uscente

dell’i-esimo Full-Adder collegato al riporto entrante dell’(i+1)-esimo Full-Adder,

come mostrato in Figura 4. 4

Figura 2: Half-Adder Figura 3: Full-Adder realizzato con due Half-Adder

Figura 4: Ripple-Carry Adder. In rosso è evidenziato il percorso critico.

L’addizionatore RCA non fa nient’altro che calcolare la somma cosı̀ come

verrebbe calcolata a mano (vedi esempio nel paragrafo precedente). La sua

architettura è semplice, ma anche lenta. Il tempo di calcolo nel caso peggiore,

infatti, dipende linearmente dal numero di stadi, in quanto bisogna attendere che

il riporto si propaghi dalla prima all’ultima cella per avere il risultato corretto.

Se si indica con T il tempo di propagazione di un Full-Adder, il tempo di

F A

propagazione di un RCA vale, nel caso peggiore,

T = nT (3)

RCA F A

La Figura 4 mostra in rosso il cammino critico del circuito, ovvero il percorso

lungo il quale si propagherà il ritardo peggiore. In maniera simile, il numero di

porte necessarie per realizzarlo risulta essere:

A = nA (4)

RCA F A

2.1 Ottimizzazione dell’RCA

In alcune tecnologie è più semplice realizzare un addizionatore che calcoli S ed

C . In tal caso, il componente elementare che si ha a disposizione è quello

out

rappresentato in Figura 5. Per costruire un addizionatore a propagazione del

Figura 5: Full-Adder con uscite negate.

riporto, pertanto, occorrerà utilizzare due porte NOT per avere i valori di S

5

e C . Come è facile notare in Figura 6, un RCA costruito in questo modo

out

presenta delle porte NOT aggiuntive sul cammino critico, che rallentano ul-

teriormente il calcolo. Si può tuttavia osservare che la tabella di verità del

Figura 6: Addizionatore a propagazione basato su FA con uscite negate.

Full-Adder (Tabella 4) gode della seguente proprietà:

S(A, B, C ) = S(A, B, C )

in in

B, C ) = C (A, B, C )

C (A, in out in

out

Possiamo, quindi, negare tutti gli ingressi, spostare le NOT dall’uscita all’ingres-

so, come in Figura 7, diminuendo cosı̀ il tempo di propagazione lungo il cammino

critico. Inoltre avendo entrambi gli ingressi negati sul secondo Full-Adder, non

abbiamo bisogno della NOT in uscita. Complessivamente, si utilizzano tre in-

vertitori ogni due Full-Adder (uno in meno rispetto a prima), ottenendo anche

un risparmio nel numero di porte.

Figura 7: Addizionatore a propagazione basato su FA con uscite negate. Schema

migliorato.

3 Sottrattore

Un sottrattore può essere costruito in maniera molto simile ad un addizionatore,

ancora una volta osservando la natura iterativa dell’operazione. La Figura 8

mostra un esempio di sottrazione. Anche in questo caso l’operazione è effettuata

bit a bit, ma per ogni coppia occorre osservare che i bit del secondo operando, B,

sono sottratti (ovvero, moltiplicati per -1 e sommati algebricamente). Inoltre,

il valore propagato da una coppia di bit alla successiva non è un riporto, ma un

prestito (in inglese, borrow), ovvero va anch’esso sommato con peso negativo. La

sottrazione relativa ad ogni coppia di bit, a sua volta, produce un bit del risultato

ed un bit di prestito che sarà considerato dalla coppia di bit immediatamente a

sinistra. 6

Figura 8: Un esempio di sottrazione tra numeri in rappresentazione binaria.

Anche in questo caso è possibile distinguere due tipi di operazioni: una,

più semplice, non prevede prestito entrante ed è effettuata sulla coppia di bit

meno significativa, l’altra, che invece prevede un prestito entrante, è effettuata

su tutte le altre coppie di bit. La prima operazione è effettuata dal circuito

Semi-Sottrattore (Half-Subtractor), la cui tabella di verità è riportata sotto

A B S C

i i out

0 0 0 0

0 1 1 1

1 0 1 0

1 1 0 0

La sottrazione sulle coppie di bit interne, invece, è realizzata dal circuito

Sottrattore Completo (Full-Subtractor), la cui tabella di verità è riportata sotto.

A B C S C

i i in out

0 0 0 0 0

0 0 1 1 1

0 1 0 1 1

0 1 1 0 1

1 0 0 1 0

1 0 1 0 0

1 1 0 0 0

1 1 1 1 1

Si noti che anche in questo caso, come per i circuiti addizionatori, la coppia

C ,S codifica la somma degli 1 in ingresso. Questa volta, però, sia gli ingressi

out

che le uscite possono avere pesi negativi. In particolare, l’ingresso A ha peso

i

e C hanno peso −1. In uscita, S ha peso 1, mentre C ha peso

1, mentre B i in out

−2. In altri termini, il Sottrattore implementa la funzione:

(−2)C + S = A + (−1)B + (−1)C

out i i in

Dalle tabelle di verità è possibile notare che, per il Semi-Sottrattore, si ha:

(A ⊕ B )

S = A ⊕ B = i i

i i

C = A B

out i i

mentre per il Sottrattore Completo si ha:

S = A ⊕ B ⊕ C = (A ⊕ B ⊕ C )

i i in i i in

7

C = A B C + A B C + A B C + A B C =

out i i in i i in i i in i i in

(A B C + A B C ) + (A B C + A B C ) + (A B C + A B C ) =

i i in i i in i i in i i in i i in i i in

A C + A B + B C = A B + C (A + B )

i in i i i in i i in i i

E’ chiaro dalle precedenti formule che un Semi-Sottrattore ed un Sottratto-

re Completo possono essere ottenuti da un Semi-Addizionatore e da un Ad-

dizionatore Completo negando l’ingresso A e l’uscita S, come riportato in

i

Figura 9.

Figura 9: Sottrattori binari realizzati tramite Full-Adder e Half-Adder.

Nella pratica, tuttavia, è preferibile fare uso di circuiti addizionatori senza

alcuna modifica circuitale interna. La tecnica più ovvia consiste nello sfruttare

le proprietà della rappresentazione in complementi, grazie alla quale è possibile

usare solo l’operazione di addizione per manipolare numeri che possono even-

tualmente essere negativi. La sottrazione consisterà pertanto nel trasformare il

numero da sottrarre nel suo opposto. Questa trasformazione, come ben noto,

può essere effettuata invertendo tutti i bit del numero ed aggiungendo uno al

valore cosı̀ ottenuto. L’aggiunta di uno, che richiederebbe un secondo addizio-

natore, può essere fatta in maniera immediata se l’addizionatore è implementato

usando un Full-Adder invece che un Half-Adder sulla cifra meno significativa. In

tal caso, infatti, è possibile aggiungere 1, visto come riporto entrante sulla cifra

di peso più basso. In definitiva, è possibile usare un addizionatore come sot-

trattore negando i bit del numero da sottrarre ed inserendo un riporto entrante

sulla cifra più bassa pari ad 1. Questa tecnica è mostrata nella Figura 10.a.

Rendendo controllabile dall’esterno la possibilità di negare o meno i bit del-

l’operando B e l’inserimento di un riporto entrante, lo stesso componente può

essere usato sia come sottrattore che come addizionatore. Nella Figura 10.b è

riportato uno schema di addizionatore/sottrattore. Il circuito esegue l’addizione

quando sub = 0 e la sottrazione quando sub = 1.

Figura 10: Addizionatore usato come sottrattore.

8

4 Carry Select Adder

È possibile costruire un addizionatore più veloce del Ripple-Carry introducendo

un certo grado di ridondanza all’interno del circuito. Possiamo, infatti, divi-

dere l’addizionatore in p blocchi di m bit. Per come abbiamo definito queste

grandezze il numero totale di bit dell’addizionatore sarà quindi n = p · m. Il

primo blocco sarà costituito da un RCA a m bit, mentre i blocchi dal secondo

al p-esimo saranno costituiti da due RCA ad m bit, l’uno col segnale C = 0

in

e l’altro con C = 1. Le uscite di questi blocchi saranno selezionate da un

in

multiplexer che riceverà in ingresso come segnale di selezione il riporto uscente

del blocco precedente.

Il parallelismo introdotto all’interno del circuito permette di velocizzare il

calcolo. È infatti importante notare che i calcoli eseguiti nei diversi blocchi

possono procedere indipendentemente, e completarsi tutti allo stesso istante,

pari al ritardo del RCA di m bit che è usato per il singolo blocco. Chiaramente,

questo vantaggio comporta un prezzo da pagare in termini di porte logiche usate:

il numero di componenti è circa doppio rispetto all’RCA.

Un addizionatore del genere prende il nome di Carry Select Adder ed è

mostrato in Figura 11, con n = 16 ed m = 4; in rosso è evidenziato il cammino

critico. Figura 11: Addizionatore Carry Select.

Analizziamone in dettaglio il ritardo. Supponendo che i blocchi elementari

siano degli RCA, i singoli blocchi avranno effettuato le loro somme in un tempo

T = mT (vedi equazione (3)). I primi m bit della somma saranno quindi

blocco F A

disponibili dopo il tempo T . I bit del secondo blocco saranno disponibili

blocco 1

dopo un tempo T +T (dove T è il ritardo del multiplexer ), quelli del

blocco mux mux

terzo dopo un tempo T + 2T e cosı̀ via. Il tempo totale di computazione

blocco mux

del circuito è quindi: T = mT + (p − 1)T (5)

CSA F A mux

Scegliendo adeguatamente m e p, è possibile rendere T minimo. Nella

CSA

(5) sostituiamo m = n/p e deriviamo rispetto a p:

dT nT

CSA F A

= − + T

mux

2

dp p

1 il tempo di propagazione del multiplexer è costante rispetto a n

9

Studiando il segno della derivata, è facile verificare che il minimo di T si ha

CSA

in corrispondenza di r

r nT n nT

F A mux

p = ⇒ m = = (6)

min

min T p T

mux min F A

Le (6) indicano i valori ottimali di p ed m. Sostituendo questi valori nella (5)

otteniamo il tempo di propagazione minimo di un Carry Select:

T = m T + (p − 1)T

CSAmin min F A min mux

p p

= nT T − T + nT T

F A mux mux F A mux

p

= 2 nT T − T (7)

F A mux mux

Il ritardo è dunque proporzionale alla radice di n.

4.1 Ottimizzazione del Carry Select Adder

In un Carry Select Adder come definito nel paragrafo precedente, le somme

calcolate dai vari blocchi RCA sono disponibili tutte allo stesso tempo T =

mT , mentre i segnali di selezione dei blocchi dal secondo al p-esimo sono

F A

disponibili solamente dopo un tempo T = mT +qT , con q ∈ [1, (p−1)],

CSA F A mux

perché occorre aspettare che il riporto si propaghi da uno stadio all’altro.

Fatta questa osservazione possiamo migliorare il Carry Select Adder elimi-

nando il vincolo che tutti i blocchi siano della stessa dimensione m. L’idea è

quella di assegnare un carico computazionale maggiore ai blocchi il cui risultato

è richiesto dopo un tempo maggiore.

Facciamo un esempio per chiarire questo concetto. Supponiamo per sem-

plificare i calcoli che T = T = 1. Il segnale C (si veda la Figura 11) è

mux F A 8

disponibile al tempo 5, mentre gli altri segnali in ingresso ai due multiplexer

che esso governa sono già disponibili al tempo 4. Possiamo quindi aumentare la

dimensione del terzo blocco da 4 a 5 senza peggiorare le prestazioni.

In generale ogni stadio avrà il segnale di riporto entrante disponibile dopo un

ritardo T rispetto allo stadio che lo precede. Quindi, se si rimane nell’ipotesi

mux

che T = T le lunghezze ottimali dei blocchi sono

mux F A m, m, m + 1, m + 2, m + 3, . . .

o più in generale m, m, m + q(1), m + q(2), . . . m + q(i), . . .

con q(i) pari all’approssimazione intera di i · T /T

mux F A

Se costruiamo il circuito in questo modo il percorso critico rimane lo stesso,

ma possiamo ridurre la dimensione del primo blocco (che è l’unico sul percorso

critico, come risulta evidente in Figura 11) e, per n sufficientemente grande,

possiamo ridurre il numero di livelli.

Per esempio per n = 64, con T = T = 1, possiamo costruire gli stadi

F A mux

secondo la sequenza: 7 7 8 9 10 11 12

Questo circuito ha 7 stadi, di cui il primo a 7 bit. Il ritardo è quindi (vedi

equazione(5)) T = 7T + 6T = 13

F A mux

10


PAGINE

22

PESO

450.70 KB

AUTORE

Sara F

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
A.A.: 2009-2010

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Sara F di informazioni apprese con la frequenza delle lezioni di Architetture Sistemi Elaborazione e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Napoli Federico II - Unina o del prof Cilardo Alessandro.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Architetture sistemi elaborazione

Architetture Sistemi Elaborazione – Interruzioni
Dispensa
Architetture Sistemi Elaborazione -  Moltiplicatori sequenziali unsigned
Dispensa
Architetture Sistemi Elaborazione – Intel
Dispensa
Architetture Sistemi Elaborazione
Appunto