Fondamenti di Informatica - 1

Prof. B.Buttarazzi

A.A. 2011/2012

22/03/2012 2

Sommario• Codifica binaria dell‟informazione

• Codifica dei caratteri

– Codice ASCII

– Codice UNICODE

• Codifica di dati multimediali

– immagini

– filmati

– suoni

• Multipli del Byte

• Esercizi

3

Codifica delle informazioni

Cosa abbiamo visto

Sistema di numerazione binario

Codifica dei numeri (interi, reali)

Cosa vedremo

– Codifica dei caratteri

– Codifica delle immagini

– Codifica dei suoni

4

Codifica binaria dell’informazione

• Il calcolatore può elaborare informazioni, riferite a

diverse tipologie di oggetti ( numeri, caratteri,

immagini,ecc.) solo se queste sono rappresentate

in codice binario.

• Esigenza: assegnare un codice univoco a tutti gli

oggetti compresi in un insieme predefinito.

.

5

Codifica binaria dell’informazione

• Quanti oggetti diversi posso codificare con

parole binarie composte da k bit?

– 1 bit: 21 = 2 stati (0, 1) 2 oggetti

– 2 bit: 22 = 4 stati (00, 01, 10, 11) 4 oggetti

– 3 bit: 23 = 8 stati (000, 001, 010, 011, 100, 101,

110, 111) 8 oggetti

– …

– k bit: 2k stati 2k oggetti

6

Codifica binaria dell’informazione

• Se passiamo da una parola binaria di k bit

ad una parola di k+1 bit si raddoppia il

numero di oggetti che si possono

rappresentare (2k+1).

7

Codifica binaria dell’informazione

• Quanti bit mi servono per codificare N

oggetti:

– N 2k k log2 N k = log2 N

• Ipotesi implicita: le parole di un codice

hanno tutte la stessa lunghezza.

8

Definire un codice

Identificare due insiemi:

• Insieme delle configurazioni ammissibili;

• Insieme degli oggetti da rappresentare.

Associare gli elementi dei due insiemi

9

Esempio

Associare una codifica binaria ai giorni della

settimana (LUN, MAR, MER, GIO, VEN, SAB, DOM).

• Quanti bit devono avere le parole binarie

usate per identificare i giorni della

settimana

(7 oggetti diversi)?

– k = log2 7 = 3

10

Esempio

LUN MAR

VEN

GIO

MER

SAB DOM

Insieme degli oggetti da codificare

111 010

110011

001

101 100000

Insieme delle configurazioni ammissibili

11

Esempio111 010

110011

001

101 100000

LUN MAR

VEN

GIO

MER

SAB DOM

Codice

12

Codifica binaria dei caratteri

• Quanti sono gli oggetti da rappresentare?

– 26 lettere maiuscole

– 26 lettere minuscole

– 10 cifre

– Circa 30 simboli d‟interpunzione (, ; …)

– Circa 30 caratteri di controllo (EOF, CR, …)

• Totale circa 120 oggetti complessivi

k = log2 120 = 7

13

Codifica binaria dei caratteri

• Codice ASCII (American Standard Code for Information Interchange) utilizza 7 bit

può rappresentare 27 = 128 caratteri detti caratteri ASCII Standard.

• Codice ASCII esteso utilizza 8 bit (1 Byte)può rappresentare 28 = 256 caratteri detti

caratteri ASCII estesi.

– Tale codice comprende i caratteri ASCII standard e alcuni caratteri semigrafici (cornici, lettere nazionali, simboli matematici, ecc.)

15

Codifica binaria dei caratteri

• Codice UNICODE utilizza 16 bit (2 Byte)

può rappresentare 216 = 65.536 caratteri.

– Utile nel caso di alfabeti particolarmente complessi quale quello cinese

Codifica di sequenza di caratteri

Le sequenze di caratteri permettono di memorizzare: parole e testi.

I file di testo contengono parole, spazi bianchi e simboli di interpunzione , ( es. <a capo>)

Esempio: codifica della parola informatica in ASCII esteso

01101001, 01101110, 01100110, 01101111, 01110010, 01101101, 01100001,

i n f o r m a

01110100, 01101001, 01100011, 01100001

t i c a

Conversione in decimale

105, 110, 102, 111, 114, 109, 97, 116, 105, 99, 97

Conversione in esadecimale

69, 6E, 66, 6F, 72, 6D, 61, 74, 69, 63, 61

17

Rappresentazione di immagini

