Corrispondenzabiunivoca Dati due alfabeti A e B, ad ogni simbolo o sequenza di simboli dellalfabeto...
-
Upload
santino-arcuri -
Category
Documents
-
view
213 -
download
0
Transcript of Corrispondenzabiunivoca Dati due alfabeti A e B, ad ogni simbolo o sequenza di simboli dellalfabeto...
Dati due alfabeti A e B, ad ogni simbolo o sequenza di simboli dell’alfabeto A si fa corrispondere (si associa) un simbolo o una sequenza di simboli dell’alfabeto B in modo che non si abbiano ambiguità, ossia la corrispondenzacorrispondenza sia biunivocabiunivoca.
• Corrispondenza biunivoca implica che esiste un modo per passare da un’informazione fornita nell’alfabeto A ad un’unica sequenza di simboli nell’alfabeto B, che fornisce la stessa informazione, e viceversa.
• La lunghezza delle stringhe corrispondenti dipende dalle cardinalità dei due alfabeti.
• Bisogna conoscere le regole che associano le due rappresentazioni della stessa informazione.
CodificheCodifiche
Insieme A = { insufficiente, sufficiente, buono, ottimo} Insieme B = {, , , }
insufficiente sufficiente buono ottimo
Insieme A = { insufficiente, sufficiente, buono, ottimo}Insieme B = { , }
insufficiente sufficiente buono ottimo
Il primo è un esempio di corrispondenza biunivoca, il secondo no: una sequenza di pallini grigi e rossi non può essere interpretata in modo univoco come sequenza di elementi di A.
Insieme A = { insufficiente, sufficiente, buono, ottimo}Insieme B = {0, 1}
insufficiente 00sufficiente 01 buono 10 ottimo 11
È importante poter tornare indietro in modo univoco, cioè poter decodificaredecodificare. Quando i simboli dell’alfabeto B sono in numero inferiore a quelli dell’alfabeto A, si usano per la codifica stringhe tutte della stessa lunghezza. Ciò assicura la possibilità di decodifica.
Insieme A = { insufficiente, sufficiente, buono, ottimo}Insieme B = { , }
insufficiente sufficiente buono ottimo
CodificheCodifiche
Se A ha m simboli e B n, con n < m, la minima lunghezza delle stringhe di simboli di B che permette di codificare i simboli di A èil minimo k tale che
nk m
Viceversa: Se B ha n simboli, le stringhe di lunghezza j permettono di codificare al massimo:
nj
simboli distinti, in quanto le sequenze distinte di lunghezza j sono proprio nj
Abbiamo a disposizione due soli simboli: 0 e 1.
Dobbiamo con essi codificare:• Caratteri• Numeri• Immagini• Suoni• Filmati
In ogni caso si ottengono sempre sequenze di 0 e 1: si deve sapere che cosa rappresentano per poter risalire all’informazione corretta.
Un’immagine:
001010000100001101001001010000010010111100101001
può rappresentare dei numeri:
40 67 73 65 47 41
oppure 10.307 18.753 12.053
o altro ancora ................
Una sequenza di caratteri: (CIAO)
Ad esempio, la sequenza:
Il codice ASCII(alcuni simboli)
ASCII Simb. ASCII Simb. ASCII Simb.
0101010 * 0111001 9 1000111 G
0101011 + 0111010 : 1001000 H
0101100 , 0111011 ; 1001001 I
0101101 - 0111100 < 1001010 J
0101110 . 0111101 = 1001011 K
0101111 / 0111110 > 1001100 L
0110000 0 0111111 ? 1001101 M
0110001 1 1000000 @ 1001110 N
0110010 2 1000001 A 1001111 O
0110011 3 1000010 B 1010000 P
0110100 4 1000011 C 1010001 Q
0110101 5 1000100 D 1010010 R
0110110 6 1000101 E 1010011 S
0111000 8 1000110 F 1010100 T
Codifica dei caratteriCodifica dei caratteri
Analogica: basata sulla similitudine tra il mezzo di rappresentazione e l'informazione rappresentata
Digitale: basata su una rappresentazione simbolica (discreta) dell'informazione
RappresentazioneRappresentazione
I segnali che forniscono suoni e immagini della realtà sono continui. Le variabili indipendenti (tempo e coordinate spaziali) variano con continuità e così pure i valori assunti.
Un segnale numerico o digitale si ottiene da quello analogico discretizzandodiscretizzando (cioè rappresentando con valori interi) le variabili indipendenti (tempo, spazio) e quantizzandoquantizzando i valori assunti.
Questa trasformazione è detta ADC, acronimo di Analogical to Digital Conversion
Il recupero del segnale analogico originale da quello numerico si ottiene con la riconversione DAC (Digital to Analogical Conversion).
Codifica delle immagini
Suddividiamo l’immagine mediante una griglia formata da righe orizzontali e verticali a distanza costante
Codifica delle immaginiPoiché una sequenza di bit è lineare, è necessario definire delle convenzioni per ordinare la griglia dei quadratini (pixel) in una sequenza. Assumiamo che i pixel siano ordinati dal basso verso l'alto e da sinistra verso destra
1 1
1 1 1 1
10
0
0
0
0 0 0 00
0 0
0
00
0 0
00
0
001 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
Con questa convenzione la rappresentazione della figura sarà data dalla stringa binaria
0000000 0111100 0110000 0100000
Codifica delle immagini
Non sempre il contorno della figura coincide con le linee della
griglia. Quella che si ottiene nella codifica è un'approssimazione
della figura originaria.
Se riconvertiamo la stringa 0000000011110001100000100000
in immagine otteniamo
Codifica delle immagini
La rappresentazione sarà più fedele all'aumentare del numero di pixel, ossia al diminuire delle dimensioni dei quadratini della griglia in cui è suddivisa l'immagine
zz
Risoluzione
Il numero di pixel in cui è suddivisa un’immagine si chiama risoluzione e si esprime con una coppia di numeri ad es. 640 480 pixel
(orizzontali per verticali)
Codifica delle immagini Assegnando un bit ad ogni pixel è possibile codificare solo
immagini senza livelli di chiaroscuro Per codificare le immagini con diversi livelli di grigio si usa la
stessa tecnica: per ogni pixel si stabilisce il livello medio di grigio cui viene assegnata convenzionalmente una rappresentazione binaria
Per memorizzare un pixel non è più sufficiente un solo bit. Ad esempio, se utilizziamo quattro bit possiamo rappresentare 24=16 livelli di grigio, mentre con otto bit ne possiamo distinguere 28=256, ecc.
Codifica delle immagini
Analogamente possiamo codificare le immagini a colori. In questo caso si tratta di individuare un certo numero di sfumature di colore differenti e di codificare ogni sfumatura mediante un'opportuna sequenza di bit
Ad esempio, i monitor utilizzano risoluzioni di 640X480, 1024X768, oppure 1280X1024 ed un numero di colori per pixel che va da 256 fino a sedici milioni di colori (un byte per ogni colore base: rosso, verde, blu nel sistema RGB)
La rappresentazione di un'immagine mediante la codifica
dei pixel, viene chiamata codifica bitmap e l’immagine
viene detta “discretizzata”.
Il numero di byte richiesti dipende dalla risoluzione e
dal numero di colori che ogni pixel può assumere.
Codifica delle immagini
Le immagini si possono anche ottenere mediante la
definizione di primitive grafiche quali linee, archi, poligoni,
cerchi, espresse analiticamente. Tali immagini vengono
dette vettoriali. Trovano applicazione nell’ambito del CAD.
Elaborazione dell’immagine
Una volta digitalizzate, le immagini possono essere elaborate facilmente
Elaborare un’immagine digitalizzata vuol dire applicare una trasformazione alla sequenza di bit che codifica l’immagine
Esempio: cambiare/neutralizzare il colore (Croma-key)
Le tecnologie di memorizzazione e trasmissione dei dati non offrono soluzioni efficienti ed economiche per gestire grandi quantità di dati.
Occorre applicare tecniche di compressionetecniche di compressione per ridurre lo spazio occupato. Tali tecniche sfruttano le regolarità delle immagini. compressione senza perdita di informazionecompressione senza perdita di informazione: si memorizzano pixel vicini identici una volta sola e si ricorda quante volte occorrono nell’immagine compressione con perdita di informazionecompressione con perdita di informazione: non si memorizzano tutti i pixel, ma solo una frazione di essi. Si usano funzioni matematiche di interpolazione per ricostruire i pixel mancanti
La tecnica è completamente reversibile e restituisce in fase di decompressione i dati originali.
Il fattore di compressione non è molto elevato (da 2 a 5 a seconda del tipo di dati).
E’ adatta per dati testuali, sonori, eidetici.
Compressione lossless
Compressione lossy Sopprime in modo irreversibile la parte di
informazione meno significativa, permettendo così, in fase di decompressione, la ricostruzione dei dati in modo ancora intelligibile.
Permette di ottenere fattori compressione dell’ordine di 10, 100.
Non è adatta per dati testuali.
Formati standard
GIF (Graphic Interchange Format) utilizza 8 bit per pixel e quindi distingue 256 colori. Usa una tecnica di compressione senza perdita
JPEG (Joint Photographic Expert Group) utilizza 24 bit, quindi 16,8 milioni di colori. Usa una tecnica sofisticata di compressione con perdita.
Altri formati PICT e TIFF
JPEG
Coded image: compr. 50:1 Original image Coded image: compr. 10:1
Immagini in movimento Memorizzazione mediante sequenze di fotogrammi La qualità della memorizzazione dipende dal numero
di fotogrammi al secondo Esempio: le immagini televisive vengono trasmesse
con 25/30 fotogrammi al secondo, con una risoluzione di 576720, con colori codificati a 16 bit.
Problema dell’occupazione di spazio: per ottimizzare lo spazio non si memorizzano tutti i fotogrammi.
I fotogrammi variano in modo continuo: si memorizza un primo fotogramma in modo completo, e per i successivi N solo le differenze con il primo.
Formati standard di compressione dei filmati
MPEG: memorizza in modo completo solo un fotogramma ogni 12, degli altri solo le differenze
AVI: (Microsoft) QuickTime: (Apple e Microsoft)
Codifica dei suoni Dal punto di vista fisico un suono è un'alterazione della
pressione dell'aria che, quando rilevata, ad esempio dall'orecchio umano, viene trasformata in un particolare stimolo al cervello.
Mediante un microfono queste alterazioni vengono trasformate in un particolare stimolo elettrico
La durata, l'intensità e la variazione nel tempo della pressione dell'aria sono le quantità fisiche che rendono un suono diverso da ogni altro
Codifica dei suoni
L'onda di pressione può essere rappresentata sul piano cartesiano rappresentando il tempo sull'asse delle ascisse e la pressione sull'asse delle ordinate.
t
p
Questa rappresentazione, analogica, fornisce una
descrizione continua dell'onda sonora
Per rappresentare in forma digitale (numerica) un’onda sonora, cioè per convertire un segnale continuo in una successione di numeri, si effettuano due successive operazioni elementari:
1. campionamento del segnale (cioè si preleva una
successione di campioni a intervalli costanti di tempo)
t
2. Ogni campione viene quantizzato ossia convertito in un numero (si codificano in forma digitale le informazioni estratte dai campionamenti)
Quanto più frequentemente il valore di intensità dell'onda
viene campionato, tanto più precisa sarà la sua
rappresentazione.
Il segnale può essere riprodotto perfettamente sulla base dei valori campione se la frequenza di campionamento èsuperiore al doppio della componente del segnale di frequenza più elevata.
Un errore viene comunque introdotto quando si converteil valore analogico di un campione in un numero con unnumero limitato di cifre.
Le frequenze sonore udibili dall’uomo sono comprese fra 20 Hz e 20.000 Hz (20 KHz)
La frequenza di campionamento per una corretta
rappresentazione dell’informazione sonora deve
essere allora maggiore di 40.000 Hz (40 KHz)
che nella pratica viene assunta di 44.1 KHz.
Compressione dei file audio
Il piu’ noto standard e’ MP3MP3 che permette di ottenere un fattore di compressione 12:1. Ad esempio un file campionato a 44,1 KHz con 16 bit per campione che occuperebbe circa 50 milioni di byte, compresso in formato MP3 ne occupa meno di 5 milioni, senza perdita di qualita’.
Trasmissione della voce sulla rete digitale ISDN:
Compact disk musicale:
curiosità
• Segnale vocale campionato ogni 125 milionesimi di secondo (8000 campioni al sec.); • Di solito vengono usati 8 bit per campione. • Sono trasmesse solo le componenti della voce di frequenza più bassa, come nella trasmissione analogica.
• Si mescolano due registrazioni (stereofonia);• 44.100 campioni al secondo per ogni registrazione; • 16 bit per campione. • Servono pertanto 1.411.200 bit per ogni secondo di registrazione.
8 milionidi bit
70 caratteri per riga 40 righe per pagina400 pagine circa
Libro giallo
Un milione di caratteri
1.000 x 1.000 pixel 256 livelli di grigio
125 sec. di voce o 5.6 sec.di musica ad alta fedeltà
1/30 di secondo di filmatoin bianco e nero ad alta risoluzione
Immagine in bianco e nero ad alta risoluzione