Sistemi Digitali
1
Definizione
DEF Sistemi Digitali Sono tutti quegli apparati al cui
interno le grandezze fisiche impiegate come segnali sono
vincolate ad assumere solo valori discreti.
DEF Sistemi Binari Sono quei sistemi digitali in cui i
segnali sono limitati a due valori di regime.
2
Analog Waveform
Voltage (V)
5
Time
0
Digital Waveform
1
1
Voltage (V)
5
0
0
Time
3
Analisi e Sintesi
Rispetto ai sistemi analogici, nei quali i segnali possono
assumere tutti i possibili valori in un continuo, i sistemi
digit ali consentono una minore complessitˆdei dispositivi
che devono generare i segnali, ed una maggiore immunitˆ
ai disturbi.
Un sistema digitale Ž un circuito costituito da componenti
elementari e dai collegamenti c he li int erconnettono. I
componenti elementari possono essere di due tipi: porte o
elementi di memoria.
L'obiettivo di questo corso Ž lo studio di
problemi di analisi e sintesi di sistemi digitali.
¥
¥
analisi dal circuito alla specifica formale
sintesi dalla specifica funzionale al circuito
4
“Viste” della progettazione
digitale.
I.
Vista comportamentale: descrive le funzioni
indipendentemente dallΥimplementazione (es:
progettare un circuito che esegua la somma aritmetica
fra due numeri interi )
II. Vista strutturale: decsrive il modello di
interconnessione dei componenti (es: disegno dei
componenti digitali elementari e loro interconnessioni)
III. Vista fisica: componenti fisici (es. transistors, layout)
5
6
Campi di Applicazione
La p rogettazione digitale interessa tutti i c ampi di
applicazione dell'elettronica:
Calcolo Automatico
Telecomunicazioni
Controlli Automatici
Misure Elettriche
....
In questo corso, oltre ad introdurre i principi generali
di progetto di sistemi digitali, siamo interessati a
studiare applicazioni nel campo del Calcolo
Automatico.
Gli Elaboratori Elettronici sono sistemi digitali
complessi in g rado di leggere, elaborare e trasmettere
7
informazioni binarie.
Componenti di un Computer
digitale
4 funzioni logiche fondamentali:
Controllo : sequenziare le operazioni di un
computer, controllando le azioni di tutti gli altri
moduli.
- Elaborazione Logico-Aritmetica: eseguire
operazioni aritmetiche e logiche (descritte in questo
corso). L'unitŽ di controllo indica quali operazioni
eseguire e come.
8
Componenti di un Computer
digitale (2)
- Memoria: q
uesta
sezione
contiene
l'informazione
da
utilizzare
durante
l'elaborazione. Per informazione si i ntendono
istruzioni e dati.
Distinguiamo due tipi di memoria:
o la memoria principale
o la memoria secondaria
- Ingresso-uscita: abilita la lettura di dati
all'interno della macchina ed il trasferimento di dati
all'esterno. I dispositivi esterni possono essere:
- dispositivi di memorizzazione (dischi, nastri, ecc.)
- dispositivi di ingresso (sensori, tastiere, fax..)
- dispositivi di uscita (stampanti, video, fax..)
9
v ideo, display ,ecc.
stampanti
Interf accia
con
Unità
logicoaritmetica
Dispositiv i
di uscita
Memoria
Principale
Interf accia
con
Unità
di
Controllo
Dispositiv i
di Ingresso
Interf accia con
dispositiv i di
memorizzazione
terminali
sensori, ecc
Dischi,
Dischi ottici,
nastri, ecc.
10
Rappresentazione
dell'Informazione
• I calcolatori elettronici sono macchine in grado di elaborare
informazioni trasformandole in altre informazioni.
• Nel mondo dell'informatica, intendiamo in modo più restrittivo
per informazione tutto ciò che può essere rappresentato tramite
opportune sequenze di simboli in un alfabeto prefissato.
• La rappresentazione estensionale di un insieme I é un insieme di
parole ognuna delle quali esprime un elemento di I.
Esempio: mela,pera,uva,arancia
• Un codice C é un insieme di parole composte da simboli di un
alfabeto S (detto alfabeto di supporto di C).
11
Codifica e decodifica
CODIFICA
La codifica di un insieme di informazioni I in un dato
codice C Ž
u na funzione
f: I  C
Esempio:
mela 
 00, pera 
 01, uva 
 10, arancia
