Elettronica dei
Sistemi Digitali LA
Università di Bologna,
II Facoltà di Ingegneria, Sede di Cesena
Aritmetica Computazionale
F.Campi, A. Romani
A.a. 2006-2007
Aritmetica Computazionale
• Si studiano possibili architetture hardware 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:
X se X  0
X N
N
2

X

2

X
se
X

0

0 1 2
00000…0
2N-1-1 -2N-1
01111…1 10000…0
-1
11111…1
Complemento a 2
L’operazione di complemento a 2 e’ realizzata attraverso una
negazione bit a bit (o inverto ogni bit oppure lo metto in XOR con 1)
N 1
X   xi  2 i
sia X  0
i 0
N 1
 X  2 N  X  2 N   xi  2 i 
i 0
N 1
 (2 N  1)  1   x i  2i 
i 0
N 1
N 1
N 1
i 0
i 0
i 0
  1  2i   x i  2i  1   1  x i   2i  1 X  1
se x i  0  (1  x i )  1
  (1  x i )  x i
se x i  1  (1  x i )  0
Moltiplicazione (potenze del 2)
• Moltiplicazione per potenze del 2
N 1
X   xi  2i
sia
i 0
N 1
 N 1
i
k
X  2    xi  2   2   xi  2i  k 
i 0
 i 0

