Vogliamo ora mostrare un semplice esempio di come la misura della informazione I di Shannon possa portare a sviluppare codici compressi, cioè che occupano meno bit. Consideriamo le 26 lettere dell'alfabeto inglese. Dovendo codificarle in binario occorrono 5 bit poiché 2⁵ = 32. Una semplice codifica consiste nell'assegnare a ogni lettera un codice da 5 bit, facendo per esempio corrispondere la lettera A al codice 00000, la lettera B al codice 00001 e così via fino alla lettera Z che avrà codice 11001 (=25 in base dieci).

Tuttavia le lettere non hanno tutte la stessa frequenza, poiché alcune sono usate più spesso e altre raramente. La tabella seguente mostra la frequenza percentuale delle lettere contenute nel Concise Oxford Dictionary:

a	8.167%
b	1.492%
c	2.782%
d	4.253%
e	12.702%
f	2.228%
g	2.015%
h	6.094%
i	6.966%
j	0.153%
k	0.772%
l	4.025%
m	2.406%
n	6.749%
o	7.507%
p	1.929%
q	0.095%
r	5.987%
s	6.327%
t	9.056%
u	2.758%
v	0.978%
w	2.360%
x	0.150%
y	1.974%
z	0.074%

La percentuale fornisce direttamente la frequenza di ogni lettera e dunque può essere considerata come la probabilità di occorrenza della lettera stessa. In base alla formula di Shannon ogni lettera non trasmette la stessa quantità di informazione. Infatti per esempio l'informazione associata alla lettera E (la più frequente nell'alfabeto inglese) è pari a

I_E = log₂(1/P_E) = log₂(1/0,12702 ) ≈ 3 bit

Viceversa l'informazione associata alla lettera Q (la più rara) è:

I_Q = log₂(1/P_Q) = log₂(1/0,00095 ) ≈ 10 bit

Ciò significa che dal punto di vista dell'efficienza nella trasmissione sarebbe più conveniente, invece di codificare tutte le lettere con lo stesso numero di bit (5), usare meno bit per le lettere più frequenti (es. 3 bit per la E) e più bit per quelle meno frequenti (es. 10 bit per la Q).

Vediamo tutto questo con un semplice esempio. Supponiamo di voler trasmettere la seguente sequenza di caratteri in inglese:

HURRY

Usando una semplice codifica a 5 bit per ogni simbolo, occorrerebbero 5 x 5 = 25 bit in totale.

Consideriamo ora l'informazione associata a ogni lettera e il relativo numero di bit, usando la formula di Shannon:

	Freq	Info (bit)
h	6.094%	4
r	5.987%	4
u	2.758%	5,2
y	1.974%	5,6

Dunque in totale il numero minimo di bit per trasmettere il nostro messaggio usando la migliore compressione è pari a 22,8 bit:

H = 4    U = 5,2    R = 4    R = 4    Y = 5,6

Si osservi che il risultato è un numero decimale. Ovviamente in un sistema di trasmissione reale occorrerà utilizzare un numero intero di bit, nel nostro caso 23. Tale numero risulta inferiore ai 25 bit che occorrerebbero codificando ogni lettera con 5 bit, indipendentemente dalla sua frequenza. Come si può dunque notare, usando l'informazione trasmessa da ogni lettera, possiamo ottenere una compressione del nostro messaggio, cioè una riduzione delle sue dimensioni.

Ben prima che Shannon esponesse la sua teoria dell'Informazione, Samuel Morse aveva inventato una codifica dei caratteri dell'alfabeto inglese che prefigura in qualche modo le teorie di Shannon. tale codifica (detta codice o alfabeto Morse) fa corrispondere a ogni carattere una sequenza di linee e di punti come mostrato nella figura seguente:

Osserviamo che nell'alfabeto Morse la lunghezza del codice assegnato a ogni lettera varia in modo inversamente proporzionale alla probabilità di occorrenza della lettera stessa. Così per esempio la lettera E (la più frequente nell'alfabeto inglese) è codificata con un solo simbolo (il punto), mentre la Q (la più rara) è codificata usando ben 5 simboli.

Ciò d'altra parte è intuitivo: se una lettera ricorre più frequentemente, si risparmia sulla lunghezza del messaggio se tale lettera viene codificata in modo abbreviato!

E' interessante notare che una codifica simile viene utilizzata in modo spontaneo anche nei linguaggi naturali, dove, solitamente, le parole più frequenti sono anche quelle composte da meno caratteri. A titolo di esempio, la lista seguente mostra le 10 parole più usate nel primo capitolo dei Promessi Sposi con la relativa frequenza:

Frequenza        Lemma

4,1255%             e
3,1548%             di
2,6209%             che
2,3621%             a
1,7635%             il
1,6179%             in
1,6179%             un
1,5693%             non
1,2943%             la
1,2619%             per

Come si può osservare si tratta di parole con una lunghezza massima di 3 caratteri.

 

precedente - successiva

Sito realizzato in base al template offerto da

http://www.graphixmania.it

Segui @ElePrograMania