Lezione 05: Codifica delle...

Walter Cazzola Lez. 5: Codifica delle Informazioni 1

Walter Walter CazzolaCazzolaDipartimentoDipartimento didi InformaticaInformatica e e ComunicazioneComunicazioneUniversitUniversità degli Studi di Milano.à degli Studi di Milano.

ee--mail: mail: [email protected]@dico.unimi.it

Laboratorio di Informatica (Chimica)Laboratorio di Informatica (Chimica)

LezioneLezione 05: 05: CodificaCodifica delledelle InformazioniInformazioni..


CodiceCodice

La relazione che associa ad ogni successione ben La relazione che associa ad ogni successione ben formata di simboli di un formata di simboli di un alfabetoalfabeto il dato il dato corrispondente è detta corrispondente è detta codicecodice..

Un codice mette quindi in relazione le successioni Un codice mette quindi in relazione le successioni di simboli con il significato loro attribuito.di simboli con il significato loro attribuito.


Rappresentazione delle informazioniRappresentazione delle informazioni

I calcolatori moderni sono detti calcolatori I calcolatori moderni sono detti calcolatori digitali:digitali:

digitdigit in inglese significa “cifra”in inglese significa “cifra”

Tutte le informazioni vengono rappresentate in Tutte le informazioni vengono rappresentate in forma numerica:forma numerica:–– numerinumeri–– carattericaratteri–– immagini statiche e in movimentoimmagini statiche e in movimento–– suonisuoni


Noi rappresentiamo i numeri utilizzando un alfabeto Noi rappresentiamo i numeri utilizzando un alfabeto di dieci simboli (0, 1, …, 9): rappresentazione di dieci simboli (0, 1, …, 9): rappresentazione posizionale decimale (in base dieci).posizionale decimale (in base dieci).

Per i calcolatori si usa un alfabeto binario.Per i calcolatori si usa un alfabeto binario.

Alfabeto binario: costituito da due simboliAlfabeto binario: costituito da due simboli–– convenzionalmente “0” e “1”convenzionalmente “0” e “1”

bitbit ((binarybinary digitdigit, cifra binaria): elemento che , cifra binaria): elemento che assume un valore binario.assume un valore binario.

il il bitbit è anche l’unità elementare di informazione.è anche l’unità elementare di informazione.

Rappresentazione delle informazioniRappresentazione delle informazioni


000 00001010000 00001010001 10010010001 10010010010 11100000010 11100000011 00111100011 00111100100 11111111100 11111111101 10000001101 10000001110 11110000110 11110000111 11100011111 11100011

Nella memoria del computer è possibile memorizzare Nella memoria del computer è possibile memorizzare esclusivamente sequenze di bit e il processore può esclusivamente sequenze di bit e il processore può processare soltanto dati espressi come sequenze di bit.processare soltanto dati espressi come sequenze di bit.

Rappresentazione delle InformazioniRappresentazione delle Informazioni

Esempio: celle di lunghezza 8.Esempio: celle di lunghezza 8.

Le celle contengono tutte lo stesso numero di Le celle contengono tutte lo stesso numero di bit, dettobit, detto lunghezza.lunghezza.

Gli indirizzi hanno una lunghezza fissata, che Gli indirizzi hanno una lunghezza fissata, che determinadetermina l’espansione massima della memoria.l’espansione massima della memoria.

Logicamente sono organizzate inLogicamente sono organizzate in celle indirizzabili.celle indirizzabili.

Esempio: con indirizzi di 3 bit Esempio: con indirizzi di 3 bit si hanno al massimo 8 celle.si hanno al massimo 8 celle.


Dimensioni TipicheDimensioni Tipiche

Celle di memoriaCelle di memoria–– 8 bit, 16 bit8 bit, 16 bit

IndirizziIndirizzi–– da 16 bit a 64 bitda 16 bit a 64 bit

Ma quante sono le celle indirizzabili con n bit?Ma quante sono le celle indirizzabili con n bit?Impariamo ora:Impariamo ora:

–– a fare qualche contoa fare qualche conto–– a conoscere le unità di misuraa conoscere le unità di misura–– come si rappresentano i dati numerici come si rappresentano i dati numerici


La Codifica BinariaLa Codifica Binaria

–– Avendo a disposizione un solo bit si possono rappresentare Avendo a disposizione un solo bit si possono rappresentare due elementi diversi: due elementi diversi:

–– si assegna al primo la codifica si assegna al primo la codifica 00–– al secondo la codifica al secondo la codifica 11

–– Con 2 bit si possono rappresentare 4 = 2Con 2 bit si possono rappresentare 4 = 222 elementi diversi, elementi diversi, assegnando a ciascuno una codifica diversa: assegnando a ciascuno una codifica diversa:

–– PaperinoPaperino codifica codifica 0000–– Qui Qui codifica codifica 0101–– Quo codifica Quo codifica 1010–– Qua codifica Qua codifica 1111

–– con n bit si possono rappresentare 2con n bit si possono rappresentare 2nn elementi diversi.elementi diversi.


Unità di Misura: il ByteUnità di Misura: il Byte

Una sequenza di 8 bit è detta Una sequenza di 8 bit è detta bytebyte, ed è l’unità di , ed è l’unità di misura della occupazione di memoria.misura della occupazione di memoria.

La scelta del byte ha ragioni storiche: La scelta del byte ha ragioni storiche: –– per codificare le lettere dell’alfabeto, cifre da 0 a 9, lo per codificare le lettere dell’alfabeto, cifre da 0 a 9, lo

spazio, la virgola, …, per un numero totale compreso tra spazio, la virgola, …, per un numero totale compreso tra 90 e 120, sono necessari almeno 7 bit (290 e 120, sono necessari almeno 7 bit (277=128);=128);

–– se ne utilizzano 8: i 7 bit indispensabili + 1 bit detto di se ne utilizzano 8: i 7 bit indispensabili + 1 bit detto di parità;parità;

8 è una lunghezza tipica delle celle di memoria.8 è una lunghezza tipica delle celle di memoria.


Rappresentazione dei CaratteriRappresentazione dei Caratteri

