Lucidi - Dipartimento di Informatica

Informatica Generale
Marzia Buscemi IMT Lucca
email: [email protected]
Ricevimento:
Giovedì ore 16.00-18.00
presso
Dipartimento di Informatica, Largo Pontecorvo 3
stanza 306 PS Tel. 050.2213102
o per posta elettronica
Pagina web del corso:
http://www.di.unipi.it/~buscemi/IG07.htm
1
Codifica e Rappresentazione
dell’informazione
 Cosa abbiamo visto :
Rappresentazione
binaria
Codifica dei numeri (interi positivi), dei
Caratteri,

delle immagini fisse.
Cosa vedremo oggi:
Codifica
dei numeri negativi, razionali
Codifica dei video e dei suoni
Compressione dei dati
2
Conversione da base 10 a
base 2
Dato un numero X si cerca la sua
rappresentazione in base 2 cN-1…c0
 Conversione per divisione :


si divide ripetutamente X per 2
il resto ottenuto nella divisione i-esima è la iesima cifra (ci) della rappresentazione binaria
3
Conversione da base 10 a
base 2 (2)
Come si converte X nella sua rappresentazione
in base 2 cN-1…c0 usando il metodo della
divisione
 Es : convertiamo il numero 13





13 / 2 da quoziente 6 e resto 1 (c0)
6 / 2 da quoziente 3 e resto 0 (c1)
3 / 2 da quoziente 1 e resto 1 (c2)
1 / 2 da quoziente 0 e resto 1 (c3)
Qual è la rappr. di 29? E di 41?
4
Proprietà
Per rappresentare K diversi numeri (cioè 0
1 2 …K-1) mi servono x cifre dove 2x è
la più piccola potenza di 2 che supera K.

Es.: Se voglio 25 numeri diversi? Se voglio
31? E 33?
Questa è l’idea che sta alla base della
rappresentazione di qualunque insieme
finito di oggetti (caratteri, punti di una
immagine, etc.)
5
La rappresentazione dei numeri
negativi
Ci sono diverse convenzioni di rappresentazione.
Tra le altre ne consideriamo 2:
1. modulo e segno in cui il primo bit viene riservato
al segno (1 negativo, 0 positivo) e gli altri al
modulo
Es.: (con 8 bit)
2 = 0000 0010 -2 = 1000 0010
Problemi:
• Lo zero ha due rappresentazioni
(es.: 0000 0000 e 1000 0000)
• La somma dà risultati scorretti
(es.: 2 + (-2) = -4)
6
La rappresentazione dei numeri
negativi (2)
2.
Complemento a 2 (variazione di complemento a
1): vale 2n-N, dove N è il numero in
considerazione e n il numero di bit
(in pratica, basta cambiare tutti gli 1 in 0 e viceversa e
aggiungere 1)
Es.: (con 8 bit)
N=0000 0010 c(N) = 1111 1110
• Risolve i problemi del doppio zero
• La somma dà risultati corretti
(es.: (-5) + (+2) = (-3). Provare)
7
La rappresentazione in virgola
fissa dei numeri razionali

Un numero razionale ha 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
8
La rappresentazione in virgola
fissa dei numeri razionali (2)

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

Vicerversa, la conversione in base 2 come
quella per i numeri interi, ma con la
rappresentazione:
cN-1 * 2N-1 + cN-2 * 2N-2 ….+ c1 * 21 + c0 * 20 +
c0 * 20 + c-1 * 2-1 ...
9
Problema dell’overflow

Overflow:
Se moltiplico o sommo due numeri molto elevati
posso ottenere un numero che non è
rappresentabile
• es.: vediamo cosa succede in base 10 con solo
3 cifre :
500 + 636 = 1136 risultato 136
se uso solo 3 cifre non ho lo spazio fisico per
scrivere la prima cifra (1) che viene ‘persa’.
• Similmente per il caso in base 2.
10
Problema dello spreco di memoria

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
La notazione esponenziale o floating point
(virgola mobile) risolve entrambi i
problemi dell’overflow e dello spreco di
memoria: i bit vengono usati più
efficientemente.
11
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
12
Rappresentazione in virgola
mobile

ogni numero N è rappresentato da una
coppia: mantissa M, esponente E, con il
seguente significato
N = M * BE
(B base)
 esempi:
1.in base 10, con 3 cifre per la mantissa e
2 cifre per l’esponente riesco a
rappresentare il numero
349 000 000 000 = 3.49 * 1011
con la coppia (3.49,11) perché M = 3.49
13
ed E = 11
Rappresentazione in virgola
mobile
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 !!!
 Lo stesso si verifica nel caso binario.
14

Rappresentazione di
immagini



Le immagini sono un ‘continuo’ e non
sono formate da sequenze di oggetti
ben finiti come i numeri e i testi
Bisogna quindi prima ‘discretizzarle’
ovvero trasformarle in un insieme di
parti distinte che possono essere
codificate separatamente con sequenze
di bit
Bisogna definire il termine informale di
“elemento d’informazione”
15
Rappresentazione di immagini

