Rappresentazione Rappresentazione dell'informazione dell'informazione

Rappresentazione Rappresentazione

dell'informazione dell'informazione

Moreno Marzolla

Dipartimento di Informatica—Scienza e Ingegneria (DISI) Università di Bologna https://www.moreno.marzolla.name/

Cap. 1 dispensa

Rappresentazione dell'informazione

●

I calcolatori elettronici rappresentano qualsiasi tipo di informazione come una sequenza di cifre binarie (bit)

– In particolare, sia i dati che il calcolatore elabora, sia le istruzioni che esegue, sono codificate con sequenze di bit

●

Bit

– Una singola cifra binaria: 0 (F, falso) oppure 1 (T, vero)

●

Byte

– Una sequenza di 8 cifre binarie: es 0010 1110

●

Parola (Word)

– Una sequenza di 4 Byte (= 32 cifre binarie)

Operazioni elementari sui bit

●

Altre notazioni usate comunemente:

– A AND B = A ∧ B = A · B

– A OR B = A ∨ B = A + B

– NOT A = ¬ A = A

A B

0 0 0

0 1 0

1 0 0

1 1 1

A AND B A B

0 0 0

0 1 1

1 0 1

1 1 1

A OR B A

0 1

1 0

NOT A

A B

A B

A

Alcune proprietà

●

Elemento neutro

– A ∧ 1 = 1 ∧ A = A

– A ∨ 0 = 0 ∨ A = A

●

Massimo e minimo

– A ∧ 0 = 0 ∧ A = 0

– A ∨ 1 = 1 ∨ A = 1

●

Assorbimento

– A ∧ (A ∨ B) = A

– A ∨ (A ∧ B) = A

●

Distributività

– A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)

– A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C)

●

De Morgan

– ¬ (A ∧ B) = (¬ A) ∨ (¬ B)

– ¬ (A ∨ B) = (¬ A) ∧ (¬ B)

Esempio dimostrazione ¬ (A ∧ B) = (¬ A) ∨ (¬ B)

(¬ A) ∨ (¬ B)

¬ (A ∧ B)

A B

0 0 1 1

0 1 0 1

0 0 0 1 1

1 1 0

1 1 0 0

1 0 1 0 1

1

1

0

Operazioni elementari sui bit

A B

0 0 0

0 1 1

1 0 1

1 1 0

A XOR B

A B

●

A ⊕ B ≡ (¬A ∧ B) ∨ (A ∧ ¬B)

Rappresentazione dell'informazione

●

Come rappresentare

– Numeri (interi, reali)

– Testi (sequenze di caratteri)

– Suoni, immagini, video

Rappresentazione di numeri non negativi

●

Una sequenza di N bit può rappresentare un intero non negativo in base 2

●

Esempio: quanto vale 00110101

?

●

Risposta: 32 + 16 + 4 + 1 = 53

– Si sommano i pesi corrispondenti alle cifre binarie “1”

●

Con N bit possiamo rappresentare tutti gli interi appartenenti all'insieme {0, … 2

- 1}

128 64 32 16 8 4 2 1

0 0 1 1 0 1 0 1

pesi

cifre binarie

Conversione decimale→binario

●

Si può procedere così

– Si divide il numero decimale ripetutamente per 2.

– I resti della divisione danno le cifre della rappresentazione binaria, a partire dalla cifra meno significativa

●

Es: come si scrive 74

in binario?

– 74 / 2 = 37 resto 0 37 / 2 = 18 resto 1

18 / 2 = 9 resto 0

9 / 2 = 4 resto 1

4 / 2 = 2 resto 0

2 / 2 = 1 resto 0

1 / 2 = 0 resto 1

1001010 ₂

Cifra più a destra

Cifra più a sinistra

Conversione decimale→base B

●

Si può procedere così

– Si divide il numero decimale ripetutamente per B

– I resti della divisione danno le cifre della rappresentazione in base B, a partire dalla cifra meno significativa

●

Esempio: in base 16 abbiamo le cifre 0, … 9, A, … F

●

Come si scrive 157

