Reti Logiche 1

Prof. B. Buttarazzi

A.A. 2009/2010

Circuiti Addizionatori

Sommario

Half-Adder

Full-Adder

Circuiti addizionatori

21/06/2010 Corso di Reti Logiche 2009/10 2

Full-Adder

CLA (Carry Look Ahead)

Addizionatori

Gli addizionatori sono dei circuiti logici che

permettono di eseguire l’operazione aritmetica di

somma su rappresentazioni binarie di numeri.

21/06/2010 Corso di Reti Logiche 2009/10 3

Vediamo come si possono realizzare reti

combinatorie in grado di effettuare questo tipo di

operazione su rappresentazioni binarie di numeri.

Cominciamo a considerare il caso semplice di rappresentazioni binarie di

numeri su un solo bit (ossia numeri interi compresi tra 0 e 1).

1 +

1=

1 +

0 =

0 +

1 =

0 +

0 =

Addizione tra 2 bit

21/06/2010 Corso di Reti Logiche 2009/10 4

1 0110

Addizione tra 2 bit

Come si vede la somma 1+1 per poter essere rappresentata richiede 2 bit,

pertanto la tavola di verità che specifica il comportamento di un tale

circuito (addizionatore) é quindi la seguente:

21/06/2010 Corso di Reti Logiche 2009/10 5

1 +

1=

1 0

1 +

0 =

1

0 +

1 =

1

0 +

0 =

0

A B S1 S0

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0

A +

B =

S1 S0

Analizzando la tabella di verità si può notare

che la funzione S0 corrisponde alla tavola di

verità della funzione XOR, mentre la

funzione S1 corrisponde a quella della

funzione AND.

Le due uscite del circuito possono quindi

A B S1 S0

0 0 0 0

0 1 0 1

1 0 0 1

21/06/2010 Corso di Reti Logiche 2009/10 6

Le due uscite del circuito possono quindi

essere ottenute mediante l'uso di queste due

porte elementari agli ingressi A e B.

Questo tipo di circuito con due ingressi,due

uscite una porta AND e una porta XOR viene

normalmente chiamato half adder (semi

addizionatore) per il motivo che scopriremo

tra poco.

1 0 0 1

1 1 1 0

A

B S1

S0

HA

Chiameremo

Half-Adder il

A B S1

R S0

S 0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0

21/06/2010 Corso di Reti Logiche 2009/10 7

1

1 +

1 =

_____

1 0

HA Half-Adder il

circuito

combinatorio in

grado di eseguire

la somma tra 2

bit e generare

Somma (S0) e

Riporto (S1)

A

B R

S

S = A ⊕⊕⊕⊕ B

R = AB

Half Adder (semi addizionatore )

A

Schema logico di un Half-AdderTabella di verità di un Half-Adder

A B S S

21/06/2010 Corso di Reti Logiche 2009/10 8

A

B S1

S0

A B S1 S0

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0 HAA

B

Schema funzionale di un Half-AdderR

S

00+

11=

11

00+

10=

10

00+

01=

01

00+

00=

00

01+

00=

01

01+

11=

100

01+

10=

11

01+

01=

10

Passiamo ora al caso di somma tra due numeri

rappresentati su 2 bit (il risultato sarà rappresentato su 3 bit).

21/06/2010 Corso di Reti Logiche 2009/10 9

11100100 01

10+

11=

101

10+

10=

100

10+

01=

11

10+

00=

10

11+

00=

11

1001110

11+

11=

110

11+

10=

101

11+

01=

100

Il funzionamento del circuito, usando la normale

codifica binaria, può essere definito mediante la

seguente mappa:

21/06/2010 Corso di Reti Logiche 2009/10 10

00 01 11 10

00

110

01

11

10

A1A0

B1 B0

000 001

001 010

011 010

100 011

011 100

010 011

110 101

101

A1A0 +

B1 B0 =

S2 S1 S0

La realizzazione diretta di tale circuito (4 ingressi e 3

uscite) risulta evidentemente molto più complessa di

quella di un semi-addizionatore.

Inoltre, la complessità di realizzazione diventa

rapidamente proibitiva se aumentiamo ulteriormente il

numero n di bit di rappresentazione per gli addendi.

21/06/2010 Corso di Reti Logiche 2009/10 11

00 01 11 10

00

100

01

11

10

A1A0

B1 B0

000 001

001 010

011 010

100 011

011 100

010 011

110 101

101

A1A0 +

B1 B0 =

S2 S1 S0

La soluzione che consente di realizzare in modo semplice ed efficiente

circuiti addizionatori per rappresentazioni su due o più bit consiste nel

modularizzare la realizzazione facendo ricorso all'algoritmo di somma

cifra per cifra.

1 1 1 1

21/06/2010 Corso di Reti Logiche 2009/10 12

