Unità 30

Sommario• Auto-informazione di un evento

• Auto-informazione di un esperimento aleatorio

• Esempi

Bibliografia[Bel] --

[Ros] 9.3

[Pap] --1

Auto-informazione di un evento

• Prima di effettuare un esperimento aleatorio, sono indeciso sul risultato che osserverò• So solo che un evento potrà accadere con

• Quando l’esperimento è concluso, so se si è verificato o no• Se è un evento raro, allora sono molto sorpreso dal risultato

• Se è quasi un evento certo, allora non sono sorpreso dal risultato

• «Weather forecast for tonight: dark. Continued dark overnight, with widely scattered light by morning.» (G. Carlin)

Auto-informazione di un evento

• Misura del livello di «sorpresa» o di informazione portata dall’accadere dell’evento

• Se l’evento è certo, , allora non porta informazione

• Se l’evento è raro, , allora porta molta informazione

• Se il logaritmo è naturale, ho misurato l’informazione in nat

• Se il logaritmo è in base 2, ho misurato l’informazione in bit

Esempio: lancio di una moneta

• Si consideri l’evento : «Esce testa»

• Moneta bilanciata:

• Il verificarsi di dà bit di informazione

• Moneta sbilanciata:

• Il verificarsi di dà bit di informazione

Esempio: lancio di un dado

• Si consideri l’evento : «Esce la faccia 1»

• Dado bilanciato:

• Il verificarsi di dà bit di informazione

• Si consideri l’evento : «Esce una faccia pari»

• Dado bilanciato:

• Il verificarsi di dà bit di informazione

Perché l’informazione è un logaritmo?

• Intuitivamente, il contenuto di informazione di due eventi indipendenti è la somma dei due contributi di informazione

• Es: A=«Esce testa al primo lancio», B=«Esce testa al secondo lancio»

Contenuto informativo di una v.a. discreta

• Un esperimento aleatorio è rappresentato da una v.a. X

• Ad ogni evento elementare è associata una prob. e quindi una auto-informazione

• Informazione media, o entropia, di una v.a. discreta

• Interpretazione: l’entropia è il numero di bit di informazione che mediamente mi aspetto di osservare dall’esperimento X

Esempio: entropia di una costante

• Si consideri una v.a. X degenere, dove per qualche

• Per definizione, si pone

• Non esistono v.a. discrete con entropia più piccola di 0

Esempio: v.a. uniforme discreta

• Sia X una v.a. uniforme discreta su m valori

•

• Data una v.a. discreta con risultati elementari, l’uniforme è quella che massimizza l’incertezza sul risultato

Esempio: lancio di moneta sbilanciata

• Sia X una v.a. che descrive il lancio di una moneta con

0.2 0.4 0.6 0.8 1.0

0.2

0.4

0.6

0.8

1.0

p

Esempio: numero di lanci alla prima testa

• Esperimento: lancio una moneta bilanciata fino all’uscita della prima testa

• V.a. discreta X che conta il numero di lanci:

Unità 30

Sommario• Codifica di messaggi

• Diseguaglianza di Kraft-McMillan

• Codifica di sorgente

Bibliografia[Bel] --

[Ros] 9.4

[Pap] --12

Rappresentare un risultato in bit

• Si vuole rappresentare il risultato di una v.a. con una stringa di bit• Ad es., per trasmetterlo a qualcuno con un sistema di comunicazione

• per memorizzarlo su un supporto elettronico

• Quanti bit devo usare per rappresentare un risultato? Come devo scegliere le sequenze di bit?

• Es: per rappresentare «testa»/«croce» nel lancio di moneta posso usare

Uso un bit per ogni risultato generato. È un metodo efficiente?

Rappresentazione dei lanci di moneta

• Se la moneta è bilanciata, sappiamo che ogni lancio genera 1 bit di informazione• Ha senso rappresentare ogni lancio con un messaggio lungo 1 bit

• Se la moneta è fortemente sbilanciata, ogni lancio genera molto meno di 1 bit di informazione• È uno spreco rappresentare ogni lancio con un messaggio lungo 1 bit

• Il risultato di un lancio deve essere descritto da un messaggio lungo almeno 1 bit.

• Come faccio a trasmettere mediamente meno di 1 bit per lancio?

Rappresentazione dei lanci di moneta

• Idea: proviamo a codificare 2 lanci consecutivi di moneta

così facendo spendo sempre 1 bit per ogni prova!

• Proviamo a risparmiare bit sulle coppie più probabili

lunghezza media del messaggio se ?

Uso bit per lancio

Codici di lunghezza variabile

• È possibile fare meglio di 0.84 bit per lancio di moneta?

• Sappiamo che con , mediamente si generano

bit di inform.

• Potremmo codificare più di 2 lanci contemporaneamente

• Esiste un modo sistematico per creare l’insieme dei messaggi (codice)?

• I messaggi non devono creare ambiguità: ad es., ogni messaggio non deve essere un prefisso di qualsiasi altro messaggio (prefix-free code)

• Es: {1, 0, 01} è ambiguo. {1, 00, 01} non è ambiguo

Diseguaglianza di Kraft-McMillan

• Non tutti i codici di lunghezza variabile sono disambigui (prefix-free)

• Teorema: Posso trovare un codice prefix-free composto da m messaggi binari di lunghezze se e solo se

• Significato: Fissato m, non posso scegliere le lunghezze tutte piccole. Qualcuna dovrà essere grande per soddisfare la diseguaglianza

• Conseguenza: non posso abbassare la lunghezza media più di tanto

Codifica di sorgente

• Qual è il meglio che si può fare? Qual è la lunghezza media minima del codice?

• Teorema: data una v.a. discreta X con m risultati, per ogni codice prefix-free che assegna una sequenza di bit al risultato si ha

• È una diretta conseguenza della diseguaglianza di Kraft-McMillan

Esempio

• Si ha