Moltiplicatore

Reti Logiche
Moltiplicatore
X
Y
n
n
Moltiplicatore
2n
Z=XxY
Moltiplicatore ad array
Moltiplicatore ad array
X3
X3
X2
X2
X1
X1
X0
Y1
X0
X3
Y0
Z0
X2
X1
X0
Y2
X2
X1
Y3
X0
ADDER
Z7
Z6
Z5
Z4
Z7
Z3
M-1 sommatori da N bit
Y1
X1
X0
FA
FA
FA
HA
X3
X2
X1
X0
FA
FA
FA
HA
X3
X2
X1
X0
FA
FA
FA
HA
Z1
Z2
X0
X2
ADDER
X3
X1
X3
ADDER
X3
X2
Z6
Z5
Z4
Y3
Z3
Z2
Y2
Z1
Y0
Z0
Moltiplicatore ad array
X3
X2
X1
X0
Y1
X3
X2
X1
X0
FA
FA
FA
HA
X3
X2
X1
X0
FA
FA
FA
HA
X3
X2
X1
X0
FA
FA
FA
HA
Y3
Moltiplicatore Carry-Save
Y2
Y0
Z6
Z5
Z4
HA
HA
HA
FA
FA
FA
HA
FA
FA
FA
FA
FA
HA
HA
Z1
Z2
HA
Z7
HA
Z0
Z3
propagare il carry in avanti e in basso
tmult = [(N-1) + (M-2)] tcarry + (M-1) tsum + tand
Moltiplicatore Carry-Save
HA
HA
HA
HA
HA
FA
FA
FA
HA
FA
FA
FA
FA
FA
HA
Vector merging adder
Critical Path: attraversa un solo sommatore
Moltiplicatore Carry-Save
HA
HA
HA
HA
FA
FA
FA
HA
FA
FA
FA
FA
FA
HA
HA
HA
HA
Vector merging adder
tmult = tand+ (M-1) tcarry + tmerge
Vector merging adder:
sommatore veloce
Moltiplicatore Carry-Save
Floorplan
X3
X2
X1
Riduzione a due livelli
X
X0
Y
Y0
HA
Y1
HA
C S
C
HA
Y2
HA
S
FA
C S
C
C
C
FA
S
C
S
FA
HA
C S
C
C
x1y0
x3y1
x2y1
x1y1
x0y1
x3y2
x2y1
x1y2
x0y2
x2y3
x1y3
x0y3
x0y0
FA
S
C
FA
S
x2y0
Z0
S
Z1
Y3
x3y0
HA
S
x3y3
FA
S
C
Matrice dei prodotti
S
Z2
VM
C S
VM
VM
VM
C
C
C
S
S
z7
z6
z5
z3
z4
z2
z1
z0
S
Z
Z7
Z6
Z5
Z4
Z3
Riduzione a due livelli
Riduzione a due livelli
MAX risultato = 4 = 100b
MAX risultato = 2 = 10b
x3y0
x2y0
x1y0
x3y1
x2y1
x1y1
x0y1
x3y2
x2y1
x1y2
x0y2
x3y3
x2y3
x1y3
x0y3
z6
z5
z4
z3
x0y0
Sommare tutti i bit su una colonna
(tenere conto dei bit di riporto
dalle colonne precedenti)
x3y0
x2y0
x1y0
x3y1
x2y1
x1y1
x0y1
x3y2
x2y1
x1y2
x0y2
x3y3
x2y3
x1y3
x0y3
z6
z5
z4
z3
riporto
x0y0
Sommare tutti i bit su una colonna
(tenere conto dei bit di riporto
dalle colonne precedenti)
riporti
z7
questa colonna somma 3+1=4 bit
z2
z1
z0
z7
z2
z1
z0
Riduzione a due livelli
x3y0
x2y0
x1y0
x3y1
x2y1
x1y1
x0y1
x3y2
x2y1
x1y2
x0y2
x3y3
x2y3
x1y3
x0y3
z6
z5
z4
z3
x0y0
Riduzione a due livelli
Sommare tutti i bit su una colonna
(tenere conto dei bit di riporto
dalle colonne precedenti)
x3y0
x2y0
x1y0
x3y1
x2y1
x1y1
x0y1
x3y2
x2y1
x1y2
x0y2
x3y3
x2y3
x1y3
x0y3
z6
z5
z4
z3
x0y0
Sommare tutti i bit su una colonna
(tenere conto dei bit di riporto
dalle colonne precedenti)
sicuramente 0
z7
z2
z1
z0
z7
Contatore parallelo:
x3y0
x2y0
x1y0
x3y1
x2y1
x1y1
x0y1
x3y2
x2y1
x1y2
x0y2
x3y3
x2y3
x1y3
x0y3
z6
z5
z4
z3
n ingressi
m = 1 + log2 n uscite
1 + log2 5 = 1+2 = 3 uscite
Z = numero di ingressi che assumono il valore 1
Z
z1
z0
Riduzione a due livelli
Riduzione a due livelli
5 ingressi
z2
Contatore parallelo 2 ingressi, 1 uscita
Half-Adder
Contatore parallelo 3 ingressi, 2 uscite
Full-Adder
z7
z2
z1
x0y0
z0
Critical-path:
propagazione del riporto lungo
tutto il circuito
Riduzione a due livelli
x3y3
x3y0
x2y0
x1y0
x3y1
x2y1
x1y1
x0y1
x3y2
x2y1
x1y2
x0y2
x2y3
x1y3
x0y3
Riduzione a due livelli
x0y0
Sommare i riporti in un secondo
stadio
x3y3
x3y0
x2y0
x1y0
x3y1
x2y1
x1y1
x0y1
x3y2
x2y1
x1y2
x0y2
x2y3
x1y3
x0y3
x0y0
Sommare i riporti in un secondo
stadio
ingressi
=
Adder
uscite
z7
Riduzione a due livelli della
matrice dei prodotti x0y0 , x1y0 , ...
z4
z5
z3
z2
z1
z0
Riduzione a due livelli
Riduzione a due livelli
X
x0y0
Moltiplicatore 6x6
x5y5
Y
Generazione matrice
(porte and)
Breve propagazione dei riporti
x0y0 , x1y0 , ...
Necessari contatori paralleli
Possono essere
necessari più livelli
di contatori
paralleli
z10
z9
z8
z7
z6
Riduzione a due righe
(contatori paralleli)
Sommatore
Adder
z11
z6
z5
z4
z3
z2
z1
z0
Z
complessi e lenti all'aumentare del numero
degli ingressi
Struttura non regolare
Moltiplicatore Wallace-Tree
Moltiplicatore Wallace-Tree
x1y0
x1y1
3 ingressi – 2 uscite
x0y0
x5y5
riduzione di un fattore 3:2
FA
Schema di collegamento (Wallace):
moltiplicazione a 32 bit
colonna di addendi più alta: 32 addendi
32
6
22
16
12
8
4
3
2
sommatore finale
Collegare il più possibile (con FA o HA) gli ingressi di ogni colonna
Uscite S sulla stessa colonna
Uscite C sulla colonna successiva
Colonna con un solo ingresso: collegare direttamente al livello successivo
8 FA e il sommatore finale
invece di
31 FA e il sommatore finale (Carry Save)
Moltiplicatore Wallace-Tree
Moltiplicatore Wallace-Tree
x0y0
x0y0
x5y5
x5y5
Moltiplicatore 6x6
Ripetere finché ci sono collegamenti da fare
Vector merging adder
Moltiplicatore Wallace-Tree
x5y0
x5y1
x5y2
x5y3
x5y4
x5y5
x4y0
x4y1
x4y2
x4y3
x4y4
FA
FA
FA
FA
x5y0
x4y0
x5y5
x4y4
Moltiplicatore Wallace-Tree
x6y1
x6y2
x6y3
x6y4
x6y5
HA
HA
FA
FA
FA
x5y0
x5y1
x5y2
x5y3
x5y4
x5y5
FA
FA
x4y0
x4y1
x4y2
x4y3
x4y4
FA
FA
x5y0
x4y0
x5y5
x4y4
HA
FA
FA
Moltiplicatore Dadda-Tree
Moltiplicatore Wallace-Tree
y0 y1
x1y0
x1y1
y2
y0 y1 y2
Ci-1
FA
y3
Ci
Ci-1
FA
x5y5
y3 y4 y5
FA
FA
Ci
Ci-1
Ci
Ci-1
y4
FA
Ci
Ci-1
FA
Ci
Ci-1
y5
FA
Ci
FA
C
S
Carry-Save
x0y0
C
S
Wallace-Tree
Breve propagazione dei riporti
Usa componenti semplici (FA, HA)
Struttura non regolare
Schema di collegamento (Dadda):
Collegare terne di ingressi di ogni colonna con un FA
Uscite S sulla stessa colonna
Uscite C sulla colonna successiva
Collegare un rimanente coppia di ingressi di una colonna con un HA solo se le uscite per
quella colonna modulo 3 sono 2
(se si tratta dell'ultimo livello: collegare con un HA se le uscite di quella colonna modulo
3 sono 1 o 2)
Colonna con un solo ingresso: collegare direttamente al livello successivo
Moltiplicatore Dadda-Tree
Compressore 4:2
x0y0
Cout
I1
x5y5
I2
I3
I4
C
Lo schema di Dadda tende a usare meno addizionatori nei livelli di riduzione ma ha
bisogno di un Vector merging adder più grande
S
Cin
In realtà è un 5:3
Ha 3 XOR sul percorso di generazione di S
(due FA in cascata ne hanno 4)
Moltiplicatore a codifica di Booth
X • 1111 = X + (X<<1) + (X<<2) + (X<<3)
X • 1111 = (X<<4) – X
Identificare le sequenze di 0 o di 1
Esaminare il moltiplicatore a coppie di bit
01 o 10: fine sequenza
00 o 11: sequenza
Moltiplicatore a codifica di Booth
Algoritmo per moltiplicare X=xxxxxxxx e Y=yyyyyyyy:
1. inizializzare P a 0
2. aggiungere uno 0 a destra di Y (Y diventa: yyyyyyyy0)
3. esaminare la coppia C di bit piu' a destra di Y
3.a se C=01 sommare X a P (P=P+X)
3.b se C=10 sottrarre X da P (P=P-X)
4. traslare X a sinistra di una posizione
5. traslare Y a destra di una posizione
6. tornare al punto 3 se non si sono esauriti i bit di Y
Moltiplicatore a codifica di Booth
79 x 83 :
X=
01001111 (79)
Y=010100110 P=0000000000000000 (0)
C=10: P=P-X=(0)-(79)=-79 ; Lshift X ; Rshift Y
X=
010011110 (158) Y= 01010011 P=1111111110110001 (-79)
C=11: Lshift X ; Rshift Y
X=
0100111100 (316) Y= 0101001 P=1111111110110001 (-79)
C=01: P=P+X=(-79)+(316)=237 ; Lshift X ; Rshift Y
X=
01001111000 (632) Y=
C=00: Lshift X ; Rshift Y
X=
010011110000 (1264) Y=
01010 P=0000000011101101 (237)
C=10: P=P-X=(237)-(1264)=-1027 ; Lshift X ; Rshift Y
X=
0100111100000 (2528) Y=
0101 P=1111101111111101 (-1027)
C=01: P=P+X=(-1027)+(2528)=1501 ; Lshift X ; Rshift Y
010100 P=0000000011101101 (237)
X= 01001111000000 (5056) Y=
010 P=0000010111011101 (1501)
C=10: P=P-X=(1501)-(5056)=-3555 ; Lshift X ; Rshift Y
X= 010011110000000 (10112) Y=
01 P=1111001000011101 (-3555)
C=01: P=P+X=(-3555)+(10112)=6557 ; Lshift X ; Rshift Y
Result = 6557