1

Informatica GeneraleMarzia Buscemi IMT Luccaemail: buscemi@di.unipi.it

Ricevimento: Giovedì ore 16.00-18.00 presso Dipartimento di Informatica, Largo Pontecorvo 3stanza 306 PS Tel. 050.2213102o per posta elettronica

Pagina web del corso: http://www.di.unipi.it/~buscemi/IG07.htm

2

Codifica e Rappresentazione dell’informazione

Cosa abbiamo visto :Rappresentazione binariaCodifica dei numeri (interi positivi), deiCaratteri, delle immagini fisse.

Cosa vedremo oggi:Codifica dei numeri negativi, razionali Codifica dei video e dei suoni Compressione dei dati

3

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 i-esima cifra (ci) della rappresentazione binaria

4

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?

5

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 dellarappresentazione di qualunque insiemefinito di oggetti (caratteri, punti di una immagine, etc.)

6

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)

7

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)

8

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

es : con 3 bit per la parte intera e 2 per quella frazionaria 011.11, 101.01

Parte intera Parte frazionaria

9

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 ...

10

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 136se 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.

11

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 frazionaria10000.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.

12

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

13

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 ed E = 11

14

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.

15

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”

16

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

000000000000000000000000000000000011111111000000000000000010000010000000000000000010000100000000000000000010001000000000000000000010010000000000000000000010100000000000000000000011000000000000000000000010000000000000

immaginecodifica

17

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

18

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)

19

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)

20

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)

21

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)

22

Rappresentazione di suoni

Caratteristiche dell’audio (e dei segnali analogici)

tempo

23

Rappresentazione di suoni (2)

Campionamento dell’audio ad intervalli di tempo fissi

tempo

Quantizzazione: ogni campione viene rappresentato con un numero finito di bit

24

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

25

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.

26

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

27

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