Elettronica deiSistemi Digitali LAUniversità di Bologna,II Facoltà di Ingegneria, Sede di Cesena

Aritmetica ComputazionaleF.Campi, A. Romani

A.a. 2006-2007

Aritmetica Computazionale• Si studiano possibili architetture hardware (ASIC) per

realizzare operazioni matematiche su segnali composti da stringhe di bit, in modo da soddisfare le specifiche fisiche che ci si propone (Funzionalità, Timing, Power, Area):

• RAPPRESENTAZIONI: – Unsigned (Codifica binaria di numeri positivi)– Two’s complement (rappresentazione in complemento a due)

• OPERAZIONI:– Addizione– Moltiplicazione– (Divisione, Radice Quadrata, etc) -> Non verranno trattate

Codifica Binaria:

N = { bn ....... b0} dove bi rappresenta il numero bi * 2i

Tipicamente n puo’ essere: 8 -> Bytes, 16-> Half Word, 32->Word o piu’.

Nel caso di architetture programmabili (Microprocessori, DSP) N e’ fissato, mentre nel caso degli ASIC viene regolato a seconda della precisione voluta in modo da ottimizzare le risorse utilizzate,

ES: 11 = { 1*8 + 0*4 + 1*2 + 1*1 } = 23 + 21 + 20 = { 0 0 0 0 1 0 1 1 }

Complemento a 2: In modo da facilitare la esecuzione della sottrazione, I numeri negativi sono espressi attraverso la seguente formula:

-n = (ñ) + 1

ES: -11 = -1 * {0 0 0 0 1 0 1 1} + 1 = { 11110100 } +1 = 11110101

Complemento a 2

• La rappresentazione binaria a N bit in complemento a 2 di un numero X è definita in questo modo:

0X se X2X2

0X se XX

NN

00000…0 11111…110000…0

0 1 2 2N-1-1

01111…1

-2N-1 -1

Complemento a 2La operazione di complemento a 2 e’ realizzata attraverso una negazione bit a bit (o inverto ogni bit oppure lo metto in XOR con 1)

iiii

ii

1N

0i

1N

0i

1N

0i

ii

ii

i

1N

0i

ii

N

i1N

0i

iNN

i1N

0i

i

