Sistemi di Elaborazione delle Informazioni Codifica delle...

Sistemi di Elaborazione delle Informazioni

Codi�ca delle informazioni

Tullio Facchinetti<[email protected]>

29 ottobre 2013

15:35

http://robot.unipv.it/toolleeo

Tullio Facchinetti <[email protected]> Sistemi di Elaborazione delle Informazioni Codi�ca delle informazioni

base binaria → rappresentazione dei numeri

codi�ca ASCII → da numeri a caratteri

codi�ca UNICODE → da numeri a caratteri (estesi)

digitalizzazione → rappresentazione mediante numeri diimmagini, suoni, testo �abbellito�


Evoluzione storica

la rappresentazione più semplice|||||| . . .

poco rappresentativa

di�coltà di memorizzazione

numeri romaniI, II, III, IV, V, V I, V II, V III, IX,X, . . .

1997→MCMXCV II

problemi di utilizzo nelle operazioni

di�coltà di rappresentazione di numeri �grandi�


Numerazione decimale

é detta numerazione in base 10

cifra 7 5 0 2

valore migliaia centinaia decine unitàpeso 103 102 101 100

7502 = 7 · 103 + 5 · 102 + 0 · 101 + 2 · 100

conteggio: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 → 0 con riporto


Rappresentazione di numeri interi

si sceglie una base β

si scelgono β simboli che rappresentano i numeri da 0 aβ − 1 (cifre)

i numeri sono rappresentati dai coe�cienti del polinomioper le potenze della base

si indica la base del sistema di numerazione con il pedice

(N)β = AsAs−1 . . . A1A0 0 ≤ Ai ≤ β − 1

valore(N) = Asβs +As−1β

s−1 + . . .+A1β1 +A0β

0

la rappresentazione è posizionale poiché il peso dellagenerica cifra Ai dipende dalla posizione di Ai


Numerazione binaria

rappresentazione inbase β = 2

conteggio:0, 1 → 0 con riporto10, 11 → 00 con riporto100, . . .

decimale binario0 01 12 103 114 1005 1016 1107 1118 10009 100110 1010


Numerazione binaria

interpretazione del valore del numero binario 1010111010

cifra 1 0 1 0 1 1 1 0 1 0

posizione 9 8 7 6 5 4 3 2 1 0peso 29 28 27 26 25 24 23 22 21 20

decimale 512 256 128 64 32 16 8 4 2 1

698 = 1 · 29 + 0 · 28 + 1 · 27 + 0 · 26 + 1 · 25+1 · 24 + 1 · 23 + 0 · 22 + 1 · 21 + 0 · 20 =

= 512 + 128 + 32 + 16 + 8 + 2


Operazioni binarie: somma e sottrazione

somma

+ 0 1

0 0 11 1 0/1

esempio

1 1 0 0 1 +1 1 0 1 =

1 0 0 1 1 0

di�erenza

- 0 1

0 0 1/11 1 0

esempio

1 1 0 0 1 -1 1 0 1 =

1 1 0 0


Operazioni binarie: moltiplicazione

moltiplicazione

· 0 1

0 0 01 0 1

esempio

1 1 0 0 1 x1 1 0 1 =

1 1 0 0 11 1 0 0 1 - -

1 1 0 0 1 - - -

1 0 1 0 0 0 1 0 1


Operazioni binarie: divisione

esempio

1 1 0 0 1 1 0 0 1

1 0 0 1 1

1 1 1 1 0


Sistema ottale

utilizza 8 cifre (o simboli)

simboli usati: 0, 1, 2, 3, 4, 5, 6, 7

interpretazione del valore del numero ottale 3715

cifra 3 7 1 5

posizione 3 2 1 0peso 83 82 81 80

decimale 512 64 8 1

3715 = 3 · 83 + 7 · 82 + 1 · 81 + 5 · 80 == 3 · 512 + 7 · 64 + 8 + 5 == 1536 + 448 + 8 + 5 = 1997


Sistema esadecimale

utilizza 16 cifre (o simboli)

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

interpretazione del valore del numero esadecimale 7CD

cifra 7 C D

posizione 2 1 0peso 162 161 160

decimale 256 16 1

