•Rappresentazioni posizionali •Codifica numeri interi •Codifica di...
Transcript of •Rappresentazioni posizionali •Codifica numeri interi •Codifica di...
Corso Informatica 2 - Codifica Binaria dell'Informazione
Codifica binaria dell’informazione
•Rappresentazioni posizionali•Codifica numeri interi•Codifica numeri in virgola mobile•Codifica di immagini •Codifica di suoni e video (cenni)
1
Corso Informatica 2 - Codifica Binaria dell'Informazione 2
La codifica binaria
L’alfabeto piu’ semplice e’ quello costituito da soli due simboli.
Facilmente implementabile su un supporto fisico
Sostanze magnetiche con due opposte polarizzazioni
Passaggio o meno di corrente Passaggio o meno di luce . . . .
Piu’ economico Piu’ affidabile
Un sistema automatico basato su un alfabeto binario e’:
2
Corso Informatica 2 - Codifica Binaria dell'Informazione 3
Es. Codice binario di Morse: . -
A . - J . - - - S . . .B - . . . K - . - T -
C - . - . L . - . . U . . -
D - . . M - - V . . . -
E . N - . W . - -F . . - . O - - - X - . . -
G - - . P . - - . Y - . - -
H . . . . Q - - . - Z - - . .I . . R . - .
• Codifica solo le lettere maiuscole
• Il numero di simboli in successione non e’ fisso per ogni lettera
3
Corso Informatica 2 - Codifica Binaria dell'Informazione 4
Sistema di numerazione decimale
1. E’ posizionale (unita’, decine, centinaia)
2. E’ costituito da 10 cifre (base = 10)
504.31 = 5 • 102 + 0 • 101 + 4 • 100 + 3 • 10-1 + 1 • 10-2
peso
valore intrinseco della cifra
Cifra piu’ significativa Cifra meno
significativa
4
Corso Informatica 2 - Codifica Binaria dell'Informazione 5
Notazione posizionaleLa notazione posizionale consente di scrivere un numero N di una certa base generica b come una sequenza di cifre.
504.31 = 5 • 102 + 0 • 101 + 4 • 100 + 3 • 10-1 + 1 • 10-2
an-1 a n-2 a n-3 . . .a 2 a 1 a 0 . a -1 a -2 …. . . a-m-2 a m-2 am-1 a-m
Generalizzando, data una base b ed un insieme di b cifre:
Valore decimale del numero N
€
0 ≤ ai ≤ b −1
5
Corso Informatica 2 - Codifica Binaria dell'Informazione 6
Sistemi posizionaliSistema Base Cifre
binario 2 0 1
ottale 8 0 1 2 3 4 5 6 7
decimale 10 0 1 2 3 4 5 6 7 8 9
esadecimale 16 0 1 2 3 4 5 6 7 8 9 A B C D E F
(208) 10=(11010000)2=(D0)16=(320)8
base
6
Corso Informatica 2 - Codifica Binaria dell'Informazione 7
Sistema non posizionale
Il sistema di numerazione romano non e’ posizionale: il valore associato a ciascun simbolo non dipende dalla sua posizione.
Es: nei due numeri XII e XIX la seconda cifra, pur avendo la stessa posizione, assume due pesi diversi:
XII = 10 + 1 + 1XIX = 10 + 10 - 1
7
Corso Informatica 2 - Codifica Binaria dell'Informazione 8
Limiti della rappresentazione posizionale (I)
Data un sistema di numerazione di base b qual e’ il massimo numero intero positivo rappresentabile in una sequenza di n cifre?
€
Nmax = (b −1) bii= 0
n−1
∑ = bn −1
Es. in 4 cifre il sistema decimale puo’ rappresentare interi positivi da 0 a 9999, ovvero 104 valori diversi, ovvero b4 valori.
Formalmente, il numero massimo Nmax rappresentabile con n cifre nella base b e’:
8
Corso Informatica 2 - Codifica Binaria dell'Informazione 9
Limiti della rappresentazione posizionale (II)
Es. in una sequenza di 16 cifre il sistema binario puo’ rappresentare 216 = 65536 interi positivi che vanno da 0 a 65535; il numero minimo di cifre per rappresentare il numero 1000 è ceil(log2
(1001)) = 10
Quante cifre sono invece necessarie per rappresentare un dato numero in una base?Basta invertire la relazione precedente:
Ceiling: minimo intero superiore
9
Corso Informatica 2 - Codifica Binaria dell'Informazione 10
Il computer e l’informazioneIl sistema posizionale binario permette la codifica dell’informazione numerica attraverso l’uso di solo due cifre. Con opportune convenzioni si possono rappresentare anche i numeri relativi interi e frazionari, i caratteri, le immagini ed i suoni.
A causa della maggiore facilita’ implementativa ed affidabilita’ su un supporto fisico, i calcolatori digitali trattano solo informazione codificata in forma binaria.
L’unita’ elementare d’informazione manipolata e memorizzata da un computer e’ detta bit (binary digit), e può assumere i valori 1 e 0.
10
Corso Informatica 2 - Codifica Binaria dell'Informazione 11
Alcune convenzionibyte sequenza di 8 bit (Es. 01001011)
word da 16 a 64 bit a seconda dell’architettura; convenzionalmente 16bit
longword convenzionalmente 32 bit
≈ 1018260 = 10246EExa≈ 1015250 = 10245PPeta≈ 1012240 = 10244TTera≈ 109 230 = 10243GGiga≈ 106220 = 10242MMega≈ 103 210 = 1024kKilo
ApprossimazioneValoreSiglaMultiplo
11
Codifica dei Numeri
12
Corso Informatica 2 - Codifica Binaria dell'Informazione
Numeri BinariTorniamo ai numeri binari. Come si sommano due numeri binari?
13
63
9
+=0 0 1 1
1 0 0 1
0 1 1 0
23 22 21 20
1+0 = 1
1+1 = 10
13
Corso Informatica 2 - Codifica Binaria dell'Informazione
Moltiplicazione
14
62
12
x=0 0 0 1
1 1 0 0
0 1 1 0
23 22 21 20
34
12
x=0 1 0 0
1 1 0 0
0 0 1 1
14
Corso Informatica 2 - Codifica Binaria dell'Informazione
Moltiplicazione
15
Dunque moltiplicare un numero per 2 equivale a spostare verso sinistra le cifre binarie riempendo con gli zeri le posizioni nuove
0 1 1 01 0
23 22 21 20 24 23 22 21x 2
0 1 1 020
0=
E se divido? Ovviamente basta ragionare al contrario: si spostano le cifre verso destra.
= 26/2 = 13 0 0 1 10 1
0 1 1 0
15
Corso Informatica 2 - Codifica Binaria dell'Informazione
Moltiplicazione/Divisione
16
Esiste una notazione compatta, identificata dall’apposito operatore di shift
<< shift a destra (moltiplicazione)
>> shift a sinistra (divisione)
0 1 1 01 0 >> 226/2 = 13
0 0 1 10 1
0 0 1 10 << 26 x 2 = 12
0 1 10 0
16
Corso Informatica 2 - Codifica Binaria dell'Informazione
Moltiplicazione/Divisione
17
Ma se faccio 13/2 ?
0 1 1 01 >> 2
13/20 0 1 10
=6!!
quindi c’è qualcosa che non può essere gestito correttamente.
0 1 1 01 << 4
13x41 0 1 00
= 20
Underflow
Overflow
17
Corso Informatica 2 - Codifica Binaria dell'Informazione 18
Guardiamo la sottrazione
1 - 0 = 1 1 - 1 = 0 0 - 1 = ?0 - 1 = 1
quindi non posso gestire bene il segno. In realtà un modo semplice è quello di usare il bit più significativo per il segno
0 0 1 1 0 01 0
1 0 1 1 0 01 0
50
-50
18
Corso Informatica 2 - Codifica Binaria dell'Informazione 19
Codifica dei numeri interi
Nell’ aritmetica binaria vi sono 4 tecniche di organizzazione dei numeri interi con segno.
1. Modulo e segno;
2. Complemento alla base diminuita;
3. Complemento alla base;
4. Eccesso M (o bias);
19
Corso Informatica 2 - Codifica Binaria dell'Informazione 20
Complemento alla base
Dato un numero Nb, il complemento alla base
C(Nb) e’ dato da:
C(Nb) = bn - N dove n e’ il numero di cifre usato per rappresentare N.
Per b = 2, il complemento e’ noto come complemento a 2.
In pratica, il complemento a 2 si ottiene invertendo tutti i bit e aggiungendo 1.
20
Corso Informatica 2 - Codifica Binaria dell'Informazione 21
Complemento alla base
C(Nb) = bn - N N0 bn
0 0 1 1 1 01 0N = (58) dec (0x3A) hex
bn = 1 1 1 1 1 11 128 (255) dec (0xFF) hex
C(Nb) = (197) dec (0xC5) hex 1 1 0 0 0 10 1
21
Corso Informatica 2 - Codifica Binaria dell'Informazione 22
Metodo del biasSi sottintende di sottrarre sempre un numero pari a 2n/2=2(n-1)
da ogni numero rappresentato. A 8 bit il numero da sottrarre (bias) è allora 128.
+(8)10 ( 1 0 0 0 1 0 0 0 )2
-(8)10 ( 0 1 1 1 1 0 0 0 )2
(8+128) 10 = (136)10
(-8+128) 10 = (120)10
•Il metodo del bias preserva l’ordinamento.•Per effettuare somme e sottrazioni occorre ogni volta sottrarre o aggiungere il bias
22
Corso Informatica 2 - Codifica Binaria dell'Informazione 23
Metodo del biasSi sottintende di sottrarre sempre un numero pari a 2n/2=2(n-1)
da ogni numero rappresentato. A 8 bit il numero da sottrarre (bias) è allora 128.
0 2n
0 2n-1-2n-1
n=4 24-1=824=16
16
8-8 0
0
23
Numeri Reali
24
Corso Informatica 2 - Codifica Binaria dell'Informazione
Numeri RealiCome si rappresenta 10.4
25
23 22 21 20 . 2-1 2-2 2-3 2-4
1 0 1 0 . 0 1 0 0
Anche in questo caso per dividere o moltiplicare basta shiftare a destra o sinistra
25
Corso Informatica 2 - Codifica Binaria dell'Informazione 26
Numeri in virgola mobile (I)Se invece voglio rappresentare un intero molto grande, come ad esempio duemila miliardi:
N = 2 000 000 000 000Avremmo bisogno di ben 41 bit per rappresentarlo come unsigned (o 42 come int).
La maggior parte dello spazio sarebbe sprecato per conservare informazione sugli zeri: in effetti si può usare la notazione scientifica e scrivere, in modo molto più compatto:
N = 2.0 x 1012N = 2.0 x 1012
26
Corso Informatica 2 - Codifica Binaria dell'Informazione 27
Numeri in virgola mobile (II)
Mantissa Base Esponente
N = 2.0 x 1012
I primi calcolatori utilizzavano ciascuno un differente sistema di convenzioni per rappresentare i floating point. Nel 1985 è stato definito uno standard che è oggi largamente accettato.
27
Corso Informatica 2 - Codifica Binaria dell'Informazione 28
Lo standard IEEE 754
Bit di segno
Mantissa frazionaria normalizzata
Esponente con bias
N = (-1)S x 1.F x 2E-B
28
Corso Informatica 2 - Codifica Binaria dell'Informazione 29
Float, double, long doubleL’esempio precedente si riferisce a un numero di tipo float o singola precisione.
Lo standard ANSI/IEEE754 definisce anche il numero di bit per ciascun campo per rappresentare numeri di tipo double (doppia precisione) e long double (quadrupla precisione).
F (23 bit)E (8 bit)S (1 bit)
F (52 bit)E (11 bit)S (1 bit)
F (112 bit)E (15 bit)S (1 bit)
Float
Double
Long double
29
Corso Informatica 2 - Codifica Binaria dell'Informazione
Precisione e bit• Cosa cambia tra i 3 tipi ? Ovviamente posso rappresentare numeri
sempre più grandi ma è solo questo?• In realtà la differenza sostanziale sta nella mantissa F.• Questa infatti ci dà il numero di cifre significative che possiamo
contare
30
F (23 bit) = 223 = 8388607• significa che posso suddividere l’unità in 223 intervalli e
quindi ho una precisione
1/223 = 1,2x10-7
1/252 = 2,2x10-16
1/2112 = 1,2x10-35
FloatDouble
Long Double
30
Corso Informatica 2 - Codifica Binaria dell'Informazione 31
Overflow e underflowNelle operazioni fra floating point, possono verificarsi due condizioni di errore :
Overflow: in un qualsiasi passo l’esponente calcolato è superiore al massimo rappresentabile; può verificarsi quando si maneggiano numeri dal valore assoluto molto elevato.
Underflow: in un qualsiasi passo l’esponente calcolato è inferiore al minimo rappresentabile; può verificarsi quando si maneggiano numeri molto vicini allo “zero” della macchina.
31
Corso Informatica 2 - Codifica Binaria dell'Informazione 32
Un “paradosso”La proprietà associativa della somma garantisce che, in generale:
Eppure…in singola precisione calcoliamo il lato destro e il sinistro dell’uguaglianza per
x = -1.5 ·1038 ; y = 1.5 ·1038 ; z = 1.0
x+(y+z) =(x+y)+z
x+(y+z) =-1.5 x1038 + (1.5 x1038 +1.0) =0.0
x+(y+z) =(-1.5 x1038 + 1.5 x1038 +1.0) =1.0
32
Corso Informatica 2 - Codifica Binaria dell'Informazione 33
Propagazione degli erroriI calcoli in virgola mobile vengono effettuati riportando i numeri allo stesso esponente, lavorando poi sulle mantisse e infine normalizzando il risultato.Tali procedure introducono un arrotondamento nei calcoli:la cifra meno significativa della mantissa sarà sempre affetta da un errore.
Per minimizzare questo errore lo standard IEEE 754 prevede di memorizzare tutti i risultati intermedi di un’operazione in virgola mobile con due cifre aggiuntive dette di cifra di guardia e cifra di arrotondamento.
In questo modo i calcoli in virgola mobile garantiscono una precisione inferiore a metà dell’unita sulla cifra meno significativa.
33
Corso Informatica 2 - Codifica Binaria dell'Informazione 34
Codifica dei caratteri
Mentre per codificare numeri si usano tecniche basate sul loro valore, per codificare dei caratteri c’e’ bisogno di una relazione convenzionale, ovvero di una tabella che faccia corrispondere a una data sequenza di bit un dato carattere.
Nel progettare tale tabella bisogna tener conto ovviamente anche di caratteri non direttamente stampabili, ma che rappresentino la formattazione del testo, come ad esempio il carriage return CR (“a capo”).
34
Corso Informatica 2 - Codifica Binaria dell'Informazione 35
Il codice ASCIILo standard internazionalmente adottato per la codifica dei caratteri è il codice ASCII, acronimo di American Standard Code for Information Interchange.
Le caratteristiche del codice ASCII sono:•7 bit ovvero 128 caratteri da 0 a 127•32 caratteri speciali non stampabili•Cifre del sistema decimale, maiuscole, minuscole, !”#$&’()*+,-./@:;<=>? Etc.•Le lettere e le cifre conservano l’ordine alfabetico/numerico•La distanza fra maiuscole e minuscole è fissata
Il codice viene spesso esteso a 8 bit per comprendere set di caratteri specifici di una certa area geografica, come è,Ç
0 1 2 3 4 5 6 7 8 9 A B C D E F
0 NUL SOH STX ETX EOT ENQ ACK BEL BS HT LF VT FF CR SO SI
1 DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM SUB ESC FS GS RS US2 SP ! " # $ % & ' ( ) * + , - . /
3 0 1 2 3 4 5 6 7 8 9 : ; < = > ?
4 @ A B C D E F G H I J K L M N O
5 P Q R S T U V W X Y Z [ ¥ ] ^ _
6 ` a b c d e f g h i j k l m n o7 p q r s t u v w x y z { | } ~ DEL
35
Codifica delle Immagini
36
Corso Informatica 2 - Codifica Binaria dell'Informazione 37
Codifica di ImmaginiNon c’è un “quanto” naturale di informazione elementare come la cifra per i numeri o la lettera per i testi.Si introduce allora un reticolo di punti detti pixel (picture element
Ad ogni pixel viene poi associato un certo numero di bit, che indica l’intensità luminosa di ciascun colore primario, ovvero della combinazione RGB RedGreenBlue .
Una tipica codifica utilizza 8 bit per colore (=256 livelli di intensità) ovvero 24 bit/pixel. In questo modo si possono rappresentare 224 ~ 16 milioni di diverse tonalità di colore.
Il numero di bit/pixel impiegati viene chiamato profondità di colore dell’immagine.
37
Corso Informatica 2 - Codifica Binaria dell'Informazione 38
Codifica di Immagini - Bitmap0 0 0 1 1 0 0 00 1 1 0 0 1 1 00 1 0 0 0 0 1 01 0 0 1 0 0 0 11 0 0 0 1 0 0 10 1 0 0 0 0 1 00 1 1 0 0 1 1 00 0 0 1 1 0 0 0
00011000011001100100001010010001100010010100001001100110000110003 zeri 2 uno 4 zeri 2 volte (2 uno 2 zeri) uno 4 zeri 1 0 1 2 zeri …
38
Corso Informatica 2 - Codifica Binaria dell'Informazione 39
Codifica di Immagini• Problema :
– la rappresentazione accurata di una immagine dipende• dal numero di pixel (definizione)• dalla codifica del pixel
– … e richiede generalmente molta memoria, ad esempio :tipo defin numero colori num. byteimm. televisiva 720x625 256 440 KBSVGA 1024x768 65536 1.5 MBfoto 15000x10000 16milioni 430 MB
COMPRESSIONE dei dati
39
Corso Informatica 2 - Codifica Binaria dell'Informazione 40
Codifica Immagini - Formati– RAW (matrice dei punti)
– TIFF Tagged Image File Format (etichette che descrivono le propietà dei dati (24 bit, LZW))
– GIF Graphics Iterchange Format (Formato concepito per l'invio di immagini in rete, più immagini)
– JPEG Joint Photographers Experts Group (Per immagini fotografiche, trasparenza, interlace)
– BMP Bitmap (formato tipico di Windows)
– PCX PC Paintbrush (formato di questo popolare programma Windows)
– PICT Formato Macintosh (anche vettoriale)
40
Corso Informatica 2 - Codifica Binaria dell'Informazione 41
.bmp 3841 Kb
.tiff 3842 Kb
.jpeg 425 Kb
41
Corso Informatica 2 - Codifica Binaria dell'Informazione 42
Compressione di ImmaginiAlgoritmi lossless (senza perdita di informazione) : operano un cambiamento di codifica dei dati che permette di diminuire il numero di bit necessari alla rappresentazione
– esempio : sequenza di 1 milione di caratteri, A=00, B=01, C=10, D=11, totale 2 milioni di bit di codifica
– se A compare il 90% delle volte posso ‘comprimere’ la codifica nel seguente modo A=0, B=100, C=110, D=111 ottenendo una lunghezza di :
900 000 * 1 + 100 000 * 3 = 1 200 000 bit
42
Corso Informatica 2 - Codifica Binaria dell'Informazione 43
Compressione di ImmaginiAlgoritmi lossy (che perdono informazione)
– generalmente sono specifici di un certo campo e sfruttano le caratteristiche degli oggetti da rappresentare per ‘buttare via’ informazione poco importanti
– gli algoritmi di compressione usati nei formati GIF e JPEG per immagini fisse 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
90%1%50%
43
Corso Informatica 2 - Codifica Binaria dell'Informazione 44
Codifica Immagini - VettorialiUn discorso a parte meritano le immagini vettoriali, usatissime nel campo della progettazione meccanica (CAD), architettonica, elettronica etc.
L’immagine, piuttosto che in punti, è scomposta in forme geometriche astratte come poligoni, cerchi etc.Per descrivere una circonferenza bastano ad es. posizione del centro e raggio.
Vantaggi: • indipendenza dalla risoluzione del
dispositivo di visualizzazione/stampa• dimensioni ridotte delle immagini• Indipendenza dalla forma • Scalabilità • Metafile
Svantaggi: • non applicabile in modo semplice a
fotografie e immagini complesse• Cartoon-like
44
Corso Informatica 2 - Codifica Binaria dell'Informazione 45
Immagini Vettoriali
• Documenti:– Postcript (ps, eps, epsi)– PDF (Portable Document Format)
• CAD 3D– AI (Adobe Illustrator)– CDR (CorelDRAW) – CMX (Corel Exchange) – CGM Computer Graphics Metafile – DXF AutoCAD – HPGL AutoCAD – WMF Windows Metafile
45
Corso Informatica 2 - Codifica Binaria dell'Informazione 46
Immagine tridimensionale vista da diverse prospettive ottenuta con un programma di CAD
Rendering
46
Corso Informatica 2 - Codifica Binaria dell'Informazione 47
47
Corso Informatica 2 - Codifica Binaria dell'Informazione 48
48
Codifica Audio
49
Corso Informatica 2 - Codifica Binaria dell'Informazione 50
Codifica AudioCaratteristiche dell’audio (e dei segnali analogici)
tempo
Segnale analogico - Continuità – nel tempo – nell’ampiezza
Segnale Digitale - Discretizzazione – nel tempo Campionamento– Nelle ampiezze (Quantizzazione)
50
Corso Informatica 2 - Codifica Binaria dell'Informazione 51
Codifica AudioCampionamento dell’audio ad intervalli di tempo fissi
tempo
51
Corso Informatica 2 - Codifica Binaria dell'Informazione 52
Codifica AudioCampionamento dell’audio ad intervalli di tempo fissi
tempo
Ogni campione vienerappresentato con un numero finito di bit (quantizzazione)
52
Corso Informatica 2 - Codifica Binaria dell'Informazione 53
Codifica Audio• Memorizzazione
Nbit=Durata • fc • bits/campione
• PlaybackRichiede un certo bit rate bit/sec
• Esempi Telefonia CD Audio
Segnale Voce Musica
Canali 1 (mono) 2 (stereo)
Banda 300 Hz-3.4 kHz 20 Hz-20 kHz
fc 8 kHz 44.1 kHz
bits/campione 8 16
Bitrate 64kbps 1.4 Mbps
53
Corso Informatica 2 - Codifica Binaria dell'Informazione 54
Codifica Audio - Formati
• PCM (Pulse Code Modulation)• WAV (Wave)• AAC (Advanced Audio Coding)• AIFF (Audio Interchange Format)• RA (RealAudio)• MP3 (MPEG-1 Layer 3) Codifica percettiva)
54
Corso Informatica 2 - Codifica Binaria dell'Informazione 55
Codifica Audio - MP3
• Non è un semplice algoritmo di compressione dati
• Codifica Percettiva basata sull’effetto mascheramento
• Qualità parametrizzata dal bitrate • Diffusissimo per l’alto fattore di compressione
120 mins = 700 Mbytes (WAV) = 50 Mbytes (mp3)
55
Codifica Filmati
56
Corso Informatica 2 - Codifica Binaria dell'Informazione 57
Codifica FilmatiTecnica di decodifica
– Campionamento di immagini (fps =frames per second)
– La persistenza sulla retina da la continuitàDimensioni tipiche
– Video signal: 25 frames per second => 60 MB/s– VHS video quality:
• 352x288 pixels per frame, 12 bits per pixel => 30.4 Mbits/s– Television quality: 704x576 pixels per frame,
• 12 bits per pixel =>121.7 Mbits/s
57
Corso Informatica 2 - Codifica Binaria dell'Informazione 58
Codifica Filmati
La compressione è d’obbligo su supporti digitali
Video CODEC
58
Corso Informatica 2 - Codifica Binaria dell'Informazione 59
Video compresso con tecnica intraframe
59
Corso Informatica 2 - Codifica Binaria dell'Informazione 60
Codifica Filmati - CODEC
• AVI (Audio Video Interleave)• MOV (QuickTime Format MacOSX)• WMV (Windows Media PLayer)• REALVideo (Real Network)• MPEG-1/2/3/4 (IEEE Standard)• XviD, DiVX, 3ivx
60
Corso Informatica 2 - Codifica Binaria dell'Informazione 61
ConclusioniLe tecniche di compressione dei dati, unite a studi di psicoacustica hanno permesso di realizzare rappresentazioni di filmati e di sequenze audio di dimensioni accettabili, dell’ordine di qualche MB. Questo ha aperto la strada all’utilizzo della multimedialità nell’informatica.
61