Rappresentazione e codificadell’informazione

Premessa

l Il calcolatore è una macchina digitale- Il suo linguaggio è composto da due soli simboli

l Gli esseri umani sono abituati a comunicareutlizzando più simboli

l Come è possibile tradurre le informazioni che ci scambiamo abitualmente in informazionicomprensibili ad un calcolatore?

Tipi di Informazioni

l Cifrel Caratteril Numeril Immaginil Suonil Videol ...

? 1001001000111110...

Un Mondo di Numeri

l Qualsiasi tipo di informazione può essere rappresentata in forma numerica- Testo: sequenza di caratteri- Ad ogni carattere è possibile associare un numero- Un testo è quindi una sequenza di numeri

Tabella ASCII (128 simboli)

Tabella ASCII Estesa (256 simboli)

Un Mondo di Numeri

l Qualsiasi tipo di informazione può essererappresentata in forma numerica- Immagine: sequenza di pixel- Pixel: 3 componenti (R, G, B)- Componente: un valore di intensità- Intensità: un numero (0..255)- Una immagine è quindi una sequenza di numeri

Pixel e RGB

Un Mondo di Numeri

l Qualsiasi tipo di informazione può essere rappresentata in forma numerica- Video: sequenza di immagini- Ma una immagine è quindi una sequenza di numeri- ...quindi anche un video è una sequenza di numeri

Un Mondo di Numeri

l Qualsiasi tipo di informazione può essere rappresentata in forma numerica- Suono: variazione della pressione in un punto- Può essere assimilata ad una funzione matematica nel

dominio del tempo- ...quindi anche un suono è una sequenza di numeri

Rappresentazioni Numeriche

l Non posizionalil Posizionali

Rappresentazioni NumericheNon Posizionali

l Il valore di ogni cifra non dipende dalla posizione della cifra- Es., i numeri romani

l XIII, I vale una unità indipendente dalla sua posizione

Rappresentazioni NumerichePosizionali

l Il valore di ogni cifra dipende dalla posizione della cifra

l 123- 1 vale 1 centinaio (100)- 2 vale 2 decine (20)- 3 vale 3 unità

Scomposizione di un Numero Decimale

l 123 = 100 + 20 + 3l Noi utilizziamo abitualmente il sistema decimale

- 10 cifre (0, 1, 2, …, 9) per comporre tutti i numeri

l La base di un numero decimale è 10l 12310 = 1 ´ 102 + 2 ´ 101 + 3 ´ 100

Numero Binario

l Un numero binario è un numero in base 2l Un numero binario utilizza due simboli

- Tipicamente 0 e 1

l 101102 = 12 ´ 24 + 02 ´ 23 + 12 ´ 22 + 12 ´ 21 + 02 ´ 20

- 1 e 0 sono simboli- Convenzionalmente 12 vale 110, 02 vale 010

l Quindi- 101102 = 2210

Numero Ottale

l Un numero ottale è un numero in base 8l Un numero ottale utilizza 8 simboli

- 0, 1, 2, 3, 4, 5, 6, 7

l 3578 = 38 ´ 82 + 58 ´ 81 + 78 ´ 80

- 3, 5 e 7 sono simboli- Convenzionalmente 38 vale 310, 58 vale 510, 78 vale 710

l Quindi- 3578 = 23910

Numero Esadecimale

l Un numero esadecimale è un numero in base 16l Un numero esadecimale utilizza 16 simboli

- 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

l 2AD16 = 216 ´ 162 + A16 ´ 161 + D16 ´ 160

- Convenzionalmente 016 vale 010, 116 vale 110, …, 916 vale 910, A16 vale 1010, B16 vale 1110, C16 vale 1210, D16 vale 1310, E16 vale 1410, F16 vale 1510

l Quindi- 2AD16 = 68510

Configurazioni

l Con 1 cifra binaria posso rappresentare 2 stati- 0, 1

l Con 2 cifre binarie posso rappresentare 4 stati- 00, 01, 10, 11

l Con 3 cifre binarie posso rappresentare 8 stati- 000, 001, 010, 011, 100, 101, 110, 111

l …l Con n cifre binarie?

Configurazioni

l Con n cifre binarie posso rappresentare 2n statil Esempio

- Con 5 bit è possibile rappresentare 32 diverse configurazioni

Configurazioni

l Sappiamo convertire un numero espresso in una qualsiasi base in un numero decimale

l ...ma il nostro obiettivo era fare il viceversa!

Decimale a Binario

l Basta esprimere il numero decimale come una somma di potenze del due- Tutte le potenze devono essere diverse tra loro

l Es. 1810 = 16 + 2 = 24 + 21

- È presente la cifra di peso 4 e la cifra di peso 1 quindi- Non è presenta la cifra di peso 3, di peso 2 e di peso 0- 1810 = 100102

l Es. 13710 = 128 + 8 + 1 = 27 + 23 + 20

- 13710 = 100010012

