Lucidi - Dipartimento di Informatica

Informatica Generale
Susanna Pelagatti
email: [email protected]
Ricevimento:
Mercoledì ore 14.30-17.30
presso
Dipartimento di Informatica, Via Buonarroti, 2
stanza 346 DE Tel. 050.2212.772
o per posta elettronica
Pagina web del corso:
http://www.di.unipi.it/~susanna/IG02/
1
Codifica e Rappresentazione
dell’informazione
• Cosa abbiamo visto :
Rappresentazione binaria
Codifica dei numeri (interi positivi,
interi con segno, razionali ….)
• Cosa vedremo oggi:
Codifica dei caratteri ,Codifica delle
immagini ,Compressione dei dati
Codifica dei suoni
2
La rappresentazione dei numeri
all’interno di un computer (5)
• Razionali
– numero finito di cifre periodiche dopo la virgola (ad
esempio 3.12 oppure 3.453
– rappresentazione solitamente su 4/8 byte
– rappresentazione in virgola fissa : riservo X bit per la
parte frazionaria
Parte intera
Parte frazionaria
– es : con 3 bit per la parte intera e 2 per quella
frazionaria 011.11, 101.01
3
La rappresentazione dei numeri
all’interno di un computer (6)
• Come si converte in base 10 una rappresentazione
in virgola fissa
– es :
101.01 = 1* 22 + 0 * 21 + 1 * 20 + 0 * 2-1 + 1 * 2-2 =
= 4 + 1+ 0.25 = 5.25
dove 2-1 = 1/2 = 0.5, 2-2 = 1/22 = 0.25
e in generale 2-n = 1/2n
4
La rappresentazione dei numeri
all’interno di un computer (7)
• Problemi della rappresentazione in virgola fissa
– overflow
– undeflow quando si scende al di sotto del minimo
numero rappresentabile
• es. vediamo in base 10, con 2 cifre riservate alla parte
frazionaria 0.01 / 2 = 0.005 non rappresentabile usando solo
due cifre
5
La rappresentazione dei numeri
all’interno di un computer (8)
• Problemi della rappresentazione in virgola fissa
(cont.)
– spreco di bit per memorizzare molti ‘0’ quando lavoro
con numeri molto piccoli o molto grandi
• es. vediamo in base 10, con 5 cifre per la parte intera e 2
cifre riservate alla parte frazionaria
10000.00 oppure 00000.02
– i bit vengono usati più efficientemente con la
notazione esponenziale o floating point (virgola
mobile)
6
La rappresentazione dei numeri
all’interno di un computer (9)
• Rappresentazione in virgola mobile
– idea : quando lavoro con numeri molto piccoli uso
tutti i bit disponibili per rappresentare le cifre dopo la
virgola e quando lavoro con numeri molto grandi le
uso tutte per rappresentare le cifre in posizioni elevate
– questo permette di rappresentare numeri piccoli con
intervalli minori fra loro rispetto ai numeri grandi
– questo riduce gli errori nel calcolo a parità di bit
utilizzati
7
La rappresentazione dei numeri
all’interno di un computer (10)
• Rappresentazione in virgola mobile (cont.)
0
Numeri rappresentabili in virgola fissa
0
Numeri rappresentabili in virgola mobile
8
La rappresentazione dei numeri
all’interno di un computer (11)
• Rappresentazione in virgola mobile (cont.)
– ogni numero N è rappresentato da una coppia
(mantissa M, esponente E) con il seguente significato
N = M * 2E
– esempi:
1. in base 10, con 3 cifre per la mantissa e 2 cifre per
l’esponente riesco a rappresentare
349 000 000 000 = 3.49 * 1011
con la coppia (3.49,11) perché M = 3.49 ed E = 11
9
La rappresentazione dei numeri
all’interno di un computer (12)
• Rappresentazione in virgola mobile (cont.)
– esempi:
2. in base 10, con 3 cifre per la mantissa e 2 per l’esponente
riesco a rappresentare
0.000 000 002 = 2.0 * 10-9
con la coppia (2.0,-9) perché M = 2.0 ed E = -9
– sia 0.000 000 002 che 349 000 000 000 non sono
rappresentabili in virgola fissa usando solo 5 cifre
decimali !!!
10
Rappresentazione di un insieme
finito di oggetti
• Vogliamo rappresentare i giorni della
settimana :
{Lu, Ma, Me, Gio, Ve, Sa, Do}
usando sequenze 0 e 1
• Questo significa costruire un ‘codice’, cioè
una tabella di corrispondenza che ad ogni
giorno associa una opportuna sequenza
• In principio possiamo scegliere in modo del
tutto arbitrario….
11
Rappresentazione di un insieme
finito di oggetti (2)
• Una possibile codifica binaria per i giorni
della settimana
Lunedì
Martedì
Mercoledì
Giovedì
Venerdì
Sabato
Domenica
0100010001
001
1100000
1
101010
111111
000001
12
Rappresentazione di un insieme
finito di oggetti (3)
• Problema : la tabellina di corrispondenza fra
codifiche tutte di lunghezza diversa
– spreco di memoria
– devo capire come interpretare una sequenza di
codifiche
– 110000011 = Me Gio Gio
– 110000011 = Gio Gio Do Gio
• Di solito si usa un numero di bit uguale per
tutti : il minimo indispensabile
13
Rappresentazione di un insieme
finito di oggetti (4)
• Per rappresentare 7 oggetti diversi servono
almeno 3 bit (minima potenza di due che
supera 7 è 8= 23) quindi :
000
001
010
011
100
101
Lunedì
Martedì
Mercoledì
Giovedì
Venerdì
Sabato
110 Domenica
111 non ammesso
14
Rappresentazione di caratteri e
stringhe
• I caratteri sono un insieme finito di oggetti e
seguono la strategia vista per i giorni della
settimana
• Perché due diversi calcolatori si possano
parlare correttamente è necessario che usino
lo stesso codice
15
Rappresentazione di caratteri e
stringhe (2)
• Codifiche di uso comune :
– il codice ASCII (American Standard code For
Information Interchange) su 7 o 8 bit
– il codice UNICODE su 16 bit (più recente,
permette di rappresentare anche alfabeti diversi
e simboli per la scrittura di lingua orientali)
• Le stringhe sono generalmente sequenze di
caratteri terminate in modo particolare
16
Rappresentazione di immagini
• Le immagini sono un ‘continuo’ e non sino
formate da sequenze di oggetti ben definiti
come i numeri e le stringhe
• Bisogna quindi prima ‘discretizzarle’ ovvero
trasformarle in un insieme di parti distinte
che possono essere codificate separatamente
con sequenze di bit
• Consideriamo prima immagini fisse (foto etc
…)
17
Rappresentazione di immagini (2)
• Immagini ‘bitmap’ :
1. l’immagina viene scomposta in una griglia di
elementi detti pixel (da picture element)
000000000000000000000000
000000000011111111000000
000000000010000010000000
000000000010000100000000
000000000010001000000000
000000000010010000000000
000000000010100000000000
000000000011000000000000
000000000010000000000000
codifica
immagine
18
Rappresentazione di immagini (3)
• Immagini ‘bitmap’ :
2. Ogni pixel è rappresentato da uno o più bit
Rappresentazione
di un pixel
000000000000000000000000
000000000011111111000000
000000000010000010000000
000000000010000100000000
000000000010001000000000
000000000010010000000000
000000000010100000000000
000000000011000000000000
000000000010000000000000
19
Rappresentazione di immagini (4)
• Rappresentazioni dei pixel :
– la rappresentazione in ‘toni di grigio’ : un byte
per pixel, con 256 gradazioni di grigio per ogni
punto (immagini bianco e nero), o più byte per
pixel, per avere più gradazioni possibili
– rappresentazione a colori RGB (red, green,blu) :
comunemente 3 byte per pixel che definiscono
l’intensità di ciascun colore base. In questo
modo ho circa 16 milioni di colori diversi
definibili
20
Rappresentazione di immagini (5)
• Problema :
– la rappresentazione accurata di una immagine dipende
• dal numero di pixel (definizione)
• dalla codifica del pixel
– … e richiede generalmente molta memoria, ad esempio :
tipo
imm. televisiva
SVGA
foto
defin
numero colori num. byte
720x625
256
440 KB
1024x768
65536
1.5 MB
15000x10000
16milioni
430 MB
21
Rappresentazione di immagini (6)
• Quindi si cerca di ‘risparmiare’ memoria :
– con l’uso di una ‘tavolozza’ (palette) che contiene il
sottoinsieme dei colori rappresentabili che compare in
una foto
• ogni pixel codifica un indice all’interno della tavolozza
– con tecniche di compressione che non codificano ogni
pixel in modo autonomo ma cercano di raggruppare i le
aree che hanno caratteristiche comuni
• Formati più usati : TIFF (tagged image file format),
GIF (graphics interchange format), JPEG (Joint
photographers expert group)
22