Sommatori

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 1

SOMMATORI

DIEET HALF-ADDER HA A B C S

1

0

1

1

0

1

0

1

0

1

1

0

0

0

0

0

C

S

B

A

S = A⊕B C = AB

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 3

FULL-ADDER FA A B C_o S C_i

1

0

0

1

0

1

1

0

0

+

0

1

1

0

0

1

1

1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 C_o S C_i B A DIEET FULL-ADDER FA A B C_o S C_i 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 C_o S C_i B A    + + = + + + = ⊕ ⊕ = AB BC AC C ABC C B A C B A C B A C B A S i i o i i i i 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 C_o S C_i B A BC_i AC_i AB

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 5

SEGNALI GENERATE (G), DELETE (D), E PROPAGATE (P)

Generate 1 1 1 1 1 Generate 1 0 0 1 1 Propagate 1 0 1 0 1 Propagate 0 1 0 0 1 Propagate 1 0 1 1 0 Propagate 0 1 0 1 0 Delete 0 1 1 0 0 Delete 0 0 0 0 0 C_o S C_i B A      ⊕ = = = B A P AB G B A D







+

=

+

=

⊕

=

⊕

=

i o i i

PC

G

C

C

C

C

P

C

S

S

"

'

'

HA HA A B C_i C_o S C’ S’ C” D, G e P dipendono soltanto da A e B DIEET

i

i

P

C

C

B

A

S

=

⊕

⊕

=

⊕

G

P

C

AB

B

A

B

A

C

AB

B

A

C

C

i

i

i

o

+

=

=

+

+

=

+

+

=

(

)

(

)

SEGNALI GENERATE (G), DELETE (D), E PROPAGATE (P)

NOTA: Il segnale propagate P può anche essere definito come OR di A e B.

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 7

SOMMATORE RIPPLE-CARRY

FA FA FA FA

A_o B_o A₁ B₁ A₂ B₂ A₃ B₃

S_o S₁ S₂ S₃

C_i,0 C_{o,0 C}

o,1 Co,2 Co,3

t_c t_c t_c t_c t_s t_c t_c t_s t_s t_s S₀ S₁ S₂ S₃

Nel caso peggiore:

tadder = (N – 1)tc+ ts

t_adderè funzione lineare di N

E’ importante ridurre t_c

N = 4 DIEET Caso peggiore ESEMPIO # 1

0

1

1

1

1

1

1

1

1

0

0

1

0

0

0

0

A=

B=

0

1

2

bit

₃

₄

₅

₆

₇

T

_SUM

=7 t

_c

+ t

_S

C

₀

= 1

T

CARRY

=8 t

c

P

P

P

G

P

P

P

P

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 9

0

1

1

1

1

0

1

1

1

0

0

1

0

0

1

0

A=

B=

0

1

2

bit

₃

₄

₅

₆

₇

4 t

_c

+ t

_S

= T

_SUM

2 t

_c

+ t

_S

= T

_SUM

t

_c

+ t

_S

= T

_SUM

2 t

_c

= T

_CARRY

C

₀

= 1

_C

4

= 0

C

6

= 1

ESEMPIO # 2

P

P

P

G

D

P

G

P

DIEET    + + = + + + = ⊕ ⊕ = AB BC AC C ABC C B A C B A C B A C B A S i i o i i i i FA A B C_o S C_i FULL-ADDER FCMOS d d d 1 10 0 1 0 d 11 d 0 d d 01 1 d 1 0 00 10 11 01 00 AB C_iC_o

)

(

_i o i

C

A

B

C

ABC

S

=

+

+

+

1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 C_o S C_i B A

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 11

A B B A Ci Ci A X VDD VDD A B Ci A B B VDD A B Ci Ci A B A B Ci Co VDD S FULL-ADDER FCMOS

)