Decimale a Binario

l Alternativamente si calcolano i resti delle divisioni per la base di destinazione (in questo caso 2)

Decimale a Base Generica

l Per convertire un numero decimale in un numero in base b basta utilizzare il metodo delle divisionisuccessive- In questo caso si divide per b

Ottale a Binario

l Un simbolo ottale è codificato da 3 simboli binari (23)

l Quindi, per convertire un numero ottale a binario, basta convertire le singole cifre del numero ottale utilizzando per ognuna di esse 3 bit

Ottale a Binario

5218 = 1010100012

101 010 001

Esadecimale a Binario

l Un simbolo esadecimale è codificato da 4 simboli binari (24)

l Quindi, per convertire un numero esadecimale a binario, basta convertire le singole cifre del numero esadecimale utilizzando per ognuna di esse 4 bit

Esadecimale a Binario

3AC16 = 0011101011002

001110101100

Numeri Interi Relativi

l Rappresentazione in Modulo e Segno (MS)l Rappresentazione in Complemento a Due (C2)

Modulo e Segno

l Il primo bit di un numero binario rappresentato in MS indica il segno del numero- 1 → segno negativo- 0 → segno positivo

l Es. 110112 è un numero rappresentato in MS in decimale vale -1110

l Es. 010112 è un numero rappresentato in MS in decimale vale 1110

Complemento a Due

l Il primo bit di un numero binario rappresentato in C2 viene pesato con segno negativo

l Es. 111012 è rappresentato in C2, in decimale vale -24+23+22+20 = -310

Operatore del Complemento a Due

l L'applicazione dell'operatore C2 ad un numerobinario opera come segue- Il numero viene copiato simbolo per simbolo da destra

verso sinistra fino al primo 1- Tale 1 viene anch'esso copiato- Ma da questo momento in poi, i restanti simboli

vengono copiati complementati (cioè gli 0 diventano 1 e gli 1 diventano 0)

l Es. Il C2 di 01101000 è 10011000

Proprietà del C2

l L'applicazione del C2 su un numero binariorappresentato in C2 ne inverte il segno

l Es. 011010002 vale 10410, applicando il C2 siottiene 100110002 che vale -10410

Intervallo di Variazione

l Con n cifre binarie a disposizione, il più piccolo ed il più grandenumero rappresentabile è- Binario Naturale: Min: 0 Max: 2n-1- Modulo e Segno: Min: -(2n-1-1) Max: 2n-1-1- Complemento a Due: Min: -2n-1 Max: 2n-1-1

l Esempio, per n=4- Binario Naturale: Min: 0 Max: 15 (16 valori)- Modulo e Segno: Min: -7 Max: 7 (15 valori)

l Un valore in meno a causa della doppia rappresentazione dello 0

- Complemento a Due: Min: -8 Max: 7 (16 valori)

Bit, Byte, KByte, ...

l Bit = solo due stati, ‘0’ oppure ‘1’l Byte = 8 bit, quindi 28 = 256 statil KiloByte [KB] = 210 Byte = 1024 Byte ~ 103 Bytel MegaByte [MB] = 220 Byte ~ 106 Bytel GigaByte [GB] = 230 Byte ~ 109 Bytel TeraByte [TB] = 240 Byte ~ 1012 Bytel PetaByte [PB] = 250 Byte ~ 1015 Bytel ExaByte [EB] = 260 Byte ~ 1018 Byte

Numeri Frazionari

l Due rappresentazioni- Virgola fissa (fixed point)- Virgola mobile (floating point)

Virgola Fissa

l Si stabilisce una posizione fissa in cui mettere la virgola che separa la parte intera da quelladecimale

l Si assume che- Le cifre a SX della virgola hanno posizione crescente a

partire da 0- Le cifre a DX della virgola hanno posizione

decrescente a partire da -1

Virgola Fissa

l Sia il numero binario di 1 + I + D bit

l Il suo valore decimale è

s bI− 1bI− 2…b1b0 , b− 1b− 2…b− D

(− 1)s�(∑i= 0

I− 1

bi 2i+ ∑

d= − 1

− D

bd 2d)

Virgola Fissa

1101,10112 = -(22 + 20 + 2-1 + 2-3 + 2-4)= = -(5 + 0.6875) == -5.687510

Virgola Fissa

0.6 × 2 = 1.2 parte intera 10.2 × 2 = 0.4 parte intera 00.4 × 2 = 0.8 parte intera 00.8 × 2 = 1.6 parte intera 10.6 × 2 = 1.2 parte intera 1

l Rappresentare il numero 0.6 in binario in virgola fissa utilizzando 5 bit

l 0,610 = ,100112

l Errore 0.6 – (2-1+2-4+2-5) = 0.00625

Virgola Fissa