Immagini ‘bitmap’ :
1.
l’immagine viene scomposta in una griglia di
elementi detti pixel (da picture element)
2.
Ogni pixel viene rappresentato da 1 o più bit
000000000000000000000000
000000000011111111000000
000000000010000010000000
000000000010000100000000
000000000010001000000000
000000000010010000000000
000000000010100000000000
000000000011000000000000
000000000010000000000000
immagine
codifica
16
Rappresentazione di immagini

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
17
Rappresentazione di immagini

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 le aree che hanno caratteristiche
comuni.
Formati più usati : TIFF (tagged image file format),
GIF (graphics interchange format), JPEG (Joint
photographers expert group)


18
Compressione di dati

Algoritmi lossless (senza perdita di informazione):
operano un cambiamento di codifica dei dati che
permette di diminuire il numero di bit necessari alla
rappresentazione. Adatti per testi e programmi.
 per sequenze uguali: codifica del primo e del numero
di elementi uguali successivi. Es.: cccccccc  c8
 per frequenza: gli elementi piu frequenti vengono
codificati con meno bit.
Se A compare il 90% delle volte posso ‘comprimere’
la codifica nel seguente modo: A=0, B=100,
C=110, D=111 ottenendo una lunghezza di :
900 000 * 1 + 100 000 * 3 = 1 200 000 bit
Esempi: zip (per testi), GIF, TIFF (per immagini)
19
Compressione di dati (2)

Algoritmi lossy (che perdono informazione) specifici di
un certo campo (multimediale, etc.) e sfruttano le
caratteristiche degli oggetti da rappresentare per
‘buttare via’ informazione poco importanti
 gli algoritmi di compressione usati per immagini fisse
(es.JPEG) sfruttano sia la compressione lossless e la
caratteristica dell’occhio umano di essere poco
sensibile a lievi cambiamenti di colore in punti
contigui. Questi lievi cambiamenti vengono ignorati.
 Gli algoritmi lossy permettono di comprimere molto
più di quelli lossless ma si applicano solo a campi in
cui è ammesso perdere informazione (sì per
immagini e suoni, no per testi e programmi)
20
Rappresentazione di immagini

Immagini in movimento (video …)



il movimento è rappresentato già in modo
discreto nei media: con un numero abbastanza
alto di fotogrammi fissi (24-30 al secondo)
l’occhio umano percepisce il movimento come un
continuo
potrei in principio codificare separatamente ogni
fotogramma come immagine fissa, ma lo spazio
di memoria richiesto sarebbe enorme (650 MB, un
intero CD per un minuto di proiezione …)
sono stati quindi sviluppati metodi di codifica che
economizzano, codificando solo le ‘differenze’ fra
un fotogramma e l’altro (MPEG)
21
Rappresentazione di suoni

Caratteristiche dell’audio (e dei segnali
analogici)
tempo
22
Rappresentazione di suoni (2)
Campionamento dell’audio ad intervalli di
tempo fissi
tempo
Quantizzazione: ogni campione viene
rappresentato con un numero finito di bit
23
Rappresentazione di suoni (3)

L’accuratezza della ricostruzione dipende :




da quanto sono piccoli gli intervalli di
campionamento
da quanti bit uso per descrivere il suono in ogni
campione nella fase di quantizzazione
al solito … maggiore accuratezza significa maggior
quantità di memoria occupata!
Anche per i suoni si possono utilizzare
tecniche di compressione per migliorare
l’occupazione di memoria della sequenza di
campioni
24
Rappresentazione di suoni (5)


Algoritmi lossy per suoni : sfruttano il fatto
che per l’orecchio umano suoni a basso
volume sovrapposti ad altri di volume
maggiore sono poco udibili e possono essere
eliminati
È quello che accade nello standard MPEG
Layer 3, detto anche MP3, in grado di ridurre
drasticamente la quantità di dati richiesti per
riprodurre un suono, mantenendo comunque
una riproduzione fedele del file originale non
compresso.
25
Lo standard MIME

MIME (Multipurpose Internet Mail
Extension)
è uno standard che permette riconoscere
correttamente la codifica di dati di natura
diversa (testo, immagini, suoni etc.)

Una codifica MIME comprende


un preambolo, in cui viene specificato in modo
standard il tipo del dato che stiamo codificando
(text/plain,image/jpeg,image/gif)
un corpo (body), che contiene la codifica vera e
propria
26
Lo standard MIME (2)

MIME è utilizzato ad esempio per
messaggi di posta elettronica
 decodifica corretta di pagine web


In entrambi i casi il l’applicazione che
legge la posta o l’applicazione che
naviga su Web utilizza il preambolo
per decodificare e presentare i dati in
modo corretto
27