dove S

 11,
DECODIFICA
La decodifica di una informazione codificata in precedenza
Žuna corrispondenza g : C  I
12
Esempio
Il cifrario di Cesare, usato nei tempi dell'antica Roma,
aveva la seguente funzione di codifica:
f: i 
 i+3(mod 26) i=0,1..25
dove al numero 0 corrisponde la lettera a, 1 a b ecc.
Secondo tale codice, la parola "babbo" Ž codificata come
"edeer" ecc;
13
Criteri di valutazione di una
codifica
Economicitˆ: sono considerate migliori rispetto a questa
caratteristica le codifiche che utilizzano pochi simboli.
Semplicitˆ dicodifica e decodifica: Žauspicabile poter
trasformare un linguaggio da un codice all'altro in modo
efficiente
Semplicitˆ di elaborazione: sono preferibili le codifiche
che consentono di eseguire le operazioni definite sui dati in
modo agevole (ad esempio, sostituendo ai simboli arabi i
simboli dei numeri romani, "saltano" il meccanismo del
riporto e della posizionalitŽ
).
14
Sistemi posizionali
Un sistema numerico posizionale in base b , ovvero basato
su un alfabeto S di b simboli distinti, consente di esprimere
un qualsiasi numero naturale N di m cifre, mediante la:
m 1
N   cib , ci  S
i
i 0
Ad esempio, nel sistema decimale (b=10,S=0,1,..9), la
sequenza N10= 284 può essere espressa come:
2x102+8x101+4x100
15
16
Codice binario
Codice binario: costituito dai simboli 0 ed 1. I simboli 0
ed 1 prendono il nome di bit, una contrazione per "binary
digit ".
George Boole dimostrŽcome la logica possa essere ridotta
ad un sistema algebrico molto semplice, che utilizza solo un
codice binario (zero e uno, vero e falso).
Il codice binario fu trovato particolarmente utile nella
teoria della commutazione per descrivere il comportamento
dei circuiti digit ali (1=acceso, 0=spento).
17
Sistemi Binari (2)
Claude Shannon defin“ un metodo per rappresentare un
qualsiasi circuito costituto da un combinazione di
interruttori (e/o rŽlais) mediante un insieme di espressioni
matematiche, basate sulle regole dell'algebra Booleana.
Un numero naturale booleano di m bit puŽessere
rappresentata mediante la:
N