in base 16?

– 157 / 16 = 9 resto 13 (D) 9 / 16 = 0 resto 9 (9)

157 ₁₀ = 9D ₁₆

...e i numeri negativi?

●

Si utilizza la rappresentazione in complemento a due

●

Con N bit, il valore intero x viene codificato in binario allo stesso modo di 2

+ x

– scartando gli eventuali bit in eccesso a sinistra

Esempio

●

Supponiamo di avere N = 4 bit, e di voler codificare il numero x = 6

– 2

+ x = 2

+ 6 = 22

– 22

in binario si scrive 10110

– Abbiamo a disposizione solo 4 bit, quindi scartiamo quello più a sinistra: rimane 0110

●

La rappresentazione in complemento a 2 di 6

coincide con la normale rappresentazione binaria

– Questo vale per tutti i numeri non negativi

– 0

(decimale) in complemento a due si scrive 0...0

(una

sequenza di N zeri)

Esempio

●

Rappresentiamo x = -7 con N = 4 bit in compl. a due

– 2

+ x = 2

– 7 = 9

– 9

in binario si scrive 1001

quindi -7

= 1001

●

Osservazione 1

– I numeri negativi (in complemento a due) hanno sempre il primo bit a sinistra 1; i numeri positivi hanno 0

●

Osservazione 2

– Con N bit è possibile rappresentare in complemento a due i valori interi compresi tra -(2

) e 2

-1 (estremi inclusi)

●

Con N = 8 bit [-128, 127]

●

Con N = 16 bit [-32768, 32767]

●

Con N = 32 bit [-2147483648, 2147483647]

Conversione

complemento a 2 → decimale

●

Si procede come per la conversione binario →

decimale, con la differenza che il peso della cifra più a sinistra è -2

anziché 2

●

Esempio: quanto vale 10110101

?

– Risposta: -128 + 32 + 16 + 4 + 1 = -75

-128 64 32 16 8 4 2 1

1 0 1 1 0 1 0 1

pesi

cifre binarie

Somma in complemento a due

●

Si usano le regole della somma binaria "normale"

●

Calcolare 5

– 7

in compl. a due con N = 4 bit

– 5

= 0101

– -7 si rappresenta come 2

- 7 = 16 - 7 = 9

= 1001

●

Sommando 0101

+ 1001

si ottiene 1110

– Il primo bit a sinistra vale uno, quindi è un valore negativo

– Infatti 1110

= -8 + 4 + 2 = -2

Somme con riporto in base 2

a b c (a+b+c) c'

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

Errore di overflow

●

Se x e y hanno lo stesso segno, può verificarsi overflow. Esempio con N = 4 bit

– valori rappresentabili in complemento a due: -8 ... +7

Riporto 1 0 0 0

1 1 1 0

+ 1 0 0 0

= 1 0 1 1 0

-2 -8 = 6 ?!?!?

Riporto 0 1 1 0

0 0 1 1

+ 0 1 1 0

= 1 0 0 1

3 + 6 = -7 ?!?!?

(-2)

+ (-8)

3

+ 6

Quando si verifica overflow?

●

Quando entrambe le seguenti condizioni sono vere

– Gli operandi hanno lo stesso segno

– Il segno della somma è diverso da quello degli operandi

1 1 1 0

+ 1 0 0 0

= 0 1 1 0

0 0 1 1

+

0 1 1 0

=

1 0 0 1

Errore di overflow

●

Se x e y sono due numeri con segno diverso in complemento a due con N bit, (x + y) sarà ancora rappresentabile con N bit in complemento a due

– Infatti: supponiamo che x sia positivo e y negativo 0 ≤ x ≤ 2

-1 -2

≤ y ≤ 0

da cui (sommando membro a membro):

-2

≤ x + y ≤ 2

-1

●

Quindi: se x e y sono due numeri con segno diverso in

complemento a due con N bit, la loro somma non può

generare overflow

Rappresentazione di numeri reali

●

Come rappresentiamo un numero reale (“con la virgola”), come ad es. 34,765

?

●

