Appunti Fondamenri di Informartica teoria - sistemi di codifica

CODICE DI HAMMING

Codici ridondanti con H>2 e perciò non capacità di auto correzione.

Il più noto e semplice (H=3) prevede di inserire in un codice non ridondante dim bit r bit di controllo in particolari posizioni. Perché possa essere corretto un errore (singolo) deve valere: m≤ 2 – r – 1

Correggere un bit in posizione arbitraria:

• Rivela la presenza di un solo errore
• Funziona bene se gli errori sono distribuiti casualmente
• Esempio: parola di 7 bit (m=7)

Per creare un codice di Hamming con H=3 bisogna rispettare la relazione precedente e quindi usare 4 bit di controllo aggiuntivi (r = 4, m ≤ 11)

4 −4−1=11

m≤ 2 3 −3−1=5

m≤ 2

CODIFICA DELLE CIFRE DECIMALI

Vi sono diverse codifiche delle cifre decimali (0,1,.....,9)

Codice BCD (Binary Codad Decimal): ogni cifra decimale viene codificata con 4 bit. È un codice pesato perché il valore di ogni cifra viene ottenuto eseguendo una somma pesata delle

quattro cifre binarie che locompongono.CODIFICA DELLE CIFRE DECIMALISono tutti codici che lasciano 6 configurazioni inutilizzate delle 16 a disposizione con 4 bit;

Numeri negativi non possono essere codificati in BCD (il segno non ha un suo codice)

CODIFICA DI INFORMAZIONI ALFANUMERICHEPer convenzione, si definisce alfabeto esterno di un calcolatore come l'insieme dei caratteri che è in grado di leggere e stampare mediante idispositivi di I/O.

Questo alfabeto deve comprendere almeno 64 caratteri:

• Le 26 lettere dell'alfabeto inglese maiuscole (A..Z)
• Le 10 cifre decimali (0...9)
• 28 caratteri vari (spazio, segni di punteggia)

In genere si utilizzano codici a 7 o 8 bit

EBCDIC (Extended Binary Coded Decimal Interchange Code): 8 bit.

Rappresenta caratteri alfanumerici e speciali. Personalizzato per le varie nazionalità (necessita di conversioni e ormai obsoleto). Usato in numerosi sistemi operativi di produzione IBM. Deriva da un sistema di

Codifica a 6bit utilizzata nelle schede perforate.

UNICODE: rappresenta tutti i caratteri della lingua parlata dall'uomo, in maniera indipendente dalla lingua, dalla piattaforma informatica e dal programma utilizzato (usato da Java e adottato da HP, IBM, Microsoft, Oracle, ...). Era stato originariamente pensato come una codifica a 16 bit (quattro cifre esadecimali) che dava la possibilità di codificare 65.536 caratteri. Ora prevede una codifica a fino 21 bit e supporta un repertorio di codici numerici che possono rappresentare circa un milione di caratteri. È supportato dai moderni standard della programmazione e del markup come XML, JAVA, JavaScript, ecc., e da vari sistemi operativi.

CODICE ASCII

ASCII American Standard Code for Information Interchange.

o Ne esistono due versioni:

o 7 bit > 128 simboli; in questo caso l'ottavo bit è usato a volte come ridondanza (H=2) per la rivelazione di un errore (bit di parità);

8 bit > 256 simboli (ASCII)

esteso); codifica anche lettereè accentate e caratteri grafici; l'estensione non è standardizzatae quindi fra i 128 simboli aggiunti può succedere che allastessa codifica corrispondano simboli diversi.È il codice più usato per la codifica dei caratteri alfanumerici (lettere eo cifre) oltre che per simboli di interpunzione e vari. Ad esempio:. ; : , ( ) [ ]{ } / \ < > = ? ! ~ | # $ % & * ^ - @ ecc.

CARATTERI DI CONTROLLOUn carattere di controllo è un carattere non visualizzabile il cui codice in un set di caratteri non rappresenta in sé un simbolo scritto.Tutti i caratteri nella tavola ASCII con codice <32 fanno parte di questa categoria.Lo standard Unicode ha aggiunto molti nuovi caratteri non visualizzabili.I caratteri di controllo nella tavola ASCII ancora d'uso comune comprendono7 (bell), provoca l'emissione di un segnale sonoro da parte del terminale ricevente;8 (backspace), utilizzato per cancellare

• l'ultimo carattere visualizzato, di solito quello a immediatamente a sinistra del cursore;
• 9 (horizontal tab), tabulatore orizzontale;
• 10 (line feed), utilizzato per terminare le linee di testo nei sistemi UNIX e le loro varianti;
• 12 (form feed), per terminare la pagina sulla stampante e avanzare al modulo successivo;
• 13 (carriage return), ritorno a capo, utilizzato per terminare le linee di testo (ad esempio nel S.O. DOS);
• 27 (escape).

CODICE ASCII

IL MESSAGGIO “128”

IL MESSAGGIO “HELLO” IN ASCII

CODIFICA IMMAGINI

IMMAGINI ANALOGICHE

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

Analogico: continuo, naturale, rappresentato da segnali continui.

Un'immagine analogica è ottenuta su un medium sfruttando direttamente fenomeni fisici:

• Scena percepita dal nostro occhio;
• Immagine televisiva trasmessa attraverso monitor analogici;
• Immagine fotografica su pellicola;
• Disegni o pitture su tela, carta,

IMMAGINI DIGITALI

In un calcolatore tutto è discreto;