i  0..m  1
ci 2i , ci  0,1
Il bit c0 , viene detto LSB (less signifying bit) mentre cm-1
viene detto bit piŽsignificativo , o MSB.
18
19
Cambiamenti di base e
artimetica in base b
•Numeri Naturali
•Numeri Interi
•Numeri decimali in virgola fissa e
mobile
20
RAPPRESENTAZIONE DEI
NATURALI
Sistema posizionale (in base b  2)
cm-i cm-2 … c1 c0
con
= S i = 0,…,m-1 ci bi
ci  { 0 , … , b-1 }
Problema : passare da Na a Nb (con N un naturale ed
a e b le basi desiderate)
21
Conversione di Base
• Problema: convertire un numero N espresso in
base a Na in un numero N’ espresso in base b:
N’b
• Metodo polinomiale: usare l’espressione:
n
Na   pi ai pi S a
im
22
Conversione di base
• Metodo polinomiale:
Si esprime il numero Na come un polinomio,
usando i numeri dell’alfabeto b nel polinomio
Si valuta il polinomio usando l’aritmetica in
base b
1011.1012  1 23 1 21 1 20 1 2 1  0  2 2 1 2 3 
8  2 11/ 2  1/ 8  (11,625)10
23
Conversione di base
• Metodo iterativo:
1. Si divide N per b (in base a), sia Q il quoziente e r il resto.
r è il bit meno significativo della parte intera di N’b
2. (finché Q>0) ripeti:
esegui Q/b : quoziente=Q’ resto=r’
Q’Q N’b r’ N’b
Esempio: 2310=101112 (a=10 e b=2)
23
Q:
11
5
2
1
0
r:
1
1
1
0
1
Nota: divido per 2 con l’aritmetica decimale. 2 espresso con codice MSB
binario è la stringa 10!!!
24
Esempio 2
Esempio 1 : esprimere in base 16 il numero 31710
317
13
16
19 16
16
I. D 1
0
D
3
1
1NOTATE che,0 nell’algoritmo sopra descritto, la
Pertanto 317 10 = 13D 16
divisione va eseguita in base a (cioè nella base del
numero di partenza). Se a10, questo può risultare
complicato.
25
Esempio 3
Convertire il numero 102202 da base 3 a
base 5
Due strade :
a) eseguire 102202 /3 12
la divisione in base 3)
(cioè effettuare
=> DIFFICILE!!!
b) convertire 102202 in base 10 e poi
convertire il risultato in base 5
- 102202 3 = 35 + 233 + 232 + 2 = 317 10
col procedimento dell'esempio precedente
317 10 = 2232 5
26
Conversioni da base 2 a base 2n
Prop. : lavorando il aritmetica in base b si ha
che
1) nm-1 … n1 n0 DIV bi = nm-1 … ni r=
ni-1 … n0
2) nm-1 … n1 n0 MOD bi = ni-1 … n0
(r = resto, MOD = modulo)
Es: 353 10 DIV 100 =35 (r=3) 1011 2 DIV 21
= 101 r=1
Da ciò :
Conversione da base 2 a base 2n : considera i
bit a n-uple partendo dal meno significativo e
traducile in base 2n
Esempio 3 : convertire 100111101 da base 2 a
base 4=22
1 00 11 11 01 2 = 1 0 3 3 1 4
(sequenza dei resti per successive divisioni per
22)
27
ARITMETICA IN BASE b PER I
NATURALI
Tutte le operazioni vengono eseguite come in
base 10 , ma modulo b ( Es.: ( 1 + 1 ) 2 = 10 2 )
e quindi anche i riporti e i p restiti agiscono modulo b.
In base 2 si ha:
0+0=0, riporto=0
0+1=1+0=1. rip=0
1+1=0, rip=1
Esempio: sommare in base 2 i numeri 1001 e
111
1001 +
111 =

10000
28
Aritmetica binaria (2)
• Sottrazione:
Differenza
Prestito
0-0
0
0
0-1
1
1
1-0
1
0
1-1
0
0
• Se c’è un prestito (borrow) e il bit adiacente è un 1, questo
viene modificato in uno zero
• Se c’è un prestito (borrow) e il bit adiacente è uno 0,
questo è modificato in 1, e così tutti i bit successivi, finché
non si incontra un bit=1. Questo viene posto=0, e si
ripristina il processo di sottrazione
29
Aritmetica binaria (2)
• Sottrazione:
Differenza
Prestito
0-0
0
0
0-1
1
1
1-0
1
0
1-1
0
0
• Se c’è un prestito (borrow) e il bit adiacente è un 1, questo
viene modificato in uno zero
• Se c’è un prestito (borrow) e il bit adiacente è uno 0,
questo è modificato in 1, e così tutti i bit successivi, finché
non si incontra un bit=1. Questo viene posto=0, e si
ripristina il processo di sottrazione
30
31
32
Aritmetica binaria (3)
• Esempio:
011
11000
-10001
00111
(24-17=7)
01011
101000
- 011001
001111
(40-25=15)
33
Lunghezza di parola
Nota: Un elaboratore lavora con “parole” (stringhe
binarie) di lunghezza fissa (diciamo n ). La
dimensione massima e minima dei numeri
rappresentabili dipende dalla lunghezza di parola.
Quindi:
 se un numero è codificato con meno di n bit
dobbiamo inserire in testa (n-m) zeri non
significativi
 se un numero è codificato con più di n bit :
dobbiamo considerare solo le n cifre meno
significative (situazione di errore detta overflow)
34
RAPPRESENTAZIONE DEGLI
INTERI
 Rispetto ai naturali, il problema è la
rappresentazione del segno.
 Esistono tre modalità di rappresentazione: in