(

_i

o

i

C

A

B

C

ABC

S

=

+

+

+

AB

B

A

C

C

_o

=

_i

(

+

)

+

DIEET A B B A Ci Ci A X VDD VDD A B Ci A B B VDD A B Ci Ci A B A B Ci Co VDD S • Occorrono 28 transistor • Molti PMOS in serie • C₀=2C_diff+ 6C_gate • Il circuito del carry ha un

invertitore in uscita • t_s> t_c(non è un problema) • I transistori pilotati da C_i

sono posti vicino all’uscita perché sono inseriti nei percorsi critici.

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 13

PROPRIETA’ INVERTENTE C_o

FA

FA

A B A B S _S C_i C_o C_i

INGRESSO: l’ingresso è complementato

USCITA: l’uscita è ottenuta attraverso un invertitore

1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 C_o S C_i B A DIEET FA’ A B C_i Co S FA” A B C_i Co S PROPRIETA’ INVERTENTE

Full adder senza invertitore nel circuito del carry

Full adder senza invertitore sia nel circuito del carry sia in quello della somma

FA’ FA” FA’

A_o B_o A1 B1 A₂ B₂ A3 B3

S_o S₁ S₂ S₃

C_i,0 C_{o,0 C}

o,1 Co,2 Co,3

FA”

Utilizzando la proprietà invertente è possibile eliminare tutti gli invertitori nella catena del carry.

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 15

A _B C_in C_in A B A B V_DD A B MIRROR ADDER X = C_o

)

