Moduli Combinatori
Moduli Combinatori
Corso di Architetture degli Elaboratori
Coder 1
Circuito codificatore
x0
x1
.
.
.
.
.
z0
zk
n=2k
xn
La linea su cui si ha valore 1 viene codificata in uscita
mediante log2n bit.
RETI LOGICHE
2
Coder 2
Circuito codificatore
RETI LOGICHE
3
Coder 3
Realizzazione di codificatori per composizione
RETI LOGICHE
4
Decoder 1
Circuito decodificatore
z0
z1
x0
k=2n
xn
zk
Per ognuno dei k valori in input viene posto il valore 1 su
una diversa linea in uscita
RETI LOGICHE
5
Decoder 2
Esempio di decodificatori per k=2,3
RETI LOGICHE
6
Decoder 3
Realizzazione di codificatori per composizione
Matrice di AND 4x4
Decoder a 2
variabili
RETI LOGICHE
7
Decoder 4
Composizione
Decoder a 2
variabili
x0 x1
4x4=16 AND (2 ingressi)
x2 x3
x4 x5
x6 x7
Matrice di
AND 4x4x4x4
256 AND (4 ingressi)
.........................................
z0
RETI LOGICHE
z 63
8
Decoder 5
Composizione
Decoder a 4
variabili
2x16=32 AND (4 ingressi)
x0 x1 x2 x3
x4 x5 x6 x7
Matrice di
AND 16x16
256 AND (2 ingressi)
.........................................
z0
RETI LOGICHE
z 255
9
Mux 1
Multiplexer (selettore)
a0
ak
...............
k=2n
x0
xn
.
.
Il valore sulla linea ai selezionata dal
valore x0,…,xn è dato sull’uscita z
RETI LOGICHE
z
10
Mux 2
Esempio di multiplexer per n=2
a0
a1
a2
a3
x0
x1
z
RETI LOGICHE
11
Mux 3
Multiplexer mediante decodificatori
a0
a1
a2
a3
x0
x1
z
RETI LOGICHE
12
Mux 4
Implementazione di funzioni mediante multiplexer
0 1 1 1 0 0 1 0
x3
x2
x1
y
0
0
0
0
0
1
0
1
0
0
1
1
0
1
1
1
0
0
1
0
1
1
0
0
1
1
1
1
0
1
1
0
x0
x1
x2
y
Vengono poste a 1 le linee corrispondenti
ai mintermini della funzione
RETI LOGICHE
13
Demux 1
Demultiplexer (deselettore)
z
x0
k=2n
xn
.
.
...............
a0
ak
Il valore sulla linea z è posto sulla linea di uscita ai
selezionata dal valore x0,…,xn
RETI LOGICHE
14
Demux 2
Implementazione di demultiplexer mediante codificatori
z
x0
x1
a0
RETI LOGICHE
a1
a2
a3
15
Mux-Demux
Multiplexer-Demultiplexer
a0
ak
...............
x0
k=2n
h=2m
xn
y0
ym
Il valore sulla linea di ingresso
selezionata dal valore x0,…,xn
è posto sulla linea di uscita ai
selezionata dal valore y0,…,ym
.
.
.
.
RETI LOGICHE
...............
b0
bh
16
Adder 1
Addizionatore
a
b
r
s
r’
0
0
0
0
0
1
0
1
0
0
1
1
0
0
0
0
1
1
1
0
0
1
0
1
0
1
0
1
0
1
1
1
1
1
0
1
0
1
1
1
s =¬a¬br+ ¬ab¬r+a¬b¬r+abr=
=(ab) r
r’ =br+ar+ab
s =¬r’(a+b+r)+abr
RETI LOGICHE
17
Adder 2
Addizionatore
r’ =br+ar+ab
s =¬a¬br+ ¬ab¬r+a¬b¬r+abr=
=(ab) r
s =¬r’(a+b+r)+abr
s
s
r’
a b r
r’
a b r
RETI LOGICHE
18
Adder 3
Addizionatore
a
1-bit adder
r
r’
s
4-bit adder
a0 b0
0
a1 b1
r0
s0
b
a2 b2
r1
s1
r2
s2
RETI LOGICHE
a3 b3
r3
s3
19
Adder 4
Addizionatore veloce
Suddivisione dei bit da sommare in blocchi
All’interno di un blocco, i bit si sono calcolati nel modo
usuale.
I bit di riporto sono trattati con reti combinatorie
aggiuntive, che consentano di propagare il riporto più
velocemente (carry look-ahead)
RETI LOGICHE
20
Adder 5
Addizionatore veloce
Calcolo rapido del riporto all’interno di un blocco
Definiamo Pi = aibi e Gi = aibi
allora si = Pi ri-1 e ri = Gi + Pi ri-1
Consideriamo un blocco da 4 bit. Allora il riporto al blocco
successivo è (r è il riporto dal blocco precedente)
r4 = G4 + P4 r3 = G4 + P4 (G3 + P3 r2) =
= G4 + P4 (G3 + P3 (G2+ P2 r1) ) =
= G4 + P4 (G3 + P3 (G2+ P2 (G1+ P1 r) ) ) =
= G4 + P4G3 + P4P3G2+ P4P3P2G1+ P4P3P2P1 r
Il riporto dal blocco è calcolato in parallelo sui vari bit, con
una unica rete a 4 livelli.
RETI LOGICHE
21
Adder 6
Addizionatore veloce
Blocco dell’addizionatore veloce
a0 b0 a1 b1 a2 b2 a3 b3
r
r’
s0 s1 s2 s3
Circuito di somma
Circuito di generazione riporto
al blocco successivo
RETI LOGICHE
22
Adder 7
Addizionatore veloce
Calcolo rapido della propagazione del riporto da un
blocco all’altro
Definiamo Ci = ai+bi
se Ci = 0 allora l’eventuale riporto
viene assorbito durante la somma del bit i-esimo
Consideriamo un blocco di 4 bit, allora se
C4C3 C2 C1 = 0 l’eventuale riporto dal blocco precedente
viene assorbito nelle somme effettuate in questo blocco
(che potrebbero generare un nuovo riporto).
La propagazione del riporto nel blocco è calcolata in
parallelo sui vari bit, con una unica rete a 2 livelli.
RETI LOGICHE
23
Adder 8
Addizionatore veloce
a0 b0 a1 b1 a2 b2 a3 b3
rp
r
s
s
s s
Circuito di somma
r’
rg
Circuito di propagazione riporto
al blocco successivo
RETI LOGICHE
24
Adder 9
Addizionatore veloce
Fase1. Il blocco opera con r =0 (per non aspettare il
riporto precedente) e calcola rg , il riporto generato.
Fase 2. Il blocco determina la propagazione rp di riporti
precedenti.
Fase 3. Il blocco calcola la somma corretta,
considerando il giusto riporto precedente.
RETI LOGICHE
25
Adder 10
Addizionatore in complemento a 2
Come l’addizionatore già visto.
Necessità di rilevare l’overflow.
Si ha overflow se i due addendi hanno lo stesso segno,
mentre il risultato ha segno opposto.
Quindi per un addizionatore a n bit:
o = an-1 bn-1¬sn-1 + ¬an-1 ¬bn-1sn-1
RETI LOGICHE
26
Adder 11
Addizionatore in complemento a 2
an-1 bn-1
a0 b0 a1 b1
.......
r0
s0 s1
o
s n.1
RETI LOGICHE
27
ALU 1
ALU
L’introduzione di componenti logiche aggiuntive e
di segnali di controllo permette di realizzare una
rete che può eseguire più operazioni.
a0
.
a.n-1
x0
b0
.......
.......
.
.
bn-1
x1
r0
.......
s0 s1
s n.1 o
RETI LOGICHE
28
ALU 2
ALU
Operazioni effettuate
x0
x1
r0
0
0
0
¬B
0
0
1
-B
0
1
0
B
0
1
1
B+1
1
0
0
A+¬B=A-B-1
1
0
1
A-B
1
1
0
A+B
1
1
1
A+B+1
RETI LOGICHE
29
ALU 3
ALU
L’introduzione di segnali di controllo opportuni può
estendere ulteriormente l’insieme delle operazioni
elementari svolte dalla ALU
Ad esempio, si introducano due segnali l0, l1 che
vengono inseriti nel circuito di riporto di tutti i
blocchi dell’adder
s =¬r’(a+b+r)+abr
r’ =br+ar+ab
r’ =br+ar+l0ab+l1
RETI LOGICHE
30
ALU 4
ALU
r’ =br+ar+l0ab+l1
s =¬r’(a+b+r)+abr
Allora, si ha che:
l0=1, l1=0
Si calcola la somma
l1=1
Comporta che r’=1 su tutti i blocchi,
ponendo r0=1 si ha che r=1 su
tutti i blocchi, e quindi che
s =ab su ogni blocco. L’ALU calcola
l’AND bit a bit.
l0=0, l1=0
Se si pone r0=0 si ha che r’=0 e
s=a+b su tutti i blocchi. L’ALU
calcola l’OR bit a bit.
RETI LOGICHE
31