modulo e segno, in complemento a uno e in
complemento a due.
 I primi due rendono le operazioni di somma e
sottrazione delicate (sono necessari controlli
preliminari sul segno e sui valori assoluti degli
operandi)
 Col secondo, invece, la sottrazione si esegue
semplicemente come somma dell’opposto (a
patto di ignorare l’eventuale overflow derivante
dalla somma di numeri negativi).
35
36
Aritmetica binaria (4)
Rappresentazione in complemento a 2:
(utile per trattare interi negativi)
2N
n2 i
 2 pi , pi (0,1)
i0
= -2n-1p n-1+
Il bit MSB rappresenta il segno: 0 = +, 1= I numeri negativi vanno da -2n-1 a -1
Quindi, per n=4 da 1000 (-8) a 1111 (-1)
37
Esempi
•
•
•
•
•
•
•
+3 = 00000011
+2 = 00000010
+1 = 00000001
+0 = 00000000
-1 = 11111111
-2 = 11111110
-3 = 11111101
38
Descrizione geometrica della
rappresentazione di interi in Ca2
39
Range dei Numeri in Ca2
• 8 bit (Ca2)
• +127 = 01111111 = 27 -1
• -128 = 10000000 = -27
• 16 bit (Ca2)
• +32767 = 011111111 11111111 = 215 - 1
• -32768 = 100000000 00000000 = -215
Il più grande numero positivo ha il primo bit 0 e
tutti gli altri 1. Il più grande numero negativo
(in valore assoluto) ha il primo bit 1 e tutti gli
altri zero
40
•
•
•
•
Complemento a 2
Proprietà-benefici:
Rappresenta i numeri da -2n-1 a +2n+1
Una sola interpretazione per “0”
Un numero negativo si esprime in
complemento a 2 invertendo i bit del
corrispondente numero positivo, e poi
sommando 1 (segue dimostrazione)
• Regola della sottrazione in Ca2:
• N1-N2=N1+not(N2)+1
41
Sottrazione in complemento a 2
• Sia A un numero espresso in complemento a 2:
n2 i
n1
2
pn1   2 pi
A=
i1
Invertiamo tutti i bit di A e sommiamo 1:
n2 i
n1
A'  A  1  2
pn1  1   2 pi
i0
Si dimostra che A’=-A !!!! Ne consegue:
2 ( N1 N2)  2 ( N1 N2  1)
42
Dimostrazione
• A=-A’A-A’=0
A-A’=
n2
n2 i
n1
i
n1
(2
pn1   2 pi )  (2
pn1   2 pi  1) 
i1
i1
n2
( pn1  pn1)2n1 1   2i ( pi  pi ) 
i0
n _1 i
n1
2
1  2  2n1  1 (2 n1 1)  0
i0
43
Sottrazione
• Quindi, per eseguire una sottrazione in binario
fra interi rappresentati in complemento a 2,
basta sommare al minuendo il complemento
del sottraendo e sommare 1
44
Moltiplicazione
•
•
•
•
Complessa
Funziona con prodotti parziali
Slittamento dei prodotti parziali
Somma prodotti parziali
45
Esempio
•
1011 Moltiplicando (11 dec)
•
x 1101 Moltiplicatore (13 dec)
•
1011 Prodotti parziali
•
0000 Nota: se il Mt=1 COPIA Md
• 1011
(slittando il valore)
• 1011
altrimenti prod_parz=0
• 10001111 Prodotto (143 dec)
• Nota: il risultato ha lunghezza doppia!
46
Divisione
• Più complessa della moltiplicazione
• In particolare per numeri negativi
• In dettaglio nel corso di Arc. II
47
Divisione per Interi senza segno
1101
1011 10010011
1011
001110
Resti parziali
1011
001111
1011
100
Divisore
Quoziente
Dividendo
Resto
48
49
Rappresentazione dei numeri
Reali
Virgola fissa e mobile
50
Numeri reali in virgola fissa
Il problema aggiuntivo è la rappresentazione della
parte intera e di quella frazionaria.
Abbiamo sempre un sistema posizionale (in base b 
2). I primi m bit rappresentano la parte intera, i
successivi n la parte frazionaria.
cm  1....c0 c1c 2...c n