(

A

B

C

B

A

C

B

C

A

B

A

C

X

=

_o

=

+

_in

+

_in

=

+

_in

+

Semplificazione della rete di pull-up del circuito del carry

C_in VDD B B A _C o A DIEET A B Cin X A B C_in X A B C_in A B Cin V_DD S A B Cin X A B Cin MIRROR ADDER

Semplificazione della rete di pull-up del circuito della somma

)

)(

(

A

B

C

in

X

A

B

C

in

S

=

+

+

+

in

in

X

A

B

C

C

B

A

S

=

(

+

+

)

+

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 17

MIRROR ADDER A A Cin V_DD B B A B A B A B C_in V_DD A B Cin VDD A B Cin A B C_in C_o S Generate Delete

Propagate (P=A+B) 24 transistori

DIEET

• Reti PDN e PUN simmetriche

• Nel circuito del carry al più due MOS in serie

• I MOS connessi a C

_i

sono posti vicini all’uscita

MIRROR ADDER A A Cin V_DD B B A B A B A B Cin VDD A B C_in VDD A B C_in A B Cin Co S

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 19

• I MOS del circuito del riporto devono essere ottimizzati per ottenere la massima velocità.

• I MOS del circuito della somma possono essere di dimensioni minime. Nel disegnare il layout della cella, l’obiettivo principale è quello di minimizzare la capacità del nodo C_o.

• L’uscita del circuito del carry pilota due capacità di gate interne e sei capacità di gate del FA successive.

• Le dimensioni dei transistori del percorso del riporto vengono aumentate rispetto a quelle dei transistori del circuito della somma di tre o quattro volte. A A Cin V_DD B B A B A B A B Cin V_DD A B C_in V_DD A B C_in A B Cin Co S MIRROR ADDER 12 12 12 6 6 6 4 4 2 2 4 4 4 4 2 2 2 2 6 6 6 3 3 3 µµµµn µµµµp =2 DIEET

FULL ADDER IN LOGICA PASS TRANSISTOR

AB

G

=

B

A

P

=

⊕

i

C

P

S

=

⊕

i o

G

P

C

C

=

+

•

SETUP SOMMA E CARRY C_i C₀ S A B

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 21

S = P

⊕

C

_i P P A C_i Co P C_o

C

_o

= G + P

⋅

C

_i Se P = A ⊕B = 0, A = B. C_o = G C_o= A (o B)

Generazione della sommae del riporto

P P Cin C_in S S P

t_carrye t_sumsono uguali: questa caratteristica è utile, per esempio, nei moltiplicatori array

S = P

⋅

C

_i

+ P

⋅

C

_i

FULL ADDER IN LOGICA PASS TRANSISTOR

DIEET A A B B P P

XOR

XNOR

A

Generazione del segnale propagate

1

0

1

1

0

1

0

1

0

1

1

0

1

0

0

0

XNOR

XOR

B

A

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 23

A B P Ci VDD A A A VDD Ci A P A B VDD V_DD Ci Ci Co S Ci P P P P P

Generazione della somma

Generazione del carry Setup

24 transistori FULL-ADDER IN LOGICA PASS TRANSISTOR

DIEET

SETUP

SOMMA CATENA DEL CARRY

A B

G P

C_o,0 C_o,1 C_{o,2 C}

o,N-2 Co,N-1

S₀ S₁ S₂ S_N-1

C_i,0

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 25

C

_i

P

P

G

D

VDD

C

_o

P = 1

D = 1

G = 1

P = 1 C

out

= C

in

D = 1 C

out

= 0

G = 1 C

out

= 1

SOMMATORE MANCHESTER CARRY-CHAIN

Implementazione statica del circuito di generazione del carrry

C

_o

= G + P

⋅

C

_i DIEET

C

_i

P = G = 0

Alta impedenza

P

CLK

V_DD

C

_o

CLK

G

G = 1

P = 1

L’uscita è precaricata a V_DD P=1 (G=D=0) ⇒C_o = C_in G = 1 (P=D=0) ⇒C_o = 0 D=1 (G=P=0) ⇒ C_o= 1

Il circuito genera il carry in forma negata

Il segnale delete non è necessario perché l’uscita è precaricata a V_DD SOMMATORE MANCHESTER CARRY-CHAIN Implementazione dinamica del circuito di generazione del carry

A

A

A

B

A

G

G = A B

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 27

C

₀

C

_i

P

₀

CLK

V_DD

C

_o

P

₁

P

₂

P

₃

G

₀

G

₁

G

₂

G

₃

CLK

C

₁

C

₂

C

3

SOMMATORE MANCHESTER CARRY-CHAIN Implementazione dinamica della catena del riporto per N = 4

DIEET

R

₁

R

₂

R

₃

R

₄

R

₅

C

₁

C

₂

C

₃

C

₄

C

₅ RC N N R C t i j j N i i p 2 ) 1 ( 69 , 0 69 , 0 1 1 + =         ∑ ∑ = = = tpè una funzione quadratica di N buffer p t M N RC M N t       − + + = 1 2 1 69 ,

0 Aggiungendo un buffer ogni M

stadi si rende t_puna funzione lineare di N

RC

t

M

_opt buffer

69

,

0

2

=

Per le moderne tecnologie M_opt=3÷4 SOMMATORE MANCHESTER CARRY-CHAIN

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 29

OTTIMIZZAZIONE DELL’ARCHITETTURA DI UN SOMMATORE

Sommatore carry-bypass

Sommatore linear carry-select

Sommatore square-root carry-select

DIEET SOMMATORE CARYY-BYPASS

FA

P₀

FA

FA

FA

P₁ P2 P₃ G₀ G₁ G₂ G₃ C_{o,0 C} C_o,2 o,1 C_o,3 BP = P₀P₁P₂P₃ C_i,0 S₀ S₁ S_{2 S} 3 Se BP = 1 C_o,3= C_i,0

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 31

catena del riporto Setup Bit 0–3 Somma M bit tsetup t_s Setup Bit 4–7 Somma t_mux Setup Bit 8–11 Somma Setup Bit 12–15 Somma catena catena catena del riporto del riporto del riporto

SOMMATORE CARRY-BYPASS s c mux c setup add

t

M

t

t

M

N

Mt

t

t



+

−

+











−

+

+

=

1

(

1

)

G P P P

P P P P

P P P P

P P P P

BP = 1 BP = 1 BP = 1 BP = 0

Caso peggiore

DIEET

Esempio: caso peggiore (16 bit)

0

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

P

G

P P

P P P P

P P P P

P P P P

4 t

_C

t

_MUX

_t

MUX

t

MUX

BP=1

BP=1

BP=0

BP=1

t

MUX

3 t

_C

t

_S

T

_CARRY

= t

_SETUP

+ 4

⋅⋅⋅⋅

t

_C

+ 4

⋅⋅⋅⋅

t

_MUX

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 33

Esempio: caso particolare (16 bit)

0

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

1

1

0

1

0

1

0

1

0

1

0

1

P

G

P P

P P P P

P P G P

P P P P

4 t

C

t

MUX

t

MUX

BP=0

t

_MUX

2 t

_C

T

_CARRY

= t

_SETUP

+ 2

⋅⋅⋅⋅

t

_C

+ 2

⋅⋅⋅⋅

t

_MUX

T

SUM

= t

SETUP

+ 4

⋅⋅⋅⋅

t

C

+ 2

⋅⋅⋅⋅

t

MUX

+ 2

⋅⋅⋅⋅

t

C

+ t

S

2 t

_C

t

MUX

t

_S

DIEET

Scelta del valore ottimo di M

0

)

(

2

+

=

−

=

_c

_mux

_c

sum

t

M

N

t

t

T

dM

d

s

c

mux

c

setup

sum

t

M

t

t

M

N

Mt

t

T



+

−

+











−

+

+

=

1

(

1

)

c mux opt

t

Nt

M

2

=

Se

t

_mux

≅

t

_c

2

N

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 35

N t_p ripple adder bypass adder 4..8 SOMMATORE CARRY-BYPASS

Confronto tra i ritardi di un sommatore ripple-carry e di un sommatore carry-bypass

Per piccoli valori di N, il ritardo dei multiplexer rende il sommatore carry-bypass meno efficiente del sommatore ripple-carry Supponiamo: t_s= t_c= t_mux= t_setup= T Se N>>M Carry-bypss T_sum= 2MT + T(N/M) Ripple carry T_sum= NT DIEET Setup (P&G)

Calcola il riporto per Co,k-1=0

Multiplexer

Generazione della somma

Co,k-1 Co,k+3

"0"

"1"

P,G

Vettore dei riporti

Calcola il riporto per Co,k-1=1

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 37

0 1 Somma Multiplexer 1-Carry 0-Carry Setup

C_i,0 C_o,3 C_o,7 C_o,11 C_o,15

S0–3

Bit 0–3 Bit 4–7 Bit 8–11 Bit 12–15

0 1 Multiplexer 1-Carry 0-Carry Setup S4–7 0 1 Multiplexer 1-Carry 0-Carry 0-Carry Setup S8–11 0 1 Multiplexer 1-Carry Setup S12–15

Somma Somma Somma

SOMMATORE LINEAR CARRY-SELECT

mux c setup carry s mux c setup add

t

M

N

Mt

t

t

t

t

M

N

Mt

t

t

+

+

=

+













+

+

=

DIEET 0 1 Somma Multiplexer 1-Carry 0-Carry Setup

Ci,0 Co,3 Co,7 Co,11 Co,15

S_0–3

Bit 0–3 Bit 4–7 Bit 8–11 Bit 12–15

0 1 Multiplexer 1-Carry 0-Carry Setup S_4–7 0 1 Multiplexer 1-Carry 0-Carry 0-Carry Setup S_8–11 0 1 Multiplexer 1-Carry Setup S_12–15

Somma Somma Somma

(1) (1) (5) (5) (5) (5) (5) (6) (7) (8) (9) (10) SOMMATORE LINEAR CARRY-SELECT

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 39

Setup "0" Carry "1" Carry Multiplexer Somma "0" "1" Setup "0" Carry "1" Carry Multiplexer Somma "0" "1" Setup "0" Carry "1" Carry Multiplexer Somma "0" "1" Setup "0" Carry "1" Carry Multiplexer Somma "0" "1"

Bit 0-1 Bit 2-4 Bit 5-8 Bit 9-13

S0-1 S2-4 S5-8 S9-13 Ci,0 (4) (5) (6) (7) (1) (1) (3) (4) (5) (6) Mux Somma S14-19 (7) (8) Bit 14-19 (9) (3)

SOMMATORE SQUARE-ROOT CARRY SELECT

DIEET

Calcolo del ritardo di propagazione

Supponiamo che ogni blocco contenga un bit in più del precedente













−

+

=

−

+

=

−

+

+

+

+

+

+

+

+

+

=

2

1

2

2

)

1

(

)

1

(

...

)

3

(

)

2

(

)

1

(

2

M

P

P

P

P

MP

P

M

M

M

M

M

N

Se M<<N (ad esempio M=2 e N = 64)

2

2

P

N

≅

P

≅

2

N

s mux c setup add

t

Mt

N

t

t

t

=

+

+

(

2

)

+

N: numero dei bit P: numero dei blocchi

M: numero di bit nel primo blocco

DIEET

Università di Palermo Elettronica digitale II Giuseppe Caruso 41

Square root select Linear select Ripple adder 20 40 N tp (i n u n it d e la y s ) 60 0 10 0 20 30 40 50