05-La codifica delle informazioni

{gspeech style=2}

Parafrasando la domanda postaci in precedenza, è ormai chiaro che i computer hanno “due dita”. Non sono molte, ma permettono di semplificare l’impostazione di molti problemi e soprattutto la rappresentazione dei numeri.

Anche se, per motivi fisici, qualsiasi configurazione di memoria del computer costituisce una sequenza binaria, è interpretabile numericamente solo quando la si vuole utilizzare per rappresentare i numeri interi. In qualsiasi altra circostanza, le rappresentazioni binarie in una certa locazione di memoria vanno interpretate a seconda dell’uso a cui è destinata quella locazione. In altre parole, poiché la memoria è comunque solo una successione di “0” e di “1”, la rappresentazione di lettere dell’alfabeto, di ideogrammi cinesi o di qualunque altro tipo di informazione non numerica dovrà passare attraverso una codifica.

C’è anche un’altra serie di considerazioni che interessano nell’operazione di codifica. Un conto è rappresentare del testo in chiaro da spedire con la posta elettronica e ben altro conto è il trasmettere dell’informazione segreta cifrata con qualche strano meccanismo. Nel secondo caso si deve fare in modo che il testo codificato sia leggibile solo possedendo un’opportuna chiave di lettura.
Riassumendo:

Il processo di codifica trasforma l’informazione al suo ingresso in modo da rappresentarla in maniera adatta alla tecnologia usata, tenendo conto di vincoli di riservatezza o sicurezza oltre a considerazioni di efficienza rispetto ad opportuni criteri di valutazione.

La ricostruzione dell’informazione originaria si chiama operazione di decodifica. Idealmente la doppia trasformazione di codifica con la successiva decodifica dovrebbe permettere di ricostruire con fedeltà l’informazione originaria. Non è detto che ciò avvenga. Si distinguono tecniche lossy e lossless. Una tecnica di codifica è lossy quando c’è perdita di informazione tra rappresentazione originaria, quella codificata e dunque quella ricostruita. Viceversa si parla di tecniche lossless se la versione codificata e quindi la sua ricostruzione è una replica fedele dell’originale. In caso di codifiche lossy è necessario che la perdita sia trascurabile o comunque accettabile.
In generale oltre alla fedeltà rappresentativa si richiede alle tecniche di codifica di permettere di conservare lo stesso tipo di manipolabilità dell’informazione che si ha nel mondo reale almeno per le applicazioni in cui la uso. Una rappresentazione numerica che non permette di fare somme con gli stessi risultati che si ottengono con carta e penna non può servire per far calcoli numerici. Potrebbe permettermi di gestire i numeri delle carte di credito risultando magari in ciò più efficiente di un’altra.
Possiamo, estendendo questo esempio, introdurre il concetto di efficacia di una rappresentazione dell’informazione. Pensiamo ai codici cifrati; è un caso in cui il codice segreto dovrà essere difficilmente scopribile, se non addirittura inviolabile. In questo caso l’efficacia è cruciale. Ma anche nel caso di codici rivelatori o correttori di errore, l’efficacia è un parametro fondamentale.
Nel diagramma di figura è indicato come le considerazioni sulle codifiche si applichino in generale anche ai sistemi di comunicazioni digitali (telefonia fissa, telefonia mobile, Tv satellitari sono solo alcuni esempi). In generale si parla di sistema telematico quando si accoppia l’elaborazione dei dati con la trasmissione a distanza (il Bancomat, Internet, la teleprenotazione, il collegamento tra una filiale e la sede centrale di un’azienda, il telelavoro, ecc.).

Le codifiche numeriche
Come primo problema reale di codifica cerchiamo di superare i limiti connessi alle rappresentazioni di numeri reali in binario. In particolare osserviamo come numeri che hanno rappresentazione finita in decimale, quando vengono trasformati in binario avrebbero bisogno di infinite cifre. Se si prova a convertire 0,2 in binario si ottiene un numero periodico: 0,2₁₀= 0,0011₂. Non si può con numeri reali garantire la stessa precisione di calcolo nei due sistemi. È ben vero che in alcuni casi 0,2 + 0,2 = 0,399 può anche andar bene, però se si tratta di milioni di dollari la questione è ben più delicata. La soluzione si trova introducendo la codifica BCD (Bynary Coded Decimal). Semplicemente si rappresentano le cifre di un generico numero decimale con le corrispondenti configurazioni a 4 bit binarie. Si scelgono 4 bit perché si devono rappresentare 10 diverse entità e vale la disequazione: 23 < 10 < 24. Inoltre le configurazioni usano tutti i quattro bit perché per ogni cifra occorre avere stessa quantità di memoria.

Decimale	0	1	2	3	4	5	6	7	8	9
BCD	0000	0001	0010	0011	0100	0101	0110	0111	1000	1001

Avremo dunque: 146 = 0001 | 0100 | 0110, 352 = 0011 | 0101 | 0001.
Vediamo come poter effettuare somme in BCD:

–si convertono i due numeri da sommare;
–si prova ad effettuare una semplice somma binaria;

Ci si accorgerà che ciò in alcuni casi funziona, in altri no.

ESEMPIO
Caso 1
Cominciamo con la seguente somma in decimale: 236 + 151 = 387

236=0010|0011|0100
151=0001|0101|0001

Si incolonnano e sommano le rappresentazioni binarie. Il tutto funziona correttamente:

	111
0010	0011	0100	236
0001	0101	0001	151
0011	1000	0101
3	8	7

Caso 2
Sommare 195 + 427 = 622
Nascono dei problemi: infatti, incolonnando si ottiene:

0001	1001	0101	195
0100	0010	0111	427
0101	1011	1100
5	?	?

Il risultato contiene dei punti di domanda, cioè configurazioni fuori dal codice. Infatti se si cerca in tabella 1100 non si trova. Esso corrisponde al 12 binario che, in modo del tutto logico, abbiamo ottenuto sommando 5 e 7.

Proviamo a fare uno strano gioco. Sotto ai due caratteri con il ? sommiamo un 0110 (6 BCD).

11	1111	1
0101	1011	1100
	0110	0110
0110	0010	0010
6	2	2

Abbiamo risolto i nostri problemi. Pare che miracolosamente aggiungere 6 ci abbia portato in salvo. Cerchiamo di capire cosa si nasconde dietro ciò. Quando si somma in decimale si conta fino al nove al massimo e poi si genera un riporto. Il riporto in binario a quattro cifre viene generato al superamento del quindici. La distanza in termini numerici tra il 9 ed il 15 è proprio 6. Allora 9 + 4 = 3 riporto 1 in binario diventa 9 + 4 = 13. Superando il 9 come risultato si deve, per generare correttamente il riporto, sommare 6 al 9 per potere ripristinare il conteggio da 0. 9 + 6 + 4 = 19 cioè 16 (il riporto di uno) + 3 il risultato. Quindi abbiamo scoperto che quando una configurazione del risultato è fuori dal codice basterà sommargli 6 per ottenere il risultato corretto. C’è ancora un’insidia. Consideriamo un terzo esempio.

Caso 3
Ancora problemi: 198 + 278 = 476. Incolonnando si ottiene:

111	1111
0001	1001	1000	198
0010	0111	1000	278
0100	0001	0000
4	1	0

Notate che stavolta tutte le configurazioni sono entro il codice. Il problema è che sommando ad esempio 8 + 8 nella prima cifra abbiamo 16 cioè nell’aritmetica esadecimale 0 con il riporto di 1 e non 6 con il riporto di 1 come è corretto in decimale. I riporti sottolineati indicano proprio la presenza di una situazione di errore anche se le cifre sono interpretabili nel codice. Per porvi rimedio basta ancora una volta sommare 6 alle cifre il cui calcolo ha generato un riporto sul primo bit della prossima cifra.
Infatti:

0100	0001	0000
	0110	0110
0110	0111	0110
4	7	6

Analoghe regole di correzione possono essere pensate per le differenze e comunque come sappiamo le differenze possono essere ricondotte a somme tramite i complementi. L’uso del BCD è talmente diffuso, che i microprocessori contengono, come istruzioni elementari in linguaggio macchina, la correzione del risultato per operazioni BCD.