7CD = 7 · 162 + 12 · 161 + 13 · 160 == 7 · 256 + 12 · 16 + 13 == 1792 + 192 + 13 = 1997


Esempi

base 2

(1010)2 = 23 + 2 = (10)10

(1100100)2 = 26 + 25 + 22 = (100)10

(1111101000)2 = 29 + 28 + 27 + 26 + 25 + 23 = (1000)10

base 8

(12)8 = 8 + 2 = (10)10

(144)8 = 82 + 4 · 8 + 4 = (100)10

(1750)8 = 83 + 7 · 82 + 5 · 8 = 512 + 448 + 40 = (1000)10

base 16

(A)16 = (10)10

(64)16 = 6 · 16 + 4 = (100)10

(3E8)16 = 3 · 162 + 14 · 16 + 8 = 768 + 224 + 8 = (1000)10


Numeri frazionari

con opportune rappresentazioni è possibile rappresentare inbase binaria numeri frazionari e numeri negativi

numeri frazionari:

vengono rappresentate separatamente la parte intera equella decimale

numeri negativi:

varie opzioni, la più semplice è �modulo e segno�si aggiunge ad un numero positivo un bit che indica se essoè positivo o negativonei computer però vengono usate altre tecniche(complemento a 1, complemento a 2)


Codi�ca di dati non numerici: de�nizioni

i calcolatori lavorano soltanto con i numeri

devono poter trattare anche altre entità

testoimmaginisuoni

per questa ragione sono stati inventati i codici


Alfabeto usato dai calcolatori

alfabeto

è un insieme �nito di simboli (caratteri) distinti

esempi:

U = {1} alfabeto unario

A = {0, 1} alfabeto binario

B = {A,B,C, . . . , Z} alfabeto inglese

C = {A,B, . . . , Z, 0, 1, . . . , 9} alfabeto alfanumerico

parola

è una successione �nita di caratteri di un alfabeto

1011001101 è una parola di A

SFSJKGH è una parola di B

SF120C è una parola di C


Alfabeto usato dai calcolatori

i calcolatori lavorano utilizzando due simboli:

interruttore: aperto/chiuso

transistor: conduce/non conduce

livello di tensione: alto/basso

ri�ettività di un'areola: alta/bassa

dominio di magnetizzazione: ↑ ↓


Alfabeti usati dall'uomo

