Sin da piccoli siamo abituati ad usare dei simboli per esprimere le nostre emozioni ed idee. Per noi é un attivitá cosí naturale da sembrare innata e non frutto di un attento ragionamento. Ció che sembra naturale é il tempo che spendiamo per padroneggiare tali tecniche. Anche se ci permettono di interagire con le altre persone fin dai primissimi attimi di vita, inizialmente non ci consentono di scambiare informazioni complesse, ma quelle vitali sono semplici e pergiunta comuni a tutte le culture, per esempio il pianto, il sorriso, il contatto fisico sono universalmente validi.
Ció che ci ha permesso di compiere il grande balzo per differenziarci dai nostri cugini primati é stata proprio la capacitá del nostro cervello di riuscire a manipolare i simboli fondendoli e riorganizzandoli di volta in volta in modo diverso per esprimere e comunicare o tramandare idee. E' ovvio che ció é possibile grazie alla facoltá della nostra mente di astrarre, cioé ricondurre qualunque oggetto che ci circonda ad un archetipo (una sorta di specifica base dell'oggetto) e successivamente di associare a questo archetipo un simbolo facilmente trasmissibile e quindi condividisile con gli altri componenti del nostro gruppo, i quali a loro volta, sempre grazie all'astrazione, estrappoleranno dal simbolo l'archetipo, comprendendo cosí il messaggio codificato mediante il simbolo. Questo é quanto avviene da migliaia di anni nella comunicazione umana, ovviamente nel corso dei secoli sono cambiate molte cose, arricchendo il procedimento trasmissivo, per esempio inizialmente la comunicazione avveniva attraverso suoni, successivamente per vincere i limiti temporali di questa tecnica si sono sperimentate nuove vie, prima per rappresentazione grafica (iconificazione del simbolo) attraverso i graffiti fino a giungere ai geroglifici egizi, piú vicini alla scrittura che alla rappresentazione grafica, poiché erano basati sull'utilizzo di regole grammaticali e si fondavano su di un ampio repertorio di simboli. Successivamente, anche grazie al crescere degli scambi commerciali e culturali tra i diversi popoli, si é sentito il bisogno di una forma di interscambio delle idee piú facile e meno coreografica, e cosí é nata la scrittura vera e propria, basata sull'accostamento di parole composte da simboli piú semplici. Ci sono state diversi tentativi, qualcuno piú riuscito di altri, per esempio l'alfabeto romano, al quale é stato aggiunto l'insieme delle cifre arabe, é il piú diffuso al modo, forse non tanto per la sua flessibilitá quanto per la diffusione e l'importanza che ha avuto la lingua latina nel mondo antico, fu la lingua franca per filosofi e scienziati, oggi soppiantata dall'inglese, come sempre per ragioni economiche. Proprio i Romani furono i primi ad ideare una rudimentale teoria di codifica delle informazioni, infatti Giulio Cesare usava un sistema cifrato (codificava in modo nuovo le informazioni) per trasferire alle sue truppe gli ordini, questo sistema impediva a chi non conoscesse la tecnica di decodifica di interpretare gli ordini. In omaggio a questa capillare diffusione nel mondo occidentale dell'alfabeto romano, il codice standard ISO per la comunicazione dei computer con lingue occidentali é detto ISO Latin 1 (2 é una variante per le lingue nordiche), anche se la micromorbida, famosa produttrice di corredi per computer, si ostina ad usare una variante di tale standard.
Per migliaia di anni non ci si é posto il problema di studiare con rigore matematico il processo di codifica dell'informazione, poi sono venuti i compurter e si é resa palese la nostra difficoltá a riprodurre artificialmente alcuni processi incredibilmente naturali per la nostra mente, come appunto la codifica delle informazioni. Proprio il ricorso agli strumenti matematici ci consente di sviluppare una tecnica generale adattabile a tutti gli utilizzi futuri.
Per prima cosa é bene introdurre alcuni strumenti matematici, mediante la loro definizione, che ci serviranno per procedere piú speditamente ed aver chiaro di cosa si sta discutendo.
Supponiamo di avere un insieme finito di simboli diversi detti "caratteri", l'insieme prenderá il nome di "alfabeto". Definiremo "parola" o "stringa" una qualunque sequenza (successione finita) di caratteri di uno stesso alfabeto, i caratteri possono essere ripetuti. Fino a qui non c'é nulla di nuovo, infatti siamo abituati a comporre le parole accodando, in modo opportuno (scartando le sequenze prive di significato), i caratteri dell'alfabeto. Ad ogni parola é in realtá associata un idea che altro non é che una parte dell'informazione da trasmettere. L'associazione della parola, inizialmente come suono e poi come segno grafico, all'idea viene appresa da ogni bambino grazie al costante contatto con i genitore, ed in particolare con la madre. Il fulcro della codifica dell'informazione é una legge che ci consente di associare un elemento estratto dall'insieme delle parole che é possibile realizzare con un dato alfabeto ad un elemento appartenente all'insieme delle idee. Per ovvi motivi questa funzione deve essere di tipo invertibile, ovvero la codifica deve essere di tipo non ambiguo. A dire la veritá nel linguaggio parlato ció non avviene, ed a molte parole sono attribuiti diversi significati. Le ambiguitá vengono risolte mediante l'analisi del contesto nel quale sono immerse le parole, basti pensare alla tipica frase: "la vecchia legge". Detta cosí é totalemente ambigua, e puó essere interpretata in diversi modi, per esempio:
1) Stiamo parlando di una persona anziana che sta compiendo un azione (lettura), la parola "vecchia" é il soggetto della frase, mentre la parola "legge" é un verbo. Per eliminare subito l'ambiguitá é sufficiente aggiungere cosa la vecchia stia leggendo, per esempio "la vecchia legge una lettera della nipotina", come si vede é sempre il contesto che indica il senso vero della frase.
2) Stiamo parlando di una "legge" che definiamo "vecchia", quindi la parola "vecchia" svolge la sua funzione di aggettivo e la parola "legge" indica un sostantivo. Se riteniamo che una frase compiuta sia formata da un soggetto un predicato ed eventualemente un complemento, questa interpretazione é del tutto errata ed illogica mancando proprio il verbo. Purtroppo questa norma non esiste nei "linguaggi parlati", che a ragione sono definiti ambigui, e proprio perché ambigui sono affascinanti e ci hanno regalato esilaranti gag o struggenti pagine di poesia, un linguaggio non ambiguo sarebbe un potroppo artificioso e freddo, come del resto sono i linguaggi di programmazione.
La difficoltá maggiore nel progettare una codifica consiste proprio nel definire, o meglio trovare una funzione invertibile e che rispecchi le nostre esigenze come rapiditá di calcolo o l'impossibilitá di estrappolare le informazioni codificate se non si possiede la funzione inversa. Questo secondo aspetto é studiato dalla crittografia, di grande importanza nel mondo moderno, specialmente dopo l'avvento di internet, che consente in pochi secondi di trasferire informazioni da un capo all'altro, e durante il tragitto potrebbero finire in mani errate. La crittografia basata su differenti codifiche era usata in antichitá, oggi si preferisce adottare degli algoritmi di codifica basati sull'uso di chiavi, anche conoscendo la funzione e la sua inversa non é possibile decodificare le informazioni se non si possiede la chiave esatta. In molti pensano che la chiave sia un banale strumento per avviare l'algoritmo di decodifica, in realtá é parte integrante dell'informazione da decodificare.
Nei "linguaggi parlati" le parole appartengono ad un sottoinsieme di quello ottenibile dalle molteplici combinazioni dei caratteri dell'alfabeto usato, questo perché si eliminano, in primo luogo, le parole impronunciabili e poi quelle prive di significato, ovvero non hanno nessuna idea associata, per esempio la parola "cadosio" é perfettamente pronunciabile, ma é priva di significato logico, non essendole stata associata alcuna idea o informazione. Le cose cambiano se qualcuno ci dice che "cadosio" sia il nome di un nuovo pub o una tecnica di massaggio orientale, ora dietro il simbolo c'é un idea o un'informazione. Quante sono le parole che possiamo formare con i caratteri di un dato alfabeto? Cosí come si presenta la domanda non é facile dare una risposta precisa e sensata, andrebbe riformulata in modo diverso, in modo da far emergere le anologie con gli strumenti matematici che stiamo usando. Quanti elementi possiede l'insieme formato dalle parole ottenute dalla combinazione dei caratteri dell'alfabeto dato? Le cose vanno meglio, ma non di molto. La matematica fornisce uno strumento detto "Cardinalitá di un insieme" che conta quanti elementi possiende un insieme, per esempio la cardinalitá di un insieme vuoto é 0, quella di un insieme con un solo elemento é 1, e cosí via, quindi basta valutare la cardinalitá dell'insieme, qui sorge una nuova difficoltá, le sequenze che formano le parole devono avere una fissata lunghezza, cosa che non é stata indicata nella domanda. Indichiamo con B l'insieme di tutte le parole che vogliamo contare e fissiamo la lunghezza max delle parole in per esempio 10 caratteri, ed indichiamo con Ai l'insieme formato da tutte le parole di lunghezza i, allora la risposta al nostro quesito si puó scrivere come:
Card(B) = Card(A0) + Card(A1) + ... Card(A10)
Abbiamo scomposto il problema iniziale in sottoproblemi piú facili da risolvere. Ovviamente A0 é l'insieme vuoto, perché non é possibile avere parole formate da 0 caratteri, quindi la sua cardinalitá é 0. A1 é l'insieme formato da un solo carattere, se indichiamo con m il numero di caratteri presenti nell'alfabeto, che é dato da Card(alfabeto), la sua cardinalitá sará m. Le parole di 2 caratteri saranno ragruppate nell'insieme A2, la cui cardinalitá sará uguale a Card(A1) * m, e cosí via fino a calcolare la cardinalitá di tutti i sottoinsiemi dati. Il problema pur essendo complesso puó essere sempre risolto. In realtá potevamo risolvere in modo piú semplice introducento elementi di calcolo combinatorio, infatti una parola di n caratteri non é altro che una "disposizione semplice" degli m simboli in n caselle. Quando selezioniamo il simbolo da inserire nella 1ª casella possiamo sceglie uno qualsiasi degli m caratteri a disposizione, abbiamo m possibili scelte diverse, quando riempiamo la 2ª casella possiamo ancora scegliere uno tra gli m caratteri possibili, su due caselle possiamo effettuare m * m scelte possibili, e cosí via. E' facile rendersi conto che alla fine avremo m^n possibili scelte, guarda caso é proprio lo stesso risultato che otterremmo considerando la cardinalitá dell'insieme An, peró questa tecnica ci consente di calcolare il numero delle parole di lunghezza pari ad n, tralasciando quelle di lunghezza inferiore, per tanto dobbiamo applicare la stessa tecnica ai problemi di ordine in feriore, e sommare successivamente tutti i risultati. Pur non essendo molto dissimile dalla precedente ci consente di operare molto piú velocemente, soprattutto se la lunghezza delle parole é fissa.
In informatica si preferisce semplificare il piú possibile i problemi da affrontare, ottenendo incrementi in termini di velocitá di diversi ordini di grandezza. Anche il problema della codifica delle informazione non sfugge a questa regola, e si utilizzano parole a lunghezza fissa, solo in applicazioni molto particolari si usa il modello piú complesso, per esempio nella compressione dei dati, ed in particolar modo negli algoritmi basati sulla tecnica di Huffman, si usa un alfabeto binario con il quale si realizzano parole di lunghezza variabile. Abbinando alle parole piú corte le informazioni piú ricorrenti, e quelle piú lunghe per per le informazioni piú rare, si ottiene un evidente guadagno in termini di occupazione della memoria. Purtroppo la tecnologia attuale dei calcolatori elettronici lega male con l'impiego di parole di lunghezza variabile, chissá un giorno i colossi informatici vaglieranno questi nuovi e quasi inesplorati scenari.
Ora abbiamo tutto quello che ci serve, o quasi, per avventurarci nel mondo della codifica dell'informazione, e come prova del fuoco procediamo alla codifica di un insieme di colori, e successivamente quella di un numero intero non segnato.
Supponiamo di avere i seguenti colori: rosso, verde, blu, ciano, giallo, magenta, nero, e bianco, e di avere il seguente alfabeto A={A, B, C, D, E, F, G, H}. Una soluzione abbastanza semplice sarebbe quella di costruire una tabella che metta in corrispondenza i simboli tra loro, in codifica si usa il nome del colore come chiave, mentre in decodifica il carattere dell'alfabeto:
| colore | rosso | verde | blu | ciano | giallo | magenta | nero | bianco |
| carattere | A | B | C | D | E | F | G | H |
Volendo trasmettere ad un nostro amico una sequenza di colori tipo: rosso, rosso, giallo, giallo, verde, blu, nero, nero, nero, sará sufficiente inviargli la parola (ottenuta mediante la suddetta codifa): AAEEBCGGG. Ovviamente sará in grado di interpretare le informazioni e se solo se possiede giá la tabella, e sa come usarla. Questo semplice esempio ci suggerisce diverse considerazioni:
1) Eseguire una codifica/decodifica di informazioni non é estremente difficile, nella maggior parte dei casi é sufficiente costruire delle tabelle di conversione per passare da un sistema all'altro. Se le chiavi possono essere riordinate secondo un certo criterio di ordinamento, é conveniente sfruttare la tecnica dicotomica per effettuare la ricerca rapida.
E' utile ordinare la tabella solo durante la progettazione o al piú durante la sua inizializzazione, inquanto gli algoritmi di riordino, per quanto efficienti ed ottimizzati siano, richiedono troppo tempo per portare a termine l'operazione, quindi riordinare la tabella prima di ogni utilizzo é sconsigliato, perchè rischia di vanificare il guadagno offerto delle ricerca dicotomica. Se i dati nella tabella subiscono frequenti alterazioni conviene usare una tabella di tipo Hash, dove mediante un opportuna funzione di parcheggio si inserisco ed estraggono i dati. Questa tecnica assicura un accesso quasi istantaneo al dato cercato, peró richiede maggiore memoria e cura nel progettare la funzione di parcheggio, che deve risultare univoca (o quasi) e rapidamente calcolabile. Un esempio classico di questa tecnica é il codice ASCII, infatti ad ogni carattere corrisponde una posizione nella tabella, e vice versa ad ogni posizione corrisponde un solo carattere, poi nella memoria del calcolatore si memorizza la posizione. Per la codifica delle informazioni sono usate parole binarie la cui lunghezza é di 8 caratteri binari, ovvero 1 byte. Invertendo il discorso si ha che con un byte si possono indicare solo 256 informazioni diverse, fortunatamente sono piú che sufficienti per memorizzare tutti simboli stampabili ed i caratteri speciali.
2) Scegliendo opportunamente la tecnica si ha una compressione dei dati, ed allo stesso tempo si impedisce ad occhi indiscreti di accedere alle informazioni.
3) Una qualunque immagine bitmap altro non é che la codifica delle informazioni che il sensore (occhio, CCD, ecc...) estrappola dalla sorgente.
Passiamo al secondo esempio, la codifica di un numero intero nelle diverse basi, ed in particolare quelle di uso piú comune, per prima cosa definiamo gli alfabeti:
Alfabeto Binario = {0, 1}
Alfabeto Decimale = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Alfabeto Esadecimale = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F }
Il sistema di numerazione adottato si dice pesato, in quanto ad ogni posizione (cifra) corrisponde un opportuno peso proporzionale alla base (Cardinalitá dell'alfabeto impiegato). Per esempio il quattrocentosettanta viene scritto nelle diverse basi:
BINARIO: 1101110110 := 1 * 2^9 + 1 * 2^8 + 0 * 2^7 + 1 * 2^6 + 1 * 2^5 + 1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 1 * 2^1 + 0 * 2^0
DECIMALE: 470 := 4 * 10^2 + 7 * 10^1 + 0 * 10^0
ESADECIMALE: 1D6 := 1 * 16^2 + D * 16^1 + 6 * 16^0
E' evidente che piú piccolo é il numero dei simboli disponibili nell'alfabeto e piú lunga sará la parola necessaria per memorizzare la stessa informazione, vedremo tra poco come sia possibile, mediante l'adozione di strumenti matematici, calcolare la lunghezza della parola necessaria per contenere l'informazione.
La funzione di trasferimento, che ci consente di cambiare alfabeto, in questo caso ha il compito di ricercare le cifre che moltiplicate per i rispettivi pesi diano la giusta rappresentazione del numero da codificare. L'algoritmo di calcolo é abbastanza semplice, si procede divindendo ripetutamente la parte intera della divisione precedente, e si annota il resto, la prima volta il dividendo é proprio il numero da convertire. Leggendo da destra verso sinistra i resti si ottiengono le cifre del numero nel nuovo alfabeto.
Supponiamo di avere un insieme di numeri in base 10 (AD) tutti di n cifre, e di doverli ri-codificare in base 2 (AB), quale dovrá essere la lunghezza della parola binaria (numero di cifre) per contenerli?
Facciamo ricorso al calcolo delle disposizioni semplici. Nella base 10 abbiamo 10 oggetti da collocare in n caselle, quindi avremo 10^n possibili "aggregazioni", il nostro problema é il seguente avendo 2 soli simboli di quante caselle abbiamo bisogno per ottenere lo stesso numero di "aggregazioni"? Basta impostare la seguente equazione e risolverla:
2^m = 10^n <=> m = n * ln(10)/ln(2) (Logaritmo in base 2)
Quasi sempre m sará un numero reale, mentre noi abbiamo bisogno che m sia intero, non é possibile prendere mezzo carattere. Cosí lo si arrotonda all'unitá superiore, in questo modo si spreca una cifra nella maggior parte dei casi, ma é l'unica soluzione possibile, altrimenti alcuni numereri sarebbero convertiti in modo errato.
Per memorizzare un numero telefonico (7 cifre decimali) di quante cifre binarie abbiamo bisogno? Ln(10)/ln(2) é pari a 3.32, quindi dalla formula precedente:
m = 7 * 3.32 = 23.24
Il risultato ottenuto va arrotondato a 24. Servono ben 24 cifre binarie per garantire un codifica corretta usando l'afabeto binario. Se vogliamo esprimerlo in esadecimale?
Questa volta si calcola ln(10)/ln(16) che é pari a 0,83, poi procede allo stesso modo
m = 7 * 0.83 = 5.81
che arrotondato, portando a 6 le cifre esadecimali necessarie.
Dando libero sfogo alla propria fantasia e facendo qualche conticino si possono trovare infinite tecniche di codifica, magari mirate a risolvere una particolare classe di problemi.