IL CODICE GRAY (O RIFLESSO)
Il codice Gray è definito anche codice riflesso a causa del particolare modo in cui viene costruito.
In Figura riportiamo alcune fasi del procedimento usato per costruire il codice Gray.
Si scrive inizialmente una coppia 0-1 in verticale e si riflette verticalmente (a). Si completa aggiungendo a sinistra due bit 0 alle prime due righe e due bit 1 alle ultime 2 (b).Si riflette di nuovo, ottenendo otto righe, che vengono completate aggiungendo a sinistra quattro bit 0 alle prime 4 e quattro bit 1 alle ultime 4 (c), dopodiché si effettua l’ultima riflessione.
Il risultato finale è rappresentato in Tabella.
Il codice Gray ha una particolare caratteristica: nel passaggio da un numero al successivo cambia un solo bit. In certe applicazioni, pensiamo soprattutto ai sistemi di controllo e di trasmissione dati questo fatto rappresenta un notevole vantaggio perché riduce molto la possibilità di errore.

I codici correttori e rivelatori di errore
Una problematica che va affrontata quando si tratta di codificare informazione che deve essere trasmessa a distanza in modo affidabile, è la gestione degli errori. Per quanto la tecnologia usata sia affidabile, può sempre succedere che per disturbi, interferenze elettro-magnetiche o malfunzionamenti di qualsiasi genere, l’informazione venga alterata. In altri termini qualcosa che è partito come 0 è arrivato come 1 o viceversa.
Esistono delle tecniche delle quali qui daremo un breve cenno che permettono almeno di scoprire se ci sono stati errori ed in alcuni casi correggerli.

Esempio
Si vuole trasmettere un messaggio numerico codificato con il codice BCD. Si parte dall’ipotesi che la probabilità che avvenga un errore sia sufficientemente bassa da ritenere che al massimo ce ne possa essere uno ogni quattro bit. Supponiamo di trasmettere la cifra BCD 7 ed aggiungiamo un bit in coda alla sua codifica secondo la seguente regola:

facciamo in modo che il numero di 1 presenti tra i cinque bit che si trasmettono sia dispari.

Cioè 7 = 0111 allora si aggiunge uno 0 in modo che nella cinquina 01110 si abbiano tre 1, cioè un numero dispari. In ricezione supponiamo sia giunto il messaggio 01010.

È cambiato a causa di un disturbo sulla linea elettrica il valore di un bit. Chi riceve (si tenga presente l’ipotesi di un solo possibile errore nei cinque bit), si accorge dell’errore perché adesso il numero di 1 presenti nella cinquina non è più dispari. Riflettete sul fatto che con un errore o un 1 diventa zero o uno zero diventa 1, in ogni caso il numero totale di 1 varia di un unità passando da pari a dispari e quindi non torna più il conteggio. Il ricevente chiederà la ritrasmissione del dato errato.

Questa tecnica si chiama tecnica del bit di parità dispari. Se avessimo fatto in modo che il numero di 1 debba essere pari avremmo parlato di parità pari. E indifferente che si scelga la parità pari piuttosto che quella dispari, la scelta deve però essere fissata nel nostro sistema una volta per tutte ed ovviamente nota sia al trasmettitore sia al ricevitore.

Vediamo un esempio di parità pari. Trasmetto 3 in BCD a parità pari. La codifica del 3 in quel codice è 0110 dunque anche in questo caso devo aggiungere uno 0 e trasmettere 01100. I codici a parità pari o dispari si chiamano codici rivelatori di errore, in quanto permettono solo di scoprire (rivelare) la presenza di un errore. La presenza di bit di parità genera uno spreco di memoria e di velocità di trasmissione, per cui può valere la pena cercare di capire ogni quanti bit mi convenga inserirne uno di parità. Ad esempio se si scopre che è bassissima la probabilità di 1 errore su 8 bit, invece di inserire un bit per ogni cifra del codice, se ne inserisce 1 ogni coppia. Ciò non potrà che essere frutto di un’analisi statistica delle caratteristiche del mezzo trasmissivo.

Modificando la tecnica del bit di parità si possono costruire anche codici correttori d’errore, cioè non solo in grado di scoprire se c’è un errore, ma anche di individuarne la posizione. In binario un errore è un 1 che diventa 0 o viceversa. A questo punto siamo a posto, basta cambiare il valore del bit che si sa essere errato. Vediamo un esempio di queste tecniche.

Consideriamo il controllo di parità longitudinale e trasversale. Partiamo dall’ipotesi che sia trascurabile la possibilità di più di un errore su 16 bit. Aggiungeremo dei bit di parità ad un blocco di 16 bit, quindi nel caso di trasmissione in codice numerico ogni quattro cifre. Facciamo l’ipotesi di trasmettere il numero 3682 in codice BCD. Si dispongono i bit da trasmettere secondo la tabella:

3	0	0	1	1	1
6	0	1	1	0	1
8	1	0	0	0	0
2	0	0	1	0	0
	0	0	0	0

Nelle caselle centrali sono state inserite le codifiche normali secondo il BCD delle cifre da trasmettere, nelle celle evidenziate sono stati inseriti i bit di parità di tipo dispari. I bit di parità a destra sono calcolati lungo le righe, quelli in basso lungo le colonne. Vediamo cosa succede in ricezione se si verifica un errore:

3	0	0	1	1	1
6	0	1	1	0	1
8	1	1	0	0	0
2	0	0	1	0	0
	0	0	0	0

Si è incappati in un errore. Lo zero al centro è diventato 1 come evidenziato dalla sottolineatura. Se però si fa in ricezione il controllo di parità si scoprirà che i conti non quadrano esattamente nella seconda colonna e nella terza riga al cui incrocio si trova proprio il bit errato. A questo punto lo possiamo correggere. Se solo una riga o una colonna presentano un valore di parità errato non può che essere il bit di parità ad essere cambiato.

?	0	1	1	1	1
6	0	1	1	0	1
?	1	1	1	0	0
2	0	0	1	0	0
	0	0	0	0

La codifica del testo
Oltre ai numeri i calcolatori elaborano ovviamente anche i testi. Vediamo come. Per la codifica dei testi ha uso molto diffuso il cosiddetto codice ASCII. La sigla sta per American Standard Code for Information Interchange. Esso è definito da uno standard internazionale noto come standard ISO 646. L’ISO è l’International Standard Organization, un ente internazionale preposto alla definizione di norme omogenee in campo tecnico valide in tutto il mondo.

Una successiva standardizzazione ha definito versioni diverse per i cosiddetti codici ASCII estesi ad 8 bit (ISO 8859). In ognuno dei vari codici le prime 127 configurazioni coincidono con quelle del codice a sette bit, mentre le restanti variano a seconda dei vari gruppi di alfabeti disponibili nel mondo. Non tutte le lingue vi sono comprese, in particolare le lingue basate su ideogrammi (cinese, giapponese e coreano). Notiamo che i primi 32 caratteri ASCII non hanno corrispondente visuale a schermo o in stampa ma sono caratteri di controllo usati per le telecomunicazioni o per rappresentare alcuni particolari simboli. Ad esempio i caratteri di tabulazione (HT), l’invio (CR), il salto pagina (NP), lo spazio bianco (SP).
Nel 1993 è stato definito un nuovo standard che promette di sostituire nel tempo l’ASCII esteso. Si tratta dell’UNICODE. È una codifica a 16 bit, quindi con 2¹⁶, cioè più di 64.000 possibilità. Le prime 256 combinazioni corrispondono all’ASCII esteso dell’Europa Occidentale e dell’America. Con il resto vengono codificati gli altri simboli necessari agli altri ASCII, simboli matematici, più di ventimila ideogrammi ed altro ancora.

Sulla codifica e la rappresentazione del testo ci sarebbe ancora da dire parecchio. Accenniamo brevemente ad alcune questioni.