Le immagini non sono formate da sequenze di oggetti ben definiti come le stringhe, quindi prima di memorizzarle è ncessario discretizzarle ovvero trasformarle in un insieme di parti distinte e codificarle(assegnare un codice numerico a ciascun elemento)

Discretizzazione: scomposizione dell‟immagine in un reticolo di punti (pixel, picture element)

18

Esempio

Per rappresentare la seguente immagine

È necessario sovrapporre ad essa una griglia

Si identificano i “quadratini” che “discretizzano” il disegno

19

Esempio

Per rappresentare la seguente immagine

È necessario sovrapporre ad essa una griglia

Si identificano i “quadratini” che “discretizzano” il disegno

• Ogni quadratino derivante da tale suddivisione prende il nome di pixel(picture element) e se l‟immagine è in bianco e nero può essere codificato secondo la seguente convenzione:

– Il simbolo “0” viene utilizzato per la codifica di un pixel corrispondente ad un quadratino in cui è predominante il bianco

– Il simbolo “1” viene utilizzato per la codifica di un pixel corrispondente ad un quadratino in cui è predominanteil nero

0 0 0 1 0 0 0 0 0 0

0 0 1 1 1 0 0 0 0 0

0 0 1 1 1 1 1 0 0 0

0 0 0 0 0 0 0 0 0 0

Se riconvertiamo la sequenza di stringhe

0000000000 0011111000 0011100000 0001000000

in immagine otteniamo un‟approssimazione della figura originaria

La rappresentazione sarà più fedele all‟aumentare

del numero di pixel, ossia al diminuire delle

dimensioni dei quadratini della griglia in cui è

suddivisa l‟immagine

Se riconvertiamo la sequenza di stringhe binarie in immagine otteniamo

un‟approssimazione migliore della figura originaria

25

Risoluzione

• Chiamiamo risoluzione dell‟immagine la dimensione della

griglia utilizzata per discretizzare l‟immagine, ovvero il

numero di pixel presenti sullo schermo (colonne x righe)

• Risoluzione tipiche sono

640 x 480 1024 x 768 1280 x 1024

• Aumentando la risoluzione (ovvero il numero dei pixel) e

quindi diminuendo la dimensione del singolo pixel, la

rappresentazione approssima meglio l‟immagine originaria

26

Effetti della riduzione di risoluzione

27

Codifica e Quantizzazione

• Dopo aver discretizzato l‟immagine occorre rappresentare ogni pixel con un numero

• Tale numero dovrà rappresentare il colore associato al pixel, usando un certo range: si parla di quantizzazione

• La rappresentazione ottenuta è nota come codifica bitmap

• Nel caso di immagini in bianco e nero (caso già analizzato) senza sfumature è sufficiente 1 bit per ogni pixel:– Il simbolo “0” viene utilizzato per la codifica di un pixel

corrispondente ad un quadratino in cui il bianco è predominante– Il simbolo “1” viene utilizzato per la codifica di un pixel

corrispondente ad un quadratino in cui il nero è predominante

• Assegnando un bit ad ogni pixel è possibile codificare solo immagini in bianco e nero

• Per codificare le immagini con diversi livelli di grigiooppure a colori si devono usare più bit per rappresentare un pixel.

• Per esempio, – se utilizziamo 4 bit possiamo rappresentare 24 = 16 valori

distinti (da associare a livelli di grigio o colori diversi)

– se utilizziamo 8 bit ne possiamo distinguere 28 = 256

• In genere il colore viene realizzato componendo i 3 colori fondamentali: Red, Green, Blue (RGB)

• Se ad ogni colore si associano 2 bit (con cui si possono ottenere (22)4 sfumature per ciascun colore) si ottengono (26) 64 colori diversi e ogni pixel per essere codificato richiede 6 bit

Il numero di bit associato a ogni pixel si chiama profondità cromatica

• Se ad ogni colore si associano 8 bit si possono

ottenere (28)256 sfumature per ciascun colore

che combinate insieme il rosso, 256 per il blu e

256 per il verde che, combinate insieme, danno

origine a circa (224) circa 16,8 milioni di colori

diversi (precisamente 16777216 colori) e ogni

pixel per essere codificato richiede 3 byte.

Ad esempio: la sfumatura di celeste nella linea

rappresentata è determinata da una certa

combinazione di R G B.

Le sequenze di bit relative a ogni sfumatura di

colore primario sono espresse in base decimale:

139 (R), 210 (G),216 (B).

I tre numeri sono ovviamente compresi fra 0 e

255.

Ogni sfumatura di colore primario è

rappresentabile da 1 byte

13910 => 100010112

21010 => 110100102