Usiamo la notazione scientifica normalizzata:

– 34,765 = 3,4765 × 10

– 0,007653 = 7,653 × 10

●

Osserviamo che

3,4765 = 3×10

+ 4×10

+ 7×10

+ 6×10

+ 5×10

Rappresentazione di numeri reali

●

Lo stesso si può applicare anche per la base 2

1,1011

= 1´2

+ 1´2

+ 0´2

+ 1´2

+ 1´2

= 1,6875

●

Possiamo scrivere un numero reale diverso da zero in base 2 come

Dove:

– mmm.. sono le cifre della parte frazionaria della mantissa

– eee... rappresenta l'esponente

●

Non si usa la rappresentazione in complemento a due, bensì la notazione “con bias”, vedi lucido seguente

±1, m m m...×2 ^{e e e ...}

Rappresentazione di numeri reali

●

Solitamente si usa un numero fisso di cifre per la mantissa e per l'esponente

– Es: standard IEEE 754 singola precisione: 32 bit totali così suddivisi

s eeeeeeee mmmmmmmmmmmmmmmmmmmmmmm

Esponente

si converte in intero senza segno e si

Mantissa normalizzata dopo la virgola (prima della virgola si

assume 1) Segno

0 = positivo

1 bit 8 bit 23 bit

Esempio

●

Valore: -1,6875 ´ 2

= -0,2109375

1 0111 1100 101 1000 0000 0000 0000 0000

Segno: -

Esponente: 0111 1100

= 124

124

– 127

= -3

Mantissa: 1,1011

= 1,6875

Attenzione

●

L'aritmetica in virgola mobile può introdurre errori di approssimazione

●

Esempio: la rappresentazione in base 2 di (0.1)

è infinita!

– (0.1)

= (0.00011)

– Troncando la rappresentazione binaria a 53 bit dopo la virgola (arrotondando) si ha

che è leggermente maggiore di 0.1

0.0001100110011001100110011001100110011001100110011001101

= 0.1000000000000000055511151231257827021181583404541015625

Quindi

●

In virgola mobile non valgono molte proprietà degli operatori aritmetici

– a + (b + c) potrebbe essere diverso da (a + b) + c

– 0.9 potrebbe essere diverso da (1.0 – (1.0 × 0.1))

– ...eccetera

Riepilogo

●

Rappresentazione in base 2

– Interi positivi

– Interi positivi e negativi (complemento a due)

– Valori reali

●

Che dire di altri tipi di informazione?

– Caratteri alfanumerici

– Suoni

– Immagini

– ...

– Le istruzioni eseguite dalla CPU

Codifica di caratteri

Codifica dei caratteri

●

Quanti simboli dobbiamo rappresentare?

–

26 lettere minuscole

–

26 lettere maiuscole

–

10 numeri (0—9)

–

simboli vari (%, $, “...)

–

alcuni caratteri di controllo (Return, Canc, Insert...)

●

La codifica ASCII usa 7 bit per codificare 2

= 128 caratteri

–

Dato che i calcolatori moderni lavorano con byte di 8 bit, si usa la codifica ASCII estesa (extended ASCII) che usa 8 bit per

carattere

●

La codifica UNICODE usa 8, 16 o 32 bit

–

Con 32 bit si possono identificare 2

= 4 294 967 296 simboli

diversi

"ASCII-Table-wide" by ASCII-Table.svg: ZZT32derivative work: LanoxxthShaddow - ASCII-Table.svg. Licensed

ASCII = American Standard Code

for Information Interchange

Da ricordare

●

Le lettere minuscole hanno codici ASCII consecutivi

– 'a' = 97, 'b' = 98, 'c' = 99, ...

●

Le lettere maiuscole hanno codici ASCII consecutivi

– 'A' = 65, 'B' = 66, 'C' = 67, ...

●

I numeri hanno codici ASCII consecutivi

– '0' = 48, '1' = 49, '2' = 50, ...

Codifica di immagini

Codifica di immagini

●

Le immagini non sono formate da “sequenze” di oggetti ben definiti come i numeri e i testi