se ci sono solo 256 codici come si fa ad avere 50 diverse forme tipografiche (Font) installate su di un computer per ognuno di quei singoli codici?
in che cosa, al di là di un gusto estetico personale, si differenziano i vari font? Perché i font di caratteri a disposizione negli editor Web o nei programmi di videoscrittura soprattutto a grandi dimensioni appaiono con lettere fortemente irregolari con una evidente seghettatura ai bordi? Perché poi stampati assumono forma molto più regolare?

Sono problematiche relative alla rappresentazione del testo da un punto di vista tipografico. Possiamo parlare comunque, almeno in senso lato, di codifica in quanto abbiamo a che fare con la medesima informazione veicolata in modi diversi a seconda delle diverse circostanze in cui deve essere utilizzata. Si tratta dunque di diverse codifiche grafiche.

Cominciamo con il primo punto. Quando specifichiamo un font stabiliamo una corrispondenza tra ciò che scriviamo ed il particolare contenuto di un file. Il codice per il carattere è sempre ASCII esteso, ma prima della visualizzazione o della stampa si va a prendere la corrispondente rappresentazione grafica nel file. I driver delle stampanti e dei monitor si occupano di fare ciò eseguendo gli ordini di Word il quale da parte sua si ricorderà con suoi codici interni di ripartire lo stesso ordine ogniqualvolta si riaprirà quel documento.

Per la seconda domanda introduciamo dei criteri di classificazione per i vari tipi di font. Una prima distinzione si ha tra i caratteri con «grazie» o serif e «senza grazie» o sans serif.

T T

la prima T è un Arial 36, ed è un carattere sans serif, cioè senza decorazioni ai bordi delle lettere. Il secondo è un Times New Roman sempre 36 ed è un carattere serif.
Le dimensioni geometriche a parità di punti dei due caratteri sono diverse. Aspettatevi che scrivendo un documento e poi modificandone il font si possa spaginare. Una tabella che prima stava in una pagina magari adesso si divide su due. L’aspetto più bello dei caratteri serif lo si nota solo alle grandi dimensioni; a piccole dimensioni, i caratteri sans serif sono più leggibili, almeno a video.

L’altra distinzione che permette di classificare i font in due grandi famiglie è tra caratteri a spaziatura fissa monospaced e variabile. Un carattere monospaced (a spaziatura fissa) è per esempio il Courier, in cui ogni lettera occupa lo stesso spazio e le lettere non si addossano, cosa che invece succede con l’Arial o col Times New Roman che riservano diverso spazio alle lettere.

Un’altra questione riguarda il cosiddetto aliasing. Si tratta di quel particolare effetto per cui i bordi dei caratteri appaiono seghettati soprattutto a grandi dimensioni. Visto che è possibile produrre caratteri con il filtro anti alias, cioè in cui l’effetto viene compensato, vien da chiedersi come mai ci siano font in cui ciò non è fatto.

I CODICI A BARRE
Una recente applicazione, soprattutto commerciale, dei codici a base binaria è rappresentata dai codici a barre. Il concetto base dei codici a barre è costituito dalla rappresentazione dei bit 0 e 1 tramite barre chiare e scure di spessore differente. Esistono diversi codici a barre, differenti nelle modalità di codifica ma sostanzialmente equivalenti rispetto al concetto base. L’uso dei codici a barre semplifica molto il lavoro dell’operatore, che si limita a “passare” l’etichetta contenente la codifica tramite una penna ottica o un lettore laser, riducendo così i tempi di lavoro e le possibilità di errore. Per il momento l’uso dei codici a barre è soprattutto diffuso nel settore del commercio (etichette dei prodotti) ma sicuramente questa tecnica di codifica troverà in futuro applicazioni sempre più ampie. Basti pensare, per esempio, ai vantaggi offerti da una codifica a barre nel caso di gestione di un magazzino aziendale o di cicli di lavorazione. L’addetto, invece di digitare su una tastiera le specifiche del prodotto o le richieste del ciclo di lavorazione, può usare una semplice penna ottica da passare su una o più serie di “istruzioni” prestampate e codificate a barre per archiviare un articolo o dettare comandi ad una macchina utensile.

ESEMPI DI CODICI A BARRE

Il codice 39
È un codice di tipo alfanumerico e permette di codificare fino a 39 caratteri. In particolare, il codice 39 prevede la codifica delle cifre decimali, delle lettere dell’alfabeto inglese (senza distinguere fra maiuscole e minuscole) e di alcuni caratteri speciali (%, $, +, -, ., eccetera).
II codice 39 utilizza, per la codifica, tanto le barre (nere) quanto gli spazi fra le barre (bianchi). In particolare, barre o spazi stretti corrispondono allo 0, barre o spazi larghi corrispondono all’1.
Riportiamo di seguito, la tabella riassuntiva del codice 39.
Si può vedere che ciascun simbolo è rappresentato da 5 barre e 4 spazi, per complessivi 9 bit. E inteso che barre e spazi sono da considerarsi alternati fra di loro (barra/spazio/barra/…). Per esempio, la lettera “K” è rappresentata (vedi tabella) dalle successioni 10001 (barre) e 0001 (spazi) e pertanto avrà l’aspetto riportato in figura destra.

II codice MSI
È uno dei più semplici, in quanto utilizza solo 4 bit e distingue lo 0 dall’1 solo per lo spessore della barra e dello spazio successivo.
Una barra sottile seguita da uno spazio largo rappresenta lo 0, mentre una barra larga seguita da uno spazio sottile rappresenta l’1.
Utilizzando un numero così piccolo di bit, il codice MSI è esclusivamente numerico. In particolare, esso è usato per la codifica dei quattro bit del codice BCD. Per esempio, il numero 5 (codice BCD 0101), nella rappresentazione a barre secondo il codice MSI diventa come in figura a destra.

Le tecniche di compressione
Finora abbiamo considerato come codificare i numeri sia in binario, sia con opportuni codici adatti ad esigenze specifiche, come codificare il testo e come affrontare il problema della gestione di eventuali errori. Per inciso si noti che le tecniche di rivelazione e correzione degli errori, basandosi sulla pura forma binaria dell’informazione, si applicano a qualsiasi flusso di bit siano essi numeri, testo, immagini od altro. Occupiamoci di un altro problema importante che è il risparmio di memoria o di tempo di trasmissione. In altri termini si vuole rappresentare una determinata informazione usando il minor numero possibile di bit.

Il nostro mostro è rappresentato su una griglia di 13 x 11 punti. Supponendo di rappresentare il disegno specificando il colore punto per punto, ipotizzando una tavolozza a 16 colori, occorrerebbero 4 bit per il colore di ogni punto, il tutto per 141 volte per un totale di 564 bit. Consideriamo ora una tecnica di codifica che farà risparmiare memoria. Ogni riga ha 13 punti; il numero 13 ha bisogno di 4 bit per essere rappresentato, teniamolo presente perché ci servirà nei conti che seguono. La prima riga è costituita da 6 caselle bianche, 1 nera e 6 bianche. Invece che codificare il colore di ogni singola casella possiamo pensare la seguente rappresentazione:

