Capitolo 5
Circuiti programmabili
5.1 - Memorie a sola lettura
5.2 - Matrici logiche programmabili
5.3 - Unità aritmetica e logica
La programmazione dell’hardware
Funzioni di
n variabili
“macchina”
di
programmazione
Ho bisogno
di questa!
Le reti combinatorie programmabili
Rete combinatoria programmabile - Rete combinatoria
in grado di presentare diverse relazioni ingresso/uscita
singolarmente selezionabili mediante l’attribuzione di
una determinata configurazione ad un gruppo di ingressi
detti bit di programmazione.
p1 p2
x1
x2
xn
py
Rete
combinatoria
programmabile
z1
z2
zm
zi = F (p1,p2 ,…..,py ,x1,x2 ,…..,xn) = Fp (x1,x2 ,…..,xn)
5.1
Memorie a sola
lettura
La rete basata sull’espressione generale
2n-1
F(x1,x2,...xi,..xn) =  m(i) . F(i)
i=0
Espressione in grado
di descrivere qualsiasi
funzione di n variabili
Rete combinatoria
programmabile in grado
di realizzare qualsiasi
F funzione di n variabile
F(0)
F(1)
F(2n-1)
F(i): bit di
programmazione
x1 x2 xn
MUX come reti
programmabili
SN74157
I0
I1
Z
A
A,B,C,D
Ii
SN74153
I0
I1
I2
Z
I3
BA
SN74151
I0
I1
I2
I3
Z
I4
I5
I6
I7
CBA
ingressi ( xi )
bit di programmazione ( pi )
SN74150
I0
I1
I2
I3
I4
I5
I6
I7
Z
I8
I9
I10
I11
I12
I13
I14
I15
DCBA
ROM (Read Only Memory)
• I MUX disponibili nelle famiglie logiche hanno un basso numero
di segnali di selezione.
Difatti al crescere di n cresce esponenzialmente il numero dei pin
del circuito integrato da utilizzare per i bit di programmazione.
Esempio: n=16
216 = 65536 pin per la
programmazione !
• Le ROM sono reti combinatorie programmabili basate sulla
espressione generale SP ed aventi i bit di programmazione
integrati all’interno del dispositivo.
Struttura di una ROM (1)
Una diversa realizzazione
del MUX ( T5 )
I contatti al posto dei segnali
di programmazione
F(3) F(2) F(1)F(0)
x1 x0
x1 x0
F
F
F(i)=0/1
Contatto aperto/chiuso
Struttura di una ROM (2)
• Rappresentazione “compatta” della struttura di una ROM :
contatto
chiuso
contatto
aperto
x1 x0
F
G
O
• Realizzazione integrata di più funzioni.
Esempio: in un contenitore da 24 pin è possibile alloggiare un chip
che realizza o 8 funzioni di 14 variabili o una funzione di 21 variabili.
Le ROM come circuiti di memoria
A0
A1
.
.
An-1
D
E
C
m
0m
1
Bit di
programmazione
m2n-1
D0
D1
Dk
Ogni configurazione delle variabili di ingresso può essere vista
come l’indirizzo di un dato formato dai bit che sono stati
programmati nella riga corrispondente.
Le “vere e proprie” ROM
• I contatti vengono realizzati dal costruttore nell’ultimo stadio del
processo di fabbricazione del circuito su ordine dell’acquirente:
• Le ROM sono programmabili una sola volta (OTP: one time
programmable).
memorie a sola lettura (Read Only).
memorie non volatili
Memorie non volatili a sola lettura
Memorizzazione di informazioni che devono permanere quando
il sistema non è alimentato e che non non cambiano durante
il funzionamento .
Esempi: il “loader” visto in 3.2, il programma di un
sistema “embedded”, il BIOS del PC …..
Limitazioni delle ROM
Costi fissi elevati
Non adatte allo sviluppo
(OTP)
Grossi volumi di
produzione.
PROM (Programmable ROM)
i
La programmazione viene effettuata dall’utente mediante
un’apposita apparecchiatura che consente di “bruciare”
selettivamente i fusibili inseriti dal costruttore.
Convenienti per bassi-medi volumi di produzione
Dispositivi programmabili una sola volta
EPROM (Erasable PROM)
Q
Q
Programmazione effettuata dall’utente mediante una apposita
apparecchiatura che consente di inviare impulsi elettrici che
provocano accumulazione di carica sul terminale di comando.
Cancellazione ottenuta convogliando luce ultravioletta sui
terminali di comando attraverso una finestra di quarzo
presente sul contenitore.
Costo superiore a quello delle PROM
Dispositivi riprogrammabili
Memorie a sola lettura cancellabili
elettricamente
EEPROM (Electrically Erasable PROM) : si programmano e
cancellano byte-per-byte tramite segnali elettrici e senza
rimuovere il dispositivo dalla piastra stampata.
FLASH-EPROM: si programmano/cancellano elettricamente
direttamente sulla piastra. La cancellazione è più veloce rispetto
alle EEPROM: con un’unica operazione è possibile cancellare
l’intero dispositivo oppure uno o più “settori”.
Selezione a due dimensioni (1)
F(A2,A1, A0)
= A2’A1’A0’ F(0) + A2’A1’A0 F(1) + A2’A1A0’ F(2) + A2’A1A0 F(3) +
A2A1’A0’ F(4) + A2A1’A0 F(5) + A2A1A0’ F(6) + A2A1A0 F(7)
= A2’(A1’A0’ F(0) + A1’A0 F(1) + A1A0’ F(2) + A1A0 F(3)) +
A2 (A1’A0’ F(4) + A1’A0 F(5) + A1A0’ F(6) + A1A0 F(7))
m0
A0
A1
D
E
C
m1
m2
m3
F(0)
F(4)
F(1)
F(5)
F(2)
F(6)
F(3)
F(7)
Bit di
programmazione
A2
MUX
F
Selezione a due dimensioni (2)
Matrice di bit di programmazione
A0
A1
R
O
w
D
E
C
C
O
L
D
E
C
Am-1
Am
Am+1
An-1
M
U
X
D0
D1
Dk
Estensione del numero di uscite
xn
x1
x0
A0 A1 ……..An-1
ROM
D0 D1 …Dk
z0 z1 … zk
A0 A1 ……..An-1
ROM
D0 D1 …Dk
zk+1 zk+2 …z2k+1
Collegamento in parallelo di più ROM
Estensione del numero di ingressi
Teorema di espansione
m
A0 A1 ……..Am-1
A0 A1 ……..Am-1
ROM
D0
n-m
A0 A1 ……..Am-1
ROM
D0
ROM
D0
Dk
A
.. m
MUX
An-1
A
.. m
MUX
An-1
D0
Dk
N.B. - Al primo livello occorrono 2(n-m) ROM
Amplificatore a 3 stati d’uscita
O
I
OE
O
I
OE
OE
H
H
L
I
L
H
X
O
L
H
Z
OE
I
O
Lo stato elettrico del segnale
è indefinito o fluttuante (Terzo
Stato, Stato di Alta Impedenza)
MUX con amplificatori 3-state (1)
I0
In ogni istante di tempo
non deve esserci più
I1
Z
I2
I3
A0
A1
3
2
1
DEC
0
MUX
4:1
di un 3-state abilitato !
Situazione di corto circuito
(conflitto elettrico) con
possibili malfunzionamenti
del sistema
Le uscite del decoder non variano simultaneamente
Nei 3-state il tempo di risposta all’abilitazione (tpZH, tpZL) è
inferiore a quello necessario per il passaggio nel terzo stato (tpHZ, tpLZ)
MUX con amplificatori 3-state (2)
I0
I0
I1
I1
Z
Z
I2
I2
I3
I3
EN
A0
A1
3
2
1
DEC
Ai
EN
Z
0
EN
A0
A1
3
2 1 0
DEC
Stadio di uscita di una ROM
A0
A1
R
O
W
D
E
C
Bit di programmazione
Am-1
Am
Am+1
An-1
C
O
L
D
E
C
MUX
D0
D1
Dk
O0
O1
Ok
CE’
OE’
Progetto di un banco di ROM (1)
Supponiamo di voler connettere 32K byte di ROM ad una CPU
con 16 bit di indirizzo (A0..A15) ed 8 bit di dato e di avere a
disposizione dispositivi ROM da 8K x 8 . Supponiamo inoltre
che la CPU veda il banco di ROM nella parte alta del suo
spazio di indirizzamento (8000H - FFFFH, cioè A15=1).
Estensione del numero degli ingressi
a[0..12]
MRD
a15
A0 A1 …A12
ROM
D0
A0 A1 …A12
ROM
D0
A0 A1 …A12
ROM
D0
A0 A1 …A12
ROM
D0
D7
a[13,14]
MUX
MUX
d0
d7
Progetto di un banco di ROM (1)
MRD*
a[0..12]
A0 A1 …A12
ROM
OE*
CE*
D0
D7
a13
a14
a15
D
E
C
7
6
5
4
3
2
1
0
d0
d7
A0 A1 …A12
ROM
OE*
CE*
D0
D7
A0 A1 …A12
ROM
OE*
CE*
D0
D7
A0 A1 …A12
ROM
OE*
CE*
D0
D7
Esercizi 5.1 e 5.2
• Si riprogetti il banco di ROM da 32KB (byte) nel caso in cui si
disponga di una ROM 16K x 8, una ROM 8K x 8, due ROM
4K x 8.
• Si individui uno schema che consente di collegare al bus dati
8 pulsanti di cui il processore deve poter fare il polling
all’indirizzo di I/O 0000H.
5.2
Matrici logiche
programmabili
Rappresentazione di una ROM in
termini di matrici AND e OR
ROM 2x2
Caso generale
Matrice AND
Programmata
dal costruttore
NAND = 2n
Matrice OR
Programmata
dall’utente
N.B. - Ogni AND realizza un potenziale mintermine e può
essere impiegato per la programmazione di ciascuna uscita
(espressione generale SP).
PLA e PAL
PLA: Programmable
Logic Array
PAL: Programmable
Array Logic
Matrice AND
Programmata
dall’utente
Matrice AND
Programmata
dall’utente
NAND << 2n
Matrice OR
Programmata
dall’utente
Matrice OR
Programmata
dal costruttore
N.B. - Ogni AND realizza un implicante (espressione normale SP).
Nelle PLA gli implicanti possono essere “comuni” a più uscite.
Sintesi con PLA
cd
ab
00
01
11
10
00 01 11 10
1 1 0 1
1 1 0 1
0 0 1 1
0 0 1 1
z
a
b
c
d
cd
ab
00
01
11
10
00 01 11 10
0 0 0 1
0 0 1 1
0 0 0 0
1 1 0 0
w
z
w
Sintesi con PAL
cd
ab
00
01
11
10
00 01 11 10
1 1 0 1
1 1 0 1
0 0 1 1
0 0 1 1
z
a
b
c
d
cd
ab
00
01
11
10
00 01 11 10
0 0 0 1
0 0 1 1
0 0 0 0
1 1 0 0
w
N.B. - Quando non si dispone di un numero sufficiente di AND
può essere utile realizzare la funzione complemento.
z’
w
Esercizio 5.3
• Si sintetizzi un trascodificatore da codice BCD a codice Gray
utilizzando una PAL con 4 ingressi, 4 uscite e 4 AND per uscita.
ABCD
WXYZ
0
0
0
0
0
0
0
0
1
1
1
0
1
0
1
0
1
0
1
0
1
1
0 0 0 0
0 0 0 1
0 0 1 1
0 0 1 0
0 1 1 0
1 1 1 0
1 0 1 0
1 0 1 1
1 0 0 1
1 0 0 0
XXXX
1 0 0 1
XXXX
0
0
0
0
1
1
1
1
0
0
0
0
0
1
1
0
0
1
1
0
0
0
BCD
Gray
PAL con I/O programmabile (16L8)
5.3
Unità aritmetica
e logica
ALU: Arithmetic and Logic Unit
c
flag
x
ALU
y
u
u = Fc (x , y)
ALU - Rete combinatoria in grado di eseguire diverse
operazioni di tipo aritmetico o logico. L’operazione di
volta in volta eseguita dipende dal valore attribuito ai
bit di programmazione (codice operazione)
CI
C2 C1 C0
0 0 0
0
1
x+y x+y+1
C2 C1 C0
0 0 0
C3
0
1
xy
x or y
(x  y)’ (xy)’
0 0 1
x - y -1
x -y
0 0 1
0 1 0
x
x+1
0 1 0
x
0 1 1
x-1
x
0 1 1
x’
1 0 0
y
y+1
1 0 0
y
1 0 1
-(y +1)
-y
1 0 1
y’
x or y’
1 1 0
0
1
1 1 0
0000
x and y
1 1 1
24 -1 , -1
0
1 1 1
1111
1111
M=1
pag. 5.23
x
x’ or y
y
M=0
pag. 5.25
Sottrazione fra numeri naturali
• Sottrazione fra due numeri da un bit
0 - 0 = 0 ; 1 - 0 = 1 ; 1 - 1 = 0 ; 0 - 1 : quantità non rappresentabile.
• Sottrazione “colonna per colonna” fra due numeri da n bit
D=A- B
(A  B)
pn-1
pi
p1 0
an-1
ai
a1 a0
bn-1
bi
b1 b0
dn-1
di
d1 d0
-
pab
P
D
000
001
010
011
100
101
110
111
0
1
0
0
1
1
0
1
0
1
1
0
1
0
0
1
Complemento a 2 di un numero naturale
N formato da n bit
2N
= 2n - N
Calcolo di 2N senza la sottrazione
2N = 2n - N
= (2n - 1) - N + 1
= not (N) + 1
1
Calcolo di A - B con A  B
A
A - B = A + (2n - B) - 2n
= (A + 2B) - 2n
• calcola A + 2B
• elimina il bit più pesante
B
CI 4 BIT
a0 ADDER
a1
a2
a3
s0
s1
s2
s3
b0
b1
b2
b3
CO
A-B
1
Numeri relativi: rappresentazione
segno-valore assoluto
n bit
bn-1 bn-2
b1 b0
segno
(0: positivo, 1: negativo)
valore assoluto
|N| = (bn-2 .2n-2 + …+ b0 .20)
N  [-(2n-1 - 1), +(2n-1 - 1)]
Numeri relativi: rappresentazione in
complemento a 2
N  0 : segno-valore assoluto
n bit
bn-1 bn-2
b1 b0
N < 0 : 2(-N)
con (-N) espresso in
segno-valore assoluto
Esempi ( n=4 )
+1 = 0 0 0 1
-1 = 1 1 1 0 +
1
=1 111
N.B. - anche nella rappresenta+7 = 0 1 1 1
- 7 = 1 0 0 0 + zione in complemento a 2 il bit
più significativo indica il
1
segno (0:positivo, 1:negativo).
=1 001
N = -2n-1 . bn-1 + bn-2 .2n-2 + …+ b0 .20
N  [-2n-1, +(2n-1 - 1)]
Proprietà della rappresentazione
in complemento a 2
Siano A e B due numeri nella rappresentazione in complemento a 2:
• eseguendo 2A si ottiene -A
A: 0 0 0 1 (+1)
1 0 0 1 (-7)
1110 +
0110 +
1
1
2A: 1 1 1 1
(-1)
0 1 1 1 (+7)
• eseguendo A+B si ottiene la somma algebrica fra A e B:
A = -3 1 1 0 1 + A = -4 1 1 0 0 +
B = -4 1 1 0 0 = B = +3 0 0 1 1 =
-7
1001
-1
1111
• eseguendo A + 2(B) si ottiene A - B
A = -4 1 1 0 0 +
B = +5 0 1 0 1 =
+1
0001
N.B. - per sommare o sottrarre due numeri relativi espressi in
complemento a 2 è sufficiente un addizionatore.
Esercizi 5.4 e 5.5
• Utilizzando una rappresentazione in complemento a 2 con n=5 si
eseguano le seguenti operazioni:
(-12) + (+4)
(-12) + (-1)
(-12) - (-12)
(-12) + (+12)
(-12) + (-4)
(+10) - (+5)
(+10) - (+11)
(+12) +(+5)
(-14) + (-4)
• Qual’è il valore dei seguenti numeri relativi espressi nella
rappresentazione in complemento a 2:
1111, 11111111, 11111110, 1110, 01111111, 10000000
Un “adder/subtractor” programmabile
CI
CI 4 BIT
a0 ADDER
a1
a2
a3
s0
s1
s2
s3
b0
b1
b2
b3
CO
x
C0
y
0
M
U
1X
CI
C0
0
0
x+y
1 x-y-1
1
x+y+1
x -y
u
….. più operazioni aritmetiche
C2 C1 C0
0 0 0
C2 CI
x
‘0000’
0M
U
X
1
C1
y
0M
U
‘0000’ X
1
C0
0M
U
X
1
CI 4 BIT
a0 ADDER
a1
a2
a3
s0
s1
s2
s3
b0
b1
b2
b3
CO
u
CI
0
1
x+y x+y+1
0 0 1
x - y -1
x -y
0 1 0
x
x+1
0 1 1
x-1
x
1 0 0
y
y+1
1 0 1
-(y +1)
-y
1 1 0
0
1
1 1 1
24 -1 , -1
0
Sintesi della rete di pre-elaborazione
ak = c2’ . xk +c2 . 0 = c2’ . xk
bk = c0’ . (c1’. yk) + c0 .(c1’ .yk)’ = c0  (c1’ . yk)
C1
x0
C0
C2
CI
CI
a0
4 BIT
ADDER
4 BIT
ADDER
x1
a1
x2
a2
s
s0 0
a3
s
s1 1
x3
y0
b0
y1
b1
y2
b2
y3
b3
s2s2
s3s
3
CO
u
Bit di modalità e operazioni logiche
M (bit di modalità, 0: logica, 1: aritmetica)
C2 C1 C0 CI
x
Rete
di
pre-elabor.
y
CI
a0
a1
a2
a3
b0
b1
b2
b3
M
C2 C1 C0
0 0 0
4 BIT
ADDER
con M
s0
s1
s2
s3
CO
M
M=0
r
R
a FA
b
s
s=ab
xy
0 0 1 (x  y)’
u
r
R
a FA
s
b
M=0
0 1 0
x
0 1 1
x’
1 0 0
y
1 0 1
y’
1 1 0
0000
1111
1 1 1
....più operazioni logiche
C3
C1
C0
C2
M=0
xk
ak r
FA
yk
uk
bk R
C2 C 1 C0
C3
0 0 0
M=0
0 0 1
x  y (xy)’
1 x + y (xy)’
0
sk
0 1 0
0 1 1
x
x
x’
x’ + y
1 0 0
y
y
1 0 1
1 1 0
1 1 1
y’
x + y’
0000
x .y
1111
1111
N. B. - In questa tabella “.” è il simbolo della
somma logica e “+” quello del prodotto.
Segnali di “flag”
c
ZF
ZERO FLAG: vale “1” se il
risultato vale “0”.
SF
SIGN FLAG: vale “1” se il
risultato è negativo.
CF
CARRY FLAG: vale “1” se
CO=1 .
flag
x
ALU
y
u
OF
OVERFLOW FLAG: vale “1” in caso di traboccamento
del risultato di un’operazione fra numeri relativi
rappresentati in complemento a 2.
PF
PARITY FLAG: vale “1” se il bit di parità del risultato
vale 1.
Generazione dei flag per una ALU a 4 bit
ZF = (u0 + u1 + u2 + u3)’
SF = u3
CF = CO
OF = r3  CO
CO r3 r2 r1
(-7)
(-2)
1000
1001+
1110=
0110
CO r3 r2 r1
(+7)
(+2)
PF = u0  u1  u2  u3
0110
0111+
0010=
1001
La ALU a 4 bit
C3 C 2 C1 C0
M
CI
x0
a0 M r0 s
0
x1
b0
ZF SF CF OF
PF
u0
R
x2
x3
Rete
di
pre-elabor.
y0
a1 M r1s
1
b1
u1
R
a2 M r2s
2
b2
u2
R
y1
y2
y3
a3 M r3s
3
b3
u3
R
CO
Uno “shifter” a 4 bit
R
W0 = 0 . L .R’ +
u0 .L’ .R’ +
u1 .L’ .R
Wi = ui-1 . L .R’ +
ui . L’ .R’ +
ui+1 . L’ .R
i=1,2
W3 = u2 . L . R’ +
u3 . L’ . R’ +
0 . L’ . R
u0
L 0
w0
u1
w1
u2
w2
u3
w3
0
Esercizi 5.6 e 5.7
• Si determini la tabella delle operazioni eseguite dalla ALU nel
caso M=1.
• Si indichi come deve essere modificato lo shifter per poter
eseguire anche delle divisioni per 2 su numeri relativi rappresentati
in complemento a 2.