●

Per poterle rappresentare bisogna prima

“discretizzarle”

– Cioè trasformarle in un insieme di parti “discrete” che possono essere codificate con sequenze di bit

●

Consideriamo prima immagini fisse (foto etc …)

Immagini bitmap

●

L’immagina viene scomposta in una griglia di elementi detti pixel (da picture element)

Immagine originale Rappresentazione bitmap

Immagini bitmap

●

Ciascun pixel di una immagine in bianco e nero può essere rappresentato da un singolo bit

– Ad es., 0 = bianco, 1 = nero

0000000000000000 0000000000000000 0000000000000000 0000011111000000 0000100000100000 0001001010010000 0001000000010000 0001010001010000 0001001110010000 0000100000100000 0000011111000000

00000000 00000000

00000000 00000000

00000000 00000000

00000111 11000000

00001000 00100000

00010010 10010000

00010000 00010000

00010100 01010000

00010011 10010000

00001000 00100000

00000111 11000000

Immagini bitmap

●

Immagini a toni di grigio

– Un byte per pixel

(0=bianco, 255=nero, gli altri valori rappresentano toni intermedi di grigio)

●

Immagini a colori: più bit (es., 3 byte) per pixel

– 1 byte per la componente Rossa (0—255)

– 1 byte per la componente Verde (0—255)

– 1 byte per la componente Blu (0—255)

R:255 G:255 B:255

R:162 G:162 B:255 R:255

G:51B:51

R:0 G:255

B:0

R:0 G:0B:0

R:0 G:255

B:0

R:0 G:255

B:0

R:0 G:255

B:0

R:0 G:255

B:0

R:0 G:255

B:0

R:0 G:255

B:0

R:0 G:255

B:0 R:162

G:162 B:255 R:162

G:162 B:255

R:162 G:162 B:255

R:162 G:162 B:255

R:162 G:162 B:255 R:162

G:162 B:255

R:162 G:162 B:255

R:162 G:162 B:255

R:1

62 G:1

62 55 B:2

R:162 G:162 B:255

R:162 G:162 B:255 R:255

G:51B:51

R:255 G:51B:51

R:255 G:51B:51

R:255 G:51B:51 R:255

G:51B:51

R:255 G:51B:51

R:255 G:51B:51

R:255 G:51B:51 R:255

G:51B:51 R:255

G:51B:51

R:255 G:51B:51

R:255 G:51B:51

R:255 G:51B:51 R:0

G:0B:0 R:255

G:255 B:255

R:255 G:255 B:255

R:255 G:255 B:255

R:255 G:255 B:255 R:255

G:255 B:255

R:255 G:255 B:255 R:255

G:255 B:255 R:255

G:255 B:255

R:255 G:255 B:255 R:255

G:255 B:255 R:255

G:255 B:255

R:255 G:255 B:255 R:255

G:255 B:255 R:255

G:255 B:255

R:255 G:255 B:255 R:255

G:255 B:255 R:255

G:255 B:255

R:255 G:255 B:255 R:255

G:255 B:255

R:255 G:255 B:255 R:255

G:255 B:255

R:255 G:255 B:255 R:255

G:255 B:255

R:255 G:255 B:255 R:255 G:255 B:255 R:255

G:255 B:255 R:255 G:255 B:255

Immagini vettoriali

●

L'immagine è descritta mediante primitive geometriche

(linee, cerchi, poligoni...) di cui si specificano i parametri

Immagini bitmap vs vettoriali

●

Ne consegue che le immagini vettoriali possono essere

scalate senza perdita di dettaglio

●

I formati vettoriali sono adatti a disegni tecnici, ma non si

prestano alla rappresentazione di immagini reali (es., un volto, un paesaggio)

By The original uploader was Darth Stabro at English Wikipedia - Transferred from en.wikipedia to Commons by

Codifica di immagini

●

La rappresentazione accurata di una immagine bitmap dipende

– dal numero di pixel (definizione, o risoluzione)

– dalla codifica del pixel

●

…e richiede generalmente molta memoria