6 codice del bianco; 1 codice del nero;
6 codice del bianco.
Invece di usare 13 x 4 = 52 bit uso 4 + 4 + 4 + 4 + 4 + 4 = 24 bit. La sequenza di quattro è dovuta al fatto che per codificare il numero di volte che un colore si ripete su una riga abbiamo bisogno di 4 bit (al massimo si può ripetere 13 volte) ed il secondo quattro è dovuto alla codifica del colore. Se si vogliono fare i conti, si verifica che il mostro è rappresentabile in questo modo con 504 bit, con un risparmio netto di 60 bit. Se la tavolozza fosse di 256 colori si può calcolare che il risparmio con questa tecnica è ancor più elevato, 756 contro 1128 bit nella codifica punto per punto.
Il metodo appena visto si chiama codifica run-length e sfrutta ovviamente il fatto che alcuni tipi di informazioni presentano parecchie ripetizioni consecutive dello stesso dato. Ciò può andar bene per le immagini, non di tutti i tipi, però per il testo non sembra una tecnica ottimale. Per quanto riguarda i file di testo possono però valere altre considerazioni. Possiamo fare il seguente ragionamento. Prendiamo una pagina a caso della «Divina Commedia» e contiamo quante w, quante z, quante k, quante a e quante e vi compaiono. Oppure quante maiuscole. Chiaramente il limite del codice ASCII, in queste situazioni, è che prevede 8 bit anche per quei caratteri che compaiono poche volte o non compaiono mai nel testo da rappresentare. Ciò avviene perché l’ASCII è un codice a lunghezza fissa in cui, cioè, ogni simbolo viene rappresentato con lo stesso numero di bit. Se inventassimo un codice che usa un bit per la a, 3 per la e, 300 per la w, 200 per la x e così via, si userebbero più o meno bit per rappresentare la pagina della Divina Commedia? La risposta è ovvia. Il problema sta nell’inventare il codice.
In questo modo introduciamo il concetto di codice a lunghezza variabile, cioè di codice nel quale i simboli vengono rappresentati con diverso numero di bit. La definizione di un codice a lunghezza variabile avviene tramite un’opportuna struttura che si chiama albero binario. Lo si può osservare nella figura. È un particolare tipo di diagramma adatto a rappresentare un albero genealogico. Si ha un’origine (radice) da cui si diramano dei tratti di collegamento a degli elementi figli (nodi) che a loro volta possono avere dei figli. E così via. Quei nodi che non hanno figli si chiamano foglie. L’albero si chiama binario perché ogni nodo può avere al massimo due figli. I codici a lunghezza variabile vengono costruiti associando ai simboli da codificare le foglie di un albero binario. Si stabilisce una regola per interpretare la struttura dell’albero molto semplice.

Si consideri il cammino che dalla radice porta ad una foglia (esso è univoco). Ogni volta che si percorre un ramo verso destra si aggiunge un 1, quando si va a sinistra si aggiunge uno 0. Chiaramente si può fissare la regola contraria, basta solo sceglierne una, una volta per tutte. Quando si arriva ad una foglia mettendo uno dietro l’altro i bit così ottenuti, si è costruita la codifica dell’elemento sottostante la foglia. Si osservi la figura e si capirà come la codifica della lettera f nel nostro caso sia 01010. Si verifichi che la a corrisponde ad 1, la e a 00, la c a 0100, la n a 01011, la d a 0110 e la i a 0111.
Ovviamente la codifica sarà vantaggiosa nel momento in cui nel testo rappresentato con il codice così definito, la a e la e compaiono molte più volte delle altre lettere. Una osservazione importante da fare è che, nel codificare le lettere, non c’è possibilità di confusione. Cioè, dato che la a è rappresentata da un 1, nessun’altra codifica inizia con 1. Dato che la e è 00, si verifica che nessun’altra codifica inizia con la sequenza 00 e così via. In questo modo risulta possibile ricostruire univocamente qualsiasi messaggio redatto usando quel codice. Quando si trasmette un’informazione codificata con un codice a lunghezza variabile dovrà essere recapitato anche l’albero che farà da chiave di lettura per ricostruire il messaggio originario. Si pensi ad un programma di compressione dei dati, WinZip, per citarne uno, esso opera proprio nel modo visto sopra, crea un codice a lunghezza variabile, memorizza in testa al documento da comprimere l’informazione necessaria per ricostruire il documento originale e poi trasforma il documento nella forma compressa.

Le tecniche crittografiche
Passiamo ora a considerare un’altro settore importante delle tecniche di codifica che fanno riferimento ad un’unica area che va sotto il nome di crittologia. Essa entra in gioco nel momento in cui si vuole comunicare dell’informazione mantenendola segreta per coloro che non hanno opportune autorizzazioni. Si divide in due branche: la crittografia (letteralmente scrittura nascosta) e l’analisi cifrata. La prima si occupa della progettazione di sistemi per comunicazioni segrete, la seconda studia i modi per violare i messaggi cifrati. Nascono entrambe in ambito militare, ma oggigiorno con le transazioni economiche in rete hanno applicazione molto comune.
Lo scenario è illustrato in figura.
Il mittente spedisce il messaggio in chiaro, dopo averlo trasformato opportunamente con un metodo di cifratura. La lettura del messaggio è possibile solo se si ha a disposizione una particolare chiave che deve essere trasmessa separatamente dal testo cifrato. Usando la chiave si ricostruisce il messaggio originario. In mezzo c’è potenzialmente il pirata, ovvero l’analista che in maniera fraudolenta, o magari no, se si stanno facendo dei test sull’affidabilità del metodo, cerca di ricostruire il messaggio in chiaro anche senza la chiave.
I requisiti principali di tale tecnica sono:

ragionevole efficienza nella creazione del messaggio;
estrema difficoltà nella interpretazione del messaggio da parte di chi non è autorizzato;
possibilità di cambiare con estrema rapidità il metodo usato.

Consideriamo adesso alcuni semplici metodi di cifratura.
Il più semplice ed anche uno dei più antichi è il cifrario di Cesare. Ad ogni lettera del messaggio in chiaro si sostituisce la lettera che sta dopo k posizioni rispetto all’originale nell’alfabeto. Giulio Cesare utilizzò k = 3. k diventa la chiave. Ad esempio con k = 2 la trasformazione è la seguente:

alfabeto normale: messaggio in chiaro
codice di Cesare: oguuciimq mp elmctq

Si tratta di un metodo ovviamente debole, bastano infatti 21 tentativi per poter decifrare il messaggio. Una tecnica decisamente migliore consiste nel definire una tabella di corrispondenza che associa ad ogni lettera la sostituta. Consideriamo il seguente caso:

alfabeto originario: ABCDEFGHILMNOPQRSTUVZ
alfabeto cifrato: ZCVBNMLHGFDSAQERTUIOP

usando l’alfabeto modificato otteniamo la seguente cifratura:

alfabeto normale: messaggio in chiaro
alfabeto cifrato: dnttzllga gs vhgzra

Metodi di questo tipo, detti a sostituzione semplice, sono comunque scarsamente sicuri pur essendo molto più potenti del cifrario di Cesare. Infatti basandosi sulla frequenza delle lettere nella lingua in cui è redatto il messaggio in chiaro, tenendo conto anche delle combinazioni di due lettere (digrammi) più frequenti e di quelli impossibili, è possibile rompere lo schema di codifica in tempo ragionevolmente breve. Un miglioramento per queste tecniche può essere eventualmente l’uso di più di una tabella di sostituzione oppure di chiavi di sostituzione opportune. Una semplice variante del cifrario di Cesare usa una tecnica di questo tipo. Si tratta del cifrario di Vigenere. Il valore di k da utilizzare per ogni lettera del messaggio in chiaro è stabilito da una chiave ripetuta. Usiamo ad esempio la chiave ciao. Per noi c vale 3, i vale 9, a vale 1 e o vale 13. Il k della prima lettera del messaggio in chiaro è dunque 3, per la seconda 9, per la terza 1 e per la quarta 13, dalla quinta si ricomincia da capo. Con questa tecnica cifriamo il nostro solito messaggio così, tenendo conto che superato il 21 si ricomincia dalla a nel conteggio delle lettere:

alfabeto normale: messaggio in chiaro
alfabeto cifrato: pptidrhar to rmtbhr