pongo j  i  k [i  0  j  k, i  N  1  j  n  k  1 ( N  1)
k
(gli ultimi bit non sono rappresent abili)
N 1
k 1
  x j k  2   0  2 j
j
j k
j 0
N-1
0
xN-1
x1 x0
N-1
xN-k-1
k k-1
x0 0 0
0
0
Divisione (potenze del 2)
• Divisione per potenze del 2
N 1
sia
X   xi  2i
i 0
N 1
N 1


X k    xi  2i   2  k   xi  2i  k 
2
i 0
 i 0

pongo j  i  k [i  0  j  k  0, i  N  1  j  n  k  1

N  k 1
j
x

2
 j k
j 0
N-1
0
xN-1
x1 x0
N-1
0/1
0/1
xN-1
Sign extension
0 con unsigned
xN-1 con signed
xk+1 xk
Sommatori
OBIETTIVO: Analizzare delle architetture gate level che descrivano
l’operazione di somma tra vettori di bit:
{an-1 … a0}
{bn-1 … b0}
+
{sn-1 … s0}
Problema: Scegliere il corretto TRADE-OFF (Compromesso) tra risorse fisiche
(Area e Consumo) e velocita’ di elaborazione
Sommatori Ripple Carry
Si vuole realizzare quindi la operazione seguente:
1
10101+
00001=
_________
10111
Vogliamo scomporre la operazione
su un singolo bit, sara’ poi sufficiente
replicare N volte la stessa logica
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.
Half-Adder
\ B
A
\ B
A
0
1
0
1
0
0
1
0
0
0
1
1
0
1
0
1
Carry Out
SUM
S= A XOR B
Si ottiene quindi
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 00
01
11
10
Cin
\ AB 00
01
11
10
Cin
0
0
1
0
1
0
0
0
1
0
1
1
0
1
0
1
0
1
1
1
SUM
Carry Out
Full Adder: Calcolo di Sum e Cout
Sum  a * b * c  a * b * c  a * b * c  a * b * c 
 c * ( a * b  a * b)  c * ( a * b  a * b) 
 c * ( a  b)  c * ( a  b) 
 ( a  b)  c
Nota:
c * (ab  ab)  c * (ab  ab)  c * (( a  b) * (a  b)) 
 c * (a a  ab  ab  bb)  c * (a  b)
Cout  a * b  b * c  a * c 
 a * b  (a  b ) * c
Full Adder, schema logico
a
b
Sum
Cout
Cin
Sommatori Ripple-Carry
AN-1 BN-1
a
CN
b
Cout
Cin
Sum
SN-1
A2
B2
A1
B1
A0
B0
a
b
a
b
a
b
Cout
Cin
Sum
S2
C2
Cout
Cin
Sum
S1
C1
Cout
Cin
Sum
C0
S0
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)
Prestazioni Sommatore Ripple-Carry
AN-1 BN-1
a
CN
b
Cout
Cin
Sum
SN-1
A2
B2
A1
B1
A0
B0
a
b
a
b
a
b
Cout
Cin
Sum
S2
C2
Cout
Cin
Sum
S1
C1
Cout
Cin
Sum
C0
S0
Il cammino critico (cioè il ritardo di propagazione del
caso peggiore) è caratterizzato da questa espressione:
t ADDER  ( N  1)t CARRY  t SUM  O( N)
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
C0
B0
A0
B1
A1
B2
A2
b
a
b
a
b
a
Cin
FA0
Cout
Sum
S0
C1
Cin
FA1
Cout
Sum
S1
C2
Cin
FA2
Cout
Sum
S2
BM-1 AM-1
b
Cin
FAM-1
SEL
a
Cout
Sum
CM
0
SM-1
1
• aggiungere una logica di “bypass”
Cout
Sommatore Carry Bypass
• Avrò dunque N/M gruppi da M full-adder
connessi come segue:
B0 A0
B1 A1
B2 A2
BM-1 AM-1
BM AM
C0
BM+1 AM+1
B2M-1 A2M-1
BN-1 AN-1
S0
S1
S2
SM-1
SM
SM+1
S2M-1
Cout
SN-1
• 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
Ci  CM
cioè quando CM dipende dal solo Ci (e non dagli ingressi A, B)
Condizione di propagazione
• Per un F.A. la condizione di propagazione è la
seguente: P(A, B)  1 tutte le volte in cui Cout  Ci
(cioè Cout non dipende dagli ingressi A e B: cioè se li
fisso allora Cout segue il valore di Cin)
\ AB 00
Cin
01
11
10
P=0
P=1
0
0
0
1
0
1
0
1
1
1
P=0 P=1
P = A xor B
Carry Out Full Adder
• Per il blocco di M f.a. avrò propagazione da C0 a
CM se: P0P1P2…PM-1 = 1
Sommatore Carry Bypass
• Quindi completiamo lo schema:
P0 P1 P2…PM-1
B0 A0
B1 A1
B2 A2
PM PM+1…P2M-1
BM-1 AM-1
BM AM
C0
BM+1 AM+1
B2M-1 A2M-1
…PN-2PN-1
BN-1 AN-1
S0
S1
S2
SM-1
SM
SM+1
S2M-1
Cout
SN-1
• Qual è il cammino critico?
– da A0, B0 a CM [se avessi propagazione C0CM 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
N

t ADDER  t SEL  M  t CARRY  
 1  t MUX  M  1  t CARRY  t SUM 
M

N

 t SEL  (2M  1)  t CARRY  
 1  t MUX  t SUM
M

Sommatore Carry-Bypass
• L’espressione del ritardo di propagazione sul
cammino critico, oltre che funzione di N, dipende
da M
N 
t ADDER  t SEL  (2M  1)  t CARRY    1  t MUX  t SUM
M 
tADDER
ripple-carry adder
carry bypass adder
N
4
8
Sommatore Carry-Bypass
• Esiste un valore ottimale di M? Posso dunque
raggruppare i F.A. secondo un criterio ottimale?
• Definiamo:
a
t MUX
t CARRY
,
t
*
ADDER
 t SEL  t CARRY t MUX  t SUM ) 
t ADDER
N

(M, N) 
 2M 
a  
t CARRY
M
t CARRY


• E andiamo a verificare quando:
 t *ADDER
0
M
(il minimo di t*adder sarà minimo anche di tadder)
Sommatore Carry-Bypass
 t *ADDER
N
0  2 2 0 
M
M
M opt 
t
*
ADDER,opt
N
a2 
2
M
aN

2
aN
aN
( N)  2


2
aN
2
 2 2aN  2 2 N
t MUX
t CARRY

t ADDER,opt  t SEL  2 2N t MUX t CARRY  t CARRY  t MUX  t SUM
il ritardo del sommatore carry-bypass ottimo va come N
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, raggruppando i soliti M full-adder:
C0
B0
A0
B1
A1
B2
A2
b
a
b
a
b
a
Cin
FA0
Cout
Sum
C1
Cin
FA1
S0
Cout
Sum
C2
Cin
FA2
S1
B0..M-1
BM-1 AM-1
b
Cout
Sum
S2
Cin
FAM-1
A0..M-1
M
M
C0
CM
M
S0..M-1
a
Cout
Sum
SM-1
CM
Carry-Select Adder
• Possiamo definire questa struttura:
B0..M-1 A0..M-1
BM..2M-1 AM..2M-1
M
M
C0
M
M
M
CM
BM..2M-1 AM..2M-1
C2M(0)
0
M
S0..M-1
0
C2M
0
M
SM..2M-
M
1
1
CN
0
CN(1)
1
(0)
1
C2M(1)
0
M
C2M
CN(0)
SM..2M-
(0)
1
M
C2M(0)
0
1
BM..2M-1 AM..2M-1
M
M
BM..2M-1 AM..2M-1
M
M
1
1
SM..2M-1(1)
C2M(1)
0
1
M
1
SM..2M-1(1)
SM..2M-1
0
SN-M-2..N-1(0)
SM..2M-1
SN-M-2..N-1(1)
SN-M-2..N-1
ATTENZIONE: Rispetto agli altri sommatori il numero di risorse aumenta!
N

M  2M   1  2 N  M full adder
M

N

2  1 mux
M

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:
t ADDER  Mt CARRY
N


 2  t MUX  t MUX ,sum
M

Sommatore Carry-Select
• Il cammino critico ha
questo ritardo:
t ADDER  Mt CARRY
• Definiamo: t
• Risulta: t
N

N


 2  t MUX  t MUX ,sum  Mt CARRY  
 1 t MUX
M

M

*
ADDER
*
ADDER
t ADDER

,
t CARRY
a
t MUX
t CARRY
N

 M
 1 a
M

• Vediamo quale
valore di M ottimizza
il ritardo peggiore:
t *ADDER
N
 1  2 a  0  M opt  aN 
M
M
 t *ADDER,opt  a 2 N  1 

 t ADDER,opt  t MUX t CARRY

2

N  1  t MUX
Sommatore Carry-Select
• E’ possibile ottimizzare i tempi di calcolo
utilizzando un semplice accorgimento:
4
4
5
6
4
5
6
• In questo modo viene effettuato il calcolo di un bit
di somma in più mentre avviene la propagazione
attraverso i mux degli stadi precedenti
Sommatori Carry-Lookahead
Si ricordi il calcolo per la determinazione del Carryout nel full-adder:
(il riporto in ingresso a una colonna dipende dalla colonna precedente)
Ci  Ai1 * Bi1  Bi1 * Ci1  Ai1 * Ci1
Si puo’ scrivere come
Ci  Ai1 * Bi1  Ci1 * (Ai1  Bi1 )
Possiamo definire GENERATE e PROPAGATE:
G i  Ai Bi

Pi  Ai  Bi
Risulta:
( Ai  Bi ai fini del calcolo di Ci)
Ci  Gi1  Pi1Ci1
Possiamo altresì scrivere:
Si  A i  Bi  Ci
Si  Pi  Ci
se Pi  A i  Bi
Sommatori Carry-Lookahead
Il calcolo dei diversi carry out presenti nel sommatore a 4 bit puo’ essere
quindi descritto secondo l’algoritmo seguente:
C1  G 0  P0C0
C2  G1  P1G 0  P1P0C0
C3  G 2  P 2G1  P 2P1G 0  P 2P1P0C0
C4  G 3  P3G 2  P3P 2G1  P3P 2P1G 0  P3P 2P1P0C0
Sommatory Carry-Lookahead
• Possiamo scrivere:
C1  G 0  P0 C0
C 2  G1  P1G 0  P1P0 C0
C3  G 2  P2 G1  P2 P1G 0  P2 P1P0 C 0
C 4  G 3  P3G 2  P3 P2 G1  P3P2 P1G 0  P3P2 P1P0 C 0
...
• Lo schema sarà di questo tipo:
Carry lookahead
P0
P1
G0
C0
P2
G1
C1
A0 B0
S0
PN-1
G2
C2
A1 B1
S1
GN-1
CN-1
A2 B2
S2
AN-1 BN-1 SN-1
Sommatori Carry-Lookahead
Anticipando il calcolo del carry secondo quanto descritto e’ possibile
Realizzare il seguente sommatore Carry-Lookahead.
G3 P3
G2 P2
C3
p3
C2
p2
s3
G1 P1
C1
C0
p0
p1
s2
G0 P0
s1
s0
Lo svantaggio principale di questa architettura e’ che le equazioni logiche
Diventano troppo complesse oltre l’ordine 4. Di conseguenza i CLA vengono
utilizzati di solito in blocchi gerarchici.
Sommatore Carry-Lookahed
• Il blocco elementare ha questa struttura:
Pi
Gi
Ci
Ci
Ai
Bi
Si
Si
Pi
Ai
Bi
Gi
Sommatori CLA ad Albero Binario
• Definiamo un operatore “o”
(g1, p1)
(g2 p2)
O
(g1+ p1g2, p1p2)
( g1, p1 )  ( g 2, p2 )  ( g1  p1 g2 , p1 p2 )
• Vale la proprietà associativa:
(g1, p1 )  (g 2 , p2 )  (g3 , p3 )  (g1, p1 )  (g 2 , p2 )  (g3 , p3 )
• Esiste un elemento neutro:
(g1, p1 )  (0,1)  (g1, p1 )
Sommatori CLA ad Albero Binario
• Possiamo definire, ricorsivamente, dei
PROPAGATE e GENERATE DI GRUPPO:
se i  1
(g i , pi )
(G i , Pi )  
(g i , pi )  (G i 1 , Pi 1 )
(risulta, se C0=0  Gi = Ci)
se i  1
Sommatori CLA ad Albero Binario
• Quindi utilizzando la proprietà associativa possiamo costruire la
seguente rete di CLA:
Albero inverso
Albero diretto
• Nodo centrale molto carico
• Ritardo:
calcolo G,P + calcolo somma
t ADDER    log 2 N  (log 2 N  1)  1  2  2 log 2 N
 è il ritardo (supposto identico) di
ogni blocco logico elementare
liv. alb. dir
liv.alb.inv.
1 liv.è sovrapposto
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à a essere precisi non èequalizzato, 
dipende dal FO di ogni sommatore....)
Sommatore CLA ad Albero Binario
• Possiamo introdurre degli operatori fittizi (il
cui unico compito è buffering)
=
(1,0)
O
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 volendo è sufficiente calcolare i Gi
(poiché ci interessano i riporti)
•
A 3.5 ns, 64 bit, carry-lookahead adder
Dozza, 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 bit
di 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
overflow
2. 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
OF  (AN  1  BN  1) * (AN  1  SN  1)
Algoritmo di Moltiplicazione
N 1
X   xi 2
i 0
i
Y
Servono N+M bit per il prodotto
M 1
y2
i
i 0
i
N 1 M 1
Z  X * Y   xi y j 2
i j
i 0 j 0
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
Moltiplicatore a matrice
x3
Y: N bit
X: M bit
x2
x3
N-1 righe
x2
x1
HA
FA
FA
x2
x1
FA
FA
x3
FA
x3
FA
z7
z6
x2
x1
FA
z5
z4
x0
HA
y2
x0
HA
y3
HA
z3
y0
y1
x0
x0
FA
M somme per riga
x1
z2
z1
z0
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
• In questo schema i bit di riporto non
vengono sommati
subito, ma passati alla riga
successiva
• Porto avanti vettori di somme
e di riporti
• Quando si fanno somme
occorre che bit di
somma e di riporto
abbiano sempre lo
stesso peso
• Infine serve uno stadio
finale per riallineare
gli ultimi vettori di
somme e riporti
• Il cammino critico
è univocamente
definito
cammino
critico
Moltiplicatore Carry-Save a matrice
• Il cammino critico è univocamente definito
• Il ritardo è: t MULT  ( N  1)t CARRY  t AND  t MERGE
• Se il Vector Merge Adder è realizzato con
architettura ripple-carry si ha:
t MERGE  (M  1)t CARRY
• Quindi, un moltiplicatore CSA, con merge adder in
ripple-carry ha:
t MULT  ( N  1)tCARRY  t AND  ( M  1)tCARRY 
 2( N  1)  t AND (se N  M)