1 0 1 0 0 0 1 +

1 1 1 1 1 0 1 =

------------------------------

1 1 0 0 1 1 1 0

Considerando anche i riporti nulli si avrebbe:

1 1 1 0 0 0 1

1 0 1 0 0 0 12 +

modulo

21/06/2010 Corso di Reti Logiche 2009/10 13

Ad ogni passo consideriamo una sola cifra Ai del primo addendo, una

sola cifra Bi del secondo addendo, e l'eventuale cifra "di riporto" ri-1

derivante dall'applicazione dello stesso algoritmo alle cifre precedenti.

1 0 1 0 0 0 12 +

1 1 1 1 1 0 12 =

------------------------------

1 1 0 0 1 1 1 02

L'unica differenza rispetto al circuito semi-addizionatore visto in

precedenza é che ora dobbiamo considerare la presenza di 3 addendi da

un bit (a, b e la cifra di riporto r).

FA

Chiameremo

Full-Adder il

21/06/2010 Corso di Reti Logiche 2009/10 14

1 1 1 0 0 0 1

1 0 1 0 0 0 12 +

1 1 1 1 1 0 12 =

------------------------------

1 1 0 0 1 1 1 02

FA Full-Adder il

circuito

combinatorio

in grado di

eseguire la

somma tra 3

bit e generare

Somma e

Riporto

La specifica di un circuito in grado di effettuare tale somma (chiamato

Full Adder, o sommatore completo a 1 bit) é data dalla seguente tavola

di verità:

r A B R S

0 0 0 0 0 r

21/06/2010 Corso di Reti Logiche 2009/10 15

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

r

A

RFull

Adder

B

S

La sintesi di questo circuito può essere diversa a

seconda delle varie soluzioni

•Sintesi canonica

21/06/2010 Corso di Reti Logiche 2009/10 16

•Sintesi canonica

•Sintesi a tre livelli

Sintesi canonica del Full AdderS = r’. A’. B + r’. A . B’ + r . A’. B’ + r. A . B

R = r’. A . B + r . A’. B + r . A . B’ + r . A . B

r’ r A’ A B’ B

r A B R S

0 0 0 0 0

0 0 1 0 1

21/06/2010 Corso di Reti Logiche 2009/10 17

S

R

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

Sintesi a 3 livelli del Full Adder

r A B R S

0 0 0 0 0

0 0 1 0 1

21/06/2010 Corso di Reti Logiche 2009/10 18

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

Sintesi a 3 livelli del Full Adder

r A B (A⊕B)⊕r R S

0 0 0 0 0 0

0 0 1 1 0 1

0 1 0 1 0 1

S = (A ⊕⊕⊕⊕ B) ⊕⊕⊕⊕ r

La funzione S vale 1 solo se il

numero di 1nella somma (r,A,

B ) è dispari (XOR)

21/06/2010 Corso di Reti Logiche 2009/10 19

0 1 0 1 0 1

0 1 1 0 1 0

1 0 0 1 0 1

1 0 1 0 1 0

1 1 0 0 1 0

1 1 1 1 1 1

Sintesi a 3 livelli del Full Adder

r A B AB+(A+B)r R S

0 0 0 0 0 0

0 0 1 0 0 1

0 1 0 0 0 1

R = AB+(A + B)r

La funzione R risulta vera se

"almeno due ingressi dei tre

assumono il valore 1".

R corrisponde alla funzione

majority.

21/06/2010 Corso di Reti Logiche 2009/10 20

0 1 0 0 0 1

0 1 1 1 1 0

1 0 0 0 0 1

1 0 1 1 1 0

1 1 0 1 1 0

1 1 1 1 1 1

Ricordando che un Half-Adder è un circuito che realizza le funzioni R e S

1

1 +A

B R

R = AB

21/06/2010 Corso di Reti Logiche 2009/10 21

1 =

_____

1 0

B R

S

S = A ⊕⊕⊕⊕ B

Sintesi a 3 livelli del Full AdderS = (A ⊕⊕⊕⊕ B) ⊕⊕⊕⊕ r

1 BitHalf

AdderA

B

1 BitHalfr

R

S

R = AB + (A ⊕⊕⊕⊕ B)r

(A ⊕⊕⊕⊕ B)

AB

(A ⊕⊕⊕⊕ B)r

21/06/2010 Corso di Reti Logiche 2009/10 22

A

B

Sr

R

HalfAdder

r S

Un Full-Adder ad 1 bit è realizzabile connettendo

secondo il seguente schema logico 2 Half-Adder.

21/06/2010 Corso di Reti Logiche 2009/10 23

A

B

r S

Carry

S Carry

1 BitHalfAdder

1 BitHalfAdder

R

Schema funzionale di un modulo Full-Adder

r

A

S

R

Full

Adder