Si noti che con l’uso della chiave ripetuta stesse lettere hanno codifiche diverse in vari posti e a lettere diverse possono corrispondere nel testo cifrato lettere uguali. Ciò porta a maggiori difficoltà nella violazione del codice. Più è lunga la chiave più e sicuro il metodo. Idealmente se la chiave ha lunghezza uguale al testo da trasmettere, abbiamo il massimo di sicurezza. In questo caso si parla di cifrario di Vernam. Questo metodo di codifica è utilizzato sulla linea di comunicazione Washington-Mosca, la famosa linea rossa. Ovviamente tale tecnica è utilizzabile solo in casi molto particolari in cui si ha a che fare con messaggi brevi e dimensioni massime note a priori e da trasmettere poco frequentemente.
In pratica, vengono utilizzate due tecniche di tipo diverso nei sistemi crittografici, i sistemi a chiave privata ed i sistemi a chiave pubblica.
Nella crittografia a chiave privata detta anche a chiave segreta, il mittente e il destinatario si accordano su una singola chiave che verrà usata sia in fase di cifratura sia di decifratura.
L’algoritmo più diffuso in questa categoria è il DES (Data Encryption Standard), inventato dall’IBM e adottato come standard del governo U.S.A. nel 1977.
Il testo in chiaro è codificato in blocchi di 64 bit, che producono ciascuno 64 bit di cifrato (cifratura a blocchi). L’algoritmo è dipendente da una chiave di 56 bit e consiste di ben 19 stadi, in ciascuno dei quali si opera una trasformazione dell’output dello stadio precedente. Inoltre, in 16 dei 19 stadi la trasformazione effettuata è identica, ma vengono usate opportune trasformazioni della chiave. Si noti che il metodo è definito pubblicamente, e quindi l’analista conosce come è avvenuta la crittografia, ma, cosa che deve valere per tutti i metodi crittografici, senza la chiave anche sapendo il metodo non si può risalire al testo in chiaro. Tutte le trasformazioni si basano su operazioni di EXOR bit a bit. L’EXOR è un’operazione binaria che a partire da una coppia di bit genera un terzo bit come risultato secondo la seguente regola:

Se i due bit sono uguali il risultato è 0, altrimenti è 1.

Vediamo cosa si ottiene crittografando con un EXOR: chiave: 10110110110
testo in chiaro: 10001011101
testo cifrato: 00111101011
Ci si basa sull’EXOR perché usando la chiave per ricifrare il testo cifrato si ottiene proprio il testo in chiaro. Infatti:
chiave: 10110110110
testo cifrato: 00111101011
testo in chiaro: 10001011101
Avvenendo a livello di singoli bit, il DES viene implementato direttamente via hardware.

Il DES è stato al centro di controversie sin dal giorno in cui è nato:
il progetto originale IBM prevedeva chiavi da 128 bit invece che da 56 bit, ma i militari U.S.A. «suggerirono» attraverso l’NSA (National Security Agency) tale riduzione. Secondo molti, la riduzione fu motivata dall’esigenza di mantenere la capacità (con opportune potenti macchine) di rompere il codice;
oggi il DES non è più considerato sicuro, in quanto recenti tecniche di criptanalisi hanno ridotto il numero di tentativi necessari per la sua violazione.
Una sua variante, il Triple DES, è però a tutt’oggi considerato sicuro, in quanto non si conosce alcun modo di romperlo. Il meccanismo è il seguente:
si usano due chiavi separate K1 e K2;
in fase di codifica si applica il DES per cifrare il flusso di bit con la chiave K1;
si decifra sempre con il DES quanto prodotto nella prima fase usando però la chiave K2; si ricifra di nuovo usando K1;
in ricezione si fanno le operazioni diametralmente opposte.

Effettivamente il Triple DES costituisce un codice per il quale l’approccio della forza bruta richiede 2¹¹² tentativi: anche con un miliardo di chip che effettuano un miliardo di operazioni al secondo, ci vorrebbero 100 milioni di anni per la ricerca completa. Un altro importante algoritmo a chiave segreta è IDEA (International Data Encryption Algorithm).
Fu progettato nel 1990 in Svizzera, e per questa ragione non è soggetto alle limitazioni sull’uso e sull’esportazione che esistono in U.S.A. (dove gli algoritmi di cifratura sono a tutti gli effetti di legge considerati armi da guerra).
Come il DES, IDEA effettua una cifratura a blocchi (di 64 bit), ma usa una chiave di 128 bit. Non sono noti risultati di criptanalisi che lo indeboliscano.

Un problema di fondo affligge la crittografia a chiave segreta quando aumenta il numero di persone che vogliono essere in grado di comunicare fra loro. Poiché ogni coppia di persone deve essere in possesso di una corrispondente chiave, se N persone desiderano comunicare fra loro ci vogliono troppe chiavi, cioè una per ogni coppia. Ciò rende estremamente difficile il problema della distribuzione delle chiavi, che resta il punto debole di tutto il sistema. Tenete conto che uno dei metodi usati dagli hacker per accedere indebitamente ai siti Internet consiste nell’ottenere le password di accesso direttamente dalle persone che le conoscono. Basta a volte spacciarsi per un collaboratore importante del capo, darsi il tono giusto e sufficientemente burbero per trovare un impiegato che riveli la parola d’ordine necessaria.
Per ovviare ai problemi della crittografia a chiave segreta, nella seconda metà degli anni ’70 fu introdotto un tipo di crittografia radicalmente nuovo, detto a chiave pubblica (o asimmetrica).
L’idea è questa:
ognuno possiede due chiavi, legate una all’altra: una è la chiave privata, nota solo al proprietario; l’altra è la chiave pubblica, nota a tutti;
ciò che viene cifrato con la prima chiave può essere decifrato con l’altra (e di solito viceversa);
è quasi impossibile, e comunque estremamente oneroso, derivare la prima chiave anche se si conosce la seconda.
Dunque, per un gruppo di N persone sono necessarie solo 2N chiavi.

Il funzionamento, per ottenere la segretezza, è questo:
in trasmissione si cifra il messaggio con la chiave pubblica del destinatario (che è nota a tutti); il destinatario decifra il messaggio con la propria chiave privata (che è nota solo a lui).
La crittografia a chiave pubblica fornisce anche un meccanismo per garantire l’autenticazione del mittente, cioè la garanzia che esso provenga veramente dall’autore e non da qualcun altro, e l’integrità del messaggio, cioè la garanzia che il messaggio non sia stato alterato.
In questo caso si opera alla rovescia:
in trasmissione si cifra il messaggio con la propria chiave privata;
in ricezione lo si decifra con la chiave pubblica del mittente questo caso non c’è segretezza, dato che chiunque può decifrare il messaggio, ma nessuno, se non il mittente, avrebbe potuto costruirlo ed inoltre nessuno può averlo alterato.

L’algoritmo a chiave pubblica più noto ed usato è l’algoritmo RSA (dalle iniziali degli autori Rivest, Shamir e Adleman), nato nel 1978. Esso trae la sua efficacia dalla enorme difficoltà di trovare la fattorizzazione di un grande numero (si stima che serva un miliardo di anni di tempo macchina per fattorizzare un numero di 200 cifre, e 1025 anni per un numero di 500 cifre). Nel 1994 RSA è stato rotto, in risposta ad una sfida degli autori pubblicata su Scientific American. Il procedimento si riferì a una chiave di 129 cifre (426 bit), e furono impiegati 1600 elaboratori su Internet per 8 mesi, per un totale di 5000 anni di calcolo a 1 MIPS (milione di istruzioni al secondo). D’altronde, poiché RSA lavora con i numeri, la dimensione della chiave è variabile e può essere aumentata a piacere, per controbilanciare gli effetti derivanti dal miglioramento delle prestazioni degli elaboratori. Infine, poiché gli algoritmi a chiave pubblica sono molto più onerosi come calcoli di quelli a chiave segreta (di un fattore da 100 a 1000), essi sono usati soprattutto per negoziare in modo sicuro una chiave segreta, detta chiave di sessione, da usare nel corso della comunicazione vera e propria la cui riservatezza viene protetta con un algoritmo quale DES o IDEA. Le tecniche a chiave pubblica sono quelle che vengono utilizzate, con alcune varianti, per realizzare la firma digitale cioè un’autenticazione del mittente posta in calce ad un documento da trasmettere anche in forma non cifrata.