La codifica binaria dei caratteri più usata è la codifica ASCII,La codifica binaria dei caratteri più usata è la codifica ASCII, che che associa ad ogni carattere una sequenza di 7 bit (ASCII standard)associa ad ogni carattere una sequenza di 7 bit (ASCII standard)..–– 128 caratteri (cifre, lettere minuscole e maiuscole, punteggiatu128 caratteri (cifre, lettere minuscole e maiuscole, punteggiatura, ra,

caratteri speciali);caratteri speciali);–– La codifica rispetta l’ordine alfabetico.La codifica rispetta l’ordine alfabetico.

Un byte contiene 8 bit Un byte contiene 8 bit -- ASCII esteso, non standardASCII esteso, non standard–– 256 caratteri (ASCII standard + lettere accentate, ecc.)256 caratteri (ASCII standard + lettere accentate, ecc.)

Un codice a 8 bit non è però sufficiente se si vuole rappresentaUn codice a 8 bit non è però sufficiente se si vuole rappresentare un re un insieme di caratteri di insieme di caratteri di cardinalitàcardinalità maggiore di 256, come per maggiore di 256, come per esempio quello dei caratteri cinesi.esempio quello dei caratteri cinesi.

Per questo motivo è stato introdotto un codice a 32 bit per la Per questo motivo è stato introdotto un codice a 32 bit per la rappresentazione dei caratteri, chiamato rappresentazione dei caratteri, chiamato UnicodeUnicode, che permette di , che permette di rappresentare fino a 2rappresentare fino a 23232 elementi distinti.elementi distinti.


TabellaTabella ASCII StandardASCII Standard


Rappresentazione dei NumeriRappresentazione dei Numeri

I numeri sono entità matematiche astratte; vanno distinti dalla I numeri sono entità matematiche astratte; vanno distinti dalla loro rappresentazione.loro rappresentazione.

Sistema di Numerazione Romano:Sistema di Numerazione Romano:–– codificacodifica basatabasata suisui multiplimultipli didi 5 5 –– alfabetoalfabeto: I V X L C D M : I V X L C D M –– i i numerinumeri sonosono combinazionicombinazioni deidei simbolisimboli dell’alfabetodell’alfabeto. Es. 5=V, . Es. 5=V,

6=VI, 7=VII, ma 9=IX;6=VI, 7=VII, ma 9=IX;–– mancamanca un un simbolosimbolo per lo zero.per lo zero.

Sistema di Numerazione Arabico:Sistema di Numerazione Arabico:–– inin base diecibase dieci: utilizza le dieci cifre 0, 1, …, 9: utilizza le dieci cifre 0, 1, …, 9–– notazione posizionalenotazione posizionale: il valore di ogni cifra dipende dalla sua : il valore di ogni cifra dipende dalla sua

posizione nella successione di simboli che rappresenta il numeroposizione nella successione di simboli che rappresenta il numero..

Es.Es. 1234 = 1x101234 = 1x1033 + 2x10+ 2x1022 + 3x10+ 3x1011 + 4x10+ 4x1000


Codifica: Numeri NaturaliCodifica: Numeri Naturali

In generale, per un numero composto di In generale, per un numero composto di nn cifre si ha cifre si ha che:che:

ccnn––1 1 ccnn––2 2 ...c...c1 1 cc00 = = ccnn––11·10·10nn––11 + + ccnn––22·10·10nn––22 + … + + … + ccnn––2 2 ...c...c11·10·1011 + + cc00·10·1000

Si chiamano Si chiamano cifre più significativecifre più significative quelle associate ai quelle associate ai pesi maggiori.pesi maggiori.

La cifra La cifra ccnn––1 1 è la più significativa e è la più significativa e cc00 è la cifra è la cifra meno significativa. meno significativa.


Sistemi di numerazione in base BSistemi di numerazione in base BSe la base della numerazione è Se la base della numerazione è BB, si hanno a disposizione B , si hanno a disposizione B cifre, comprese tra cifre, comprese tra 00 e e BB––11..

ccnn ccnn––1 1 ...c...c1 1 cc00 = = ccnn..BBnn + + ccnn––22.

.BBnn––11 + … + + … + cc11..BB11 + + cc00.

.BB00

= = ΣΣi:0..n i:0..n ccii..BBii

Esempio:Esempio:101100101100duedue = (1x2= (1x255 + 0x2+ 0x244 + 1x2+ 1x233 + 1x2+ 1x222 + 0x2+ 0x211 + 0x2+ 0x200) ) diecidieci

= (32 + 8 + 4)= (32 + 8 + 4)diecidieci = 44= 44diecidieci..

Tramite Tramite mm cifre in base cifre in base BB è possibile rappresentare è possibile rappresentare BBmm

numeri naturali, da numeri naturali, da 00 a a BBmm--11..

Codifica: Numeri NaturaliCodifica: Numeri Naturali


Aritmetica FinitaAritmetica Finita

A livello HDW i calcoli numerici vengono eseguiti A livello HDW i calcoli numerici vengono eseguiti dalladalla–– ALU: Unità Logico Aritmetica;ALU: Unità Logico Aritmetica;–– Che si trova nella CPU e lavora con i registri della Che si trova nella CPU e lavora con i registri della

CPU.CPU.Siccome i registri hanno lunghezza prefissata L, Siccome i registri hanno lunghezza prefissata L,

numeri la cui rappresentazione binaria richiede più numeri la cui rappresentazione binaria richiede più di L cifre non sono rappresentabili.di L cifre non sono rappresentabili.


Aritmetica FinitaAritmetica Finita

Si usa dunque un’aritmetica finita, cioè con un numero massimo Si usa dunque un’aritmetica finita, cioè con un numero massimo di cifre binarie disponibili; di cifre binarie disponibili;

Nell’aritmetica finita dei calcolatori:Nell’aritmetica finita dei calcolatori:–– i numeri relativi sono rappresentati in complemento;i numeri relativi sono rappresentati in complemento;–– i numeri “reali” sono rappresentati in virgola mobile.i numeri “reali” sono rappresentati in virgola mobile.

Siccome il numero di cifre massimo è limitato, la precisione Siccome il numero di cifre massimo è limitato, la precisione raggiungibile nella rappresentazione dei numeri reali è raggiungibile nella rappresentazione dei numeri reali è limitata; abbiamo le seguenti precisioni:limitata; abbiamo le seguenti precisioni:–– Semplice 32 bit;Semplice 32 bit;–– Doppia 64 bit; edDoppia 64 bit; ed–– Estesa 128 bitEstesa 128 bit