parteintera parte frazionaria
n
i
 c ib
i  m 1
con ci  { 0 , … , b-1 }
51
Precisione
NOTA: la precisione con cui i numeri possono essere
espressi è f inita e predeterminata perchè questi
devono essere memorizzati in un determinato spazio
di memoria
2  1.141421356
52
Cambiamento di base
Riserva m bit per la parte intera (P.I.) e n bit per la parte
frazionaria (P.F.) ( m e n fissati)
trasformare <Ni, Nf >a in <Ni , Nf >b, Ni indica la
Parte Intera, Nf indica la Parte Frazionaria.
53
Conversione di base
• Metodo iterativo, parte intera: come per i numeri interi
• Metodo iterativo, parte frazionaria
1. Si moltiplica Nf per b (sempre con l’aritmetica di a!!) . Il
prodotto sia p=pi,pf (es 0,46)
pi è la cifra più significativa di N’f (in base b).
2. (finché pf=0) esegui:
pfb = p’i,p’f
N’f = N’fp’i (concatena la cifra p’i a destra di N’f)
p’fpf
• NOTA: Il processo può o meno terminare (pf può non essere mai
54
zero!)
Conversione di base
• Esempio
(0,625)10=(0,N’f)8 0,6258=5,00 N’f=5
(0,23)10= (0,N’f)2 0,23 2=0,46 N’f=0
0,46 2=0,92 N’f=00
0,92 2=1,84 N’f=001
0,84 2=1,68 N’f=0011…
(N’f)2=0011
55
Esempio 2 : convertire 17,416 in base 2 con 8 bit sia
per P.I. che per P.F.
1. 17 10 = 10001 2
2. - 0,416 * 2 = 0,832
da cui P.I. = 0
P.F. = 0,832
0,832 * 2 = 1,664
da cui P.I. = 1
P.F. = 0,664
0,664 * 2 = 1,328
da cui P.I. = 1
P.F. = 0,328
0,328 * 2 = 0,656
da cui P.I. = 0
P.F. = 0,656
0,656 * 2 = 1,312
da cui P.I. = 1
P.F. = 0,312
0,312 * 2 = 0,624
da cui P.I. = 0
P.F. = 0,624
0,624 * 2 = 1,248
da cui P.I. = 1
P.F. = 0,248
0,248 * 2 = 0,496
da cui P.I. = 0
P.F. = 0,49
Perciò 0,41610 = 0,011010102
17,41610 = 00010001 , 011010102
56
Precisione in virgola fissa
N.B.: nell’esercizio precedente la versione binaria è
un'approssimazione del numero decimale originale.
Infatti :
10001,0110101 2 = 24 + 1 + 2-2 + 2-3 + 2-5 + 2-7 =
17,4140625 10
Problema: l'intervallo dei reali rappresentabile è
piccolo e con approssimazioni grossolane
Esempio 2 : avendo a disposizione 32 bit e dandone
20 per la P.I. e 12 per la P.F. si ha
a) P.I.  { 2-19 + 1 , … , 219 - 1 } = { -524287 , … , 524287
}
b) si hanno a disposizione solo 3 o 4 cifre frazionarie
(infatti 212 = 4096 )
57
Rappresentazione in virgola mobile
Un reale r è rappresentato dalla terna < s , m , e >
dove
r = (–1)s · m · be
e gli elementi della terna sono chiamati rispettivamente s=
bit di segno , m= mantissa (o significante) e e = esponente
, espresso in Ca2.
58
Forma Normalizzata
Tipicamente si adotta una forma normalizzata (tranne
che per lo zero) in cui la mantissa è tale che :
1. la sua parte intera è nulla
2. la sua parte frazionaria inizia con una cifra non
nulla
Banalmente < s , m , e > soddisfa ciò se e solo se
b-1  m < 1 .
59
Forma Normalizzata ((2)
Quindi, adottando la rappresentazione normalizzata,
r = (–1)s · 0,m · be
dove
s è il bit di segno della mantissa
m ( m è un intero ) rappresenta la parte frazionaria
del numero normalizzato (quindi la mantissa è un
intero rappresentato con bit di segno)
e è l'esponente, rappresentato in complemento alla base (se
b=2, in complemento a 2)
60
CAMBIAMENTO di BASE in
virgola mobile
Trasformare < s , ma , ea > in < s , mb , eb >
1. applica il procedimento per numeri in virgola
fissa a ( 0,ma · ae ) a ottenendo h , k b
2. mb e eb sono la mantissa e l'esponente normalizzati
di h , k b
61
Esempio
Nel seguito assumeremo di avere 1 bit per il segno, 8
per la mantissa e 4 per l'esponente.
Esempio 3 : convertire in base 2 il numero
0,0937510 = <+,0,9375,-1>
1. applico il procedimento per la P.F., ottenendo
0,0937510 = 0,000112=0,112-3
2. la rappresentazione cercata è < 0 , 11000000 2 ,
1101 2 >
(-3 in complemento a 2 è appunto 1101)
62
“Range” della rappresentazione
In base 2, intervallo rappresentato dando M bit alla
mantissa e E all'esponente :
1.
i
numeri
positivi
sono
E1
E1 1
2
2
,0,1.....1  2
[ 0,1  2
]
2.
[
i
M
numeri
negativi
E1 1
2
0,1......1  2
,0,1  2 E1
sono
]
M
63
64
65
Precisione e Ampiezza
Come si vede, all’aumentare del numero
di bit della mantissa aumenta la
precisione della rappresentazione
(diminuiscono gli intervalli fra numeri
adiacenti), mentre all’aumentare del
numero di bit dell’esponente aumenta
l’ampiezza del campo dei numeri
rappresentabili.
Occorre dunque trovare un compromesso.
66
STANDARD IEEE 85
Per uniformare la gestione della rappresentazione in
virgola mobile nei vari sistemi digitali (ad evitare cioè
che gli stessi dati elaborati su sistemi digitali diversi
diano risultati diversi) l’IEEE ha emesso degli
standard di rappresentazione.
La rappresentazione utilizza una polarizzazione, o
bias, cioè un valore costante che viene sommato
all’esponente e, per ottenere un esponente
polarizzato.
67
Standard IEEE
NaN è lo standard di rappresentazione di Not a
Number. Inoltre vengono mostrate le convenzioni di
rappresentazione per 0 e per infinito.
68
69
Operazioni fra reali in VM
Moltiplicazione(in base b )
< s1 , m1 , e1 > * < s2 , m2 , e2 > = < s , m , e >
dove
0
se s1 = s2
1
altrimenti
1. s =
2. m ed e sono la mantissa e l'esponente
normalizzati di m1 · m2 · b e1 + e2
N.B. : attenzione all'overflow degli esponenti!!
Analoga
è
la
e1e2
m1  m2b
.
formula
per
la
divisione:
70
Esempio
Eseguire in base 2 18 * -0,06640625
< 0 , 10010000 , 0101 > * < 1 , 10001000 , 1101 > =
< 1 , 10011001 , 0001 >
Il risultato, convertito in base 10, è correttamente
– 1,1953125
71
Somma
Somma
< s1 , m1 , e1 > + < s2 , m2 , e2 > = < s , m , e >
-se e1 = e2
s1
s =
s2
se ( –1 ) s1 · m1  ( –1 ) s2 · m2
altrimenti
m ed e sono le normalizzazioni di m’ ed e’ definiti
come :
(i) e = e1
(ii) m =
m1 + m2
se s1 = s2
| m1 – m2 |
altrimenti
72
Somma (2)
altrimenti (sia e1 < e2 )
shift a destra di m1 di e2 – e1 posizioni (inserendo 0 a
sinistra)
- porta così i numeri allo stesso esponente
- procede come al punto precedente
73
Esempio
eseguire in base 2
18 – 100
1810=0000101020=0,1001000025
10010=0110010020=0,110010027
< 0 , 10010000 , 0101 > – < 1 , 11001000 , 0111 >
=(e1=+5,e2=+7, e2 – e1=2)
< 0 , 00100100 , 0111 > – < 1 , 11001000 , 0111 >
=< 1 , 10100100 , 0111 >
- 0,1010010027 = - 0101001020 = – 82
N.B. : nell'operazione di shift ci può essere perdita di
cifre significative !!
74