Le Immagini Digitali
Cominciamo a chiarire la differenza tra un’immagine analogica ed un’immagine digitale.
Un’immagine analogica è, ad esempio, una fotografia stampata su opportuna pellicola. Si tratta di colori distribuiti uniformemente sulla carta. Un’immagine è digitale quando viene rappresentata sotto forma di bit. Sono possibili due diversi metodi per rappresentare immagini al computer e si parla rispettivamente di grafica vettoriale e grafica bitmap o raster. In un’immagine bitmap la digitalizzazione avviene rappresentando le foto come insiemi di punti colorati. Ogni punto si chiama pixel (picture element) e ad esso è associata una posizione ed un colore sullo schermo. Un’immagine è vettoriale quando invece la si rappresenta tramite formule. Ad esempio, per un cerchio bastano centro e raggio, per un rettangolo vertice in alto a sinistra ed in basso a destra, per le linee i due estremi del segmento, per le curve opportune formule matematiche. È vero anche che le immagini vettoriali vengono rappresentate con i pixel, però nel file grafico corrispondente vengono memorizzate formule e coordinate mentre nel caso bitmap si immagazzina uno per uno ogni pixel dell’immagine. In generale le bitmap vanno bene per immagini fotografiche, mentre le vettoriali si adattano meglio al disegno geometrico o pubblicitario. La differenza principale tra i due tipi di immagine è che le raster occupano più memoria. Inoltre tale tipo di immagine dipende dalla risoluzione a cui è visualizzata. Infatti un ingrandimento provoca una riduzione della qualità, mentre le immagini vettoriali possono essere scalate a piacimento senza perdere di definizione. Vengono semplicemente ridisegnate usando nuove coordinate.
Consideriamo adesso quali caratteristiche contribuiscono a definire un’immagine bitmap.

Risoluzione. Con essa si intende il massimo numero di pixel visualizzati per unità di lunghezza. Si esprime in dpi (dot per inches, punti per pollice) o ppi (pixel per inches, pixel per pollice). Sono due nomi diversi ma che indicano la medesima cosa. Maggiore è la risoluzione, maggiore sarà la quantità di informazione da immagazzinare. La risoluzione va scelta in funzione dell’uso che si intende fare dell’immagine stessa. Il valore di risoluzione standard tipografico è 300 dpi. Se l’immagine deve essere visualizzata a schermo (pagine Internet) si deve tener presente che il valore standard di risoluzione dei monitor dei PC è 96 dpi, per i monitor dei Mac è 72 dpi. Per cui si adotta la prassi di lavorare con 72 dpi per produzione di immagini per il Web.
Profondità di colore. Si intende con tale valore la quantità di memoria in bit destinata a rappresentare ogni singolo pixel. Con una profondità di un bit abbiamo solo 2 colori, con la profondità di 8 bit abbiamo 2⁸ = 256 colori e con 24 bit abbiamo 2²⁴ cioè più di 16 milioni di colori.

Dimensione in pixel. La dimensione in pixel viene definita come il numero di pixel in orizzontale ed in verticale utilizzati dall’immagine stessa. Attenzione che tale grandezza va vista in relazione alla risoluzione effettiva del monitor. Se un’immagine su un monitor a 13″ occupa tutto lo schermo a 15″ lo fa solo in parte.
A questo punto è chiaro come per quanto riguarda i siti Web o i prodotti multimediali per la grande distribuzione, tipicamente enciclopedie, il 640 x 480 è il limite massimo per le immagini da utilizzare. Infatti corrisponde alla minima risoluzione disponibile. Anzi nel caso di pagine Internet si ha a disposizione ancor meno spazio perché parte dello schermo è utilizzato per le barre dei menu e degli strumenti di Explorer o Netscape.

Dimensione del file grafico. Sicuramente c’è un legame tra risoluzione, profondità del colore, la dimensione in pixel e la dimensione del file grafico nel senso che quest’ultima sicuramente cresce al crescere delle prime tre. Attenzione che a parità di profondità, risoluzione e dimensioni due file grafici possono avere grandezza diversa. Entra infatti in gioco il formato con cui è memorizzata l’immagine.
Per capire come siano codificate le immagini bisogna addentrarsi nelle tecniche di rappresentazione dei colori. I metodi più frequentemente utilizzati sono 4:
HSB, RGB, CMYK e Lab. Entriamo nel dettaglio solo per I’RGB ed il CMYK.
RGB: In esso ogni colore è definito da una terna di valori numerici compresi tra 0 e 255. Questi valori sono associati al rosso (Red), al verde (Green) ed al blu (Blu). da cui il nome di RGB. Lo 0 corrisponde all’assenza di colore il 255 al massimo valore possibile di intensità. Mescolando tali tre colori è possibile rappresentare una gamma cromatica di più di 16 milioni di tinte. Si dice che l’immagine lavora con tre canali cioè memorizza per ogni pixel tre diverse informazioni. In questo modo la profondità di colore è 24 bit, cioè 8 bit per colore fondamentale. Infatti 2⁸ fa proprio 256 che è il numero di livelli per ogni singolo canale. Questo modello viene utilizzato poiché la riproduzione di immagini a video avviene grazie all’emissione luminosa di piccole porzioni di sale fosforico applicate sul retro dello schermo a formare una matrice di punti. Ogni singolo pixel è fisicamente costituito da tre fosfori che emettono radiazione luminosa di tipo verde, blu e rossa. Tre fasci di elettroni possono essere collimati per colpire ognuno dei tre fosfori di ciascun pixel. Regolando dallo 0 fino ad un valore massimo l’intensità del fascio si ottiene una variazione a 256 livelli dell’intensità cromatica di ogni singolo colore. Avviene così anche per la ripresa televisiva.
Addentrandoci nel mondo delle stampanti le cose cambiano ancora. I tre colori fondamentali sono Ciano, Magenta e Giallo (Yellow). Gli inchiostri per le stampanti a getto ed i toner per le stampanti laser a colori, sono proprio di quei colori. Si tratta del sistema CMYK, ovvero Cyan, Magenta. Yellow e Black.
Si parla di stampa in quadricromia o immagini a 4 canali. Pur se teoricamente non necessario si usa anche il canale per il nero perché con i pigmenti disponibili per gli inchiostri da stampa non si riesce che a costruire un’approssimazione scarsa del nero usando CMY. Ne risulta un marrone scuro. Questo effetto è dunque corretto dall’utilizzo direttamente di inchiostro o toner nero.

Per concludere, introduciamo brevemente i principali formati per la rappresentazione delle immagini:
• .BMP, è il formato standard di Windows. È possibile una profondità di colore a 1, 4. 8, 24 bit. Nel caso delle prime tre scelte viene applicata all’immagine una codifica run lenght, come abbiamo già considerato nel paragrafo sulla compressione.
• .EPS (Encapsulated PostScript). Fa convivere al suo interno sia elementi vettoriali sia elementi bitmap. Utilizza un particolare linguaggio per rappresentare i vari oggetti: il PostScript. È adatto alla rappresentazione di file per stampe tipografiche.
• .TIFF (Tagged Image File Format). E un formato bitmap supportato da quasi tutte le applicazioni grafiche ed è multipiattaforma. Spesso le raccolte in CD di fotografie usano immagini di questo tipo. Come gli altri già visti supporta i vari modelli di colore ed ammette anche la compressione LZW.
• .PDF (Portable Document Format). È un formato multipiattaforma pensato per integrare la rappresentazione di testo ed immagini. E un formato di proprietà della Adobe ed ha bisogno per essere letto di un particolare programma, l’Acrobat Reader. Spesso i file scaricabili da Internet sono in tal formato. Per poter essere creati i file PDF hanno bisogno di software opportuni, Acrobat appunto di Adobe, ma anche Freehand di Macromedia, un’altra azienda di sviluppo software.
• .GIF (Graphic lnterchange Format) è uno degli standard per la visualizzazione in lnternet. In realtà esso corrisponde a due diversi standard fissati nel tempo il CiIF87 ed il GIF89a, introdotto per aggiungere alcune prestazioni in più. ln particolare nell’89 sono state aggiunte le funzionalità di trasparenza, interlacciamento e le immagini multiple. La trasparenza permette di eliminare uno dei colori dell’immagine e di solito si tratta dello sfondo. L’interlacciamento è quella tecnica che permette una comparsa «a veneziana» delle immagini. Invece di salvare le righe dell’immagine ad una ad una vengono salvate la prima, poi la nona e così via di 8 in 8. Quindi si salvano la quinta, la tredicesima e via di 8 in 8. Poi la terza, la settima la undicesima proseguendo di 4 in 4 ed infine tutte le righe pari che erano rimaste fuori dall’operazione proseguendo di due in due. Ciò permette di avere un’anteprima dell’immagine mentre la si sta ancora scaricando.
Le immagini multiple permettono la costruzione di semplici animazioni. Il limite del formato gif è quello di lavorare con 256 colori al massimo, cioè con una profondità di 8 bit. Non è dunque adatto alla rappresentazione di immagini fotografiche, ma va benissimo per icone, loghi ed in genere disegni.
• .JPEG,.JPG (Joint Photographic Expert Group). È un formato compresso a 3 canali ad otto bit con fino a 16 milioni di colori. È possibile durante il salvataggio di una .jpg selezionare la quantità di compressione, in altri termini stabilire quanti colori effettivamente selezionare per la rappresentazione e quindi la qualità dell’immagine finale.
• .PNG nato per diventare l’erede del GIF in realtà, questo formato (Portabile Network Graphic) ha caratteristiche interessanti. Va bene sia nel caso di immagini di qualità fotografica sia per immagini con grandi zone di colore uniforme, supporla la trasparenza ed è indipendente dalla piattaforma. Le ultime versioni dell’Explorer visualizzano oltre che GIF e JPEG anche il PNG.

