Entropia

P

I

P(x)

Esempio: se un simbolo ha probabilità 0.5 allora

I= -log (0.5)=1 bit

Più è raro, più bit servono per rappresentarlo.

2. Cos’è l’entropia?

L’entropia è la media pesata dell’informazione di tutti i simboli. “Pesata” significa

che ogni simbolo contribuisce in base alla sua probabilità.

Entropia = H = P(X) I(X). = - P(X)• log P(x)

∑ • ∑

Esempio:

Quadrato = 0,5• log (1/0.5)=-0,699 0.5 1 = 0.5

•

Cerchio: = 0.3 (1/0.3)=-0,3 1,737= 0,521

•log •

Triangolo: = 0.1 (1/0.1)=-0,1 3,321 = 0,332

•log •

Rombo: = 0.1 (1/0.1)=-0,1 3,321 = 0,332

•log •

Somma totale:

H= 0,5 + 0,521 + 0,332 + 0,332 = 1,685 bit

Quindi in media ogni simbolo porta circa 1,685 bit di informazione.

Perché è utile?

Se vuoi codificare questi simboli nel modo più efficiente possibile, non puoi scendere

sotto l’entropia. È il limite teorico minimo. Se il tuo codice ha una lunghezza media

di 1,7 bit, sei molto vicino all’ottimo.

L’entrop'ia è una media pesata dell’informazione dei simboli. Ogni simbolo ha:

una probabilità di apparire (quanto spesso lo troviamo)

una quantità di informazione che porta (quanto ci “sorprende”)

La formula dell’entropia è:

H= p log 1

∑ •

i 2

i p i

E quel numero davanti al log?

Quel numero è la probabilità del simbolo. Lo mettiamo davanti al log perché stiamo

moltiplicando la quantità di informazione del simbolo per quanto spesso appare.

È come se stiamo dicendo: “Questo simbolo porta 1 bit di informazione, ma appare

solo metà delle volte, quindi il suo contributo medio è 0,5 bit.”

In sintesi

Il logaritmo misura quanta informazione porta un simbolo.

La probabilità davanti al log serve per fare la media pesata: quanto spesso quel

simbolo contribuisce all’informazione totale.

Ricorda:

Se si lavora con una calcolatrice che utilizza solo log in base 10, bisogna

dividere il risultato per log10(2) per ottenere correttamente il valore in bit.

Quando calcoliamo l’informazione di un simbolo, mettiamo davanti il segno meno.

perché il meno?

Perché il logaritmo di una probabilità è negativo

Le probabilità sono sempre tra 0 e 1. E il logaritmo in base 2 di un numero tra 0 e 1

è negativo.

Se non mettessimo il segno meno, otterremmo valori negativi per l’informazione. Ma

l’informazione, per definizione, deve essere una quantità positiva: non ha senso dire

che un simbolo porta “-2 bit” di informazione.

Ricorda:

Il logaritmo di una probabilità è negativo.

Il meno serve a rendere il risultato positivo

H dipende solo dalle probabilità pi e non dai simboli si.

Se una sorgente ha entropia H(X), allora la lunghezza media L del codice deve

rispettare: L H(X)

≥

Implicazioni:

→

Se L < H(X) non è possibile ricostruire l’informazione originale senza errori.

(perde informazioni)

→

Se L = H(X) codifica ottimale, ma difficile da raggiungere nella pratica.

→

Se L > H(X) codifica valida, ma non necessariamente efficiente.

Codifica dell’informazione

Un codice a lunghezza variabile è univocamente decodificabile se soddisfa la

condizione del prefisso:

una parola di codice non deve mai essere l’inizio di una qualsiasi altra parola dello

stesso codice. Entropia per simboli equiprobabili

L’entropia di una sorgente con M simboli equiprobabili è pari a log (M).

M

Dim.: Per simboli equiprobabili (pi = p), dovendo essere pi = 1

∑ i 1

=

segue pi = 1/M, per cui M

M

H= 1. log (M) = 1 log (M)•∑. 1 = log. (M)

∑ 2

i 1 2 2 11

= M M

Upper bound

L’entropia è massima per simboli equiprobabili.

Dim.: Per una funzione convessa si ha E(f(X)) (disuguaglianza di Jensen).

≥f(E(X))

Posto f(x) = log (1/x), segue

p f ( p ) f ( p / M ). Ovvero. H≥ log (M).

∑ ≥ ∑ i

i i i 2

i Condizione del codice e proprietà del prefisso

Per garantire una decodifica univoca, ogni codice assegnato a un simbolo deve

rispettare la condizione del prefisso, ovvero non deve mai essere l’inizio di un altro

codice. Questa proprietà è essenziale per evitare ambiguità nella decodifica dei

messaggi.

Punti chiave:

Un codice valido non deve mai essere preposto a un altro codice.

Esempi di codici non validi includono codici in cui '10' è l’inizio di '101'.

Il rispetto della condizione del prefisso assicura che la decodifica possa essere

eseguita in maniera univoca.

Spiegazione

Il codebook utilizzato per la codifica deve essere progettato in modo da rispettare

la condizione del prefisso. Ciò significa che nessun codice assegnato ad un simbolo

può risultare essere l’inizio di un codice assegnato ad un altro simbolo.

Esempio:

Si consideri un insieme di codici per i simboli 0, +1, +2, +3. È necessario verificare

che nessun codice sia l'inizio di un altro. Ad esempio, se il codice '10' è usato per un

simbolo, non deve esistere un altro codice che inizi con '10'.

Identificare e confrontare ogni codice per verificare l'assenza di prefissi comuni.

Convalidare il codebook in modo che ogni codice possa essere decodificato in

maniera univoca.