0.6 × 2 = 1.2 parte intera 10.2 × 2 = 0.4 parte intera 00.4 × 2 = 0.8 parte intera 00.8 × 2 = 1.6 parte intera 10.6 × 2 = 1.2 parte intera 10.2 × 2 = 0.4 parte intera 00.4 × 2 = 0.8 parte intera 00.8 × 2 = 1.6 parte intera 1

l Rappresentare il numero 0.6 in binario in virgola fissautilizzando 8 bit

l 0,610 = ,100110012

l Errore 0.6 – (2-1+2-4+2-5+2-8) = 0.00234

Virgola Fissa

l All'aumentare del numero di bit aumenta la precisione- Cioè diminuisce l'errore

l A meno che il numero non sia approssimabile in manieraperfetta

0.625 × 2 = 1.25 parte intera 10.25 × 2 = 0.5 parte intera 00.5 × 2 = 1.0 parte intera 10.0 × 2 = 0.0 parte intera 00.0 × 2 = 0.0 parte intera 0

... ...0.0 × 2 = 0.0 parte intera 0

Virgola Fissa

l Per rappresentare un numero decimale con la virgola in binario in virgola fissa con N bit occorre- Rappresentare la parte intera (es., metodo delle divisioni

successive) con I bit- Rappresentare la parte decimale (es., metodo delle

moltiplicazioni successive) con D bit- Rappresentare il segno con 1 bit

l N = I + D + 1

Virgola Mobile

l Deriva dalla rappresentazione scientifica (o standard)l Il numero è il prodotto di due parti

- Un fattore di scala (potenza del 10)- Parte frazionaria

l Quindi esistono più rappresentazioni dello stesso numero- 7,824 ´ 103

- 78,24 ´ 102

- 782,4 ´ 101

- 78240 ´ 10-1

Virgola Mobile

l Si utilizza la rappresentazione normalizzata- 0,7824 ´ 104

l Rappresentazione normalizzata- La parte frazionaria è minore di 1- La cifra più significativa è diversa da 0

l 0,007824 ´ 106 viene quindi riscritto come 0,7824 ´ 104

Virgola Mobile

l La rappresentazione in virgola mobile è la rappresentazione scientifica normalizzata con l’utilizzo del sistema binario- Dunque il fattore di scala è una potenza del 2

l La parte frazionaria è detta mantissal L'esponente del 2 è detto caratteristica (o

esponente)

±mantissa ´ 2±esponente

Virgola Mobile

l La normalizzazione evita di dover memorizzare la posizione della virgola

l Per evitare l'uso del segno nell'esponente, può essere rappresentato con un eccesso- Es. 7 bit per esponente e eccesso 64

l 0 – 63 considerati negativil 64 considerato 0l 65 – 127 considerati positivil esponenteeffettivo = esponente - 64

Virgola Mobile

segno esponente mantissa

0 1 2 3 4 5 6 7 8 9 10 11 12 … 31

l Singola precisione

l Doppia precisione

segno esponente mantissa

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... 63

Precisione

Virgola Fissa vs Virgila Mobile

l Intervallo di valori più ampio nella rappresentazione in virgola mobile

l Errore = Numero reale – Numero rappresentato- Virgola fissa: errore costante- Virgola mobile: errore variabile

l Piccolo per numeri piccolil Grande per numeri grandi

Scorrimento Logico a Destra

l Lo scorrimento logico a destra di n bit fa scorrere a destra i bit del numero di n posizioni- Gli n bit più significativi del numero ottenuto sono

fissati a zero - Gli n bit meno significativi del numero di partenza non

vengono considerati

Scorrimento Logico a Destra

0

l Scorrimento logico a destra di 2 bit

I due bit più significativi si azzerano

I due bit meno significativi si perdono

0

Osservazione

l Quando si scorre a destra il numero di 1 bit- Il bit di posizione i che originariamente pesava 2i ora

pesa 2i-1

l Il peso di ogni bit è dimezzato- Il numero è dimezzato

l Generalizzando- Lo scorrimento logico a destra di n bit equivale a

dividere (divisione intera) il numero per 2n

Esempio

l Si considerei il numero rappresentato in binario naturale 10102 cioè 1010

l Scorrimento logico a destra di 1 bit- 01012 cioè 510

l Infatti 10 : 2 = 5

Scorrimento Aritmetico a Destra

l L'osservazione secondo cui lo scorrimento logico a destra equivale e dividere il numero per una potenza del due vale solo per i numeri positivi

l Se il numero è rappresentato in complemento a due è opportuno utilizzare lo scorrimento aritmetico

Scorrimento Aritmetico a Destra

l Lo scorrimento aritmetico a destra di n bit fa scorrere a destra i bit del numero di n posizioni- Gli n bit più significativi del numero ottenuto assumono

lo stesso valore del bit più significativo del numero di partenza

- Gli n bit meno significativi del numero di partenza non vengono considerati

Scorrimento Aritmetico a Destra

l Scorrimento aritmetico a destra di 2 bit

I due bit più significativi Sono ugluali al bit più significativo del numero di partenza

I due bit meno significativi si perdono