Parliamo, prima di concludere il paragrafo sulla codifica delle immagini. delle tecniche di compressione. Abbiamo già citato la presenza di tecniche lossy e lossless. Per quanto riguarda le gif viene usata una tecnica lossless. In realtà rispetto all’immagine originale se ci sono più di 256 colori la perdita comunque c’è. Comunque tutto ciò che viene interpolato approssimando i colori con il più vicino da questo punto in avanti rimarrà rappresentato in modo fedele all’originale. L’algoritmo si chiama LZW dai nomi dei tre inventori, Lempel, Ziv e Welch. Semplicemente è un algoritmo che va alla ricerca dei pixel affiancati che si ripresentano con stesso colore. Per quanto riguarda le animazioni registra solo i pixel che variano tra un’immagine e l’altra. Nel formato JPEG si ha invece perdita. Si può selezionare nei programmi di grafica la quantità di compressione da effettuare per cercare di ottenere un compromesso accettabile tra qualità dell’immagine e sua grandezza. Anche nel formato GIF è possibile aumentare il livello di compressione, basta diminuire al di sotto di 256 i colori utilizzati. Chiaro che in questo modo la fedeltà rischia di essere persa. Nel caso JPEG la compressione si basa sull’osservare le differente tra un pixel ed i suoi adiacenti. Quando scopre differenze difficilmente distinguibili a occhio nudo tra pixel adiacenti di colore poco differente, li raggruppa e li rappresenta con stesso colore. Quanto sia grande l’effetto di raggruppamento e quindi di perdita di dettaglio dipende, dal livello di compressione scelto.

I suoni digitali
Prima di tutto bisogna capire la natura del suono nel suo formato analogico e poi come sia possibile renderlo in forma digitale. Il suono è un’onda elastica che si propaga nell’aria. Essa provoca zone di condensazione e rarefazione della pressione nel mezzo in cui propaga. In questo modo la vibrazione sonora giunge al nostro orecchio e da lì viene convertita in impulsi nervosi che vengono decodificati dal nostro cervello. Per descrivere un suono basta dunque descrivere una vibrazione. L’onda sonora più semplice, una nota pura, è descritta da una sinusoide.
Tale onda è caratterizzata da due valori, l’ampiezza A che stabilisce l’intensità del suono ed il periodo T che ne stabilisce la tonalità. Al periodo è legata un’altra grandezza che è frequenza, f, definita come il numero di oscillazioni al secondo compiute dall’onda. In atri termini la frequenza è il reciproco del periodo. Si misura in hertz. I suoni che effettivamente percepiamo non sono così semplici. In realtà risultano dalla sovrapposizione di parecchie queste onde. In particolare noi sentiamo i suoni in un preciso intervallo di frequenze. Anche se soggetto ad una variazione individuale e variabile con l’età, che è quantificabile tra i 20 hertz e i 20.000 hertz.

Per adesso stiamo descrivendo il suono come grandezza analogica, cioè variabile in modo continuo; cosa succede quando viene digitalizzato? L’onda viene divisa in una serie di valori discreti chiamati campioni. Si definisce frequenza di campionamento il numero di campioni estratti in un secondo di segnale sonoro. Esistono opportuni teoremi della teoria dei segnali elettrici che stabiliscono a quale frequenza minima campionare un segnale affinché possa aversi una rappresentazione fedele, senza perdita di informazione del segnale sonoro. Più elevata è la frequenza di campionamento, migliore è la qualità sonora a spese dell’ampiezza del file risultante.

I valori più utilizzati per il campionamento sono 11,025 kHz, 22,05 kHz, 44,1 kHz e 48 kHz. Le frequenze più alte sono utili nel caso di riproduzione di musica.
Un’altro parametro che influisce sulla qualità del sonoro digitalizzato è la profondità in numero di bit. Si possono usare 8, 16, e nei casi più precisi anche 24 bit. Il numero di bit stabilisce i valori possibili per le ampiezze digitalizzate. Questa operazione si chiama quantizzazione ed influisce sul suono facendogli perdere leggermente in fedeltà.

Al crescere della frequenza e della profondità varia il numero di bit. Il calcolo è facilmente fattibile ovvero:
dimensione del file in byte = durata in secondi x frequenza di campionamento x n. di canali x risoluzione/8.
Si provi a fare il calcolo per tre minuti e mezzo di musica stereofonica (a due canali, destro e sinistro) a 44,1 kHz. che è lo standard della qualità per CD Audio e si troveranno parecchi kByte, anzi dei MegaByte.
Fortunatamente anche per il suono sono previste opportune tecniche di compressione.
I due formati principali per i file audio sono il .wav per sistemi Windows ed il .aif per piattaforme Macintosh. Entrambe sono molto versatili e supportano diverse frequenze di campionamento e diversi numeri di bit.
Comunque soffrono entrambe del difetto di richiedere parecchia memoria. Il formato che attualmente spopola in Internet è l’MP3.

Si tratta di una versione opportunamente compressa del flusso audio. Così come il formato JPG comprime immagini basandosi su considerazioni di psicoottica, cioè cercando di eliminare dettagli difficilmente percepibili dall’occhio, l’MP3 si basa su considerazioni di psicoacustica. Le frequenze emesse dagli strumenti musicali possono superare anche i 20 kHz che però sappiamo essere il limite superiore oltre il quale l’orecchio umano comincia a non percepire più il suono. Dunque queste frequenze superiori non vengono riprodotte. Vengono inoltre eliminate anche componenti in frequenza «oscurate» da componenti a forte intensità. In altri termini può accadere che due tonalità molto vicine siano prodotte con intensità molto diversa. La vicinanza come frequenza delle due fa sì che la meno intensa sia praticamente impercepibile, dunque può essere eliminata senza quasi perdita di fedeltà in riproduzione. Usando una strategia di questo tipo si ottengono rapporti di compressione anche pari a 10-12 che è davvero notevole considerata la scarsissima differenza di qualità sonora tra formato .wav ed mp3. Sottolineiamo un altro vantaggio di questa tecnica. Essa è adatta allo streaming, ovvero alla riproduzione anche prima che il file venga completamente scaricato sulla macchina. Si comincia a sentir musica man mano che il brano è trasferito da Internet sul disco locale.
Per completare questo paragrafo sui segnali audio, vogliamo far notare che anche per quanto riguarda il sonoro esistono rappresentazioni vettoriali. Si tratta dei file .mid. Invece di registrare in forma campionata e quantizzata i segnali acustici, in un file .mid sono registrate istruzioni in un particolare linguaggio che può istruire un sintetizzatore elettronico presente sulle schede audio moderne in grado di riprodurre musica. In pratica è come se registrassimo lo spartito del brano ed il sintetizzatore si occupa della riproduzione. La qualità è scarsa, perché il suono è percepibilmente di origine elettronica, quindi non paragonabile assolutamente all’armonia degli strumenti musicali, però è enorme il risparmio di memoria. Per questo il formato .mid ha comunque avuto successo in Internet.

