Post on 21-Aug-2020
1
Laboratorio di Informatica AA 2007/2008
1
Rappresentazione dell’informazione
Laboratorio di Informatica AA 2007/2008
2
Scopo della lezione
• Capire i dati vengono rappresentati nel calcolatore;
• Rappresentazione di numeri interi, relativi, in virgola mobile, mediante il sistema binario.
2
Laboratorio di Informatica AA 2007/2008
3
• La relazione che associa ad ogni successione ben formata di simboli di un alfabeto il dato corrispondente è detta codice.
• Un codice mette quindi in relazione le successioni di simboli con il significato loro attribuito.
Codice
Laboratorio di Informatica AA 2007/2008
4
• Esempio: GATTO codice “lingua italiana” felino con quattro zampe, una coda, etc…
• Att.ne! E’ importante l’ordine con cui vengono considerati i simboli! Nel codice “lingua italiana”, la parola OTGAT non significa nulla!
Codice
3
Laboratorio di Informatica AA 2007/2008
5
Calcolatori digitali
• Nei calcolatori, tutta l’informazione è rappresentata in forma numerica (binaria).
• Ad esempio, intensità di un suono di durata temporale pari a 8s:
[1, 2, 7, 9, 3, 1, 5, 5] dB (decibel) [0001, 0010, 0111, 1001, 0001, 0101, 0101] (binario)
• Altri esempi: immagini (intensità RGB per ogni pixel), caratteri (codifica ASCII), …
Laboratorio di Informatica AA 2007/2008
6
Il bit• noi rappresentiamo i numeri utilizzando un
alfabeto di dieci simboli (0, 1, …, 9)• per i calcolatori si usa un alfabeto binario• alfabeto binario: costituito da due simboli
– convenzionalmente “0” e “1”• binit o bit (binary digit, cifra binaria): elemento che
assume un valore binario• il bit è anche l’unità elementare di informazione
(teoria dell’informazione, Shannon – può essere misurato in bit il contenuto informativo di un’immagine, di un testo, …)
4
Laboratorio di Informatica AA 2007/2008
7
La codifica binaria
• Avendo a disposizione un solo bit si possono rappresentare
• due elementi diversi: • si assegna al primo la codifica 0• al secondo la codifica 1
Laboratorio di Informatica AA 2007/2008
8
La codifica binaria
• con 2 bit si possono rappresentare 4 = 22
elementi (oggetti, individui, ...) diversi, assegnando a ciascuno una codifica diversa:
• paperino codifica 00• qui codifica 01• quo codifica 10• qua codifica 11
• con 3 bit si possono rappresentare 8 = 23 elementi diversi
• …..• con n bit si possono rappresentare 2n elementi
5
Laboratorio di Informatica AA 2007/2008
9
Unità di misura: il byte
• una sequenza di 8 bit è detta byte, ed èuna unità di misura della occupazione di memoria
• la scelta del byte ha ragioni storiche • 8 è una lunghezza tipica delle celle di
memoria
Laboratorio di Informatica AA 2007/2008
10
Cosa rappresentare con 1 byte?
• 1 byte = 8 bit.• 256 possibili configurazioni dei bit.• … Possiamo rappresentare:
– I numeri interi da 0 a 255;– I numeri interi da -127 a 128;– Un set di 256 caratteri diversi (codifca ASCII);– 256 intensità di colore diverse (immagini RGB);– 256 colori diversi (immagini con colormap);– …
6
Laboratorio di Informatica AA 2007/2008
11
Es. Codifica ASCII• Ogni numero compreso tra 0 e 255 viene
rappresentato utilizzando una stringa di 8 bit. Il processo completo per la comprensione di un file ASCII è dunque rappresentato da:
– leggi 8 bit, es. 01100011 converti in numero decimale, es. 35 identifica il carattere ASCII associato a quel numero, cioè “#”.
– Il calcolatore non effettua la conversione binario numero decimale, bensì interpreta direttamente la stringa 01100011 come il carattere “#” in formato ASCII!
Laboratorio di Informatica AA 2007/2008
12
Es. Codifica ASCII
7
Laboratorio di Informatica AA 2007/2008
13
Es. colore immagine• Il pixel di un’immagine è rappresentato da una
tripletta RGB;• Ciascun valore R, G o B esprime la luminosità
della componente corrispondente;• Esempi:
– [11111111 00000000 00000000]due [255 0 0]dieci pixel rosso (R);
– [00000000 11111111 00000000]due [0 255 0]dieci pixel verde (G);
– [01111111 01111111 01111111]due [127 127127]dieci pixel grigio, mezza saturazione.
Laboratorio di Informatica AA 2007/2008
14
Le memorie del computer
• Nella memoria del computer è possibile memorizzare esclusivamente sequenze di bit e il processore può processare soltanto dati espressi come sequenze di bit.
8
Laboratorio di Informatica AA 2007/2008
15
Le memorie centrali
Laboratorio di Informatica AA 2007/2008
16
Le memorie del computer• Per modificare un singolo bit…
– Prelievo del byte [00010011] dalla memoria;– Il byte [00010011] si trova nei registri della CPU;– La CPU elabora il byte;– Il risultato [10010011] è nei registri della CPU;– Prelievo del byte [10010011] dai registri della CPU;– Deposito del byte [10010011] in memoria.
• … Si elabora il byte!• C’è bisogno di un indirizzo che identifichi il byte da
elaborare.
9
Laboratorio di Informatica AA 2007/2008
17
Le memorie “usano” i bit
Esempio: celle di lunghezza 3
Le celle contengono tutte lo stessonumero di bit, detto lunghezza
Gli indirizzi hanno una lunghezzafissata, che determinal’espansione massima della memoria
Logicamente sono organizzate in celle indirizzabili
Esempio: con indirizzi di 4 bit si hanno al massimo 16 celle
10010000100111
……
0000110110010101101000110011101001011100010010000
Laboratorio di Informatica AA 2007/2008
18
Dimensioni della memoria
• N° di byte per cella:– Bc;
• N° di bit per indirizzo:– bi;
• Numero di celle massimo della memoria:– 2bi;
• Dimensione massima della memoria (in byte):– 2bi · Bc;
10
Laboratorio di Informatica AA 2007/2008
19
Dimensioni tipiche
• Celle di memoria– 8 bit,16 bit (=1, 2 byte)
• Indirizzi– da 16 bit a 64 bit
– Es. memoria con celle da 2 byte, 16 bit per l’indirizzamento:– Dimensione = 2bi · Bc = 216 · 2 = 8,589,934,592 byte ~
8.5GByte
• Equipaggiamento tipico di un PC odierno: 1G o 2G Byte RAM
Laboratorio di Informatica AA 2007/2008
20
Esercizio• Si consideri un calcolatore le cui memorie centrali hanno
indirizzi di 7 bit e celle di lunghezza 6 bit– Quanto è l’espansione massima di memoria?
Si hanno 27 indirizzi e quindi l’espansione massima di memoria è27 =128 celle di memoria
– Quante informazioni posso rappresentare nella singola cella di memoria?26 =64 informazioni
– Si fornisca un esempio di informazioni rappresentabiliEs: i nomi delle 64 stelle più vicine
- Quale è la dimensione totale della memoria?(27 = 128 celle di memoria) · (6 bit per cella) = 768 bit = 96 byte
11
Laboratorio di Informatica AA 2007/2008
21
Rappresentazione dell’informazione nel computer
• Nel PC, ogni informazione è memorizzata in formato numerico…– Es. intensità di un suono di durata temporale
pari a 8s:• [1, 2, 7, 9, 3, 1, 5, 5] dB (decibel) • [0001, 0010, 0111, 1001, 0001, 0101, 0101]
(binario)
• …La rappresentazione dei numeri nel calcolatore è binaria.
Laboratorio di Informatica AA 2007/2008
22
Rappresentazione dei numeriI numeri sono entità matematiche astratte;
vanno distinti dalla loro rappresentazione
Numero:Il numero cardinale quattro: cardinalitàdegli insiemi contenenti quattro elementi
Rappresentazione:Rappresentazione unitaria: IIIIRappresentazione additiva/sottrattiva: IVRappresentazione posizionale (base dieci): 4ecc.
12
Laboratorio di Informatica AA 2007/2008
23
Rappresentazioneadditivo/sottrattivo:
• Il significato dei simboli che compongono un numero è indipendente dalla posizione in cui compaiono
• Es. sistema con un unico simbolo, per l’unità (I = 1, II = 2, III = 3, …)
• Es. sistema di numerazione romano, con i simboli I, V, X, L, C, D, M
• L’ordine in cui compaiono i simboli determina il significato additivo / sottrattivo (ad esempio IX per 9, XI per 11)
Laboratorio di Informatica AA 2007/2008
24
Rappresentazioneposizionale
• Sistema di numerazione arabico:– introdotto in Europa nel Medio Evo – in base dieci: utilizza le dieci cifre 0, 1, …, 9– è una notazione posizionale: il valore di ogni
cifra dipende dalla sua posizione nella successione di simboli che rappresenta il numero.
– Es. 1234 = 1x103 + 2x102 + 3x101 + 4x100
– Es. 4321 = 4x103 + 3x102 + 2x101 + 1x100
13
Laboratorio di Informatica AA 2007/2008
25
Rappresentazione posizionale• Sistema di numerazione arabico:
– In generale, per un numero composto di n cifre si ha che:
cn–1 cn–2 ...c1 c0 = cn–110n–1 + cn–210n–2 + … + c1101 + c0100
– Si chiamano cifre piú significative quelle associate ai pesi maggiori.
– La cifra cn–1 è la piú significativa e c0 è la cifra meno significativa.
– Es. 1234 = 1x103 + 2x102 + 3x101 + 4x100
– Es. 4321 = = 4x103 + 3x102 + 2x101 + 1x100
Laboratorio di Informatica AA 2007/2008
26
Rappresentazione posizionale• Base 2: quella in cui lavora il calcolatore
– cifre 0,1• Base 10: quella dell’utente umano
– cifre 0,1,2,3,4,5,6,7,8,9• Base 8: per abbreviare i numeri binari
– cifre 0,1,2,3,4,5,6,7• Base 16: per abbreviare i numeri binari
– cifre 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
14
Laboratorio di Informatica AA 2007/2008
27
Rappresentazione posizionale
• Se la base della numerazione è B, si hanno a disposizione B cifre, comprese tra 0 e B–1. • Tramite n cifre in base B è possibile rappresentare Bn
numeri naturali, da 0 a Bn-1.• cn cn–1 ...c1 c0 =
= cn. Bn + cn–1
. Bn–1 + … + c1 . B1 + c0
. B0
= Σi:0...n ci . Bi
• Esempio: (705)8 = 7x82 + 0x81 + 5x80 = (453)10
Laboratorio di Informatica AA 2007/2008
28
Cambio di rappresentazione
• Si applica la definizione– cn cn–1 ...c1 c0 = cn
. Bn + cn–1 . Bn–1 + … + c1
. B1 + c0 .
B0
• Esempi– base 2: (1011)due = (1 . 23 + 0 . 22 + 1 . 21 + 1)dieci
– base 8: (2705)otto = (2 . 83 + 7 . 82 + 0 . 81 + 5)dieci
– base 16: (3F01)16 = (3 . 163 + 15 . 162 + 0 . 161 + 1)dieci
15
Laboratorio di Informatica AA 2007/2008
29
Rappresentazione posizionale: proprietà notevoli
• (pn1) 1 seguito da n 0 rappresenta Bn; ad es.
– base 10: 100000 = 105
– base 2: 100000 = 25
– base 8: 100000 = 85
– base 16: 100000 = 165
• (pn2) n cifre “massime” rappresentano Bn-1; ad es:
– base 10: 99999 = 105 - 1– base 2: 11111 = 25 - 1– base 8: 77777 = 85 - 1– base 16: FFFFF = 165 - 1
Laboratorio di Informatica AA 2007/2008
30
: numeri naturali, base 2• Tramite n cifre in base 2 è possibile
rappresentare 2n numeri naturali, da 0 a 2n-1.
– Nel calcolatore, per i numeri naturali si usano di solito 32 bit;
– I valori rappresentabili sono:232= 4.294.967.296 ≅ 4x109
– Raddoppiando la lunghezza, il massimo numero rappresentabile aumenta esponenzialmente.
– Se si utilizzano 64 bit 264–1 ≅ 1,6x1019
16
Laboratorio di Informatica AA 2007/2008
31
I primi 16 numeri binari
0 = 01 = 110 = 211 = 3100 = 4101 = 5110 = 6111 = 7
1000 = 81001 = 91010 = 101011 = 111100 = 121101 = 131110 = 141111 = 15
Laboratorio di Informatica AA 2007/2008
32
Numeri naturali: cambio di rappresentazione (da base B a base 10)• Esempio:
101100due = (1x25 + 0x24 + 1x23 + 1x22 + 0x21 + 0x20) dieci
= (32 + 8 + 4)dieci = 44dieci
• Esercizio:
100011due = (1x25 + 0x24 + 0x23 + 0x22 + 1x21 + 1x20) dieci= (32 + 2+ 1)dieci = 35dieci
17
Laboratorio di Informatica AA 2007/2008
33
Cambio di rappresentazione (da base 10 a base B)
• Altre basi vengono spesso utilizzate per comodità di rappresentazione (es. base 8, base 16).
• Come passare da una base all’altra?• Si usano divisione intera div e resto mod:
5 div 2 = 25 mod 2 = 1
(il risultato di cinque diviso due è due con resto 1)
15 div 5 = 3, 15 mod 5 = 0;15 div 16 = 0, 15 mod 16 = 15.
Laboratorio di Informatica AA 2007/2008
34
Cambio di rappresentazione• Si usano divisione intera div e resto mod, e si applica
la:• Proprietà notevole delle rappresentazioni in base B:
– n mod B è rappresentato dalla cifra c0 meno significativa della rappresentazione di n in base B
– n div B è rappresentato dalle cifre precedenti – Ad es., nella base 10:
• 1537 mod 10 = 7 è rappresentato da 7• 1537 div 10 = 153 è rappresentato da 153
• La rappresentazione emerge attraverso divisioni intere successive, raccogliendo i resti, che corrispondono alle cifre, partendo da quella meno significativa
18
Laboratorio di Informatica AA 2007/2008
35
Cambio di rappresentazione
• Iterando le operazioni div / mod, estraiamo dal numero in base 10 i vari componenti (cifre) del numero in base B…
• … Ad esempio, estraiamo le cifre di (1537)10 in base 10:
– 1537 mod 10 = 7, 1537 div 10 = 153 la prima cifra del numero, quella meno significativa, in base 10, è 7…
– 153 mod 10 = 3, 153 div 10 = 15 … la seconda cifra del numero, in base 10, è 3 …
– 15 mod 10 = 5, 15 div 10 = 1 … la terza cifra del numero, in base 10, è 5; …
– 1 mod 10 = 1, 1 div 10 = 0 … la quarta cifra del numero, quella più significativa, in base 10, è 1.
Laboratorio di Informatica AA 2007/2008
36
Cambio di rappresentazione
• Iterando le operazioni div / mod, estraiamo dal numero in base 10 i vari componenti (cifre) del numero in base B…
• … Ad esempio, estraiamo le cifre di (1537)10 in base 8:
– 1537 mod 8 = 1, 1537 div 8 = 192 la prima cifra del numero, quella meno significativa, in base 8, è 1…
– 192 mod 8 = 0, 192 div 8 = 24 … la seconda cifra del numero, in base 8, è 0 …
– 24 mod 8 = 0, 24 div 8 = 3 … la terza cifra del numero, in base 8, è0; …
– 3 mod 8 = 3, 3 div 8 = 0 … la quarta cifra del numero, quella piùsignificativa, in base 8, è 3.
– Dunque, (1537)dieci = (3001)otto;
– Verifichiamo il risultato: (3001)otto = (3·83+ 0·82+ 0·81+ 1·80)dieci = (1536 +0 + 0 + 1)dieci = (1537) dieci
19
Laboratorio di Informatica AA 2007/2008
37
Numeri naturali: cambio di rappresentazione
numero div base quoz. resto
6 div 2 = Cifra posto 0
div 2 = Cifra posto 1
div 2 = Cifra posto 2
610 = 1102
Ad esempio, per il numero 6 in base 10, se la base desiderata è 2…
si ripete ladivisione interaper 2
e si raccolgonoi quozienti interied i resti comecifre
Le cifre ottenute corrispondonoalla rappresentazione binaria
3 0
3 1 11 0 1
Laboratorio di Informatica AA 2007/2008
38
Numeri naturali: esempio
numero divisore quoziente resto
41 2 20 1 cifra bin. meno significativa
20 2 10 0 10 2 5 0
5 2 2 1 2 2 1 0 1 2 0 1 cifra bin. più
significativa 1
41dieci = 101001due prova: 25+23+20=32+8+1=41
Si considerino celle di memoria di 6 bit:
20
Laboratorio di Informatica AA 2007/2008
39
Numeri naturali: esempio
numero divisore quoziente resto
10 2 5 0 cifra bin. meno significativa
5 2 2 1 2 2 1 0 1 2 0 1 0 2 0 0 0 2 0 0 cifra bin. più
significativa 1
10dieci = 001010due riprova: 23+21=8+2=10
Si considerino celle di memoria di 6 bit:
Laboratorio di Informatica AA 2007/2008
40
Numeri naturali: esercizio
• Si consideri un calcolatore le cui memorie centrali hanno indirizzi di 7 bit e
celle di lunghezza 6 bit
– Quanti e quali numeri naturali posso rappresentare?Si possono rappresentare 26 = 64 numeri naturali da 0 a 63
– Come viene rappresentato il numero in base decimale 11? 001011
– Come viene rappresentato l’indirizzo della cella 11? 0001011
– In una cella è memorizzato il numero: 111111. A quale numero in base decimale corrisponde?63 perché 25+24+23+22+21+20= 32+16+8+4+2+1 o per la proprietà np1
– Posso rappresentare l’operazione 30+40?– No, perché 70 non appartiene al range di numeri naturali rappresentabili con
celle di 6 bit (errore di overflow)
21
Laboratorio di Informatica AA 2007/2008
41
Numeri naturali: esercizio
numero divisore quoziente resto
11 2 5 1 cifra bin. meno significativa
5 2 2 1 2 2 1 0 1 2 0 1 0 2 0 0 0 2 0 0 0 2 0 0
1
11dieci = 001011due riprova: 23+21+20=8+2+1=11
Si considerino celle di memoria di 6 (7) bit:
Laboratorio di Informatica AA 2007/2008
42
: numeri interi relativi
• Codifica con modulo e segno: consiste nell’indicare il segno seguito dal valore assoluto, come succede normalmente nella codifica decimale.
• Il primo bit indica il segno– 0 per positivo– 1 per negativo
• Gli altri n–1 bit rappresentano il valore assoluto
22
Laboratorio di Informatica AA 2007/2008
43
: codifica con modulo e segno
• Esempi0011 = 30000 = 01000 = – 01011 = – 3
• Ha il difetto di duplicare la rappresentazione del numero 0, cosa che può complicare l’esecuzione ed il controllo delle operazioni aritmetiche.
Laboratorio di Informatica AA 2007/2008
44
Aritmetica finita
• A livello HDW i calcoli numerici vengono eseguiti dalla
– ALU (Unità Logico Aritmetica)
– Si trova nella CPU e lavora con i registri della CPU
• Siccome i registri hanno lunghezza prefissata L, numeri la cui rappresentazione binaria richiede più di L cifre non sono rappresentabili.
23
Laboratorio di Informatica AA 2007/2008
45
Aritmetica finita• Si usa dunque un’aritmetica finita, cioè con un numero massimo di
cifre binarie disponibili;
• Nell’aritmetica finita dei calcolatori
– i numeri relativi sono rappresentati in complemento, come vedremo– i numeri “reali” sono rappresentati in virgola mobile, come vedremo
• Siccome il numero di cifre massimo è limitato, la precisione raggiungibile nella rappresentazione dei numeri reali è limitata; abbiamo le seguenti precisioni, che spiegheremo poi:
– semplice 32 bit– doppia 64 bit– estesa 128 bit
Laboratorio di Informatica AA 2007/2008
46
Aritmetica finita• La rappresentazione grafica dei numeri sulla retta
permette di comprenderne alcune proprietà
• Per comprendere le proprietà dell’aritmetica finita occorre passare alla rappresentazione su circonferenza
0
0
24
Laboratorio di Informatica AA 2007/2008
47
Aritmetica finita• Man mano che ci si sposta lungo la retta, la
rappresentazione usuale dei numeri continua a cambiare, dando luogo a infinite rappresentazioni per infiniti numeri.
• Con l’aritmetica finita, abbiamo a disposizione un numero finito di rappresentazioni (combinazioni di cifre) per i numeri. Continuando ad avanzare lungo la circonferenza, si ritorna alla notazione utilizzata per il numero 0!
Laboratorio di Informatica AA 2007/2008
48
: rappresentazione in complemento
• In complemento a 60, si ha l’aritmetica dell’orologio per quanto riguarda la lancetta dei minuti
da 0 a 59
0
15
30
45
0
15
-30
-15negativi:quanto mancaall’ora?
da 0 a 29 non negativida -30 a -1 negativi
Interiassoluti
25
Laboratorio di Informatica AA 2007/2008
49
: complemento a 2 con 3 bit• Cioè, in complemento a 2 con 3 bit significa:
– in complemento a 8 = 23
Valori in complemento;per i blu: quanto manca a 8?
0 12
34567 0 1
23-4-3
-2-1
Valori assoluti
da 0 a 3 non negativida -4 a -1 negativi
Con 3 bit possono essere rappresentati gli interi compresi tra -4 e +3
Laboratorio di Informatica AA 2007/2008
50
: Rappresentazione in complemento a due
• Range di rappresentabilità con n bit
– Con n bit possono essere rappresentati gli interi compresi tra –2n-1 e +(2n-1 – 1).
– Esempio: con 4 bit possono essere rappresentati gli interi compresi tra –24-1 e +(24-1 – 1) cioè tra -8 e +7
• Rappresentazione in complemento a due
– Dati n bit, un numero negativo –x si rappresenta con il valore binario corrispondente a 2n-x.
26
Laboratorio di Informatica AA 2007/2008
51
Esercizio: Interi assoluti e interi relativi
Esercizio: date celle di memoria di un byte
• quanti e quali numeri interi assoluti posso rappresentare?posso rappresentare 28 =256 numeri interi assoluti:da 0 a 255
• quanti e quali numeri interi relativi posso rappresentare?posso rappresentare 28 =256 numeri interi relativi: da -128 a +127 (utilizzando la notazione in complemento a due)
Laboratorio di Informatica AA 2007/2008
52
Notazione in complemento a 2• Utilizziamo n=3 bit;• I numeri rappresentabili vanno da -23-1 = -4 a
+23-1-1 = +3.• Per passare in complemento a due con un
numero positivo:• (3)10 (011)2 (011)C2• Per passare in complemento a due con un
numero negativo:• (-3)10 (1000)2 – (011)2 (101)C2• (-3)10 (8)10 – (3)10 = (5)10 (101)C2
27
Laboratorio di Informatica AA 2007/2008
53
: cambio di rappresentazione
n assoluto n in compl. a 2
1° bit dettobit del segno
23-4=410=1002
01133010220011100000
1117-11106-21015-31004-4
1° bit0: +
1° bit1: -
23-3=510=1012
23-2=610=1102
23-1=710=1112
Esempio: dati 3 bit, un numero negativo –x si rappresenta con il valore binario corrispondente a 23-x.
Laboratorio di Informatica AA 2007/2008
54
: cambio di rappresentazione
n assoluto n in compl. a 2
1° bit dettobit del segno
4-23=-410
33011220101100100000
-17111-26110-35101-44100
1° bit0: +
1° bit1: -
5-23=-310
6-23=-210
7-23=-110
Viceversa: dalla rappresentazione in complemento due alla base 10.
X10(assoluto)-23
X10(assoluto)-2n
28
Laboratorio di Informatica AA 2007/2008
55
: cambio di rappresentazione• Esempio: celle di memoria di 4 bit
Rappr. per interi: Complemento a due:
– 0000 0 1000 – 8 (24-8=8dieci= 1000due)– 0001 1 1001 – 7 (24-7=9dieci= 1001due) – 0010 2 1010 – 6 (24-6=10dieci=1010due)– 0011 3 1011 – 5 (24-5=11dieci=1011due)– 0100 4 1100 – 4 (24-4=12dieci=1100due)– 0101 5 1101 – 3 (24-3=13dieci=1101due)– 0110 6 1110 – 2 (24-2=14dieci=1110due)– 0111 7 1111 – 1 (24-1=15dieci=1111due)
Cella di memoria
Numero rappresentato
Cella di memoria
Numero rappresentato
Laboratorio di Informatica AA 2007/2008
56
Perché il complemento a due?• (1001)C2 (– 7)10 +• (0010)C2 (2)10 =• ----------------------------------• (1011)C2 (-5)10
• ( 1101)C2 (– 3)10 +• ( 0100)C2 (4)10 =• ----------------------------------• (10001)C2 (1)10
Rappresentazione numeri negativi;
Comodità nelle operazioni con i numeri relativi (non c’è bisogno di controllare il segno);
Somma = differenza, stessa circuiteria! Inoltre lo stesso circuito esegue somma e differenza in complemento e non!.
Note: l’eventuale riporto fuori dal numero di bit della stringa non viene considerato.
29
Laboratorio di Informatica AA 2007/2008
57
Gli errori di overflow• L’intervallo dei numeri interi (assoluto o relativi)
rappresentabili con un fissato numero di bit è limitato• Eseguendo un’operazione su numeri rappresentabili,
può accadere che il risultato esca dall’intervallo rappresentabile; in tal caso si dice che– si ha un errore di overflow
• ESEMPIO con 8 bit: 28=256– Caso di valori assoluti: massimo rappresentabile
= 255• Overflow 150 + 150 = 300 perché > 255
– Caso complemento a 2: intervallo rappr.: -128 ... 127
• Overflow -100 - 100 = -200 perché < -128
Laboratorio di Informatica AA 2007/2008
58
Esempio overflow• Registri della CPU a 8 bit;• Vogliamo eseguire 255 + 1 = 256;• Otteniamo 255 + 1 = 0!• Infatti:
– (255)10 ( 11111111)2 +– (1)10 ( 00000001)2 =– ---------------------------------------– (256)10 (100000000)2– (0)10 ( 00000000)2
I registri della CPU contengono 8 bit – il primo bit a sinistra non ci sta!
30
Laboratorio di Informatica AA 2007/2008
59
Verifica dell’overflow
• L’errore di overflow si verifica solo quando sommiamo due numeri positivi o due numeri negativi.
• Se si verifica un overflow, la somma di due numeri positivi dà un numero negativo e viceversa.
• E’ sufficiente verificare il bit di segno per capire se c’è stato l’overflow!
Laboratorio di Informatica AA 2007/2008
60
: Rappresentazione in eccesso (o biased)
• Per rappresentare un intervallo –N ... +(N-1) mediante positivi si può traslarlo di +N– -N ... +(N-1) traslato di +N diventa 0 ... 2N-1– La traslazione N è detta eccesso o bias– Esempio:
-4 -3 -2 -1 0 1 2 3
0 1 2 3 4 5 6 7
+4 -4
Intervallo di relativi
Sua rappresentazionein eccesso 4
31
Laboratorio di Informatica AA 2007/2008
61
: Rappresentazione in eccesso (o biased)
• Con n bit:– eccesso = 2n-1; – talora eccesso = 2n-1 - 1
• Esempio con 8 bit– eccesso = 128
• -128 ... +127 -128 +128 0...255– talora eccesso = 127
• -127 ... +127 -127 +127 0...254– 255 è trattato come 0
Laboratorio di Informatica AA 2007/2008
62
Rappresentazione in eccesso: esempio
• Rappresentazione in eccesso 128 (8 bit)
• Interpreto il numero binario, tolgo 128
• 00000000 (0-128) = -128• 10000000 (128-128) = 0• 11111111 (255-128) = 127
32
Laboratorio di Informatica AA 2007/2008
63
: numeri reali
• Rappresentazione con la virgola in base B:cn..c0,c-1..c-k= cnBn + .. + c0B0 + c-1B-1+ .. + c-kB-k
• Esempio: 123,45=1x102 + 2x101 + 3x100 + 4x10-1 + 5x10-2
• Esercizio: 543,21543,21=5x102 + 4x101 + 3x100 + 2x10-1 + 1x10-2
Laboratorio di Informatica AA 2007/2008
64
: cambio di rappresentazione (da base B a base 10)
• Per passare dalla rappresentazione in base B alla rappresentazione in base dieci si applica la definizione:– cn..c0,c-1..c-k = cnBn + .. + c0B0 + c-1B-1+ .. + c-kB-k
• Esempio col numero binario 101,01– tralasciando il contributo nullo delle cifre 0:
101,01 = 1 . 22 + 1 . 20 + 1 . 2-2 = 4 + 1 + 1/4 = 5,25
• Esercizio col numero binario 110,10– tralasciando il contributo nullo delle cifre 0:
110,10 = 1 . 22 + 1 . 21 + 1 . 2-1 = 4 + 2 + 1/2 = 6,50
33
Laboratorio di Informatica AA 2007/2008
65
: cambio di rappresentazione (da base 10 a base B)
• Si trattano separatamente parte intera e frazionaria; – per la intera, si procede come già visto; – per la frazionaria, si applica la proprietà:
• sia 0, c-1c-2..c-k = n ; allora• c-1, c-2..c-k = B.n• Esempio in decimale: 0,231 . 10 = 2,31
moltiplicando per la base 10 emerge la cifra 2
• Cioè, per far emergere c-1 basta moltiplicare per B;
moltiplicando ancora per B emergerà c-2 e così via
Laboratorio di Informatica AA 2007/2008
66
: cambio di rappresentazione
parte fraz. × base prod. parte intera0,25 × 2 =
× 2 = × 2 =
0,25 = 0,01
Contiene le cifrebinarie, nell’ordine
Ci si arresta quando la partefrazionaria si azzera o quandoabbiamo un numero di cifreabbastanza elevato
0,50,5 1,0
0
01
Si riporta la parte frazionariadella riga precedente
Si riporta la parte interacome cifra
34
Laboratorio di Informatica AA 2007/2008
67
: sui numeri periodici• Un numero può essere non periodico in una base e
periodico in un’altra:
– esempio da base 10 a 2: 0,4 = 0,0110011001100….
0,4 2 0,8 00,8 2 1,6 10,6 2 1,2 10,2 2 0,4 00,4 2 0,8 0 Si ripete la prima riga!
Laboratorio di Informatica AA 2007/2008
68
: codifica• Notazione scientifica: un numero viene rappresentato come:
± m x 10p Es. 123.000.000 = 1,23x108
• Se, piú in generale, la base è B,
± m x Bp
• Il coefficiente m è detto mantissa (la convenzione è di inserire implicitamente la virgola decimale subito dopo la prima cifra)
• p, detto caratteristica, è l’esponente a cui elevare la base B
35
Laboratorio di Informatica AA 2007/2008
69
: codifica
• Esempio: 1,23x108
base 10, segno +, mantissa 123, caratteristica 8
• Esercizio: Scrivere in notazione scientifica il numero 40000002 e indicarne mantissa e caratteristica
40000002=4,0000002x107
base 10, segno +, mantissa 40000002, caratteristica 7
Laboratorio di Informatica AA 2007/2008
70
: rappresentazione in virgola mobile
• La rappresentazione binaria dei numeri reali che usa la notazione scientifica è detta rappre-sentazione in virgola mobile (floating point).
• Cambiando il numero di cifre dedicato alla rappresentazione di mantissa ed esponente cambia la precisione dei risultati che si ottengono.
• L’interesse a uniformare la precisione di calcolo ha condotto alla definizione di uno standard internazionale proposto dall’Institute of Electrical and Electronic Engineers (IEEE).
36
Laboratorio di Informatica AA 2007/2008
71
: rappresentazione in virgola mobile
• Virgola mobile: m E e con – mantissa m per numeri diversi da 0: 1 ≤ m < B– e esponente – significato m E e = m.Be
– Esempio decimale: 344,013 in virgola mobile si scrive:
• 3,44013 E 3 = 3,44013 . 103
– Esempio binario: 101,001 in virgola mobile si scrive:
• 1,01001 E 10 = (1+2-2+2-5) . 22
Laboratorio di Informatica AA 2007/2008
72
: rappresentazione in virgola mobileprecisione singola, 32 bit
1 bit segno0 +1 -
23 bit per la partefrazionaria F della mantissa
s F
8 bit per l’esponentein eccesso 127
e
La mantissa è F. Per convenzione, la prima cifra della mantissa è sempre 1 (dunque dovremo considerare 1,F).
l’esponente rappresentato èE = (e-127)
37
Laboratorio di Informatica AA 2007/2008
73
: rappresentazione in virgola mobileprecisione singola, 32 bit
0
+
0010011000000000000000010000100
1 + 2-3 + 2-6 + 2-725 .
(10000100)due = (132)dieci132 – eccesso =132 - 127 = 5
Laboratorio di Informatica AA 2007/2008
74
: errori di arrotondamento
• Rappresentazione dello zero.• Numeri troppo piccoli non rappresentabili
assimilati a zero (underflow).• La rappresentazione esatta di alcuni numeri
richiederebbe un numero infinito di cifre– Es. 1/3 = 0,3333333… π = 3,14159…..
• Un problema analogo sorge per numeri con valore assoluto molto grande o molto piccolo, in cui il numero di cifre richiesto non sarebbe infinito, ma molto elevato.
• In questi casi possiamo considerare solo le cifre piúsignificative.
38
Laboratorio di Informatica AA 2007/2008
75
: errori di arrotondamento• Qualunque sia la codifica scelta, la rappresentazione dei
numeri nel calcolatore è soggetta ad approssimazioni.• Il limitato numero di cifre disponibili nella mantissa porta ad
errori di arrotondamento quando si debbano rappresentare numeri con una mantissa più lunga.
• Tali approssimazioni si propagano nel corso della esecuzione delle operazioni causando errori numericianche importanti.
• Il calcolo numerico è la disciplina che studia le proprietàdell’esecuzione delle operazioni tramite calcolatore e valuta l’entità degli errori introdotti durante l’esecuzione.
Laboratorio di Informatica AA 2007/2008
76
Riassunto• Codice / alfabeto;• Rappresentazione in memoria, indirizzamento in
memoria;• Notazione posizionale, sistema binario;• Conversione tra basi;• Rappresentazione in complemento;• Rappresentazione in eccesso;• Rappresentazione in virgola mobile;• Problemi numerici (accenno).