Codifica dei Numeri NaturaliCodifica dei Numeri Naturali

Con una successione di Con una successione di nn bit si rappresentano i 2bit si rappresentano i 2nn

numeri naturali, da 0 a 2numeri naturali, da 0 a 2nn––1.1.

Per i numeri naturali si usano di solito 32 bitPer i numeri naturali si usano di solito 32 bit–– 223232––1 = 4.294.967.295 1 = 4.294.967.295 ≅≅ 4x4x101099

Raddoppiando la lunghezza, il massimo numero Raddoppiando la lunghezza, il massimo numero rappresentabile aumenta esponenzialmente. Se rappresentabile aumenta esponenzialmente. Se si utilizzano 64 bit:si utilizzano 64 bit:–– 226464––1 1 ≅≅ 1,6x1,6x10101919


Sistemi di NumerazioneSistemi di Numerazione

Base Base 22: quella in cui lavora il calcolatore: quella in cui lavora il calcolatore–– cifre 0,1cifre 0,1

Base Base 1010: quella dell’utente umano: quella dell’utente umano–– cifre 0,1,2,3,4,5,6,7,8,9cifre 0,1,2,3,4,5,6,7,8,9

Base Base 88: per abbreviare i numeri binari: per abbreviare i numeri binari–– cifre 0,1,2,3,4,5,6,7cifre 0,1,2,3,4,5,6,7

Base Base 1616: per abbreviare i numeri binari: per abbreviare i numeri binari–– cifre 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,Fcifre 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F


Fare i Conti: Proprietà NotevoliFare i Conti: Proprietà Notevoli

(pn1) 1 seguito da (pn1) 1 seguito da nn 0 rappresenta 0 rappresenta BBnn; ad ; ad eses..–– base 2: 100000 = base 2: 100000 = 2255–– base 10: 100000 = base 10: 100000 = 101055–– base 8: 100000 = base 8: 100000 = 8855–– base 16: 100000 = base 16: 100000 = 161655

(pn2)(pn2) nn cifre massime rappresentano cifre massime rappresentano BBnn--11; ad ; ad eses::–– base 2: 11111 = base 2: 11111 = 225 5 -- 11–– base 10: 99999 = base 10: 99999 = 10105 5 -- 11–– base 8: 77777 = base 8: 77777 = 885 5 -- 11–– base 16: FFFFF = base 16: FFFFF = 16165 5 -- 11


Dalla Rappresentazione al NumeroDalla Rappresentazione al Numero

Si applica la definizioneSi applica la definizione–– ccnn ccnn––1 1 ...c...c1 1 cc00 = = ccnn .. BBn n + + ccnn––22 .. BBnn––11 + … + + … + cc11 .. BB11 + + cc00 .. BB00

EsempiEsempi–– base 2: 1011 = base 2: 1011 = 11 . . 2233 + 0+ 0 . . 2222 + 1+ 1 . . 2211 + 1+ 1 = 10= 10–– base 8: 2705 = base 8: 2705 = 22 . . 8833 + 7+ 7 . . 8822 + 0+ 0 . . 8811 + 5+ 5 = 1477= 1477–– base 16: 3F01 = base 16: 3F01 = 33 . . 161633 + 15+ 15 . . 161622 + 0+ 0 . . 161611 + 1+ 1 = 16129= 16129


Dal Numero alla RappresentazioneDal Numero alla Rappresentazione

Si usano la divisione intera (Si usano la divisione intera (divdiv) e il resto () e il resto (modmod), e si ), e si applica la proprietà notevole delle rappresentazioni in applica la proprietà notevole delle rappresentazioni in base B:base B:–– n n modmod B è rappresentato dalla cifra cB è rappresentato dalla cifra c00 meno significativa della meno significativa della

rappresentazione di n in base Brappresentazione di n in base B–– n div B è rappresentato dalle cifre precedenti n div B è rappresentato dalle cifre precedenti

Ad es., nella base 10: Ad es., nella base 10: –– 1537 1537 modmod 10 = 7 è rappresentato da 710 = 7 è rappresentato da 7–– 1537 1537 divdiv 10 = 153 è rappresentato da 15310 = 153 è rappresentato da 153

La rappresentazione emerge attraverso divisioni intere La rappresentazione emerge attraverso divisioni intere successive, raccogliendo i resti, che corrispondono alle successive, raccogliendo i resti, che corrispondono alle cifre, partendo da quella meno significativa cifre, partendo da quella meno significativa


Dal Numero alla RappresentazioneDal Numero alla Rappresentazione

nnuummeerroo ddiivv bbaassee qquuoozziieennttee rreessttoo

66 ddiivv 22 == --ssiiggnniiffiiccaattiivvaa ddiivv 22 == ddiivv 22 == ++ssiiggnniiffiiccaattiivvaa

6 = 110

Ad esempio, se la base è 2: Ad esempio, se la base è 2:

si ripete la divisione intera per si ripete la divisione intera per 2 finché il quoziente non è zero.2 finché il quoziente non è zero.

e si raccolgono i quozienti e si raccolgono i quozienti interi ed i resti come cifreinteri ed i resti come cifre

Le cifre ottenute corrispondonoLe cifre ottenute corrispondonoalla rappresentazione binariaalla rappresentazione binaria

33 033 11 1

11 00 1


Conversioni da Basi 2 a Base 8 o 16Conversioni da Basi 2 a Base 8 o 16

La conversione dalla base 2 alla base 8 può essere fatta La conversione dalla base 2 alla base 8 può essere fatta per parti, considerando volta per volta una tripla di per parti, considerando volta per volta una tripla di cifre binarie.cifre binarie.

Es.Es. 001.010.110.111 = 1267001.010.110.111 = 1267ottootto

La conversione dalla base 2 alla base 16 può essere La conversione dalla base 2 alla base 16 può essere fatta per parti, considerando volta per volta una fatta per parti, considerando volta per volta una quadrupla di cifre binarie.quadrupla di cifre binarie.

Es.Es. 0010.1011.0111 = 2B70010.1011.0111 = 2B7sedicisedici