• Serve un numero di sommatori pari a: N(M-1)
[ N-1 sommatori CSA + 1 Merge Adder, tutti a M-1 bit]
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)
b3A
b2 A
b1 A
b0 A
P0
CSA 2:2 (h.a.)
P1
CSA 3:2
P2
CSA 3:2
P3
Merge Adder
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)
b3 A
b2 A
b1 A
CSA 3:2
CSA 3:2
Merge Adder
b0 A
Moltiplicatore Carry-Save a 8-bit
XY2
XY4 XY3
XY5
XY6
XY7
XY1
XY0
8-bit CSA
8-bit CSA
8-bit CSA
Risultato parziale (8bit)
8-bit CSA
8-bit CSA
Carry-Save out (8bit)
8-bit CSA
8-bit CSA
Merge adder
8-bit
Tdelay= o(N)
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:
n
N
3
N
3
 n log 2  log 2

  
2
2
2
2
 
N
log 2
2  1.71 log  N  
n
2
3
 2
log 2
2
 1.71 log 2 N  1
•
•
VANTAGGIO: Ritardo logaritmico!
SVANTAGGIO: struttura irregolare,
layout e routing difficoltosi
(es. provare a sostituire i CSA con i relativi FA
e tracciare le interconnessioni….)
Moltiplicatore Carry-Save ad Albero di Wallace
•
•
Quanti CSA richiede questo moltiplicatore
Ad ogni livello ne abbiamo:
1.
N
3
2.
N 2
3 3
3.
N 2 2
3 3 3
4. …
•
Abbiamo una serie geometrica:
n
2
1

 
2
n 1
N 
2 2
 2   N
