>>>>>

Scheda 8 - Caso, informazione e algoritmi

4. Codici.

    A questo punto possiamo svolgere alcune considerazioni introduttive sul ruolo del calcolo delle probabilità nello studio dei processi di trasmissione dell'informazione e nella messa a punto dei codici.

    Abbiamo visto che la lunghezza di un messaggio dipende dalla codifica adottata. Cosa si intende per codifica?

    Si tratta della rappresentazione di un sistema fisico X mediante un altro sistema fisico Y. Restringiamoci al caso che sia X che Y possano assumere solo un insieme finito di stati:

Dom(X) = {x₁,.....,x_n}, Dom(Y) = {y₁,.......,y_m}

    Una sequenza finita (una stringa) di stati è un messaggio. Chiamiamo {x₁,.....x_n} alfabeto e ogni x_i lettera. Chiamiamo ogni y_i segnale.

    Sia F una funzione {messaggi di X} {messaggi di Y}. F sia "calcolabile", cioè ci sia un algoritmo per associare "meccanicamente" ai messaggi di X messaggi di Y.

    Diremo di aver fissato un codice (e che F è la codifica) se ogni messaggio di Y è unicamente decifrabile, cioè F è invertibile e anche F^–1 è calcolabile.

    Restringiamoci al caso m < n: ogni stato (lettera) x_i del sistema X è rappresentato da una successione di stati (segnali) del sistema Y, che indichiamo cod(x_i) (parola di codice della lettera x_i).

    Una condizione sufficiente affinché F sia invertibile è che, se "+" è il simbolo di concatenazione tra stringhe e x e y sono variabili stringa:
–  F(x+y)=F(x)+F(y) (la codifica di una concatenazione di stringhe sia la concatenazione delle loro codifiche; in questo caso si parla di codice letterale, in quanto esso dipende unicamente dalle parole di codice, cioè dalla codifica delle lettere), e
–  nessuna parola di codice sia il prefisso di un'altra parola di codice.
    Un codice che soddisfi questa duplice condizione viene detto istantaneo.

    Ad es. per X= {lettere dell'alfabeto, segni di interpunzione} abbiamo che:

–  il cosiddetto alfabeto Morse, per il quale Dom(Y) = {punto, linea, spazio corto, spazio lungo}, è un codice letterale non istantaneo, mentre

–  il codice ASCII, per il quale Dom(Y) = {0, 1}, è un codice istantaneo: è un codice letterale in cui tutte le parole di codice hanno la stessa lunghezza.

    Dati X e Y, un codice è ottimale se richiede il tempo minimo di trasmissione. Se ci restringiamo ai codici letterali e supponiamo che ogni segnale y_i richieda lo stesso tempo di trasmissione, un codice è ottimale se rende minima la lunghezza media L delle parole di codice: L = Σp_in_i (i=1, …, n), n_i = lunghezza di cod(x_i), p_i = Pr(X= x_i), probabilità con cui viene usata la lettera x_i nei messaggi generati da X.

    Ciò accade se ogni segnale ha il massimo contenuto informativo, cioè se H(Y) è massima. In base alla seconda osservazione dopo il quesito 3, ciò accade se i segnali sono (il più possibile) equiprobabili, cioè se nei messaggi codificati i diversi segnali occorrono (più o meno) con la stessa frequenza.

4

  Il codice di Shannon-Fano di una lingua che usa l'alfabeto A consiste nell'ordinare le lettere di A in base alla loro frequenza e suddividere A in due gruppi quasi equiprobabili; alle lettere del primo gruppo viene assegnato come primo simbolo della codifica 0, a quelle del secondo gruppo 1; poi ciascun gruppo viene suddiviso in due gruppi quasi equiprobabili e in modo analogo viene assegnato il secondo bit della codifica; e così via. Spiegare perché si tratta di un codice ottimale. Supposto che le frequenze delle lettere di A siano le seguenti, si determini il codice.

–:	0.161	a:	0.108	e:	0.085	o:	0.079	i:	0.073	s:	0.060	n:	0.055	l:	0.053
t:	0.051	r:	0.050	c:	0.049	d:	0.038	u:	0.027	v:	0.025	m:	0.016	p:	0.015
f:	0.014	b:	0.010	h:	0.009	z:	0.008	g:	0.006	q:	0.004	':	0.004