Risoluzione N. colori Byte Immagine

Televisiva 720 ´ 625 256

(8 bpp) 450'000 Telev. 4K 3840 ´ 2160 4096

(12 bpp) 12'441'600 Foto 15000 ´ 10000 16 milioni

(24 bpp) 450'000'000

Esercizio

●

Una immagine ha una risoluzione di 1800 ´ 1200

pixel; ogni pixel può avere un colore scelto tra 65536 colori possibili

●

Quanti Byte sono necessari per codificare l'immagine?

– Ipotizzare che il colore di un pixel sia rappresentato con il minimo numero di bit necessari per rappresentare

univocamente un intero tra 0 e 65535

– Trascurare lo spazio necessario per memorizzare la

“tavolozza dei colori”

Algoritmi di compressione

●

Per “risparmiare” memoria si impiegano tecniche di compressione

●

Alcuni formati comunemente usati

– JPEG (immagini)

– MP3, FLAC (audio)

– MP4, H.264 (video)

– ZIP, RAR, BZ2 (file generici)

Algoritmi di compressione

●

Algoritmi lossless (senza perdita di informazione):

–

Operano un cambiamento di codifica dei dati che permette di diminuire il numero di bit necessari alla rappresentazione

–

Consentono di ricostruire esattamente la sequenza di dati originali a partire dai dati compressi

●

Esempio: sequenza di 1 milione di caratteri scelti tra A, B, C, D

–

Usando la codifica ASCII: 8 milioni di bit

–

Usando una codifica ad hoc a lunghezza fissa, es. A=00, B=01, C=10, D=11: 2 milioni di bit

–

Supponiamo di sapere che il 90% dei caratteri sono A. Allora usando la codifica a lunghezza variabile A=0, B=100, C=110, D=111 sono richiesti:

900 000 ´ 1 + 100 000 ´ 3 = 1 200 000 bit

Algoritmi di compressione

●

Algoritmi lossy (con perdita di informazione)

– Sfruttano le caratteristiche degli oggetti da rappresentare per scartare informazione “poco importanti“

– Possono ottenere livelli di compressione elevati, ma non

consentono di ricostruire esattamente i dati originali a partire da quelli compressi

●

Alcune informazioni sono eliminate dal processo di compressione

– L'algoritmo JPEG sfrutta la caratteristica dell’occhio umano di essere poco sensibile a lievi cambiamenti di colore in

punti contigui, e quindi elimina questi lievi cambiamenti

“appiattendo” il colore dell’immagine

●

È possibile specificare mediante alcuni parametri quanto siamo

disposti a perdere in qualità nel processo di compressione

Codifica di video e audio

Codifica di video

●

Il movimento è simu- lato mostrando imma- gini fisse in sequenza (24-30 al secondo) che l’occhio umano percepisce come un continuo

●

Per risparmiare spa- zio alcuni metodi di codifica memorizzano solo le “differenze” fra un fotogramma e

l’altro

http://nickyguides.digital-digest.com/keyframes.htm

Codifica di suoni

●

Un generico suono (o segnale analogico) è rappresentato da un'onda continua

Tempo

Codifica di suoni Campionamento

●

Il segnale viene misurato ad istanti discreti

– Es: 1KHz = 1000 campioni/sec = 1 campione/msec

Tempo

Codifica di suoni Quantizzazione

●

Per ogni campione, il valore assunto dal segnale viene espresso con un numero finito di bit (quantizzazione)

Tempo

Segnale originale Segnale campionato e quantizzato

Codifica di suoni

●

L’accuratezza della ricostruzione dipende:

– da quanto sono piccoli gli intervalli di campionamento (intervalli più piccoli → qualità migliore)

– da quanti bit vengono utilizzati per descrivere il suono in ogni campione (più bit → qualità migliore)

●

Gli algoritmi lossy di compressione audio 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 (MP3)

Idee chiave

●

Rappresentazione binaria di interi

●

Complemento a due

●

Rappresentazione di informazione non numerica

●

Compressione lossless e lossy

●

Campionamento e discretizzazione