Le basi 8 e 16 sono usate perché hanno delle conversioni Le basi 8 e 16 sono usate perché hanno delle conversioni dalla base 2 molto semplici.dalla base 2 molto semplici.


Lunghezze Base 10 Lunghezze Base 10 -- Base 2Base 2

La situazione non è così semplice per la base 10, La situazione non è così semplice per la base 10, perché 10 non è potenza di 2.perché 10 non è potenza di 2.

La prima potenza di 10 vicina ad una potenza di 2 La prima potenza di 10 vicina ad una potenza di 2 è:è:–– 101033 ~ ~ 221010 = 1024= 1024

Per questo 1 K = 1024Per questo 1 K = 1024–– 1 K = 21 K = 21010

–– 1 K1 K ~ ~ 101033


Codifica Binaria: Interi RelativiCodifica Binaria: Interi Relativi

Codifica con modulo e segnoCodifica con modulo e segno: consiste : consiste nell’indicare il segno seguito dal valore nell’indicare il segno seguito dal valore assoluto, come succede normalmente nella assoluto, come succede normalmente nella codifica decimale.codifica decimale.

Il primo bit indica il segnoIl primo bit indica il segno–– 0 per positivo0 per positivo–– 1 per negativo1 per negativo

Gli altri Gli altri nn––1 bit rappresentano il valore assoluto.1 bit rappresentano il valore assoluto.



Codifica con modulo e segnoCodifica con modulo e segnoEsempiEsempi

00110011 == 3300000000 == 0010001000 == –– 0010111011 == –– 33

Ha il difetto di duplicare la rappresentazione del Ha il difetto di duplicare la rappresentazione del numero 0, cosa che può complicare l’esecuzione numero 0, cosa che può complicare l’esecuzione ed il controllo delle operazioni aritmetiche.ed il controllo delle operazioni aritmetiche.


Rappresentazione in Complemento a 60.Rappresentazione in Complemento a 60.SSi ha l’aritmetica dell’orologio senza la lancetta delle ore i ha l’aritmetica dell’orologio senza la lancetta delle ore

(segna sempre l’ora zero )(segna sempre l’ora zero )

da 0 a 59da 0 a 59

00

1515

3030

4545

00

1515

--3030

--1515

negativi: quanto negativi: quanto manca all’ora? manca all’ora?

da 0 a 29 non negativida 0 a 29 non negativida da --30 a 30 a --1 negativi1 negativi

InteriInteriassolutiassoluti



Rappresentazione in complemento a dueRappresentazione in complemento a due: : dati dati nn bit, un numero negativo bit, un numero negativo xx si rappresenta si rappresenta

con il valore binario corrispondente a 2con il valore binario corrispondente a 2nn++xx..Ad esempio, con successioni di 4 bitAd esempio, con successioni di 4 bit

–– 00000000 00 11011101 –– 3 = 10000 3 = 10000 -- 1111–– 00010001 11 11101110 –– 2 = 10000 2 = 10000 -- 1010–– 00100010 22 11111111 –– 1 = 10000 1 = 10000 –– 11



Codifica Binaria: Interi RelativiCodifica Binaria: Interi RelativiComplemento a 2 con 3Complemento a 2 con 3 bitbit

Se usiamo una cella di 3 bit abbiamoSe usiamo una cella di 3 bit abbiamo–– 000 000 +1+1 001 001 +1+1 010 010 +1+1 011 011 +1+1 100 100 +1+1 101 101 +1+1 110 110

+1+1 111 111 +1+1 10001000;;–– ma, siccome abbiamo solo 3 bit:ma, siccome abbiamo solo 3 bit: 111 111 +1+1 000000

–– ciocioèè si torna a 0, come nellsi torna a 0, come nell’’orologio dopo il orologio dopo il minuto 59minuto 59

–– Dunque una cella di 3 bit Dunque una cella di 3 bit èè come un orologio con come un orologio con ore di 8 = 2ore di 8 = 233 minutiminuti


Cioè, complemento a 2 con 3 bit significaCioè, complemento a 2 con 3 bit significa–– in complemento a 8 = 2in complemento a 8 = 233

0011

22

3344

55

66

77 0011

22

33--44

--33

--22

--11

Valori assolutiValori assoluti Valori in complemento;Valori in complemento;per gli arancione: quanto manca a 8?per gli arancione: quanto manca a 8?

Codifica Binaria: Interi RelativiCodifica Binaria: Interi RelativiComplemento a 2 con 3Complemento a 2 con 3 bitbit


3333011011

2222010010

1111001001

0000000000

--1177111111

--2266110110

--3355101101

--4444100100

1° bit1° bit0: +0: +

1° bit1° bit1: 1: --

numeronumero assolutoassoluto numeronumero in compl. a 2in compl. a 2

1° bit detto1° bit dettobit di segnobit di segno

Codifica Binaria: Interi RelativiCodifica Binaria: Interi RelativiComplemento a 2 con 3Complemento a 2 con 3 bit (bit (bitbit di segno)di segno)


Rappresentazione in complemento a dueRappresentazione in complemento a dueCon n bit possono essere rappresentati gli interi Con n bit possono essere rappresentati gli interi

compresi tra compresi tra ––22nn--11 e +(2e +(2nn--11 –– 1).1).Operativamente, si Operativamente, si complementanocomplementano i bit della i bit della

rappresentazione binaria del modulo x del rappresentazione binaria del modulo x del numero e si somma 1 al risultatonumero e si somma 1 al risultato

Ad esempio, con successioni di 4 bit (2Ad esempio, con successioni di 4 bit (244=16) =16) 55diecidieci = 0101= 0101

–– 55diecidieci = 1010 + 1 = 1011= 1010 + 1 = 1011



Errori di Errori di OverflowOverflow

L’intervallo dei numeri interi (assoluto o relativi) rappresentaL’intervallo dei numeri interi (assoluto o relativi) rappresentabili bili con un fissato numero di bit è limitato.con un fissato numero di bit è limitato.

Eseguendo un’operazione su numeri rappresentabili, può Eseguendo un’operazione su numeri rappresentabili, può accadere che il risultato esca dall’intervallo rappresentabile; accadere che il risultato esca dall’intervallo rappresentabile; in tal caso si dice che:in tal caso si dice che:

si ha un errore di overflowsi ha un errore di overflowESEMPIO con 8 bitESEMPIO con 8 bit

–– Caso di valori assoluti: massimo rappresentabile = 255Caso di valori assoluti: massimo rappresentabile = 255Overflow 150 + Overflow 150 + 150150 = 300 perché > 255= 300 perché > 255

–– Caso complemento a 2: intervallo Caso complemento a 2: intervallo rapprrappr.: .: --128.128..127.127OverflowOverflow --100 100 -- 100 = 100 = --200 perché < 200 perché < --128128


Numeri FrazionariNumeri Frazionari

Rappresentazione con la virgola:Rappresentazione con la virgola:–– ccnn ... c... c00,,cc--1 1 ... c... c--kk= = ccnnBBnn + ... + c+ ... + c00BB00 + c+ c--11BB--11+ ... + + ... + cc--kkBB--kk

Per passare dalla rappresentazione in base B al numero si Per passare dalla rappresentazione in base B al numero si applica la definizione.applica la definizione.

Esempio col numero binario 101,01Esempio col numero binario 101,01–– tralasciando il contributo nullo delle cifre 0:tralasciando il contributo nullo delle cifre 0:

101,01 = 101,01 = 1 1 . . 2222 + 1 + 1 . . 2200 + 1 + 1 .. 22--2 2 = = 4 + 1 + 1/44 + 1 + 1/4 = = 5,255,25


Numeri Frazionari: Numeri Frazionari: dal Numero alla Rappresentazionedal Numero alla Rappresentazione

Si trattano separatamente parte intera e frazionaria; per la Si trattano separatamente parte intera e frazionaria; per la intera, si procede come per i numeri interi; intera, si procede come per i numeri interi; –– per la frazionaria, si applica la proprietà:per la frazionaria, si applica la proprietà:

sia 0,csia 0,c--11cc--2 2 ... c... c--k k = = nn ; allora; alloracc--11,c,c--2 2 ... c... c--kk = = BB..nnEsempio in decimale:Esempio in decimale: 0,231 0,231 .. 10 = 2,3110 = 2,31moltiplicando per la basemoltiplicando per la base 10 10 emerge la cifraemerge la cifra 22

Cioè, per far emergere Cioè, per far emergere cc--11 basta moltiplicare per basta moltiplicare per BB;;moltiplicando ancora per moltiplicando ancora per BB emergerà emergerà cc--22 e così viae così via


ppaarrttee ffrraazziioonnaarriiaa ×× bbaassee pprrooddoottttoo ppaarrttee iinntteerraa

00,,2255 ×× 22 ==

×× 22 ==

×× 22 ==

0,250,25 = 0,01= 0,01

Contiene le cifreContiene le cifrebinarie, nell’ordinebinarie, nell’ordine

0,50,5

0,50,5 1,01,0

00

Ci si arresta quando la parteCi si arresta quando la partefrazionaria si azzerafrazionaria si azzera

00

11

Si riporta la parte frazionariaSi riporta la parte frazionariadella riga precedentedella riga precedente

Si riporta la parte interaSi riporta la parte interacome cifracome cifra

Numeri Frazionari: Numeri Frazionari: dal Numero alla Rappresentazionedal Numero alla Rappresentazione

NotaNota: un numero può essere non periodico in una base e periodico in : un numero può essere non periodico in una base e periodico in un’altra: es. un’altra: es. 0,40,4diecidieci ==duedue 0,0110011001100….0,0110011001100….


Codifica: Numeri RazionaliCodifica: Numeri Razionali

Notazione scientificaNotazione scientifica: un numero viene rappresentato come: : un numero viene rappresentato come: ±±m m x 10x 10pp

Es.Es. 123.000.000 = 1,23x10123.000.000 = 1,23x1088

Se, in generale, la base è Se, in generale, la base è BB, la rappresentazione è: , la rappresentazione è: ±± m m x x BBpp..

Il coefficiente Il coefficiente m m è detto è detto mantissamantissa (la convenzione è di (la convenzione è di inserire implicitamente la virgola decimale subito dopo la inserire implicitamente la virgola decimale subito dopo la prima cifra).prima cifra).

P, P, detto detto caratteristicacaratteristica,, è l’esponente a cui elevare la base è l’esponente a cui elevare la base B.B.

Es.Es. 1,23x101,23x1088 base 10, segno +, mantissa 123, caratteristica 8base 10, segno +, mantissa 123, caratteristica 8


Codifica Binaria: Numeri RazionaliCodifica Binaria: Numeri Razionali

La rappresentazione binaria dei numeri razionali che usa la La rappresentazione binaria dei numeri razionali che usa la notazione scientifica è detta notazione scientifica è detta rappresentazione in virgola rappresentazione in virgola mobilemobile ((floatingfloating pointpoint).).

101010000101010000duedue = 1,0101x10= 1,0101x1010001000duedue

Cambiando il numero di cifre dedicato alla Cambiando il numero di cifre dedicato alla rappresentazione di mantissa ed esponente cambia la rappresentazione di mantissa ed esponente cambia la precisione dei risultati che si ottengono.precisione dei risultati che si ottengono.

L’interesse a uniformare la precisione di calcolo ha L’interesse a uniformare la precisione di calcolo ha condotto alla definizione di uno standard internazionale condotto alla definizione di uno standard internazionale proposto dall’proposto dall’InstituteInstitute of of ElectricalElectrical and and ElectronicElectronicEngineersEngineers (IEEE). (IEEE).


Codifica Binaria: Numeri RazionaliCodifica Binaria: Numeri RazionaliVirgola Mobile (Virgola Mobile (floatingfloating pointpoint))

Virgola mobile: Virgola mobile: m E em E e con con –– mantissa mantissa mm per numeri diversi da 0: per numeri diversi da 0: 11 ≤ ≤ mm < < BB–– ee esponente esponente –– significato significato m E em E e = = mm..BBee

–– Esempio decimale: 344,013 in virgola mobile si scrive:Esempio decimale: 344,013 in virgola mobile si scrive:

3,44013 E 3 =3,44013 E 3 = 3,44013 3,44013 . . 101033

–– Esempio binario: 10,1001 in virgola mobile si scrive:Esempio binario: 10,1001 in virgola mobile si scrive:

1,01001 E 10 1,01001 E 10 == (1+2(1+2--22+2+2--55) ) . . 2222


Rappresentazione Rappresentazione FloatingFloating PointPoint::Singola Precisione, 32 bitSingola Precisione, 32 bit

ss FFee

UtilizzandoUtilizzando 32 bit per 32 bit per rappresentarerappresentare un floating un floating point, point, sisi ha:ha:

–– 1 bit 1 bit didi segnosegno (0 (0 rappresentarappresenta ilil +);+);–– 8 bit per 8 bit per l’esponentel’esponente (E=e(E=e--127); e127); e–– 23 bit per la mantissa (mantissa 1,F). 23 bit per la mantissa (mantissa 1,F).

NotaNota: : l’esponentel’esponente ––127, 127, cioècioè 00000000 è 00000000 è usatousato per per rappresentarerappresentare lo zero. lo zero. QuindiQuindi ilil numeronumero piùpiù piccolo piccolo positivopositivo saràsarà::

0|00000001|00000000000000000000000.0|00000001|00000000000000000000000.


Codifica Binaria: Numeri RealiCodifica Binaria: Numeri Reali

La rappresentazione esatta di un numero irrazionale La rappresentazione esatta di un numero irrazionale richiederebbe un numero infinito di cifrerichiederebbe un numero infinito di cifre–– Es.Es. 1/3 = 0,3333333… 1/3 = 0,3333333… ππ = 3,14159= 3,14159……....

Un problema analogo sorge per numeri con valore assoluto Un problema analogo sorge per numeri con valore assoluto molto grande o molto piccolo, in cui il numero di cifre molto grande o molto piccolo, in cui il numero di cifre richiesto non sarebbe infinito, ma molto elevato.richiesto non sarebbe infinito, ma molto elevato.

In questi casi possiamo considerare solo le cifre In questi casi possiamo considerare solo le cifre piúpiúsignificative.significative.


Codifica Binaria: Codifica Binaria: Errori di ArrotondamentoErrori di Arrotondamento

Qualunque sia la codifica scelta, la rappresentazione dei Qualunque sia la codifica scelta, la rappresentazione dei numeri nel calcolatore è soggetta ad numeri nel calcolatore è soggetta ad approssimazioniapprossimazioni..

Il limitato numero di cifre disponibili nella mantissa porta ad Il limitato numero di cifre disponibili nella mantissa porta ad errori di arrotondamento quando si debbano rappresentare errori di arrotondamento quando si debbano rappresentare numeri con una mantissa più lunga.numeri con una mantissa più lunga.

Tali approssimazioni si propagano nel corso della esecuzione Tali approssimazioni si propagano nel corso della esecuzione delle operazioni causando delle operazioni causando errori numericierrori numerici anche importanti.anche importanti.

Il Il calcolo numericocalcolo numerico è la disciplina che studia le proprietà è la disciplina che studia le proprietà dell’esecuzione delle operazioni tramite calcolatore e valuta dell’esecuzione delle operazioni tramite calcolatore e valuta l’entità degli errori introdotti durante l’esecuzione.l’entità degli errori introdotti durante l’esecuzione.


Rappresentazione delle Rappresentazione delle Informazioni non NumericheInformazioni non Numeriche

Nella memoria del computer è possibile memorizzare Nella memoria del computer è possibile memorizzare esclusivamente sequenze di bit e il processore può esclusivamente sequenze di bit e il processore può processare soltanto dati espressi come sequenze di processare soltanto dati espressi come sequenze di bit.bit.

Come memorizzo filmati, immagini e suoni?Come memorizzo filmati, immagini e suoni?


Grandezze Digitali e AnalogicheGrandezze Digitali e Analogiche

Si chiama Si chiama digitaledigitale una grandezza che può assumere un una grandezza che può assumere un insieme numerabile di valori.insieme numerabile di valori.

Ad esempio: il numero di granelli di sabbia di una spiaggia Ad esempio: il numero di granelli di sabbia di una spiaggia caraibicacaraibica, il numero di stelle e pianeti nell’universo., il numero di stelle e pianeti nell’universo.

Se la grandezza può assumere valori all’interno di un Se la grandezza può assumere valori all’interno di un insieme finito, allora è detta finita.insieme finito, allora è detta finita.

Si chiama Si chiama analogicaanalogica una grandezza che può assumere un una grandezza che può assumere un insieme non numerabile (cioè continuo) di valori.insieme non numerabile (cioè continuo) di valori.

Per esempio l’intensità di corrente che passa attraverso Per esempio l’intensità di corrente che passa attraverso un filo.un filo.


Analogico Analogico vsvs DigitaleDigitale

Il computer può lavorare soltanto con grandezze di tipo Il computer può lavorare soltanto con grandezze di tipo digitale e finite.digitale e finite.

Non tutte le grandezze che vorremmo rappresentare sono Non tutte le grandezze che vorremmo rappresentare sono digitali (digitali (eses: il colore, il suono, le forme).: il colore, il suono, le forme).

Dobbiamo Dobbiamo DiscretizzareDiscretizzare le informazionile informazioni

Dobbiamo trasformare le informazioni da analogico a Dobbiamo trasformare le informazioni da analogico a digitale, e digitale, e codificarelecodificarele come sequenze di bit prima di come sequenze di bit prima di poterle trasmettere al computer.poterle trasmettere al computer.


Da Analogico a DigitaleDa Analogico a Digitale

CampionamentoCampionamento: il segnale viene misurato a : il segnale viene misurato a intervalli discretiintervalli discreti–– la la frequenza di campionamentofrequenza di campionamento è il numero di è il numero di

campioni rilevati in un intervallo (di spazio o di campioni rilevati in un intervallo (di spazio o di tempo);tempo);

–– se la frequenza di campionamento è troppo bassa si se la frequenza di campionamento è troppo bassa si perde una parte del segnale;perde una parte del segnale;

La trasformazione del segnale da analogico a digitale La trasformazione del segnale da analogico a digitale consiste di due passi:consiste di due passi:


QuantizzazioneQuantizzazione: i valori possibili che ciascun : i valori possibili che ciascun elemento del campione può assumere sono elemento del campione può assumere sono fissatifissati

