Codice (teoria dell'informazione)

Disambiguazione – "Codifica" rimanda qui. Se stai cercando il processo di traduzione proteica delle informazioni contenute nei geni, vedi Codice genetico.

Questa pagina sull'argomento Informatica sembra trattare argomenti unificabili alla pagina Teoria dei codici.

Questa voce o sezione sull'argomento teorie dell'informatica non cita le fonti necessarie o quelle presenti sono insufficienti.

Il codice, nella teoria dell'informazione, e specificatamente nelle telecomunicazioni, nell'elettronica e nell'informatica, è un sistema di segnali, segni o simboli convenzionalmente designati per rappresentare un'informazione.

Significati

Il termine codice viene usato con due significati:

procedimento di codifica, riguarda la modalità seguita per assegnare univocamente ad ogni elemento dell'insieme da rappresentare una stringa che lo rappresenti. In questo significato, il codice è la forma prestabilita che assume un messaggio nel momento in cui viene trasmesso^[1];
insieme delle codifiche, denota l'insieme delle stringhe rappresentative (questo è il significato utilizzato nella branca della matematica chiamata teoria dei codici (v. 94-XX).

Un codice si dice efficiente quando utilizza un numero di simboli strettamente necessario per codificare l'informazione, mentre all'opposto si dice ridondante quando usa un numero di simboli abbondanti, e quindi più di quelli necessari, ma utili per semplificare la generazione e la interpretazione delle informazioni.

Definizione formale

Sia S un insieme finito di elementi detto alfabeto del codice, come ad esempio le due facce con una moneta (T, C). Un insieme A di sequenze costruite giustapponendo uno o più elementi di S è un codice. Ogni elemento di A è una parola del codice e il numero di elementi dell'alfabeto usati per costruirla ne indica la lunghezza. Perché un codice abbia utilità e senso, tuttavia, dev'essere associato con qualche meccanismo controllabile (formula, algoritmo, elenco ben definito, ...) a un insieme di possibili dati che deve rappresentare fedelmente e dunque averne la stessa cardinalità. Per esempio, l'insieme {T, C, TC, TT} è un codice e può essere usato come codifica dei numeri 0, 1, 2, 3.

Proprietà

Giustapponendo più parole del codice si ha un messaggio costruito su tal codice, come ad esempio TTC o TCTC. Dipendentemente dal fatto che un qualsiasi messaggio possa essere scomposto in modo che esista un'unica serie di parole del codice che la compongano il codice si dice univocamente decodificabile o meno. Il codice di cui sopra non è univocamente decodificabile poiché il messaggio TT potrebbe essere scomposto come la ripetizione 2 volte della parola T o la parola stessa del codice TT. Al contrario, {C, TC, TTC, TTTC} è un codice univocamente decodificabile. Un codice in cui tutte le parole hanno la stessa lunghezza si dice codice a blocchi o in caso contrario codice a lunghezza variabile.

Altre proprietà di un codice sono la capacità di correggere errori, comprimere i messaggi, essere lineari o meno, essere utilizzabili in crittografia o essere istantanei.

Lo studio dei codici in maniera sistematica come elementi fondamentali per la teoria dell'informazione e della trasmissione è nato nel 1948 con il lavoro di Claude Shannon.

Esempi

Un esempio tradizionale di codice è il Morse, appartenente alla codifica di caratteri e utilizzato nei primi tempi della telegrafia (1840): in esso, ad ogni lettera dell'alfabeto latino (l'insieme di informazioni da rappresentare) viene assegnata una sequenza di punti e linee (gli elementi dell'alfabeto usato per la codifica).

Altre esempi di codifica sono la codifica digitale di un segnale analogico ovvero la conversione analogico-digitale, la codifica di sorgente e la codifica di canale.

Utilità

L'unicità della rappresentazione gioca un ruolo cruciale in tutte le applicazioni della codifica (il procedimento di trasportare gli elementi dalla rappresentazione di partenza a quella definita dal codice) e di decodifica (l'inverso). I codici risultano utili quando la comunicazione verbale normale non è sufficiente o non è praticabile. Con un'opportuna codifica è possibile descrivere realtà ben più complesse del lessico del linguaggio naturale, come ad esempio un'immagine o una serie di suoni.

Con l'avvento dell'informatica e delle telecomunicazioni i codici hanno preso ulteriore piede per la trasmissione affidabile e la compressione dati, anche se già all'epoca del telegrafo venivano usate delle parole in codice per trasmettere frasi di uso particolarmente frequente, ad esempio:

BYOXO (Are you trying to weasel out of our deal? - Stai cercando di uscire dal nostro accordo?)
LIOUY (Why do you not answer my question? - Come mai non rispondi alla mia domanda?)
AYYLU (Not clearly coded, repeat more clearly. - Codificato male, per favore ripetere più chiaramente).

Codice di Gödel

In matematica, la numerazione di Gödel è alla base della dimostrazione del Teorema di incompletezza. In tal caso, l'idea consiste nel trasformare la notazione matematica in un numero naturale.