{A,B,C,D, . . . , Z}{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}{ ; , . ! ? : ( ) ' � � . . . }

{ Caratteri giapponesi }

{ Caratteri arabi }

è necessario stabilire delle regole di corrispondenza, dettecodi�che

la codi�ca mette in corrispondenza biunivoca ogni simboloappartenente all'alfabeto più ricco con una stringa di simboli

appartenenti all'alfabeto più ridotto


Codi�ca

sia dato un insieme I di elementi qualsiasi

sia dato un alfabeto A

si dice codi�ca di I mediante parole di A un procedimento chepermette di stabilire una corrispondenza biunivoca tra glielementi di I e le parole di un sottoinsieme Q dell'insieme

delle parole di A

esempio: codi�ca di lettere tramite cifre decimaliA→ 01, B → 02, C → 03, D → 04, Z → 26


Codi�ca binaria

un codice binario è la codi�ca dei simboli di un alfabetoS mediante stringhe di bit

sia C è la cardinalità di S (n. di elementi)

sia n il numero di bit da utilizzare

allora deve valere C ≤ 2n, ossia:

n ≥ dlog2Ce =M

teorema

dati due alfabeti A = {a1, a2, . . . , ak}, B = {b1, b2, . . . , bh} conh, k > 1 è sempre possibile codi�care l'insieme delle parole di Amediante parole di B


Codice ASCII

è il codice più usato per la codi�ca dei caratteri alfanumerici(lettere e cifre) oltre che per simboli di interpunzione e vari

ad esempio:. ; : , ( ) [ ] { } / \ < > = ? ! ∼ | # $ % & * ∧ − @ ecc.


Codice ASCII: American Standard Code for Information Interchange

ne esistono due versioni

7 bit

128 simboli

in questo caso l'ottavo bit è usato a volte come ridondanza(H=2) per la rilevazione di un errore (bit di parità)

8 bit

256 simboli (ASCII esteso)

codi�ca anche lettere accentate e caratteri gra�ci

l'estensione non è standardizzata e quindi fra i 128 simboliaggiunti può succedere che alla stessa codi�cacorrispondano simboli diversi


Codice ASCII

Decimal Hex Char Decimal Hex Char Decimal Hex Char Decimal Hex Char

fonte Wikipedia


Codi�ca UNICODE

la codi�ca ASCII utilizza al più 7 bit

al massimo può rappresentare �solo� 27 = 128 simboli

nel 1968, anno della creazione, potevano essere su�cienti

la di�usione dell'informatica ha spinto la necessità diestendere l'insieme dei simboli da rappresentare

Codi�ca UNICODE

nata per utilizzare 16 bit e permettere di rappresentare216 = 65536 simboli di�erenti


Codi�ca UNICODE

standard nato nel 1991 per superare i limiti del codiceASCII

l'ultima versione dello standard supporta una codi�ca a 21bit

questo permette di rappresentare più di un milione disimboli di�erenti


Codi�ca UNICODE

sono rappresentati i caratteri di tutte le lingue più di�use almondo, incluso cinese e giapponese

le maggiori lingue antiche (es. greco) e morte (es. fenicio,runico, etrusco)

codi�cati simboli tecnici (es. chimica, musica, matematica)

i simboli attualmente assegnati sono poco più di 100.000

(dati aggiornati a settembre 2013)


Codi�ca delle immagini

in un calcolatore tutto è discreto

l'immagine è un insieme continuo di informazioni (luce,colore) in due dimensioni

quando si memorizzano immagini pittoriche o fotogra�chesi scompone arti�ciosamente l'immagine in una sequenza dielementi di informazione codi�cati con sequenze binarie


Codi�ca bitmap di immagini

l'immagine viene suddivisa in un reticolo di punti dettipixel (picture element)

ogni pixel viene codi�cato con una sequenza di bit

0 0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 0 00

0 0 0 0 0 0 0 0 0 0 0 0 0 00

1 1 1 1 1 1 1

1

1

1

1

1

1

la qualità dell'immagine dipende dal numero di pixelper unità di lunghezza e dal numero di bit utilizzati per

codi�care ogni pixel


Codi�ca bitmap di immagini

problema: non è possibileingrandire a piacimentoun'immagine perché non siaaumenta il dettaglio, ma sidistinguono i pixel

la soluzione di aumentare ilnumero di pixel non è possibileperché questo aumenterebbe lospazio necessario permemorizzare una immagine


Codi�ca dei pixel: immagini in bianco e nero

raramente si usa un solo bit

ogni pixel di solito si codi�ca con 8 bit per rappresentarediversi livelli di grigio (28 = 256 livelli)

8 bit � 256 livelli 2 bit � 4 livelli 1 bit � 2 livelli


Codi�ca dei pixel: immagini a colori

i colori vengono ottenuti tramite la combinazioni di almeno3 colori base, detti primari

la composizione può avvenire tramite la tecnica di sintesisottrattiva o additiva in funzione del tipo di dispositivoutilizzato (stampante, monitor o televisore)


Codi�ca dei pixel: immagini a colori

per codi�care un pixel si devono codi�care i tre coloriprimari, la cui combinazione consente di ottenere il coloredel pixel stesso

codi�ca RGB : (R)ed (G)reen (B)lue

per ciascun colore primario spesso si usano 8 bit e quindi intotale per codi�care ciascun pixel servono 24 bit

ciò consente di codi�care 224 ∼ 16 milioni di colori diversi

con il termine profondità di colore si intende il numero dibit utilizzati per codi�care i pixel

aumentando la profondità di colore:

aumenta il numero di sfumature rappresentabili

aumenta l'occumazione di memoria dell'immagine


Occupazione di memoria di un'immagine

l'occupazione di memoria di un'immagine dipende da:

de�nizione o risoluzione dell'immagine (intesa come ilnumero di pixel per unità di lunghezza: dot per inch =DPI)

numero dei colori (dipende a sua volta dal numero di bitusati per codi�carli: 8, 16, 24 bit)

tipo immagine de�nizione colori occupazione

televisiva 720× 650 256 (8 bit) ∼ 440 KBmonitor PC 1024× 768 65536 (16 bit) ∼ 1.5 MBfotogra�ca 15000× 10000 16.000.000 (24 bit) ∼ 430 MB


Formati di �le bitmap

TIFF (Tagged Image File Format)

profondità �no a 24 bit e vari metodi di compressione

GIF (Graphics Interchange Format)

consente di memorizzare più immagini in uno stesso �le

JPEG (Joint Photographers Expert Group)

formato standard che usa due tipi di compressione moltoutilizzato su Internet

prevede la tecnica di visualizzazione interallacciata(l'immagine viene composta per righe alterne per cui vienecaricata velocemente, ma diventa più nitida man mano cheviene completata)


Formati di �le bitmap

BMP (BitMaP)

usata con Windows supporta immagini con profondità 1, 4, 8 e24 bit

PNG (Portable Network Graphics)

creato per l'uso su Internet: adottato come formatostandard

nato a causa dell'imposizione di royalties sul formato GIF

visualizzazione progressiva dell'immagine medianteinterlacciamento

informazioni ausiliare di qualsiasi natura accluse al �le

immagini a colori �no a 48 bpp (bit per plane);

immagini in scala di grigio sino a 16 bpp;


Immagini vettoriali

si usa in applicazioni di progettazione meccanica,architettonica, elettronica

l'immagine viene costruita con elementi di alto livello qualilinee, cerchi, poligoni, archi, colori, ecc.

ogni oggetto è codi�cato attraverso un identi�catore (es.polyline, circle, etc.) e alcuni parametri quali le coordinatedel centro e la lunghezza del raggio (per la circonferenza) ole coordinate dei vertici (per il poligono)


Immagini vettoriali

al contrario delle immagini bitmap in cui l'elemento diinformazione è il pixel, in quelle vettoriali gli elementi

dell'immagine sono gli oggetti gra�ci che la compongono


Formato vettoriale per le immagini

vantaggi:

indipendenza dal dispositivo di visualizzazione e dalla suarisoluzione

gli elementi gra�ci sono indipendenti l'uno dall'altro e sipossono elaborare distintamente

minore occupazione di memoria rispetto alla gra�ca bitmap

svantaggi:

applicabilità limitata: un'immagine fotogra�ca non si puòscomporre in elementi primitivi


Formati di �le vettoriali

PostScript

incorporato in molte stampanti, si è evoluto nel tempo econsente di rappresentare immagini vettoriali e bitmapanche a colori con diverse tecniche di compressione

formati derivati del PostScript sono EPS e PDF

DXF (Drawing Interchange Format)

usato da molti programmi di disegno memorizza i vettori informato testo

la versione binaria DXB è più compatta ma meno di�usa


Formati di �le vettoriali

SVG (Standard Vector Graphics)

formato basato sul linguaggio derivato dall'XML

formato vettoriale standard per il Web

formato di �le aperto

supporto nativo da parte di molti browser

permette di gestire �gure dinamiche e interattive

un formato di �le aperto è un speci�ca pubblica per ladescrizione e l'archiviazione di dati digitali solitamente gestitada un ente di standardizzazione non proprietario e libera da

restrizioni legali per il suo utilizzo


Rappresentazione di immagini in movimento

immagini in movimento vengono rappresentate attraversosequenze di immagini �sse (frame) visualizzate ad unafrequenza su�cientemente alta da consentire all'occhioumano di ricostruire il movimento (24, 25 o 30 immagini alsecondo)

lo standard multimediale per le immagini in movimento,MPEG, codi�ca ciascun frame separatamente secondo lostandard JPEG

si utilizzano tecniche di compressione in quanto un minutodi �lmato a 25 fotogrammi al secondo richiederebbe unospazio di memorizzazione di 644 MByte (un CD contiene680 MByte)

alcuni tipici formati di �le video sono avi, mpg, 3gp, mp4,�v e mov, webm


Sistemi di Elaborazione delle Informazioni Codifica delle...

Documents

Transcript of Sistemi di Elaborazione delle Informazioni Codifica delle...