–– i i livelli di quantizzazionelivelli di quantizzazione sono generalmente sono generalmente fissati a intervalli regolari;fissati a intervalli regolari;

–– Se il livelli di Se il livelli di quantizzazionequantizzazione sono troppo pochi sono troppo pochi non si riescono a rappresentare passaggi di non si riescono a rappresentare passaggi di valore graduali;valore graduali;

Da Analogico a Digitale (Segue)Da Analogico a Digitale (Segue)


Esempi di campionamento e Esempi di campionamento e quantizzazionequantizzazione::

9 livelli di quantizzazione

Campionamento a 20 hertz

2 livelli di quantizzazione

Campionamento (risoluzione): 25 punti al cm2

Da Analogico a Digitale (Segue)Da Analogico a Digitale (Segue)


Rappresentazione delle FormeRappresentazione delle Forme

Le forme sono elementi di tipo analogico, perché Le forme sono elementi di tipo analogico, perché costituite da un tratto continuo.costituite da un tratto continuo.

Per rappresentare in modo digitale una forma la Per rappresentare in modo digitale una forma la si inscrive in una griglia.si inscrive in una griglia.


Rappresentazione delle Forme (Segue)Rappresentazione delle Forme (Segue)

Ogni elemento della griglia può essere pieno oppure Ogni elemento della griglia può essere pieno oppure vuoto.vuoto.

Il contenuto delle celle della griglia è l’immagine Il contenuto delle celle della griglia è l’immagine digitalizzatadigitalizzata


La densità di celle nella griglia è detta La densità di celle nella griglia è detta risoluzionerisoluzione..

Più fitta è la griglia, più la Più fitta è la griglia, più la digitalizzazionedigitalizzazione è fedele è fedele all’originale.all’originale.

Se si dedicano n celle alla rappresentazione di una Se si dedicano n celle alla rappresentazione di una immagine (in bianco e nero), sono necessari n bit.immagine (in bianco e nero), sono necessari n bit.

Una qualità di rappresentazione maggiore (griglia più Una qualità di rappresentazione maggiore (griglia più fitta) richiede una occupazione di memoria maggiore.fitta) richiede una occupazione di memoria maggiore.

Rappresentazione delle Forme (Segue)Rappresentazione delle Forme (Segue)


Rappresentazione dei ColoriRappresentazione dei Colori

Se si vuole aggiungere informazione riguardo ai colori, si Se si vuole aggiungere informazione riguardo ai colori, si può aggiungere, per ogni cella, una “tavolozza” nella può aggiungere, per ogni cella, una “tavolozza” nella quale è stato selezionato il colore dell’immagine in quel quale è stato selezionato il colore dell’immagine in quel punto.punto.

Se la tavolozza contiene m colori, sono necessari m bit Se la tavolozza contiene m colori, sono necessari m bit (verrà messo a 1 il bit corrispondente al colore che (verrà messo a 1 il bit corrispondente al colore che interessa, a 0 tutti gli altri).interessa, a 0 tutti gli altri).

In totale: In totale: n*mn*m bit per rappresentare una immagine su bit per rappresentare una immagine su una griglia di n elementi.una griglia di n elementi.


Rappresentazione delle ImmaginiRappresentazione delle Immagini

Se si vogliono rappresentare immagini complesse, come ad Se si vogliono rappresentare immagini complesse, come ad esempio un paesaggio o un ritratto, garantendo una buona esempio un paesaggio o un ritratto, garantendo una buona risoluzione dell’immagine e una fedeltà cromatica, allora le risoluzione dell’immagine e una fedeltà cromatica, allora le esigenze in termini di occupazione di memoria crescono molto esigenze in termini di occupazione di memoria crescono molto velocemente.velocemente.

Infatti:Infatti:–– la tavolozza deve rappresentare la la tavolozza deve rappresentare la digitalizzazionedigitalizzazione dello spettro dello spettro

cromatico (grandezza analogica) per poter mantenere le cromatico (grandezza analogica) per poter mantenere le sfumature;sfumature;

–– la griglia deve essere abbastanza fitta da non perdere i la griglia deve essere abbastanza fitta da non perdere i particolari dell’immagine.particolari dell’immagine.

Se si usano 8 bit si possono rappresentare 256 colori diversi.Se si usano 8 bit si possono rappresentare 256 colori diversi.Questa Questa quantizzazionequantizzazione non è sufficiente per mantenere le non è sufficiente per mantenere le

sfumature presenti nell’originale.sfumature presenti nell’originale.


Rappresentazione delle ImmaginiRappresentazione delle Immagini

Il metodo RGB (Il metodo RGB (RedRed, Green and Blue) prevede di:, Green and Blue) prevede di:–– associare 3 byte ad ogni cella, uno per il rosso, uno per il associare 3 byte ad ogni cella, uno per il rosso, uno per il

verde e uno per il blu verde e uno per il blu Rappresentare le sfumature per ciascun colore primario Rappresentare le sfumature per ciascun colore primario

con un insieme di 8 bit. con un insieme di 8 bit. In totale sono rappresentabili: 2In totale sono rappresentabili: 288 =256 sfumature per =256 sfumature per

ciascun colore primario.ciascun colore primario.Ad ogni cella sono quindi associati 3*8= 24 bit, e si Ad ogni cella sono quindi associati 3*8= 24 bit, e si

possono rappresentare 2possono rappresentare 22424 = circa 16 milioni di colori = circa 16 milioni di colori diversi.diversi.


Rappresentazione delle Immagini: Rappresentazione delle Immagini: FormatiFormati

BITMAPBITMAP: è il formato della rappresentazione più semplice: la : è il formato della rappresentazione più semplice: la sequenza dei bit della griglia ad ognuno dei quali sono sequenza dei bit della griglia ad ognuno dei quali sono associati 24 bit per il colore. E’ ingombrante.associati 24 bit per il colore. E’ ingombrante.

I file di tipo I file di tipo bitmapbitmap hanno estensione hanno estensione .bmp.bmp..

Per evitare una eccessiva occupazione di memoria si sono Per evitare una eccessiva occupazione di memoria si sono introdotti metodi per la codifica che prevedono anche una introdotti metodi per la codifica che prevedono anche una compressionecompressione delle immagini.delle immagini.