21610 => 101001112

• Le immagini codificate pixel per pixel sono dette immagini in grafica bitmap (o raster)

– Le immagini bitmap occupano parecchio spazio

• Esistono delle tecniche di compressione che permettono di ridurre le dimensioni– Ad esempio, se più punti vicini di un‟immagine assumono lo

stesso colore, si può memorizzare la codifica del colore una sola volta e poi ricordare per quante volte deve essere ripetuta

• I formati compressi più diffusi sono: GIF, JPEG e PNG

33

Principali formati di compressione per immagini bitmap

• TIFF (Tagged Image File Format): uso di tag (etichette) descrittivi, 24

bit/pixel, compressione senza perdita

• GIF (Graphics Interchange Format, Compuserve): più immagini nello

stesso file, compressione senza perdita

• PNG (Portable Network Graphics): compressione lossless, studiato per

sostituire GIF (coperto da brevetti). Supporta solo grayscale e RGB.

Studiato per trasmissione di immagini su Web

• BMP (BitMaP, Microsoft e IBM): 1, 4, 8, 24 bit/pixel, compressione

senza perdita (RLE)

• JPEG (Joint Photographic Expert Group))(meglio noto come “formato

JPEG”)

34

Compressione di immagini• In fase di codifica esiste la necessità di adottare tecniche di compressione per

ottimizzare:– Occupazione di spazio di memoria

– Velocità di trasmissione attraverso la rete

• Tecniche di compressione senza perdita d informazione (lossless)– Reversibili

• Ad hoc per le immagini ad es. PNG

• Algoritmi con perdita di informazione (lossy)– Generalmente sono specifici di un certo campo e sfruttano le caratteristiche degli

oggetti da rappresentare per „eliminare‟ informazione poco importanti

– Nel caso di immagini gli algoritmi usati nei formati GIF e JPEG sfruttano la caratteristica dell‟occhio umano di essere poco sensibile a lievi cambiamenti di colore in punti contigui, e quindi eliminano questi lievi cambiamenti “appiattendo” il colore dell‟immagine

– Generalmente è possibile specificare quanto siamo disposti a perdere attraverso alcuni parametri

35

La dimensione delle immagini

• La risoluzione e la profondità cromatica determinano la dimensione di memoria necessaria a memorizzare un‟immagine.

• Esempio: 1024x768 pixel x 8 bit / pixel =

(256 toni di grigio / pixel)

768 Kbyte

• Esempio di immagine a colori :1024x768 pixel x 3 componenti / pixel x 256 toni /

componente =

1024x768 pixel x 3 componenti / pixel x 8 bit / pixel =

2304 Kbyte

Grafica bitmap

Le immagini codificate pixel per pixel sono dette immagini in grafica bitmap

La grafica bitmap va bene per immagini complesse o irregolari.

I formati più conosciuti sono:

BITMAP(.bmp), GIF (.gif), JPEG (.jpg)

Nelle pagine web si usano principalmente le immagini in

formato GIF o JPEG (recentemente anche PNG)