I formati multimediali
Per concludere questa unità consideriamo il problema della riproduzione video. Parlando di immagini ed audio, abbiamo visto come possa essere spinoso il problema della quantità di memoria richiesta. Figuriamoci quando andiamo ad integrare i due tipi di informazione in un unico file corrispondente ad un video. Tenendo conto che gli standard televisivi impongono la riproduzione di 25 fotogrammi al secondo per ottenere una sufficiente rapidità in riproduzione, si hanno 250 immagini per dieci secondi di video più il sonoro. Senza compressione sarebbe impensabile gestire filmati. Per la compressione dei filmati valgono le solite considerazioni relative a tecniche lossy e lossless, ma a differenza degli altri casi la compressione avviene su due fronti, una compressione cosiddetta spaziale che si occupa di restringere il singolo fotogramma, trattandolo come una singola immagine, ed una compressione temporale che registra solo le differenze tra i diversi fotogrammi, non ripetendo ciò che si ripresenta inalterato. Il software che effettua la compressione si chiama CODEC da codificatore-decodificatore. Sono programmi caratterizzati oltre che dal metodo di compressione utilizzato anche dai tempi di conversione. In particolare si distinguono CODEC simmetrici ed asimmetrici. È simmetrico nel caso in cui il tempo di compressione equivale a quello di decompressione, asimmetrico altrimenti. Citiamo per concludere quattro tipi diversi di formato multimediale che vengono a tutt’oggi molto utilizzati.
.AVI è il formato di riproduzione proprietà di Microsoft, standard dunque su piattaforme, Windows. La sigla sta per Audio-Video Interleaved (audio-video intercalati).
.MOV è noto anche come formato QUICKTIME dal nome del software necessario per la sua riproduzione. È stato sviluppato da Apple per i sistemi Mac, ma esistono versioni del riproduttore per parecchie piattaforme.
.MPG o MPEG è uno standard internazionale, dunque non proprietario, sviluppato nell’ambito del progetto Moving Picture Export Group, da cui il nome. In questo progetto è anche avvenuta la definizione dello standard MP3. Ha ottime caratteristiche di compressione e flessibilità che lo rendono adatto alla visione in streaming.
.SWF ShockWave Flash. È un formato proprietario di Macromedia, sviluppato per creare filmati a partire da grafica vettoriale e quindi poco pesanti.

{/gspeech}

ESERCIZI

1. Si eseguano le seguenti operazioni in BCD apportando le opportune correzioni qualora sia il caso:
128 + 235; 472 + 339; 198 + 279.
2. Si codifichino in BCD a parità pari ed a parità dispari le seguenti cifre: 5, 7, 3.
3. Si codifichi con la tecnica della parità longitudinale e trasversale il seguente numero: 3429.
4. Se la parità è pari la seguente cifra BCD 10011 è corretta?
5. Se la parità è dispari la seguente cifra BCD 10011 quanto vale?
6. Si mostri l’errore in questo schema di codifica con parità longitudinale e trasversale a parità dispari, decodificando l’informazione trasmessa in BCD.

7. Si dica se il seguente messaggio codificato con parità longitudinale e trasversale è corretto o meno e nel caso lo si decodifichi o si indichi il numero di errori presenti; la parità è pari:

8. Si indichi la sequenza di numeri associata al seguente messaggio quando viene codificato in ASCII esteso: prova ascii.
9. Si decodifichi la seguente sequenza di numeri sapendo che essa corrisponde a codifiche ASCII: 67 105 97 111.

10. Dato il seguente albero di codifica di Huffman si decodifichi il messaggio (0 se vai a sinistra, 1 a destra)
00111011001000011001011

11. Data la seguente tabella di frequenze si ricavi l’albero binario corrispondente ad un codice a lunghezza variabile di Huffmann.

Esercizi
1. Si definiscano bit, nibble, byte e word.
2. Si definiscano kB, MB, GB, TB.
3. Qual è il vincolo tecnologico invalicabile nella rappresentazione di informazioni al calcolatore?
4. Che cos’è una codifica lossy?
5. Che cos’è una codifica lossless?
6. Si mostri il codice BCD.
7. Che cosa significa la sigla BCD?
8. Che cosa rappresenta 1011 in BCD?
9. Che cosa si intende con il termine codice rivelatore d’errore?
10. Che cosa si intende per codice correttore d’errore?
11. Chi si occupa di gestire la visualizzazione corretta dei caratteri a video ed in stampa?
12. Che cosa indica il termine font?
13. Secondo quali criteri si classificano, da un punto di vista tipografico, i font?
14. Che cosa si intende con i termini aliasing e filtro antialias?
15. Che differenza c’è tra un codice a lunghezza fissa ed uno a lunghezza variabile?
16. Si definiscano i termini Crittografia, Crittologia ed Analisi cifrata.
17. Quali requisiti deve avere una tecnica di cifratura?
18. In cosa consistono il cifrario di Cesare, quello di Vigenere, quello di Vernam?
19. A cosa servono i metodi DES e Triple DES?
20. Cosa sono le chiavi privata e pubblica?
21. Che cosa si intende con i termini autenticazione del mittente ed integrità del messaggio?
22. Che cos’è la firma digitale?
23. Che cos’è un pixel?
24. Si indichino le risoluzioni standard per la stampa, per il sistema Macintosh e per il sistema Windows.
25. Che cosa si intende con il termine profondità di colore?
26. Si indichino le quattro sigle che denotano i metodi per la rappresentazione del colore in grafica.
27. Si indichino i formati grafici conosciuti.
28. Qual’è la profondità di colore dei formati grafici GIF e JPG?
29. Si definiscano l’ampiezza A, il periodo T e la frequenza f per un’onda sonora.
30. Si definisca la frequenza di campionamento.
31. Che cosa significa il termine streaming?
32. Si indichino i formati audio conosciuti.
33. Che cosa sono la compressione spaziale la compressione temporale?
34. Si indichino i formati audio conosciuti.

Esercizi
1. Il processo di codifica permette di:
 ricostruire un’informazione da versione binaria ad altro formato
 rappresentare in formato binario l’informazione
 comprimere e modificare informazioni
 ottenere rappresentazioni migliori

2. Il processo di decodifica:
 ricostruisce fedelmente la versione originaria dell’informazione
 ricostruisce un’informazione da formato binario ad altro formato
 trasforma da binario a binario compresso
 rappresenta l’informazione in formato binario

3. La fedeltà rappresentativa di una codifica indica:
 che la codifica è lossy
 che la codifica è lossless
 la manipolabilità dell’informazione
 la conservazione della grandezza dell’informazione

4. Un sistema telematico:
 si occupa della trasmissione a distanza dell’informazione
 si occupa dell’elaborazione dell’informazione
 corrisponde ad una rete di calcolatori
 integra la trasmissione e l’elaborazione dell’informazione

5. La caratteristica peculiare del codice Gray è:
 usa sempre 4 bit per la codifica
 nel passaggio da un numero al seguente cambia un solo bit
 è un codice a correzione d’errore

6. II codice Gray è utile perché:
 riduce le possibilità di errore
 semplifica la scrittura e la lettura dei numeri
 usa sempre 4 bit

Esercizi
1. Applicate un bit di parità dispari ai seguenti numeri binari:
00111 01010 00000 11111
2. Provate a scrivere in ASCII il vostro nome, inserendo un bit di parità pari. Alla fine, riportate in esadecimale i numeri binari ottenuti.
3. Di seguito è riportata una frase scritta in codice ASCII. Provate a “tradurla”.
4E 4F 4E 20 45 27 20 44 49 46 46 49 43 49
4C45206C61 76 6F 72 61 72 65 20 69 6E
20 41 53 43 49 49
4. Scrivete la vostra data di nascita nel codice 39 e nel codice MSI, utilizzando un doppio “0” per separare giorno mese ed anno.

05-La codifica delle informazioni

Commento all'articolo Annulla risposta