Una immagine viene rappresentata in un calcolatore come insieme di numeri interi che racchiudono informazioni cromatiche;

Quando si memorizzano immagini pittoriche o fotografiche si scompone artificiosamente l'immagine in una sequenza di elementi di informazione codificati con sequenze binarie (digitalizzazione).

CODIFICA BITMAP (O RASTER) DI IMMAGINI

L'immagine viene suddivisa in un reticolo di punti detti pixel (picture element);

Ogni pixel viene codificato con una sequenza di bit;

La qualità dell'immagine dipende da:

• numero di pixel per unità di lunghezza (risoluzione);
• numero di bit utilizzati per codificare ogni pixel (profondità di colore).

CODIFICA BITMAP DI IMMAGINI

Problema: non è possibile ingrandire a piacimento un'immagine perché non si aumenta il dettaglio, ma si distinguono i singoli pixel;

La soluzione è aumentare il numero di pixel.

È possibile perché questo aumenterebbe lo spazio necessario per memorizzare un'immagine (si compressione). Richiederebbe una codifica dei pixel. Immagini in bianco e nero: raramente si usa un solo bit. Ogni pixel di solito si codifica con 8 bit per rappresentare diversi livelli di grigio (2^8 = 256 livelli). Immagini a colori: i colori vengono ottenuti tramite le combinazioni di almeno 3 colori base, detti primari (Red Green Blue, RGB). La sottrattiva composizione può avvenire tramite la tecnica di sintesi o additiva in funzione del tipo di dispositivo utilizzato (stampante, monitor o televisore). Per codificare un pixel si devono codificare i tre colori primari (es. RGB), la cui combinazione consente di ottenere il colore del pixel stesso. Per ciascun colore primario spesso si usano 8 bit e quindi in totale per codificare ciascun pixel servono 24 bit. Ciò consente di codificare ~ 16 milioni di colori diversi; o numero di bit con profondità di colore si.Intende il utilizzati pero codificare i pixel. OCCUPAZIONE DI MEMORIA DI UN'IMMAGINE L'occupazione di memoria di un'immagine dipende da: - Definizione o risoluzione dell'immagine (intesa come il numero di pixel per unità di lunghezza: dot per inch = DPI); - Numero dei colori (dipende a sua volta dal numero di bit usati per codificarli: 8, 16, 24 bit). TECNICHE DI COMPRESSIONE A perdita di informazione (lossy): classe di algoritmi di compressione dati che porta alla perdita di parte dell'informazione originale durante la fase di compressione/decompressione dei dati che la rappresentano. In generale tendono a scartare le informazioni poco rilevanti, archiviando solo quelle essenziali (JPEG, MPEG, WMV); Senza perdita di informazione (lossless) è una classe di algoritmi di compressione dati che non porta alla perdita di parte dell'informazione originale durante la fase di compressione / decompressione dei dati che la rappresentano. (GIF, PNG, TIFF).

TIFF).COMPRESSIONE LOSSLESS: ESEMPIOPrendiamo ad esempio la seguente stringa di dati (48 caratteri):005555550055555500555555005555550055555500555555Algoritmo di compressione lossless Run-length encoding (RLE): "cifra- numerodi ripetizioni". Stringa compressa (24 caratteri):025602560256025602560256I dati non sono più direttamente disponibili ma occorre svolgere un passaggiointermedio (decompressione). La decompressione è solitamente molto piùfrequente della compressione, perciò molti algoritmi sono fortementeasimmetrici (il tempo richiesto per la compressione è sostanzialmentesuperiore a quello richiesto per la decompressione).

IMMAGINI BITMAP: LA PALETTEPer distinguere 16.777.216 colori sono necessari 24 bit per la codifica diciascun pixel: la codifica di un'immagine formata da 640X480 pixel richiede7.372.800 bit (921.600 byte).Un’immagine può occupare molto spazio anche se non tutti i 224 colori sonoCONTEMPORANEAMENTE

usati. Si può usare un sottoinsieme dei colori (tavolozza o palette) codificati con il sistema RGB. La palette è una lista di colori scelti nell'insieme di tutti quelli disponibili. Ogni colore della tavolozza è associato ad un indice, cioè ad un ordinale che identifica il colore nella tavolozza stessa.

La rappresentazione dei pixel di un'immagine attraverso indici nella tavolozza permette un drastico risparmio memoria e tempo computazionale rispetto ad altre tecniche, ma limita la gamma di colori utilizzabili a quelli presenti nella tavolozza.

Si associa ad ogni pixel un indice che individua una riga di una tabella contenente le triplette RGB dei colori utilizzati nell'immagine (palette).

Esempio:

Sono comuni palette a 256 colori, ciascuno dei quali può essere identificato da una sequenza di 8 bit.

Ciò consentirebbe di ottenere una immagine a profondità di colore di 8 bit, mentre ciascuno dei 256 colori può essere rappresentato

in RGB a 24 bit. La palette viene memorizzata insieme al resto dei dati dell'immagine. Occupazione di un'immagine 640X480; Sono necessari 8 bit per la codifica di ciascun pixel e 24 bit per ciascun colore della palette. La codifica richiederà 2.457.600 bit (307.200 byte) per immagine e 256*3=768 byte per la palette per un totale di 307.968 byte con un'occupazione di circa il 33%.

FORMATI DI FILE:

• BITMAP
• TIFF (Tagged Image File Format): Profondità fino a 24 bit e vari metodi di compressione
• GIF (Graphics Interchange Format): consente di memorizzare più