3  N2
1      ...   

3 
3 3
 3   3 1   2 
 
3
dove n  1.71 (log 2 N  1)
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à:
X
N2
n
N 1
x
2

x
2
 n
N 1
n 0
N2

N 1
n
   x N 1 2   x n 2 
n 0


• Separiamo i bit di indice pari da quelli di indice
dispari:
N
N
1
1
2
2
X   x2 n 2   x2 n 1 2 2 n 1  xN 1 2 N 1 
n 0
2n
n 1
N
1
 N2 1

2
  x2 n 2 2 n  2  x2 n 1 2 2 n 1   x2 n 1 2 2 n 1   xN 1 2 N 1 
 n 1

n 0
n 1


N
1
2
Codifica di Booth
corretta
 N2 1
  N2 1




2n
2 n 1
2 n 1
N 1 
  x2 n 2  2  x2 n 1 2     x2 n 1 2
 x N 1 2  
n 0
 n 1
  n 1


 

N
1
2
N
1
2
N
1
2
N
2
n 0
n 1
n 1
l’indice 2n-1 varia in 1,3,..,N-3
  x2 n 2 2 n   x2 n 1 2 2 n   x2 n 1 2 2 n 1 
Definisco x-1=0 ed estendo la sommatoria
cambio indice n’=n-1
N
1
2
N
1
2
N
1
2
n 0
n 0
n  0
N
1
2
N
1
2
N
1
2
n 0
n 0
n 0
2n-1= 2(n’+1)-1=2n’+1
  x2 n 2 2 n   x2 n 1 2 2 n   x2 n1 2 2 n1 