x)x1(0)x1(1x se

1)x1(0x se

1X12x112x21

2x1)12(

2x2X2X

0X sia 2xX

Moltiplicazione (potenze del 2)

• Moltiplicazione per potenze del 2

1k

0j

jj1N

kjkj

ki1N

0i

ik

1N

0i

ii

k

i1N

0i

i

202x

abili)rappresent sononon bit ultimi (gli

)1N( 1knj1Ni ,kj0i[k ij pongo

2x22x2X

2xX sia

0N-1x0x1

xN-1

N-1 0k-1k

000x0xN-k-1

Divisione (potenze del 2)

• Divisione per potenze del 2

j1kN

0jkj

ki1N

0i

ik

1N

0i

iik

i1N

0i

i

2x

1knj1Ni ,0kj0i[k ij pongo

2x22x2

X

2xX sia

0N-1x0x1

xN-1

N-10/1 0/1 xN-1 xkxk+1

Sign extension0 con unsignedxN-1 con signed

Sommatori

OBIETTIVO: Analizzare delle architetture gate level che descrivano l’operazione di somma tra vettori di bit:

Problema: Scegliere il corretto TRADE-OFF (Compromesso) tra risorse fisiche (Area e Consumo) e velocita’ di elaborazione

{an-1 … a0}

{bn-1 … b0}+ {sn-1 … s0}

Si vuole realizzare quindi la operazione seguente:

1 0 1 0 1 + Vogliamo scomporre la operazione0 0 0 0 1 = su un singolo bit, sara’ poi

sufficiente_________ replicare N volte la stessa logica1 0 1 1 1

Si puo’ scomporre dunque il calcolo in due funzioni logiche a bits, il calcolo della somma (Sum) e del riporto (Carry Out): In generale, la operazione e’ descritta dalle seguenti mappe di Karnaugh per S e Co.

Sommatori Ripple Carry

1

Half-AdderA/B 0 1

0 0 1

1 1 0

A/B 0 1

0 0 0

1 0 1

SUM Carry Out

Si ottiene quindi

S= A XOR B Co = A and B

Tale Circuito, definito HALF ADDER, somma soltanto 2 bit, mentre gli stadi successivi dovranno sommare anche il CO dei precedenti stadi. Sara’ quindi necessario un circuito a 3 ingressi.

Full-Adder

\ AB

Cin

00 01 11 10

0 0 1 0 1

1 1 0 1 0

SUM Carry Out

\ AB

Cin

00 01 11 10

0 0 0 1 0

1 0 1 1 1

Full Adder: Calcolo di Sum e Cout

cba

bacbac

babacbabac

cbacbacbacbaSum

)(

)(*)(*

)**(*)**(*

********

)(*)(*

))(*)((*)(*)(*

bacbbbabaaac

babacabbacabbac

Nota:

c*ac*bb*aCout

c*)ba(b*a

Full Adder, schema logico

a

b Sum

Cout

Cin

Sommatori Ripple-Carry

RIPPLE-CARRY = Propagazione del Carry

Vantaggi:• Struttura regolare

Svantaggi:• Il ritardo introdotto e’ proporzionale al numero di stadi, e quindi al

numero di bit degli operandi. (ogni bit di somma può essere calcolato solo quando è disponibile anche il suo carry-in)

a b

CinCout

Sum

a b

CinCout

Sum

a b

CinCout

Sum

a b

CinCout

SumC0

A0 B0A1 B1A2 B2AN-1 BN-1

S0S1S2SN-1

C1C2CN

Prestazioni Sommatore Ripple-Carry

a b

CinCout

Sum

a b

CinCout

Sum

a b

CinCout

Sum

a b

CinCout

SumC0

A0 B0A1 B1A2 B2AN-1 BN-1

S0S1S2SN-1

C1C2CN

)N(Ott)1N(t SUMCARRYADDER

Il cammino critico (cioè il ritardo di propagazione del caso peggiore) è caratterizzato da questa

espressione:

Il ritardo di propagazione cresce linearmente con N.

Anche il numero di sommatori (risorse) cresce linearmente con N.

Sommatore Carry-Bypass

• Sommatore Ripple-Carry: ritardo O(N) [lento]

• Idea: raggruppare i FA a gruppi di M

• aggiungere una logica di “bypass”

ab

Cin Cout

Sum

ab

Cin Cout

Sum

ab

Cin Cout

Sum

ab

Cin Cout

SumC0

A0B0 A1B1 A2B2AM-1BM-1

S0 S1 S2SM-1

C1C2 CM

FA0 FA1 FA2 FAM-1

Cout

0

1

SEL

Sommatore Carry Bypass

• Avrò dunque N/M gruppi da M full-adder connessi come segue:

• Come controllare i mux?– il mux di un blocco dovrà attivarsi tutte le volte che il

riporto si propaga da Ci a CM

Il riporto si propaga in tutte le configurazioni di A e B tali che

cioè quando CM dipende dal solo Ci (e non dagli ingressi A, B)

C0

B0 A0 B1 A1 B2 A2 BM-1 AM-1

BM+1 AM+1BM AMB2M-1 A2M-1

S0 S1 S2 SM-1

SM SM+1 S2M-1

BN-1 AN-1

SN-1

Cout

Mi CC

Condizione di propagazione• Per un F.A. la condizione di propagazione è la

seguente:

(cioè Cout non dipende dagli ingressi)

• Per il blocco di M f.a. avrò propagazione da C0 a CM se: P0P1P2…PM-1 = 1

Carry Out Full Adder

\ AB

Cin

00 01 11 10

0 0 0 1 0

1 0 1 1 1

CC cuiin voltele tutte1)B,A(P iout

P=1 P=1P=0 P=0

P = A xor B

Sommatore Carry Bypass

• Quindi completiamo lo schema:

• Qual è il cammino critico?– da A0, B0 a CM [se avessi propagazione C0CM allora il mux

selezionerebbe l’altro cammino: + veloce, non è caso peggiore]

– attraverso tutti i mux

– nell’ultimo gruppo attraverso i f.a. fino a SN-1

C0

B0 A0 B1 A1 B2 A2 BM-1 AM-1

BM+1 AM+1BM AMB2M-1 A2M-1

S0 S1 S2 SM-1

SM SM+1 S2M-1

BN-1 AN-1

SN-1

Cout

P0 P1 P2…PM-1

PM PM+1…P2M-1

…PN-2PN-1

SUMMUXCARRYSEL

SUMCARRYMUXCARRYSELADDER

tt1M

Nt)1M2(t

tt1Mt1M

NtMtt

Sommatore Carry-Bypass• L’espressione del ritardo di propagazione sul

cammino critico, oltre che funzione di N, dipende da M

SUMMUXCARRYSELADDER tt1M

Nt)1M2(tt

ripple-carry adder

N

carry bypass adder

4 8

tADDER

Sommatore Carry-Bypass

• Esiste un valore ottimale di M? Posso dunque raggruppare i F.A. secondo un criterio ottimale?

• Definiamo:

• E andiamo a verificare quando:

CARRY

SUMMUXCARRYSEL

CARRY

ADDER*ADDER

CARRY

MUX

t

)tttta

M

NM2

t

t)N,M(t ,

t

ta

0M

t *ADDER

Sommatore Carry-Bypass

2a

M

N 0

M

N2 0

M

t 22

*ADDER

CARRY

MUX

*opt,ADDER

opt

t

tN22aN22

2aN

aN

2

aN2)N(t

2

aNM

SUMMUXCARRYCARRYMUXSELopt,ADDER ttttt N22tt

Carry-Select Adder• Idea: invece di attendere, per il calcolo dei riporti, l’arrivo del carry in

degli stadi precedenti effettuiamo i calcoli nei 2 casi possibili (Cin = ‘0’, Cin = ‘1’)

• Utilizziamo questa notazione

ab

Cin Cout

Sum

ab

Cin Cout

Sum

ab

Cin Cout

Sum

ab

Cin Cout

SumC0

A0B0 A1B1 A2B2AM-1BM-1

S0 S1 S2SM-1

C1C2 CM

FA0 FA1 FA2 FAM-1

C0 CM

A0..M-1B0..M-1

S0..M-1

M M

M

Carry-Select Adder• Possiamo definire questa struttura:

0 C2M(0)

AM..2M-1BM..2M-1

SM..2M-1(0)

M M

M

1

C2M(1)

AM..2M-1BM..2M-1

SM..2M-1(1)

M M

M

0

1

0

1

SM..2M-1

C2M 0C2M

(0)

AM..2M-1BM..2M-1

SM..2M-1(0)

M M

M

1

C2M(1)

AM..2M-1BM..2M-1

SM..2M-1(1)

M M

M

0

1

0

1

SM..2M-1

C2M

CN(0)

CN(1)

0

1

CN

SN-M-2..N-1(1)

0

1

SN-M-2..N-1

SN-M-2..N-1(0)

C0CM

A0..M-1B0..M-1

S0..M-1

M

M M

ATTENZIONE: Rispetto agli altri sommatori il numero di risorse aumenta! mux adder full

1

M

N2MN2M1

M

NM2

Carry-Select Adder

• Effettuo il calcolo nei due casi possibili:

– Cin = 0, Cin = 1 (uno dei 2 sarà necessariamente quello giusto)

• Ogni gruppo di F.A. inizia il calcolo da subito

• Sulla base del riporto dello stadio precedente SELEZIONO un risultato già pronto (NON CALCOLO! perchè i risultati sono già pronti…)

Sommatore Carry-Select

• Vediamo il ritardo di propagazione del cammino critico:

sum,MUXMUXCARRYADDER tt2M

NMtt

Sommatore Carry-Select

• Il cammino critico ha questo ritardo:

• Definiamo:

• Risulta:

• Vediamo quale valore di M ottimizza il ritardo peggiore:

CARRY

MUX

CARRY

ADDER*ADDER t

ta,

t

tt

MUXCARRYsum,MUXMUXCARRYADDER t1M

NMttt2

M

NMtt

a1M

NMt*

ADDER

MUXCARRYMUXopt,ADDER

*

opt,ADDER

opt2

*ADDER

t1N2ttt

1N2at

aNM0aM

N1

M

t

Sommatore Carry-Select

• E’ possibile ottimizzare i tempi di calcolo utilizzando un semplice accorgimento:

• In questo modo viene effettuato il calcolo di un bit di somma in più mentre avviene la propagazione attraverso i mux degli stadi precedenti

4 4

4

5

5

6

6

Sommatori Carry-Lookahead

iiiiii

iiii

BAPCPS

CBAS

se

)BA(*CB*AC 1i1i1i1i1ii

1i1i1i1i1i1ii C*AC*BB*AC

Si ricordi il calcolo per la determinazione del Carryout nel full-adder:(il riporto in ingresso a una colonna dipende dalla colonna precedente)

Si puo’ scrivere come

Possiamo definire GENERATE e PROPAGATE:

)BA(BAP

BAG

iiiii

iii

Ci di calcolo del fini ai

Possiamo altresì scrivere:

Risulta: 1i1i1ii CPGC

Sommatori Carry-Lookahead

0012301231232334

00120121223

0010112

0001

CPPPPGPPPGPPGPGC

CPPPGPPGPGC

CPPGPGC

CPGC

Il calcolo dei diversi carry out presenti nel sommatore a 4 bit puo’ esserequindi descritto secondo l’algoritmo seguente:

Sommatory Carry-Lookahead• Possiamo scrivere:

• Lo schema sarà di questo tipo:...

CPPPPGPPPGPPGPGC

CPPPGPPGPGC

CPPGPGC

CPGC

0012301231232334

00120121223

0010112

0001

Carry lookahead

A0 B0 S0

P0 G0

C0

A1 B1 S1

P1 G1

C1

A2 B2 S2

P2 G2

C2

AN-1 BN-1 SN-1

PN-1 GN-1

CN-1

Sommatori Carry-Lookahead

Anticipando il calcolo del carry secondo quanto descritto e’ possibile Realizzare il seguente sommatore Carry-Lookahead.

Lo svantaggio principale di questa architettura e’ che le equazioni logicheDiventano troppo complesse oltre l’ordine 4. Di conseguenza i CLA vengono

utilizzati di solito in blocchi gerarchici.

p3 p0p2 p1

s3 s2 s1s0

G3 P3 G2 P2 G1 P1 G0 P0

C3 C2 C1 C0

Sommatore Carry-Lookahed

• Il blocco elementare ha questa struttura:

Ai Bi Si

Pi Gi

Ci

Ci

Ai

Bi

Si

Pi

Gi

Sommatori CLA ad Albero Binario

• Definiamo un operatore “o”

• Vale la proprietà associativa:

• Esiste un elemento neutro:

O(g1, p1)

(g2 p2)(g1+ p1g2, p1p2)

)pp,gpg()p,g()p,g( 212112211

)p,g()p,g()p,g()p,g()p,g()p,g( 332211332211

)p,g()1,0()p,g( 1111

Sommatori CLA ad Albero Binario

• Possiamo definire, ricorsivamente, dei PROPAGATE e GENERATE DI GRUPPO:

(risulta, se C0=0 Gi = Ci)

1i)P,G()p,g(

1i)p,g()P,G(

1i1iii

iiii se

se

Sommatori CLA ad Albero Binario• Quindi utilizzando la proprietà associativa possiamo costruire la

seguente rete di CLA:

• Nodo centrale molto carico

• Ritardo:

Albero diretto Albero inverso

Nlog221)1N(logNlogt 222ADDER

liv. alb. dir liv.alb.inv. 1 liv.è sovrapposto

calcolo G,P + calcolo somma

Sommatori CLA ad Albero Binario• Si può anche ridurre il numero di livelli, sfruttando le

proprietà dell’operatore “o”

• Fan out elevato. FOmax = N/2• Ritardo: tADDER = log2N (in realtà non è equalizzato, dipende

dal FO di ogni sommatore)

Sommatore CLA ad Albero Binario

• Possiamo introdurre degli operatori fittizi (il cui unico compito è buffering)

O(1,0)=

Sommatore CLA ad Albero Binario• Con gli operatori fittizi:

Sommatore CLA ad Albero Binario• Ogni blocco ha FAN-OUT = 2

– Ritardi equalizzati– Struttura geometrica regolare

• Ritardo di propagazione:tADDER = (log2N + 2)

• Il numero di blocchi per la logica di CLA è:Nblocks = N log2N

• Per l’ultimo livello sarebbe sufficiente calcolare i Gi (poiché ci interessano i riporti)

• A 3.5 ns, 64 bit, carry-lookahead adderDozza, D.; Gaddoni, M.; Baccarani, G.; 1996 Int. Symposium on Circuits and Systems

Determinazione dell’Overflow

Se la operazione di somma (o sottrazione) e’ eseguita senza segno, il bitdi overflow e’ semplicemente determinato dal Carry-out dello stadio N.In caso di operazione in complemento a 2, si utilizza il seguente algoritmo:

1. Se il bit di maggior peso dei due operandi e’ diverso, non ci puo’ essere overflow2. Se I due operandi hanno uguale bit di maggior peso, il bit di maggior peso del risultato deve essere uguale ai due bit degli operandi

)SA(*)BA(OF 1N1N1N1N

Moltiplicatori Hardware

• Moltiplicatore Seriale

• Moltiplicatore Parallelo

• Moltiplicatore Booth-Encoded

Algoritmo di Moltiplicazione

ii

1N

0i

2xX

ii

1M

0i

2yY

0110 * 0011 = ______ 0110 + 0110- + 0000-- +0000--- =________0010010

x3 x2 x1 x0 * y3 y2 y1 y0 = ---------------------------- x3y0 x2y0 x1y0 x0y0 + x3y1 x2y1 x1y1 x0y1 - + x3y2 x2y2 x1y2 x0y2 - - + x3y3 x2y3 x1y3 x0y3 - - - = -----------------------------------------------Z7 Z6 Z5 Z4 Z3 Z2 Z1 Z0

jij

N

i

M

j

iyxYXZ

2*

1

0

1

0

Servono N+M bit per il prodotto

Moltiplicatore a matricey0

y1

y2

y3

z0z1z2z3z4z5z6

x3 x2 x1 x0

z7

x3 x2 x1 x0

x3 x2 x1 x0

x3 x2 x1 x0

HAHA

HA

HA

FAFA

FA FA FA

FA FA FA

Y: N bitX: M bit

N-1 righe

M somme per riga

Moltiplicatore a matrice

Vantaggi: • Grande simmetria (layout rettangolare)

Svantaggi:• Notevole Impiego di risorse Hardware• Critical Path non ben identificabile

Delay:Tmult=[(M-1)+(N-2)] tcarry+ (N-1) tsum + tand

Risorse:N*M porte AND + M(N-1) sommatori

Moltiplicatore Carry-Save a matrice• I bit di riporto non vengono sommati

subito, ma passati alla rigasuccessiva

• Porto avanti vettori di sommee di riporti

• Quando si fanno somme occorreche bit di somma e di riportoabbiano lo stesso peso

• Infine serve uno stadiofinale per riallinearegli ultimi vettori di somme e riporti

• Il cammino criticoè univocamentedefinito

camminocritico

Moltiplicatore Carry-Save a matrice• Il cammino critico è univocamente definito• Il ritardo è:• Se il Vector Merge Adder è realizzato con

architettura ripple-carry si ha:

• Quindi, un moltiplicatore CSA, con merge adder in ripple-carry ha:

• Serve un numero di sommatori pari a: N(M-1)[ N-1 sommatori CSA + 1 Merge Adder, tutti a M-1 bit]

MERGEANDCARRYMULT ttt)1N(t

CARRYMERGE t)1M(t

)t)1N(2

t)1N(tt)1N(t

AND

CARRYANDCARRYMULT

MN (se

Moltiplicatore Carry-Save a matrice• Possiamo

schematizzarlo nel modo seguente(es. N = M = 4)

• Ogni stadio Carry Save Adder (tranne il primo) riceve in ingresso 3 vettori di bit, riducendoli a 2 in uscita (1 vett. di riporti ed 1 vett. di somme)

CSA 2:2 (h.a.)

b0Ab1Ab2A

CSA 3:2

CSA 3:2

b3A

Merge Adder

P1

P2

P3

P0

P7..4

Moltiplicatore Carry-Save a matrice• Utilizzando dei soli

sommatori CSA con riduzione 3:2 possiamo accorpare i primi due livelli

• I sommatori riallineano i vettori di bit in ingresso in modo da sommare i bit dello stesso peso

• N-2 livelli di CSA+ 1 Merge Adder

• Il numero di FA complessivo è:NFA = N(N-2)+N = N(N-1)

b0Ab1Ab2A

CSA 3:2

CSA 3:2

b3A

Merge Adder

Moltiplicatore Carry-Save a 8-bit

8-bit CSA

8-bit CSA

8-bit CSA

8-bit CSA

8-bit CSA

8-bit CSA

8-bit CSA

Risultato parziale (8bit)

Carry-Save out (8bit)

Merge adder

Tdelay= o(N)

XY4XY6

XY0XY1XY2XY3XY

7

XY5

8-bit

Moltiplicatore Carry-Save ad Albero di Wallace

• E’ possibile comporre i CSA in uno schema ad albero

• Ad ogni livello ho un fattore di riduzione 3:2, mentre globalmente (fino all’ingresso del merge adder) lo avrò N:2. Se n è il numero di livelli avremo allora:

• VANTAGGIO: Ritardo logaritmico!• SVANTAGGIO: struttura irregolare,

layout e routing difficoltosi(es. provare a sostituire i CSA con i relativi FA e tracciare le interconnessioni….)

1Nlog71.1

2

Nlog71.1

23

log

2N

logn

2

Nlog

2

3logn

2

N

2

3

2

2

2

2

22

n

Moltiplicatore Carry-Save ad Albero di Wallace

3

2

3

2

3

N

3

N

• Quanti CSA richiede questo moltiplicatore

• Ad ogni livello ne abbiamo:

1.

2.

3.

4. …

• Abbiamo una serie geometrica:

3

2

3

N

)1N(log71.1n

2N

32

1

32

1

3

N

3

2...

3

2

3

21

3

N

2

n

1n2

dove

Moltiplicatore ad albero di Wallace

Vantaggi: • Cala la complessita’ dell’albero, viene aumentata la prestazione• Diminuisce il numero di risorse utilizzate

Svantaggi:• Layout fortemente asimmetrico

Delay:Tmult= (N-1)tcarry+tand+tmerge = o(N)

Codifica di Booth per la moltiplicazione• Sia {xN-1, xN-2, …. x1, x0} un numero in

complemento a 2. [xN-1 sarà il segno]

• Il numero rappresentato sarà:

• Separiamo i bit di indice pari da quelli di indice dispari:

2N

0n

2N

0n

nn

1N1N

1N1N

nn 2x2x2x2xX

1N1N

12

N

1n

n2n2

12

N

1n

1n21n2

12

N

0n

n2n2

1N1N

12

N

1n

1n21n2

12

N

0n

n2n2

2x2x2x22x

2x2x2xX

Codifica di Booth

12

N

0n

n2

12

N

0n

n21n21n2n2

12

N

0n

n21n2

12

N

0n

n21n2

12

N

0n

n2n2

12

N

0n

1n21n2

12

N

0n

n21n2

12

N

0n

n2n2

2

N

1n

1n21n2

12

N

1n

n21n2

12

N

0n

n2n2

1N1N

12

N

1n

n2n2

12

N

1n

1n21n2

12

N

0n

n2n2

2)n2(f2x2xx

2x22x2x

2x2x2x

2x2x2x

2x2x2x22x

Definisco x-1=0 ed estendo la sommatoria cambio indice n’=n-1

sposto un 2 dell’esponente

Codifica di Booth

• Abbiamo ottenuto• Considerando la moltiplicazione X*Y avremo:

12

N

0n

nn2

12

N

0n1n2n21n2 2)n2(f2x2xxX

12

N

0n

nn2

12

N

0n1n2n21n2 2)n2(fY2x2xxYYX

x2n+1 x2n x2n-1 f(2n) f(2n)Y

0 0 0 0 0

0 0 1 1 Y

0 1 0 1 Y

0 1 1 2 2Y

1 0 0 -2 -2Y

1 0 1 -1 -Y

1 1 0 -1 -Y

1 1 1 0 0

Otteniamo 5 possibili

configurazioni in Y:

0, Y, 2Y, -Y, -2Y

(tutte facilmente generabili)

La moltiplicazione consiste nella somma di N/2

configurazioni di f(2n)Y

Codifica di Booth

• Sono i bit di X che mi fanno scegliere quale configurazione di f(2n)Y utilizzare nel calcolo della moltiplicazione (in ogni addendo)

– n=0, f(0) = x-1 + x0 + 2 x1 = 0 + x0 + 2 x1

– n=1, f(1) = x1 + x2 + 2 x3

– n=2, f(2) = x3 + x4 + 2 x5

– n=3, f(3) = x5 + x6 + 2 x7

Codifica di Booth

Ogni operazione di prodotto parziale viene gestita con un multiplexer che seleziona le possibili uscite tra le operazioni imposte

MUXX2i+1X2iX2i-1

Ad ogni passo il prodotto parziale puo’ essere shiftato di DUE PASSI (invece che uno)Verso sinistra. Il numero di livelli necessari a realizzare questo tipo di moltiplicazione e’ quindi N/2 invece di N, l’area e il ritardo si dimezzano praticamente, anche se si introduce una logica di controllo piu’ complessa.

Y –Y 2Y -2Y 0

BOOTH ENCODING:

Booth Encoded Multiplier a 8 bit

MUXX1X0X-1

Y –Y 2Y -2Y 0

MUXX3X2X1

Y –Y 2Y -2Y 0

MUXX5X4X3

Y –Y 2Y -2Y 0

7 bit

9 bit

MUXX7X6X5

Y –Y 2Y -2Y 0

adder stage

adder stage

adder stage

9 bit

2 bit

8 bit2 bit

9 bit

8 bit2 bit

Slide

modificata!!!

10 bit

9 98 8 8

9 98 8 8

9 98 8 8

9 98 88

Moltiplicatore Seriale

Basato sui registri :• A Moltiplicatore• B Moltiplicando (64 bit)• P Registro accumulazione parziale (64 bit)

Il Prodotto e’ basato su una serie di AND bit a bit,

A (shift left)

64-bit adder

P

B (shift right)

en

Moltiplicatore Seriale (2)

Basato sui registri :• A Moltiplicatore• B Moltiplicando (64 bit)• P Registro accumulazione parziale (64 bit)In questa soluzione P ed A sono concatenati, permettendo un notevole risparmio

di risorse:

A

32-bit adder

P/B (Shift Right)en