Tali sistemi sono basati su vari criteri orientati alla Tali sistemi sono basati su vari criteri orientati alla eliminazione delle parti superflue nella rappresentazione eliminazione delle parti superflue nella rappresentazione (per esempio una sequenza di celle dello stesso colore).(per esempio una sequenza di celle dello stesso colore).


Rappresentazione delle Immagini: Rappresentazione delle Immagini: FormatiFormatiI sistemi di codifica con compressione più diffusi sono:I sistemi di codifica con compressione più diffusi sono:

GIFGIF ((GraphicGraphic InterchangeInterchange Format):Format):–– Compressione;Compressione;–– 8 bit per il colore;8 bit per il colore;–– Adatto alla rappresentazione di immagini sempliciAdatto alla rappresentazione di immagini semplici

I file che contengono immagini codificate secondo questo I file che contengono immagini codificate secondo questo sistema hanno estensione .gif.sistema hanno estensione .gif.

PNGPNG ((portableportable Network Network GraphicsGraphics):):–– Compressione migliore rispetto a GIFCompressione migliore rispetto a GIF–– 24 bit per il colore24 bit per il colore

I file che contengono immagini codificate secondo questo I file che contengono immagini codificate secondo questo sistema hanno estensione sistema hanno estensione .png.png..


Rappresentazione delle Immagini: Rappresentazione delle Immagini: FormatiFormatiJPEGJPEG ((JointJoint Picture Picture ExpertsExperts GroupGroup):):

–– Codifica più efficiente rispetto al GIF;Codifica più efficiente rispetto al GIF;–– Colori codificati con 24 bit;Colori codificati con 24 bit;–– Adatto a rappresentare immagini ricche di sfumature di colore.Adatto a rappresentare immagini ricche di sfumature di colore.

I file che contengono immagini codificate secondo questo I file che contengono immagini codificate secondo questo sistema hanno estensione .jpg.sistema hanno estensione .jpg.

TIFFTIFF ((TaggedTagged ImageImage File Format): File Format): –– Compressione che mantiene una fedeltà maggiore all’immagine Compressione che mantiene una fedeltà maggiore all’immagine

originale;originale;–– Colori rappresentati con 24 bit;Colori rappresentati con 24 bit;–– Rispetto agli altri che compattano l’immagine richiede una Rispetto agli altri che compattano l’immagine richiede una

occupazione di memoria maggiore. occupazione di memoria maggiore. I file che contengono immagini codificate secondo questo I file che contengono immagini codificate secondo questo

sistema hanno estensione sistema hanno estensione .tif.tif


Rappresentazione del SuonoRappresentazione del Suono

La La digitalizzazionedigitalizzazione avviene nel dominio delle frequenze.avviene nel dominio delle frequenze.La frequenza di campionamento è espressa in La frequenza di campionamento è espressa in KhzKhz

(migliaia di hertz al secondo).(migliaia di hertz al secondo).I livelli di I livelli di quantizzazionequantizzazione costituiscono i suoni base costituiscono i suoni base

diversi che si possono distinguere:diversi che si possono distinguere:–– 8 bit (256 suoni) per un segnale tipo telefonico;8 bit (256 suoni) per un segnale tipo telefonico;–– 16 bit (circa 65.000 suoni) per una qualità CD;16 bit (circa 65.000 suoni) per una qualità CD;

Anche nel caso del suono i sistemi di codifica includono la Anche nel caso del suono i sistemi di codifica includono la compressione delle informazioni, per ridurre la compressione delle informazioni, per ridurre la dimensione dei file.dimensione dei file.


Rappresentazione del Suono: Rappresentazione del Suono: FormatiFormati

Formati di file audio più diffusi:Formati di file audio più diffusi:

AIFFAIFF (Audio (Audio InterchangeInterchange File Format)File Format)–– Estensione: Estensione: .aif.aif

WAVEWAVE–– Comparabile al Comparabile al .aif.aif–– Estensione Estensione .wav.wav

MP3 MP3 (MPEG Audio (MPEG Audio LayerLayer 3)3)–– Formato compresso a perdita di informazioneFormato compresso a perdita di informazione–– Estensione Estensione .mp3.mp3


Rappresentazione di Informazioni Rappresentazione di Informazioni MultimedialiMultimedialiA questo punto è chiaro che la rappresentazione digitale A questo punto è chiaro che la rappresentazione digitale

di di informazioni multimedialiinformazioni multimediali, che consistono di testo, , che consistono di testo, immagini, filmati (che sono sequenze di migliaia di immagini, filmati (che sono sequenze di migliaia di fotogrammi) e suoni, richiede una occupazione di fotogrammi) e suoni, richiede una occupazione di memoria imponente.memoria imponente.

Formati più diffusi per la rappresentazione multimediale:Formati più diffusi per la rappresentazione multimediale:–– MPEGMPEG (Moving Picture Expert Group), estensione (Moving Picture Expert Group), estensione .mpg.mpg–– QuickTimeQuickTime (nato su Macintosh), estensione (nato su Macintosh), estensione .mov.mov..–– AVIAVI (Audio Video (Audio Video InterleavedInterleaved), estensione ), estensione .avi.avi (usato (usato

per i per i divxdivx))


Riassumendo Riassumendo

La frequenza di campionamento:La frequenza di campionamento:–– nelle immagini è data dal numero di celle per unità di nelle immagini è data dal numero di celle per unità di

superficie, in genere misurata in punti per pollice(dpi: dot persuperficie, in genere misurata in punti per pollice(dpi: dot perinch)inch)

–– nel suono è misurata in nel suono è misurata in KhzKhz..I livelli di I livelli di quantizzazionequantizzazione::

Nelle immagini:Nelle immagini:–– 16 milioni di colori 16 milioni di colori -- 24 bit24 bit–– 256 colori 256 colori –– 8 bit8 bit–– 64 colori 64 colori –– 6 bit6 bit–– 2 colori 2 colori –– 1 bit1 bit Nel suonoNel suono–– 256 256 –– 8 bit (codifica usata per la trasmissione sulla rete)8 bit (codifica usata per la trasmissione sulla rete)–– 65536 valori 65536 valori –– 16 bit (codifica usata nei CD)16 bit (codifica usata nei CD)

Lezione 05: Codifica delle...

Documents

Transcript of Lezione 05: Codifica delle...