21/06/2010 Corso di Reti Logiche 2009/10 24

RB

Ciascun modulo lavora su 2 cifre binarie A,B ed un riporto r

(proveniente dal modulo che lo precede) e genera una cifra S

come somma ed una cifra R di "riporto" verso il modulo

successivo.

L'operazione di somma tra rappresentazioni binarie su più

cifre, può essere ottenuta combinando in modo opportuno i

moduli base.

21/06/2010 Corso di Reti Logiche 2009/10 25

Schema di connessione di 3 moduli per formare un addizionatore per

addendi rappresentati su 3 bit (e risultato rappresentato su 4 bit).

1 BITFULLADDER

S0

S1

A0B0

A1

0

ADDIZIONATORE PARALLELO

21/06/2010 Corso di Reti Logiche 2009/10 26

1 BITFULLADDER

1 BITFULLADDER

S2

S3

A1B1

A2B2

Questo tipo di addizionatore presenta il grande vantaggio

(derivante dalla modularità della realizzazione) che la

complessità della realizzazione cresce linearmente

all'aumentare del numero di bit degli addendi (in quanto

Osservazione

21/06/2010 Corso di Reti Logiche 2009/10 27

all'aumentare del numero di bit degli addendi (in quanto

l'aggiunta di una cifra comporta esattamente l'aggiunta di un

modulo full-adder).

1 BITFULLADDER

S0

S1

A0B0

A1

0

ADDIZIONATORE PARALLELO

Schema di connessione di 4 moduli per formare un addizionatore per

addendi rappresentati su 4 bit (e risultato rappresentato su 4 bit).

21/06/2010 Corso di Reti Logiche 2009/10 28

S4

1 BITFULLADDER

1 BITFULLADDER

1 BITFULLADDER

S2

S3

A1B1

A2B2

A3B3

Il circuito addizionatore parallelo n- bit progettato può

operare su rappresentazioni binarie di numeri senza segno.

Osservazione

21/06/2010 Corso di Reti Logiche 2009/10 29

Il circuito addizionatore parallelo n- bit può essere usato

anche per operare su rappresentazioni di numeri con segno in

complemento a 2 .

Osservazione

21/06/2010 Corso di Reti Logiche 2009/10 30

L'unica accortezza che occorre osservare in tal caso é quella

di definire il risultato su n bit (senza considerare l‘n+1-esimo

bit di riporto) e accertarsi che il risultato di una operazione di

somma tra numeri dello stesso segno non generi condizioni di

overflow.

Questo tipo di addizionatore detto anche ripple carry

(a propagazione di riporto) presenta un difetto, quello di richiedere un

tempo di assestamento del risultato che cresce linearmente al crescere

del numero di bit della rappresentazione degli addendi.

In particolare, a causa della propagazione del riporto il tempo di

Osservazione

21/06/2010 Corso di Reti Logiche 2009/10 31

In particolare, a causa della propagazione del riporto il tempo di

assestamento del segnale per la cifra più significativa sarà n volte più

grande di quello per la cifra meno significativa,infatti per generare il

risultato occorre aspettare che il riporto via via generato attraverso tutti i

moduli full-adder.

1 BITFULLADDER

S0

S1

A0B0

A1

0

ADDIZIONATORE PARALLELO

21/06/2010 Corso di Reti Logiche 2009/10 32

S4

1 BITFULLADDER

1 BITFULLADDER

1 BITFULLADDER

S2

S3

A1B1

A2B2

A3B3

Addizionatore per numeri binari rappresentati su 4 bit (e

risultato rappresentato su 5 bit) ottenuto dalla connessione di 4

moduli FA.

1 BITFULLADDER

Z0

Z1

X0Y0

X1

0

Esempio di RC: ADDIZIONATORE PARALLELO

21/06/2010 Corso di Reti Logiche 2009/10 33

Z4

1 BITFULLADDER

1 BITFULLADDER

1 BITFULLADDER

Z2

Z3

X1Y1

X2Y2

X3Y3

I limiti dell’addizionatore parallelo (ripple carry) legati al tempo

di assestamento del risultato (che cresce linearmente al crescere

del numero di bit della rappresentazione degli addendi) potrebbero

essere rimossi se riuscissimo a realizzare una rete combinatoria

che sia in grado di calcolare simultaneamente le cifre di riporto

per ogni coppia di addendi (carry look ahead).

21/06/2010 Corso di Reti Logiche 2009/10 34

per ogni coppia di addendi (carry look ahead).

1 BITFULLADDER

Z0

Z1

X0Y0

X1

0

ADDIZIONATO PARALLELO CLA

R0

R1

Dotato di un

circuito logico

aggiuntivo

CLA

21/06/2010 Corso di Reti Logiche 2009/10 35

1 BITFULLADDER

1 BITFULLADDER

1 BITFULLADDER