GIF (Graphics Interchange Format) JPEG (Joint Phot

Grafica vettoriale

Se le immagini sono regolari si può usare una codifica di tipo vettoriale in cui non si specificano le informazioni di colore dei singoli pixel ma ogni elemento geometrico primitivo viene specificato individualmente

• Le immagini vengono costruite a partire dalla descrizione degli elementi che le compongono mediante un linguaggio testuale o delle formule geometriche (es. SVG)

• Spesso occupano meno spazio rispetto alle immagini bitmap

38

Immagini vettoriali

• Codifica simbolica di elementi grafici – es.:

• Applicabilità limitata al mondo geometrico (non fotografie)• Nessuna perdita di dettaglio ingrandendo o rimpicciolendo l‟immagine• Formato principale: SVG (+ un vasto insieme di formati proprietari)

– forme geometriche, cioè linee costituite da segmenti di retta e curve e aree delimitate da linee chiuse;

circle

polyline…..

Codifica di filmati

• Un filmato è una sequenza di immagini statiche (dette fotogrammi o frame)

• Per codificare un filmato si “digitalizzano” i suoi fotogrammi

• Esempio:– 30 immagini ad alta risoluzione al secondo

– 30 imm./sec x 2457600 bit/imm. = 73728000 bit/sec

– Un minuto richiederebbe 60 sec x 73728000 = 4.423.680.000 bit (5.529.600 byte)

• Esempi di formati per il video: AVI, MOV

• Compressione: MPEG (Moving Picture Expert Group), differenza tra fotogrammi

Codifica dei suoni

• Fisicamente un suono è rappresentabile come un‟onda

che descrive la variazione della pressione dell‟aria nel

tempo (onda sonora)

• Sull’asse delle ascisse viene rappresentato il tempo e sull’asse delle

ordinate la variazione di pressione corrispondente al suono stesso

t

41

Codifica dei suoni

• Le onde sonore sono segnali „continui‟ pertanto per rappresentarli in binario sono necessarie 2 fasi

– Discretizzazione del tempo• Campionamento: scelta degli istanti in cui considerare il

valore del segnale (discretizzazione)

– Discretizzazione delle ampiezze• Quantizzazione: codifica dei campioni con un numero

predefinito di bit

Codifica dei suoni

• Si effettua il campionamento sull‟onda (cioè si misura il valore

dell‟onda a intervalli di tempo costanti) e si codificano in forma

digitale le informazione estratte da tali misure (campioni)

• Quanto più frequentemente viene campionato il valore di intensità

dell‟onda, tanto più precisa sarà la sua rappresentazione

• Il numero di campioni raccolti per ogni secondo definisce la frequenza di

campionamento che si misura in Hertz (Hz)

t

43

Campionamento

• Si misura l‟ampiezza del segnale analogico a intervalli

regolari, ogni T secondi

• T è detto periodo di campionamento (in secondi)

• F = 1/T è detta frequenza di campionamento (in Hz)

44

Campionamento

• Per segnali audio di tipo vocale (ad es. telefono), la frequenza di campionamento è tipicamente di 8 kHz

• Per segnali audio musicali (ad es. CD audio), la frequenza di campionamento è tipicamente di 44.1 kHz

• Un campionamento più fitto (ovvero con una frequenza di campionamento maggiore) consente di rappresentare i segnali analogici con maggiore fedeltà

Quantizzazione• L‟ampiezza dei singoli segnali estratti con il campionamento

rappresenta i valori che dobbiamo codificare.• Per poter essere rappresentato da un calcolatore, il valore

dell‟ampiezza deve essere espresso tramite un numero finito di bit

• La quantizzazione suddivide l‟intervallo dei valori ammissibili in 2k bit, dove k è il numero di bit per campione.

• La figura mostra una quantizzazione a 3 bit / campione

001

000

010

011

100

Codifica dei suoni

• La sequenza dei valori numerici ottenuti dai

campioni può essere facilmente codificata con

sequenze di bit

•La rappresentazione è tanto più precisa quanto maggiore è il numero

di bit utilizzati per codificare l’informazione estratta in fase di

campionamento

Codifica dei suoni

(esempio)Per codificare la musica di qualità dovremmo:

– Usare due registrazioni corrispondenti a due microfoni distinti (stereo)

– Campionare il segnale musicale producendo 44.100 campioni al secondo (frequenza di campionamento 44.1 kHz)

– Codificare ogni campione (che è un numero) con 16 bit

– Per cui, il numero di bit che sarebbero necessari per codificare ogni secondo di musica è pari a

2 x 44100 campioni x 16 bit/campione = 1.414.200 bit

=1,767 byte

Osservazione

Per calcolare lo spazio occupato da un file di testo, da un‟immagine, da un file audio, la tecnica è sempre la stessa

• Si trova lo spazio occupato da ogni unità elementare costituente il file (un carattere per il testo, un pixel per l‟immagine, un campione per il file audio)

• Si trova il numero di unità elementari che costituiscono il file (il numero di caratteri per il testo, il numero di pixel per l‟immagine - sfruttando la risoluzione, il numero di campioni per il file audio - sfruttando la frequenza di campionamento)

• Si moltiplicano queste due quantità

Unità di misura nel sistema binario

I prefissi (Kilo, Mega, ecc.) che normalmente sono associati a potenze di 10, in binario, per i multipli

del bit, si riferiscono a potenze di 2.

1MB non corrisponde a 1000KB ma a 1024KB

Ordini di grandezza binari

In un sistema binario gli ordini di grandezza sono dati dalle potenze di 2

20 21 22 23 24 25 26 27 28 29

1, 2, 4, 8, 16, 32, 64, 128, 256, 512

210 = 1.024 ~ 103 1 Kilobyte

220 = 1.048.576 ~ 106 1 Megabyte

230 = 1.073.741.824 ~ 109 1 Gigabyte

240 = 1.099.511.627.770 ~ 1012 1 Terabyte

250 = 1.125.899.906.842.624 ~ 1015 1 Petabyte

Esempio

226 = 26* 220 = 64 M

3/22/2012 51

ESERCIZIO

•Dato un insieme di 300 simboli; quanti bit si

devono utilizzare per rappresentarli tutti?

•Quanti byte occupa la frase “esonero di informatica” se la si

codifica utilizzando il codice ASCII esteso (8bit)?

•Quanti byte occupa la stessa frase scritta in codice UNICODE?

•Dati 12 bit per la codifica, quante informazioni distinte si possono

rappresentare?

Soluzione

• L‟esercizio richiede di trovare il numero di

bit che sono necessari per codificare 300

informazioni diverse.

• Dobbiamo quindi applicare la formula

2N>=M e ricavare N= log2 M

N=9

Soluzione

Quanti byte occupa la frase “esonero di informatica?” se la si codifica

utilizzando il codice ASCII esteso?

Quanti byte occupa la stessa frase scritta in codice UNICODE?

Codifica dell‟informazione: soluzione

Poichè sappiamo che ogni carattere in codice ASCII esteso occupa un

byte dobbiamo contare il numero di caratteri (inclusi gli spazi

bianchi) che formano la frase e moltiplicare per 1

23 caratteri =23 byte

Poichè ogni carattere in codice UNICODE occupa due byte avremo

23 caratteri 23 x 2 byte = 46 byte

Soluzione

Dati 12 bit per la codifica, quante informazioni

distinte si possono rappresentare?

In questo caso conosciamo la lunghezza delle

sequenze di bit che sono usate per la codifica

dell‟informazione e basterà applicare la formula

2N per trovare il numero di informazioni distinte

che si possono rappresentare

• 212 = 4096 (1024*4)

Esercizi

• Quanti byte occupa un‟immagine di 100 x 100

pixel in bianco e nero?

• Quanti byte occupa un‟immagine di 100 x 100

pixel a 256 colori?

• Se un‟immagine di 16.777.216 byte a colori

occupa 2400 byte, da quanti pixel sarà composta?

Soluzione

• Conoscendo la risoluzione dell‟immagine

possiamo trovare il numero di pixel che la

compongono: 100x100 = 10.000 pixel.

• Inoltre, nel caso di immagini in bianco e nero

basta un solo bit per codificare il colore di ogni

pixel e quindi saranno necessari 10.000 bit per

memorizzare l‟immagine.

• Per trovare il numero di byte basta fare 10.000 / 8

= 1250 byte

Soluzione

Quanti byte occupa un‟immagine di 100x100 pixel a 256 colori?

• Rispetto all‟esercizio precedente, in questo caso cambia lo spazio occupato da ciascun pixel. Sappiamo che l‟immagine è a 256 colori.

• Per poter rappresentare 256 configurazioni diverse sono necessari 8 bit, ovvero 1 byte

• L‟immagine occuperà quindi 10.000 x 1 byte = 10.000 byte

Soluzione

Se un’immagine a 16,7 milioni di colori occupa 2.400 byte, da quanti pixel sarà composta?

In questo caso le informazioni fornite dall‟esercizio sono il numero

colori e lo spazio occupato dall‟immagine.

Dal numero di colori ricaviamo lo spazio occupato da ciascun pixel,

calcolando il valore N nell‟espressione 2N>=16,7 milioni.

Il risultato è 24 bit, ovvero 3 byte.

Se ogni pixel richiede 3 byte e l‟immagine occupa 2.400 byte,

sarà composta da 2400 / 3 = 800 pixel

Esercizio

• Quanto spazio occupa un suono (non in

stereo) della durata di 10 secondi campionato

a 100 Hz (ovvero 100 campioni al secondo),

in cui ogni campione occupa 4 byte?

Soluzione

• La frequenza di campionamento ci dice quanti campioni di suono vengono memorizzati in un secondo, in questo caso 100.

• Avendo 10 secondi di suono avremo 10 x 100 = 1.000 campioni.

• Poiché ogni campione richiede 4 byte, il suono occuperà 1000 x 4 = 4000 byte

Esercizio

Un secondo di suono campionato a 512 Hz

occupa 1KB. Quanti valori distinti si

possono avere per i campioni?

Soluzione

Poichè vengono memorizzati 512 campioni al secondo, avremo in tutto 512 campioni (stiamo considerando un solo secondo di suono).

• Visto che il file sonoro di 512 campioni occupa 1 KB, cioè 1024 byte, ogni singolo campione occuperà 1024 / 512 = 2 byte, ovvero 16 bit.

• Quindi si potranno quindi a 216 = 65536 valori distinti per i campioni.