sposto un 2 dell’esponente
  x2 n 2 2 n   x2 n 1 2 2 n   2  x2 n 1  2 2 n 
N
1
2
N
1
2
n 0
n 0
   x2 n  x2 n 1  2 x2 n 1   2 2 n   f (2n)  2 2 n
Codifica di Booth
• Abbiamo ottenuto
X
N
1
2
2n


x

x

2
x

2
 2n 1 2n
2 n 1

n 0
N
1
2
n
f
(
2
n
)

2

n 0
• Considerando una moltiplicazione X*Y avremo:
N
1
2
X  Y  Y   x 2 n 1  x 2 n  2x 2 n 1   2 2 n 
n 0
N
1
2
n
Y

f
(
2
n
)

2

n 0
x2n+1
x2n
x2n-1
f(2n)
f(2n)Y
0
0
0
0
0
Otteniamo 5 possibili
configurazioni in Y:
0
0
1
1
Y
0, Y, 2Y, -Y, -2Y
0
1
0
1
Y
0
1
1
2
2Y
(tutte facilmente
generabili)
1
0
0
-2
-2Y
1
0
1
-1
-Y
1
1
0
-1
-Y
1
1
1
0
0
La moltiplicazione
consiste nella somma di
N/2 configurazioni di
f(2n)Y opportunamente
shiftate
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
BOOTH ENCODING:
Y –Y 2Y -2Y 0
X2i+1X2iX2i-1
MUX
Ad ogni passo il prodotto parziale viene shiftato di DUE PASSI (invece che uno)
verso sinistra. Il numero di livelli necessari a realizzare questo tipo di moltiplicazione è
quindi N/2 invece di N, l’area e il ritardo si dimezzano praticamente,
anche se si introduce una logica di controllo piu’ complessa.
Booth Encoded Multiplier a 8 bit
Y –Y 2Y -2Y 0
8
Y –Y 2Y -2Y 0
8
9
8
Y –Y 2Y -2Y 0
8
X7X6X5
8
8
9
9
MUX
9 bit
adder stage
10 bit
8
9
9 bit
8
9
X5X4X3
MUX
9 bit
Y –Y 2Y -2Y 0
8
9
7 bit
MUX
X3X2X1
8
9
adder stage
8 bit
adder stage
2 bit
8 bit
9
8
MUX
X1X0X-1
Slide
modificata!!!
8
2 bit
2 bit
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)
B
64-bit adder
P
en
(shift right)
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