Z2

Z3

X1Y1

X2Y2

X3Y3 Z4

R2

R3

che calcola in

anticipo tutti i

riporti e li

fornisce

simultanea-

mente a

ciascun

modulo “Full-

Adder”

R A B R S

Per comprendere il principio che è alla base della logica ausiliaria di calcolo del riporto

nel CLA analizziamo nuovamente la tabella di verità e vediamo in quali condizioni può

essere generato ciascun riporto.

Dalla osservazione della tabella si vede che il riporto Ri+1 (che andrà ad alimentare la

somma tra Ai+1.Bi+1 viene generato se (Aie Bi in ingresso valgono contemporaneamente

1)Ai.Bi =1 oppure se

al passo precedente si era verificato un riporto (Ri =1) e (Ai + Bi)=1 ovvero

(Ai + Bi).Ri.

21/06/2010 Corso di Reti Logiche 2009/10 36

Ri Ai Bi Ri+1 Si

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

Ri+1 = Ai.Bi + (Ai + Bi).Ri.

Ri Ai Bi Ri+1 Si

mentre Si vale 1 solo se il numero di 1nella tabella (Ai, Bi,Ri ) è

dispari (XOR)

21/06/2010 Corso di Reti Logiche 2009/10 37

Ri Ai Bi Ri+1 Si

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

quindi

Si = Ai ⊕ Bi ⊕ Ri

Ri+1 = Ai.Bi + (Ai + Bi).Ri.

Si = Ai ⊕ Bi ⊕ Ri

21/06/2010 Corso di Reti Logiche 2009/10 38

Ri+1 = Ai.Bi + (Ai + Bi).Ri.

i termini G (Generate- che genera il riporto) e P

(Propagate - che causa la propagazione del riporto)

Indicando nella formula:

21/06/2010 Corso di Reti Logiche 2009/10 39

(Propagate - che causa la propagazione del riporto)

Gi = Ai.Bi

Pi. = (Ai + Bi)

si ha che

Ri+1 = Gi + Pi.Ri

mentre

Si = Ai ⊕ Bi ⊕ Ri = Pi ⊕ Ri.

Ri+1 = Gi + Pi.Ri

Interpretazione

Il riporto Ri+1 o è generato (Ai Bi=1) ex-novo oppure è propagato Ri attraverso la funzione Pi

oppure entrambi

Ri Ai Bi Ri+1 Si

0 0 0 0 0

0 0 1 0 1

21/06/2010 Corso di Reti Logiche 2009/10 40

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

Applicando le espressioni di calcolo del riporto a un addizionatore a 4-bit e facendo le

sostituzioni :

R1 = G0 + P0.R0 = A0.B0 + (A0 + B0) .R0

R2 = G1 + P1.R1 = G1 + P1.G0 + P1.P0.R0 = A1.B1 +

(A1 + B1) A0B0 +

(A1 + B1) (A0 + B0) R0

R3 = G2 + P2. R2 = G2 + P2. G1 + P2.P1.G0 + P2.P1.P0.R0 =

21/06/2010 Corso di Reti Logiche 2009/10 41

R3 = G2 + P2. R2 = G2 + P2. G1 + P2.P1.G0 + P2.P1.P0.R0 =

R4 = G3 + P3.R3 = G3 + P3.G2 + P3.P2.G1 + P3P2.P1.G0 + P3P2.P1.P0.R0 =

R3 = G2 + P2. R2 = G2 + P2. G1 + P2.P1.G0 + P2.P1.P0.R0 =

A2.B2 +

(A2 + B2) A1B1 +

(A2 + B2)(A1 + B1) A0.B0

(A2 + B2)(A1 + B1) (A0 + B0) R0

R4 = G3 + P3.R3 = G3 + P3.G2 + P3.P2.G1 + P3P2.P1.G0 + P3P2.P1.P0.R0 =

A .B +

21/06/2010 Corso di Reti Logiche 2009/10 42

A3.B3 +

(A3 + B3) A2B2 +

(A3 + B3)(A2 + B2) A1.B1

(A3 + B3)(A2 + B2) (A1 + B1) A0B0

(A3 + B3)(A2 + B2) (A1 + B1) (A0 + B0) A0B0

emerge che è possibile generare una rete combinatoria, non più modulare, denominata

carry look ahead che tramite circuiti opportuni è in grado di calcolare qualunque

riporto (carry) Ri .

21/06/2010 Corso di Reti Logiche 2009/10 43

Si noti però la perdita di modularità (derivante dal fatto che ogni blocco che genera un

carry è diverso dagli altri) derivante da questa tecnica può comportare un aggravio di

tempo in fase di progetto del circuito.

La figura mostra lo schema di una possibile implementazione per sommatore CLA

21/06/2010 Corso di Reti Logiche 2009/10 44