Elettronica dei Sistemi Digitali LA Università di Bologna, II Facoltà di Ingegneria, Sede di...
-
Upload
costanzo-tarantino -
Category
Documents
-
view
213 -
download
1
Transcript of Elettronica dei Sistemi Digitali LA Università di Bologna, II Facoltà di Ingegneria, Sede di...
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