Reti logiche
Circuiti aritmetici
Capitolo 5: Circuiti aritmetici
Reti Logiche
Contemporary Logic Design
Randy H. Katz
University of California, Berkeley
May 1993
Trasparenze tradotte da:
Luciano Lavagno
Universita’ di Udine
Settembre 1998
© R.H. Katz 5-1
Motivazioni
Reti logiche
Circuiti aritmetici
Circuiti aritmetici sono un’ottimo esempio di progetto di reti logiche
• Decisioni di progetto sull’asse spazio/tempo
Calcolare velocemente richiede reti piu’ complesse e
quindi piu’ spazio
Esempio: circuito di carry lookahead
• Unita’ logico-aritmetica
Componente fondamentale di processori moderni
Usata nel ciclo principale di quasi tutte le istruzioni
© R.H. Katz 5-2
Riassunto del capitolo
Reti logiche
Circuiti aritmetici
• Rappresentazione dei numeri binari
Modulo e segno, complemento ad uno, complemento a due
• Somma binaria
Rivediamo il full-adder...
• Progetto di ALU
• Circuiti BCD
• Circuito moltiplicatore combinatorio
• Esempio di progetto: moltiplicatore ad 8 bit
© R.H. Katz 5-3
Numerazione binaria
Reti logiche
Circuiti aritmetici
Rappresentazione dei numeri negativi
La rappresentazione dei numeri positivi e’ la stessa in tutti i casi
La differenza fondamentale e’ come sono rappresentati i numeri
negativi
Tre metodi principali:
modulo e segno
complemento ad uno
complemento a due
In questo capitolo:
supporremo una parola a 4 bit
si possono rappresentare 16 valori
circa meta’ sono positivi e meta’ sono negativi
© R.H. Katz 5-4
Reti logiche
Circuiti aritmetici
Numerazione binaria
Rappresentazione in modulo e segno
-7
-6
-5
1111
1110
+0
+1
0000
0001
1101
0010
+2
+
-4
1100
0011
+3
0 100 = + 4
-3
1011
0100
+4
1 100 = - 4
-2
1010
0101
1001
-1
+5
-
0110
1000
-0
0111
+6
+7
Bit piu’ significativo (MSB) e’ il segno:
0 = positivo (o zero), 1 = negativo
Tre bit meno significativi sono il modulo: da 0 (000) a 7 (111)
Intervallo per n bit = +/-2n-1 -1
Due rappresentazioni per lo 0!!
© R.H. Katz 5-5
Reti logiche
Circuiti aritmetici
Numerazione binaria
Modulo e segno
Somma e sottrazione sono difficili
Bisogna confrontare i moduli per decidere il segno
Complemento ad uno
Se N e’ un numero positivo, allora N e’ l’opposto,
ottenuto complementando ad 1
n
N = (2 - 1) - N
2 4 = 10000
-1
= 00001
Esempio: complemento ad 1 di 7
1111
-7
=
Metodo piu’ rapido:
0111
1000
= -7 in cpl. ad 1
basta calcolare il complemento bit a bit
0111 -> 1000
© R.H. Katz 5-6
Reti logiche
Circuiti aritmetici
Numerazione binaria
Complemento ad uno
-0
-1
-2
1111
1110
+0
+1
0000
0001
1101
0010
+2
+
-3
1100
0011
+3
0 100 = + 4
-4
1011
0100
+4
1 011 = - 4
-5
1010
0101
1001
-6
+5
-
0110
1000
-7
0111
+6
+7
Sottrazione realizzata con complemento ad 1 e somma
Ci sono ancora due rappresentazioni dello 0!
Cio’ causa ancora dei problemi
Complessita’ aggiuntiva per la somma
© R.H. Katz 5-7
Reti logiche
Circuiti aritmetici
Numerazione binaria
Complemento a due
-1
-2
-3
Come il
complem. ad 1
ma spostato
di una posizione
in senso orario
1111
1110
+0
+1
0000
0001
1101
0010
+2
+
-4
1100
0011
+3
0 100 = + 4
-5
1011
0100
+4
1 100 = - 4
-6
1010
0101
1001
-7
+5
-
0110
1000
-8
0111
+6
+7
Solo una rappresentazione dello 0
Un numero negativo in piu’ dei positivi
© R.H. Katz 5-8
Reti logiche
Circuiti aritmetici
Numerazione binaria
Numeri in complemento a due
n
N* = 2 - N
4
2 = 10000
Esempio: complemento a 2 di 7
sub 7 =
0111
1001 = repr. of -7
Esempio: complemento a 2 di -7
4
2 = 10000
sub -7 =
1001
0111 = repr. of 7
Metodo abbreviato:
Complemento a 1 = complemento ad 1 (bit a bit) + 1
0111 -> 1000 + 1 -> 1001 (rappresentazione di -7)
1001 -> 0110 + 1 -> 0111 (rappresentazione di 7)
© R.H. Katz 5-9
Reti logiche
Circuiti aritmetici
Numerazione binaria
Somma e sottrazione binarie
Modulo e segno
Quando i segni sono
uguali, basta sommare
ed il segno del risultato
e’ uguale a quelli degli
operandi
Quando i segni sono
diversi, bisogna sottrarre
ed il segno del risultato
dipende da quello
del numero
con il modulo piu’ grande
4
0100
-4
1100
+3
0011
+ (-3)
1011
7
0111
-7
1111
4
0100
-4
1100
-3
1011
+3
0011
1
0001
-1
1001
© R.H. Katz 5-10
Reti logiche
Circuiti aritmetici
Numerazione binaria
Somma e sottrazione binarie
Calcoli in complemento ad uno
4
0100
-4
1011
+3
0011
+ (-3)
1100
7
0111
-7
10111
“Riporto all’inizio”
1
1000
4
0100
-4
1011
-3
1100
+3
0011
1
10000
-1
1110
“Riporto all’inizio”
1
0001
© R.H. Katz 5-11
Numerazione binaria
Reti logiche
Circuiti aritmetici
Somma e sottrazione binarie
Calcoli in complemento ad uno
Perche’ il riporto all’inizio funziona?
E’ come sottrarre 2n e sommare 1
n
n
M - N = M + N = M + (2 - 1 - N) = (M - N) + 2 - 1
n
n
-M + (-N) = M + N = (2 - M - 1) + (2 - N - 1)
n
n
= 2 + [2 - 1 - (M + N)] - 1
(M > N)
M+N<2
n-1
dopo il riporto all’inizio:
n
= 2 - 1 - (M + N)
questa e’ la rappresentazione corretta di -(M + N)
in complemento ad uno!
© R.H. Katz 5-12
Reti logiche
Circuiti aritmetici
Numerazione binaria
Somma e sottrazione binarie
Calcoli in complemento a due
4
0100
-4
1100
+3
0011
+ (-3)
1101
7
0111
-7
11001
Se il riporto sul segno e’
uguale al riporto in uscita,
ignorare il riporto
Se il riporto sul segno e’
diverso dal riporto in uscita,
overflow!
4
0100
-4
1100
-3
1101
+3
0011
1
10001
-1
1111
Questo meccanismo piu’ semplice di somma rende il complemento
a due la rappresentazione piu’ usata nei calcolatori
© R.H. Katz 5-13
Reti logiche
Circuiti aritmetici
Numerazione binaria
Somma e sottrazione binarie
Calcoli in complemento a due
Perche’ possiamo ignorare il riporto in uscita?
-M + N se N > M:
M* + N = (2
n
- M) + N = 2
n
+ (N - M)
Ignorare il riporto in uscita e’ come sottrarre 2n
-M + -N se N + M < = 2n-1
n
n
-M + (-N) = M* + N* = (2 - M) + (2 - N)
n
n
= 2 - (M + N) + 2
Ignorando il riporto, questa e’ la rappresentazione corretta
in complemento a due di -(M + N)!
© R.H. Katz 5-14
Reti logiche
Circuiti aritmetici
Numerazione binaria
Condizioni di overflow
Sommare due numeri negativi ed ottenerne uno positivo
oppure due positivi ed ottenerne uno negativo
-1
-2
1111
0001
-4
1101
0010
1100
-5
0100
1010
0101
1001
-7
0110
1000
-8
0111
+6
+7
5 + 3 = -9
-3
+2
0011
1011
-6
-2
+1
0000
1110
-3
-1
+0
+3
-4
1111
+1
0000
1110
0001
1101
0010
1100
-5
1011
+4
+5
+0
1010
-6
0110
1000
-8
0011
+3
0100
+4
0101
1001
-7
+2
0111
+5
+6
+7
-7 - 2 = +7
© R.H. Katz 5-15
Reti logiche
Circuiti aritmetici
Numerazione binaria
Condizioni di overflow
5
0111
0101
-7
1000
1001
3
0011
-2
1100
-8
1000
7
10111
Overflow
Overflow
5
0000
0101
-3
1111
1101
2
0010
-5
1011
7
0111
-8
11000
Non e’ overflow
Non e’ overflow
Overflow quando il riporto sul segno e’ diverso
dal riporto in uscita
© R.H. Katz 5-16
Reti logiche
Circuiti aritmetici
Reti per somma binaria
Half Adder
In complemento a due, basta la somma
Ai Bi Sum Carry
0 0
0
0
0 1
1
0
1 0
1
0
1 1
0
1
Ai
0
Bi
0 0
1
1
1
1
0
Sum = Ai Bi + Ai Bi
Ai
0
Bi
0
0
1
0
1
0
1
Carry = Ai Bi
= Ai + Bi
Ai
Sum
Schema dell’half-adder
Bi
Carry
© R.H. Katz 5-17
Reti logiche
Circuiti aritmetici
Reti per somma binaria
Full Adder
A3 B3
Sommatore multi-bit
in cascata
A2 B2
A1 B1
+
+
S3
C3
A0 B0
+
S2
C2
+
S1
C1
S0
di solito si sommano numeri con piu’ di un bit
quindi serve il full adder (con riporto)
© R.H. Katz 5-18
Reti logiche
Circuiti aritmetici
Reti per somma binaria
Full Adder
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
CI
0
1
0
1
0
1
0
1
S
0
1
1
0
1
0
0
1
CO
0
0
0
1
0
1
1
1
AB
CI 00 01 11 10
S
0
0
1
0
1
1
1
0
1
0
AB
CI 00 01 11 10
CO
0
0
0
1
0
1
0
1
1
1
S = CI xor A xor B
CO = B CI + A CI + A B = CI (A + B) + A B
© R.H. Katz 5-19
Reti logiche
Circuiti aritmetici
Reti per somma binaria
Full Adder/Half Adder
Metodo standard: 6 porte
A
B
A
B
S
CI
CI
CO
A
B
Realizzazione con half-adder: 5 porte
A
B
S
A+B
Half
AdderCO A B
S
A + B + CI
Half
Adder CO CI (A + B)
S
CI
+
CO
A B + CI (A xor B) = A B + B CI + A CI
© R.H. Katz 5-20
Reti logiche
Circuiti aritmetici
Reti per somma binaria
Sommatore/sottrattore
A 3 B 3 B3
A 2 B2 B2
0 1 Sel
A
B
CO +
CI
A 1 B1 B1
0 1 Sel
0 1 Sel
A
B
CO +
CI
A 0 B 0 B0
A
B
CO +
CI
0 1 Sel
A
B
CO +
S
S
S
S
S3
S2
S1
S0
CI
Add/Subtrac t
Overflow
A - B = A + (-B) = A + B + 1
© R.H. Katz 5-21
Reti logiche
Circuiti aritmetici
Reti per somma binaria
Circuito di carry lookahead
Ritardo critico: propagazione del riporto dagli stadi precedenti
segnale
che si
stabilizza
piu’ tardi
@0
@0
A
B
@1
@N+1
@N CI
@0
@0
CO
@N+2
A
B
@1
ritardo di
due porte per
calcolare CO
C0
A0
sommatore
a 4 stadi
B0
S0 @2
0
C1 @2
A1
B1
S1 @3
1
C2 @4
A2
B2
2
S2 @5
C3 @6
A3
B3
3
S3 @7
C4 @8
somma e riporto
finali
© R.H. Katz 5-22
Reti per somma binaria
Reti logiche
Circuiti aritmetici
Circuiti di carry lookahead
Ritardo critico: propagazione del riporto dagli stadi precedenti
1111 + 0001
caso peggiore
per somma
T0: ingressi del sommatore validi
T2: riporto in uscita stadio 0 (C1)
T4: riporto in uscita stadio 1 (C2)
T6: riporto in uscita stadio 2 (C3)
T8: riporto in uscita stadio 3 (C4)
2 ritardi per calcolare
la somma
ma l’ultimo riporto e’ valido
solo dopo 6 ritardi
© R.H. Katz 5-23
Reti logiche
Circuiti aritmetici
Reti per somma binaria
Circuiti di carry lookahead
Carry Generate Gi = Ai Bi
generare il riporto se A = B = 1
Carry Propagate Pi = Ai xor Bi
riporto in uscita = riporto in ingresso
Sum e Carry possono essere espressi in funzione di Gi e Pi
Si = Ai xor Bi xor Ci = Pi xor Ci
Ci+1 = Ai Bi + Ai Ci + Bi Ci
= Ai Bi + Ci (Ai + Bi)
= Ai Bi + Ci (Ai xor Bi)
= Gi + Ci Pi
© R.H. Katz 5-24
Reti per somma binaria
Reti logiche
Circuiti aritmetici
Circuiti di carry lookahead
Riscriviamo la logica del riporto come segue:
C1 = G0 + P0 C0
C2 = G1 + P1 C1 = G1 + P1 G0 + P1 P0 C0
C3 = G2 + P2 C2 = G2 + P2 G1 + P2 P1 G0 + P2 P1 P0 C0
C4 = G3 + P3 C3 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0 + P3 P2 P1 P0 C0
Ogni equazione puo’ essere rappresentata su due livelli
Le variabili di ingresso sono gli addendi ed il riporto di ingresso
allo stadio 0!
© R.H. Katz 5-25
Reti logiche
Circuiti aritmetici
Reti per somma binaria
Carry Lookahead Implementation
Ai
Bi
Pi @ 1 ritardo
Ci
Si @ 2 ritardi
Sommatore con uscite
Generate e Propagate
Gi @ 1 ritardo
Logica di lookahead
sempre piu’ complicata!
C0
P0
C1
G0
C2
G1
P2
G2
G1
C0
P0
P1
P2
P3
G0
P1
P2
C0
P0
P1
G0
P1
C0
P0
P1
P2
C3
G0
P1
P2
P3
G1
P2
P3
G2
P3
C4
G3
© R.H. Katz 5-26
Reti logiche
Circuiti aritmetici
Reti per somma binaria
Circuiti di carry lookahead
Carry lookahead in cascata
La logica di
lookahead genera
tutti i riporti
C0
A0
S0 @ 2
B0
C1 @ 3
Le somme possono
essere calcolate
molto piu’ in fretta!
A1
S1 @ 4
B1
C2 @ 3
A2
S2 @ 4
B2
C3 @ 3
A3
S3 @ 4
B3
C4 @ 3
© R.H. Katz 5-27
Reti logiche
Circuiti aritmetici
Reti per somma binaria
Circuiti di carry lookahead
Carry lookahead in cascata
4
4
4
C16 A [15-12] B[15-12] C12
4-bit Adder
P G
4 @8
S[15-12]
@2 @3
C16
@5
P3
C4
G3
4
4
A [11-8] B[1 1-8] C
8
4-bit Adder
P G
4 @8
S[1 1-8]
@5
C3
@2 @3
P2
G2
4
A [7-4]
B[7-4]
4-bit Adder
P G
4 @7
S[7-4]
@5
C2
A [3-0]
B[3-0]
4-bit Adder
P G
C4
4
C0
@0
@4
S[3-0]
@4
@2 @3
P1 G1
4
4
C1
@2 @3
P0
G0
C0
Lookahead Carry Unit
P3-0 G3-0
@3
C0
@0
@5
sommatori a 4 bit con lookahead interno
unita’ di lookahead di secondo livello estende il
calcolo del riporto a 16 bit
© R.H. Katz 5-28
Reti logiche
Circuiti aritmetici
Reti per somma binaria
Sommatore a selezione del riporto
Logica ridondante per calcolare il riporto piu’ in fretta
C8
C4
C8
4¥
2:1 Mux
C8
4-Bit Adder
[7:4]
0
Adder
Low
4-Bit Adder
[7:4]
1
Adder
High
1 0 1 0 1 0
S7
S6
S5
1 0
S4
C4
C0
4-Bit Adder
[3:0]
S3
S2
S1
S0
Calcolare le somme degli MSB in parallelo
una somma suppone riporto = 0
l’altra suppone riporto = 1
© R.H. Katz 5-29
Progetto di unita' logico-aritmetica (ALU)
Reti logiche
Circuiti aritmetici
Esempio di ALU
M = 0, operazioni logiche bit-a-bit
S1 S0
0 0
0 1
1 0
1 1
Funzione
Fi = Ai
Fi = not Ai
Fi = Ai xor Bi
Fi = Ai xnor Bi
Commento
Copiare ingresso A in uscita
Copiare complemento di A in uscita
Calcolare XOR di A, B
Calcolare XNOR di A, B
M = 1, C0 = 0, operazioni aritmetiche
0 0
F=A
Copiare ingresso A in uscita
0 1
F = not A
Copiare complemento di A in uscita
1 0
F = A piu’ B
Sommare A e B
1 1
F = (not A) piu’ B
Sommare B ed il cpl. ad 1 di A
M = 1, C0 = 1, operazioni aritmetiche
0
0
1
1
0
1
0
1
F = A piu’ 1
F = (not A) piu’ 1
F = A piu’ B piu’ 1
F = (not A) piu’ B piu’ 1
Incrementare A
Complemento a due di A
Sommadi A piu’ B piu’ 1
B meno A
Operazioni aritmetiche e logiche
Non tutte le operazioni servono, ma sono il “risultato automatico”
della logica interna
© R.H. Katz 5-30
Reti logiche
Circuiti aritmetici
Progetto di unita' logico-aritmetica (ALU)
M
0
Esempio di ALU
Progetto tradizionale
S1
0
S0
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
0
0
0
1
1
0
1
1
Tavola di verita’ ed espresso
.i 6
.o 2
m
23 termini prodotto! .ilb
.ob fi
.p 23
111101
110111
1-0100
Equivalente a
1-1110
25 porte
1001010111-10001
010-01
-11011
011-11
--1000
0-1-00
--0010
0-0-10
-0100001-0-0001000-1-1-1-1
--1-01
--0-11
--110--011.e
s1 s0 ci ai bi
co
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
01
01
01
01
01
1
1
Ci
X
X
X
X
X
X
X
X
X
X
X
X
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
1
1
1
1
Ai
0
1
0
1
0
0
1
1
0
0
1
1
0
1
0
1
0
0
1
1
0
0
1
1
0
1
0
1
0
0
1
1
0
0
1
1
Bi
X
X
X
X
0
1
0
1
0
1
0
1
X
X
X
X
0
1
0
1
0
1
0
1
X
X
X
X
0
1
0
1
0
1
0
1
Fi
0
1
1
0
0
1
1
0
1
0
0
1
0
1
1
0
0
1
1
0
1
0
0
1
1
0
0
1
1
0
0
1
0
1
1
0
Ci+1
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
0
0
0
1
0
1
0
0
0
1
1
0
0
1
1
1
1
1
0
1
© R.H. Katz 5-31
Reti logiche
Circuiti aritmetici
Progetto di unita' logico-aritmetica (ALU)
Esempio di ALU
Realizzazione multi-livello
.model alu.espresso
.inputs m s1 s0 ci ai bi
.outputs fi co
.names m ci co [30] [33] [35] fi
110--- 1
-1-11- 1
--01-1 1
--00-0 1
\S1
.names m ci [30] [33] co
\Bi
-1-1 1
--11 1
M
S1
111- 1
Bi
.names s0 ai [30]
01 1
S0
10 1
Ai
.names m s1 bi [33]
111 1
.names s1 bi [35]
0- 1
-0 1
.end
[35]
[33]
Ci
[33]
[30]
[33]
Co
M
Ci
[30]
[30]
M
Ci
\Co
Ci
[30]
[33]
\Co
[30]
[35]
\Co
\[30]
\[35]
Fi
12 porte
© R.H. Katz 5-32
Progetto di unita' logico-aritmetica (ALU)
Reti logiche
Circuiti aritmetici
Esempio di ALU
Realizzazione piu’ “intelligente” multi-livello
S1 Bi
S0
Ai
M
X1
A1
A2
Ci
S1 = 0 blocca Bi
Serve nelle operazioni su Ai
Lo stesso succede a Ci se M = 0
Esegue somma se M = 1
Bi, Ci vanno alle porte XOR X2, X3
X2
S0 = 0, X1 passa A
S0 = 1, X1 passa A
A3
A4
Modo aritmetico:
Gli ingressi della porta OR sono
Ai Ci e Bi (Ai xor Ci)
O1
Ci+1
X3
Modo logico:
Fi
8 porte (ma 3 sono XOR)
Gli XOR in cascata generano
l’uscita da Ai e Bi
© R.H. Katz 5-33
Progetto di unita' logico-aritmetica (ALU)
Reti logiche
Circuiti aritmetici
74181 ALU TTL
S3
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
Selection
S2 S1 S0
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
M=1
Logic Function
F = not A
F = A nand B
F = (not A) + B
F=1
F = A nor B
F = not B
F = A xnor B
F = A + not B
F = (not A) B
F = A xor B
F=B
F = A+ B
F=0
F = A (not B)
F = AB
F=A
M = 0, Arithmetic Functions
Cn = 0
Cn = 1
F = A minus 1
F=A
F = A B minus 1
F = AB
F = A (not B) minus 1
F = A (not B)
F = minus 1
F = zero
F = A plus (A + not B)
F = A plus (A + not B) plus 1
F = A B plus (A + not B)
F = A B plus (A + not B) plus 1
F = A minus B minus 1
F = (A + not B) plus 1
F = A + not B
F = A minus B
F = A plus (A + B)
F = (A + not B) plus 1
F = A plus B
F = A plus (A + B) plus 1
F = A (not B) plus (A + B)
F = A (not B) plus (A + B) plus 1
F = (A + B)
F = (A + B) plus 1
F=A
F = A plus A plus 1
F = A B plus A
F = AB plus A plus 1
F= A (not B) plus A
F = A (not B) plus A plus 1
F=A
F = A plus 1
© R.H. Katz 5-34
Reti logiche
Circuiti aritmetici
Progetto di unita' logico-aritmetica (ALU)
74181 ALU TTL
Notate che il tipo dei riporti di ingresso ed uscita (attivo alto)
e’ OPPOSTO rispetto agli ingressi (attivi bassi)
19
21
23
2
18
20
22
1
A3
A2
A1
A0
B3
B2
B1
B0
7 Cn
8 M
181
F3
F2
F1
F0
13
11
10
9
A=B 14
Cn+4 16
G 17
P 15
S3 S2 S1 S0
3 4 5 6
6
15
2
4
5
14
1
3
182
P3
P2
P1
P0
G3
G2
G1
G0
P
G
7
10
Cn+z 9
Cn+y 11
Cn+x 12
13 Cn
Per fortuna il generatore di carry lookahead
usa anch’esso riporti attivi alti
© R.H. Katz 5-35
Reti logiche
Circuiti aritmetici
Progetto di unita' logico-aritmetica (ALU)
ALU a 16 bit con carry lookahead
19 A3
21 A2 181 F3
23 A1
F2
2 A0
F1
18 B3
F0
20 B2
A=B
22 B1
Cn+4
1 B0
G
7 Cn
P
8M
S3S2S1S0
3 4 5 6
19
21
23
2
18
20
22
1
7
8
A3
A2
A1
A0
B3
B2
B1
B0
Cn
M
13
11
10
9
14
16
17
15
F3 13
F2 11
F1 10
F0 9
A=B 14
Cn+4 16
G 17
P 15
181
S3S2S1S0
3 4 5 6
19 A3
21 A2
23 A1
2 A0
18 B3
20 B2
22 B1
1 B0
7 Cn
8M
C16
181 F3
F2
F1
F0
A=B
Cn+4
G
P
13
11
10
9
14
16
17
15
6 P3182
15 P2
2 P1
P
4 P0
G
5 G3
14 G2 Cn+z
1 G1 Cn+y
3 G0 Cn+x
13 Cn
7
10
9
11
12
S3 S2S1S0
3 4 5 6
C0
19
21
23
2
18
20
22
1
7
8
A3
A2
A1
A0
B3
B2
B1
B0
Cn
M
181 F3
F2
F1
F0
A=B
Cn+4
G
P
13
11
10
9
14
16
17
15
S3S2S1S0
3 4 5 6
© R.H. Katz 5-36
Reti logiche
Circuiti aritmetici
Somma BCD
Rappresentazione BCD
Cifre da 0 a 9 rappresentate come numeri da 0000 a 1001 in binario
Somma:
5 = 0101
3 = 0011
1000 = 8
5 = 0101
8 = 1000
Problema
quando la somma
di una cifra e’ piu’ di 9
1101 = 13!
Soluzione: sommare 6 (0110) se la somma e’ piu’ di 9!
5 = 0101
9 = 1001
8 = 1000
7 = 0111
1101
6 = 0110
1 0011 = 1 3 in BCD
1 0000 = 16 in binario
6 = 0110
1 0110 = 1 6 in BCD
© R.H. Katz 5-37
Reti logiche
Circuiti aritmetici
Somma BCD
Progetto di un sommatore
A3
B3
CO FA
CI
S
A1
11XX
A2
1X1X
A2
B2
CO FA
S3
B1
CO FA
CI
A0
CI
CO FA
S
S
S2
S1
B0
CO FA
S
S
CO FA
Cout
CI
A1
CI
Cin
S
CI
0
S0
Sommare 0110 alla somma quando e’ maggiore di 1001 (11XX o 1X1X)
© R.H. Katz 5-38
Reti logiche
Circuiti aritmetici
Moltiplicatore combinatorio
Idea base
moltiplicando
moltiplicatore
1101 (13)
* 1011 (11)
prodotto di 2 numeri a 4 bit
e’ un numero ad 8 bit
1101
1101
prodotti parziali
0000
1101
10001111
(143)
© R.H. Katz 5-39
Reti logiche
Circuiti aritmetici
Moltiplicatore combinatorio
Accumulazione prodotti parziali
S7
A3
A2
A1
A0
B3
B2
B1
B0
A2 B0
A2 B0
A1 B0
A0 B0
A3 B1
A2 B1
A1 B1
A0 B1
A3 B2
A2 B2
A1 B2
A0 B2
A3 B3
A2 B3
A1 B3
A0 B3
S6
S5
S4
S3
S2
S1
S0
© R.H. Katz 5-40
Reti logiche
Circuiti aritmetici
Moltiplicatore combinatorio
Accumulazione prodotti parziali
A 3 B3 A 3 B2 A 2 B3 A 3 B1 A 2 B2 A 1 B3 A 3 B0 A 2 B1 A 1 B2 A 0 B3 A 2 B0 A 1 B 1 A 0 B 2 A 0 B 1 A 1 B 0 A 0 B0
FA
FA
S7
HA
FA
FA
FA
FA
HA
FA
S6
S5
S4
S3
HA
HA
FA
S2
S1
S0
Notare l’uso dei carry-out in parallelo
per le somme di ordine piu’ elevato
12 sommatori: se sono full adder, servono 6 porte ciascuno = 72 porte
16 porte formano i prodotti parziali
totale = 88 porte!
© R.H. Katz 5-41
Reti logiche
Circuiti aritmetici
Moltiplicatore combinatorio
Un’altra rappresentazione del circuito
Sum In
X
Blocco base: full adder + and
Cin
Y
FA
A B
CO CI
S
Cout
Sum Out
A3
B0
A3 B0
C
B1
A3 B1
C
B2
A3 B2
C
B3
C
A2 B2
C
S
S
S
A2 B3
A1 B3
A0 B3
S
S
S
S
P6
P5
P4
P3
A0
A2 B0
A1 B0
A0 B0
S
C
A1 B1
C
A1 B2
C
A1
C
A2 B1
A3 B3
C
P7
S
S
S
A2
S
S
C
S
A0 B1
C
S
A0 B2
C
S
P2
P1
P0
Matrice 4 x 4 di blocchi base
© R.H. Katz 5-42
Reti logiche
Circuiti aritmetici
Esempio di progetto: moltiplicatore 8 x 8
Moltiplicatore TTL
A0
A1
A2
A3
B0
B1
B2
B3
14
2
8
4
G
A
13
4 7 6 5 15 1 2 3
A A A A B B B B G
3 2 1 0 3 2 1 0 B
14
2
8
5
Y Y Y Y
7 6 5 4
9 10 11 12
Y6
Y7
Y4
Y5
Y2
Y3
G
A
13
4 7 6 5 15 1 2 3
A A A A B B B B G
3 2 1 0 3 2 1 0 B
Y Y Y Y
3 2 1 0
9 10 11 12
Y0
Y1
Realizzazione con 2 integrati di un moltiplicatore 4 x 4
© R.H. Katz 5-43
Reti logiche
Circuiti aritmetici
Esempio di progetto: moltiplicatore 8 x 8
Decomposizione del problema
Come realizzare la moltiplicazione 8 x 8 usando moltiplicatori 4 x 4?
*
A7-4
A3-0
B7-4
B3-0
A3-0 * B3-0
prodotti ad 8 bit
A7-4 * B3-0
= PP1
A3-0 * B7-4
= PP2
A7-4 * B7-4
P15-12
= PP0
P11-8
= PP3
P7-4
P3-0
P3-0 = PP0 3-0
P7-4 = PP0 3-0 + PP1
+ PP2
+ Carry-in
3-0
3-0
P11-8 = PP1 7-4 + PP2 7-4 + PP3 3-0 + Carry-in
+ Carry-in
P15-12 = PP3 7-4
© R.H. Katz 5-44
Reti logiche
Circuiti aritmetici
Esempio di progetto: moltiplicatore 8 x 8
Calcolo dei prodotti parziali
A6
A7
A4
A5
B6 B4
B7 B5
4 x 4 Multiplier
74284/285
PP3
7-4
PP3
3-0
A2
A3
A0
A1
B6 B4
B7 B5
4 x 4 Multiplier
74284/285
PP2
7-4
PP2
3-0
A6
A4
A5
A7
B2 B0
B3 B1
4 x 4 Multiplier
74284/285
PP1
7-4
PP1
3-0
A2
A0
A1
A3
B2 B0
B3 B1
4 x 4 Multiplier
74284/285
PP0
7-4
PP0
3-0
Usare 4 coppie di 74284/285 per creare i 4 prodotti parziali
© R.H. Katz 5-45
Reti logiche
Circuiti aritmetici
Esempio di progetto: moltiplicatore 8 x 8
Sommatore tre-per-volta
Uso intelligente dei riporti in ingresso
Sommare A[3-0], B[3-0], C[3-0]:
FA
C3
FA
A0 B0
A1 B1
A2 B2
A3 B3
C2
FA
C1
FA
FA
FA
S3
S2
S1
FA
C0
0
S0
Circuito di somma a due livelli
Nota: si puo’ usare anche carry lookahead!
© R.H. Katz 5-46
Esempio di progetto: moltiplicatore 8 x 8
Sommatore tre-per-volta con componenti TTL
Reti logiche
Circuiti aritmetici
C3 B3 A3 C2 B2 A2 C1 B1 A1 C0 B0 A0
Cn B A Cn B A
74 183
74 183
Cn+1 S Cn+1 S
Cn B A Cn B A
74 183
74 183
Cn+1 S Cn+1 S
Full Adder
(2 per integrato)
+
B3 A3
G
P
Cn+4
F3
B2 A2
B1 A1
74 181
B0 A0
ALU standard configurata
come sommatore di
secondo livello a 4 bit
(con carry lookahead interno)
Cn
F2
F1
F0
S
3
S
2
S
1
S
0
Notare lo spostamento delle uscite!
© R.H. Katz 5-47
Reti logiche
Circuiti aritmetici
Esempio di progetto: moltiplicatore 8 x 8
Accumulazione dei prodotti parziali
PP1
PP2
PP3
PP3
7
6
PP3
5
PP3
4
PP3
7
7
PP3
PP1
2
PP2
PP2
2
PP1 PP3
6
1
3
Cn B A Cn B A
74183
74183
Cn +1 S Cn +1 S
5
PP3
5
PP0
0
PP2
4
PP1
PP1
4
Cn B A Cn B A
74183
74183
Cn +1 S Cn +1 S
PP2
3
7
PP2
PP0
2
PP1
PP1
2
PP0 PP2
6
1
3
Cn B A Cn B A
74183
74183
Cn +1 S Cn +1 S
5
PP2
1
0
PP1
0
PP0
4
Cn B A Cn B A
74183
74183
Cn +1 S Cn +1 S
+
B3 A3
G
P
Cn +4
F3
B2 A2
B1 A1
74181
B0 A0
Cn
F2
F1
F0
P
15
P
14
P
13
B3 A3
G
P
Cn +4
F3
B2 A2
B1 A1
F2
F1
F0
B3 A3
G
P
Cn +4
F3
P
12
P
11
P
10
P
9
P
8
74181
B0 A0
Cn
B2 A2
B1 A1
74181
B0 A0
Cn
F2
F1
F0
P
7
P
P
5
6
P
4
Basta una cascata di sommatori tre-per-volta
© R.H. Katz 5-48
Reti logiche
Circuiti aritmetici
Esempio di progetto: moltiplicatore 8 x 8
Il sistema completo
A7-0
B7-0
8
8
Partia l Product Calcula tion
4 x 74 284, 742 85
4
4
PP3
7-4
PP3
PP2
3-0
4
4
7-4
PP2
PP1
3-0
4
0
G
P
Cn+4
P
15
P
14
Cn
P
13
7-4
4
PP1
3-0
G
P
Cn+4
P
12
74 181
P
11
P
10
4
4
PP0
PP0
7-4
4
4
2 x 74 183
PP3 PP3 PP3 PP3
7
4
6
5
74 181
4
4
4
3-0
4
2 x 74 183
Cn
P
9
P
8
74 181
P
7
P
6
Cn
P
5
P
4
P
3-0
+
G3 P3 G2 P2 G1 P1 G0 P0
74 182
Cn
Cn+z
Cn+y Cn+x
G
P
Cn+4
+
© R.H. Katz 5-49
Esempio di progetto: moltiplicatore 8 x 8
Calcolo dei circuiti integrati e prestazioni
Reti logiche
Circuiti aritmetici
4 coppie 74284/74285 = 8 integrati
4 74183, 3 74181, 1 74182 = 8 integrati
16 integrati in totale
Calcolo prodotti parziali (74284/285) = 40 ns typ, 60 ns max
Somme intermedie74183) = 9 ns/20ns = 15 ns typ, 33 ns max
Somme di secondo livello con carry lookahead
74LS181: carry G e P = 20 ns typ, 30 ns max
74182: carry di secondo livello = 13 ns typ, 22 ns max
74LS181: formazione delle somme = 15 ns typ, 26 ns max
Totale: 103 ns typ, 171 ns max
© R.H. Katz 5-50
Riassunto del capitolo
Reti logiche
Circuiti aritmetici
Abbiamo esaminato:
• Rappresentazioni dei numeri binari
per i numeri positivi e’ sempre la stessa
la differenza e’ nella rappresentazione dei numeri negativi
complemento a due e’ il piu’ semplice:
una sola rappresentazione per lo zero,
complementazione (sottrazione) un po’ complicata
somma facile
• Reti per somma ad un bit
HA, FA di base
circuiti di carry lookahead
• Progetto di una ALU
specifica e realizzazione
• Sommatori BCD
semplice estensione di sommatori binari
• Moltiplicatori
moltiplicatore 4 x 4: accumulazione prodotti parziali
estensione al caso 8 x 8
© R.H. Katz 5-51