Rappresentazione Rappresentazione dell'informazionedell'informazione
Moreno MarzollaDipartimento di Informatica—Scienza e Ingegneria (DISI)
Università di Bolognahttps://www.moreno.marzolla.name/
Cap. 1 dispensa
Rappresentazione dell'informazione 2/53
Rappresentazione dell'informazione 3/53
Rappresentazione dell'informazione 4/53
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)
Rappresentazione dell'informazione 5/53
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 B0 0 00 1 01 0 01 1 1
A AND B A B0 0 00 1 11 0 11 1 1
A OR B A0 11 0
NOT A
A
B
A
B
A
Rappresentazione dell'informazione 6/53
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)
Rappresentazione dell'informazione 7/53
Esempio dimostrazione ¬ (A ∧ B) = (¬ A) ∨ (¬ B)
(¬ A) ∨ (¬ B)¬ (A ∧ B)A B
0011
0101
0001
1110
1100
1010
1110
……..
Rappresentazione dell'informazione 8/53
Operazioni elementari sui bit
A B0 0 00 1 11 0 11 1 0
A XOR B
A
B
● A ⊕ B ≡ (¬A ∧ B) ∨ (A ∧ ¬B)
Rappresentazione dell'informazione 9/53
Rappresentazione dell'informazione
● Come rappresentare– Numeri (interi, reali)– Testi (sequenze di caratteri)– Suoni, immagini, video
Rappresentazione dell'informazione 10/53
Rappresentazione di numeri non negativi
● Una sequenza di N bit può rappresentare un intero non negativo in base 2
● Esempio: quanto vale 001101012?
● 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, … 2N - 1}
128 64 32 16 8 4 2 1
0 0 1 1 0 1 0 1pesi
cifre binarie
Rappresentazione dell'informazione 11/53
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 7410
in binario?
– 74 / 2 = 37 resto 037 / 2 = 18 resto 118 / 2 = 9 resto 09 / 2 = 4 resto 14 / 2 = 2 resto 02 / 2 = 1 resto 01 / 2 = 0 resto 1
10010102
Cifra più a destra
Cifra più a sinistra
Rappresentazione dell'informazione 12/53
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
10 in base 16?
– 157 / 16 = 9 resto 13 (D)9 / 16 = 0 resto 9 (9)
15710
= 9D16
Rappresentazione dell'informazione 13/53
...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 2N + x– scartando gli eventuali bit in eccesso a sinistra
Rappresentazione dell'informazione 14/53
Esempio
● Supponiamo di avere N = 4 bit, e di voler codificare il numero x = 6– 2N + x = 24 + 6 = 22– 22
10 in binario si scrive 10110
2
– Abbiamo a disposizione solo 4 bit, quindi scartiamo quello più a sinistra: rimane 0110
2C
● La rappresentazione in complemento a 2 di 610
coincide con la normale rappresentazione binaria– Questo vale per tutti i numeri non negativi– 0
10 (decimale) in complemento a due si scrive 0...0
2C (una
sequenza di N zeri)
Rappresentazione dell'informazione 15/53
Esempio
● Rappresentiamo x = -7 con N = 4 bit in compl. a due– 2N + x = 24 – 7 = 9– 9
10 in binario si scrive 1001
2 quindi -7
10 = 1001
2C
● 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 -(2N-1) e 2N-1-1 (estremi inclusi)
● Con N = 8 bit [-128, 127]● Con N = 16 bit [-32768, 32767]● Con N = 32 bit [-2147483648, 2147483647]
Rappresentazione dell'informazione 17/53
Conversionecomplemento a 2 → decimale
● Si procede come per la conversione binario → decimale, con la differenza che il peso della cifra più a sinistra è -2N-1 anziché 2N-1
● Esempio: quanto vale 101101012C
?
– Risposta: -128 + 32 + 16 + 4 + 1 = -75
-128 64 32 16 8 4 2 1
1 0 1 1 0 1 0 1pesi
cifre binarie
Rappresentazione dell'informazione 18/53
Somma in complemento a due
● Si usano le regole della somma binaria "normale"● Calcolare 5
10 – 7
10 in compl. a due con N = 4 bit
– 510
= 01012C
– -7 si rappresenta come 24 - 7 = 16 - 7 = 910
= 10012C
● Sommando 01012C
+ 10012C
si ottiene 11102C
– Il primo bit a sinistra vale uno, quindi è un valore negativo– Infatti 1110
2C = -8 + 4 + 2 = -2
Rappresentazione dell'informazione 19/53
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
Rappresentazione dell'informazione 20/53
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 01 1 1 0
2C+
1 0 0 02C
=
1 0 1 1 02C
-2 -8 = 6 ?!?!?
Riporto 0 1 1 00 0 1 1
2C+
0 1 1 02C
=
1 0 0 12C
3 + 6 = -7 ?!?!?
(-2)10
+ (-8)10
310
+ 610
Rappresentazione dell'informazione 21/53
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 02C
+
1 0 0 02C
=
0 1 1 02C
0 0 1 12C
+
0 1 1 02C
=
1 0 0 12C
Rappresentazione dell'informazione 22/53
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 ≤ 2N-1-1 -2N-1 ≤ y ≤ 0da cui (sommando membro a membro):
-2N-1 ≤ x + y ≤ 2N-1-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 dell'informazione 23/53
Rappresentazione di numeri reali
● Come rappresentiamo un numero reale (“con la virgola”), come ad es. 34,765
10?
● Usiamo la notazione scientifica normalizzata:– 34,765 = 3,4765 × 101
– 0,007653 = 7,653 × 10-3
● Osserviamo che
3,4765 = 3×100 + 4×10-1 + 7×10-2 + 6×10-3 + 5×10-4
Rappresentazione dell'informazione 24/53
Rappresentazione di numeri reali● Lo stesso si può applicare anche per la base 2
1,10112 = 1´20 + 1´2-1 + 0´2-2 + 1´2-3 + 1´2-4 = 1,6875
10
● 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,mmm ...×2e e e ...
Rappresentazione dell'informazione 25/53
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 sottrae 127
Mantissa normalizzata dopo la virgola (prima della virgola si
assume 1)
Segno0 = positivo1 = negativo
1 bit 8 bit 23 bit
Rappresentazione dell'informazione 26/53
Esempio
● Valore: -1,6875 ´ 2-3 = -0,210937510
1 0111 1100 101 1000 0000 0000 0000 0000
Segno: -
Esponente: 0111 11002 = 124
10
12410
– 12710
= -310
Mantissa: 1,10112 = 1,6875
10
Rappresentazione dell'informazione 27/53
Attenzione
● L'aritmetica in virgola mobile può introdurre errori di approssimazione
● Esempio: la rappresentazione in base 2 di (0.1)10
è infinita!– (0.1)
10 = (0.00011)
2
– Troncando la rappresentazione binaria a 53 bit dopo la virgola (arrotondando) si ha
che è leggermente maggiore di 0.110
0.00011001100110011001100110011001100110011001100110011012
= 0.100000000000000005551115123125782702118158340454101562510
Rappresentazione dell'informazione 28/53
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
Rappresentazione dell'informazione 29/53
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
Rappresentazione dell'informazione 30/53
Codifica di caratteri
Rappresentazione dell'informazione 31/53
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 27 = 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 232 = 4 294 967 296 simboli
diversi
Rappresentazione dell'informazione 32/53
"ASCII-Table-wide" by ASCII-Table.svg: ZZT32derivative work: LanoxxthShaddow - ASCII-Table.svg. Licensed under Public Domain via Wikimedia Commons -
https://commons.wikimedia.org/wiki/File:ASCII-Table-wide.svg#/media/File:ASCII-Table-wide.svg
ASCII = American Standard Code for Information Interchange
Rappresentazione dell'informazione 33/53
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, ...
Rappresentazione dell'informazione 34/53
Codifica di immagini
Rappresentazione dell'informazione 35/53
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 …)
Rappresentazione dell'informazione 36/53
Immagini bitmap
● L’immagina viene scomposta in una griglia di elementi detti pixel (da picture element)
Immagine originale Rappresentazione bitmap
Rappresentazione dell'informazione 37/53
Immagini bitmap
● Ciascun pixel di una immagine in bianco e nero può essere rappresentato da un singolo bit– Ad es., 0 = bianco, 1 = nero
00000000000000000000000000000000000000000000000000000111110000000000100000100000000100101001000000010000000100000001010001010000000100111001000000001000001000000000011111000000
00000000 0000000000000000 0000000000000000 0000000000000111 1100000000001000 0010000000010010 1001000000010000 0001000000010100 0101000000010011 1001000000001000 0010000000000111 11000000
Rappresentazione dell'informazione 38/53
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:255G:255B:255
R:162G:162B:255
R:255G:51B:51
R:0G:255
B:0
R:0G:0B:0
R:0G:255
B:0
R:0G:255
B:0
R:0G:255
B:0
R:0G:255
B:0
R:0G:255
B:0
R:0G:255
B:0
R:0G:255
B:0
R:162G:162B:255
R:162G:162B:255
R:162G:162B:255
R:162G:162B:255
R:162G:162B:255
R:162G:162B:255
R:162G:162B:255
R:162G:162B:255
R:162G:162B:255
R:162G:162B:255
R:162G:162B:255
R:255G:51B:51
R:255G:51B:51
R:255G:51B:51
R:255G:51B:51
R:255G:51B:51
R:255G:51B:51
R:255G:51B:51
R:255G:51B:51
R:255G:51B:51
R:255G:51B:51
R:255G:51B:51
R:255G:51B:51
R:255G:51B:51
R:0G:0B:0
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255
R:255G:255B:255R:255G:255B:255
R:255G:255B:255R:255G:255B:255
Rappresentazione dell'informazione 39/53
Immagini vettoriali● L'immagine è descritta mediante primitive geometriche
(linee, cerchi, poligoni...) di cui si specificano i parametri
By Tonchino - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=23776193
Rappresentazione dell'informazione 40/53
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 Pbroks13 using CommonsHelper., CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=15789788
Rappresentazione dell'informazione 41/53
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 ´ 625256
(8 bpp)450'000
Telev. 4K 3840 ´ 21604096
(12 bpp)12'441'600
Foto 15000 ´ 1000016 milioni(24 bpp)
450'000'000
bpp = bit per pixel
Rappresentazione dell'informazione 42/53
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”
Rappresentazione dell'informazione 43/53
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)
Rappresentazione dell'informazione 44/53
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
Rappresentazione dell'informazione 45/53
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
Rappresentazione dell'informazione 47/53
Codifica di video e audio
Rappresentazione dell'informazione 48/53
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
Rappresentazione dell'informazione 49/53
Codifica di suoni
● Un generico suono (o segnale analogico) è rappresentato da un'onda continua
Tempo
Rappresentazione dell'informazione 50/53
Codifica di suoniCampionamento
● Il segnale viene misurato ad istanti discreti– Es: 1KHz = 1000 campioni/sec = 1 campione/msec
Tempo
Rappresentazione dell'informazione 51/53
Codifica di suoniQuantizzazione
● Per ogni campione, il valore assunto dal segnale viene espresso con un numero finito di bit (quantizzazione)
Tempo
Segnaleoriginale
Segnale campionato e quantizzato
Rappresentazione dell'informazione 52/53
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)
Rappresentazione dell'informazione 53/53
Idee chiave
● Rappresentazione binaria di interi● Complemento a due● Rappresentazione di informazione non numerica● Compressione lossless e lossy● Campionamento e discretizzazione
Rappresentazione dell'informazione 54/53
Top Related