Blog

Primo teorema di Shannon

Valutazione attuale: 0 / 5

Stella inattivaStella inattivaStella inattivaStella inattivaStella inattiva
 

Ringrazio, come sempre, Wikipedia

Premessa. 

Tale teorema è la base dei meccanismi di compressione che vengono usati quotidianamente nei nostri pc, smartphones, telefonia, in tutti cioè gli apparati digitali. Vi siete mai chiesti come si fa a rendere così piccola un'immagine (jpg) , una musica (mp3) un video (mp4)?

I metodi di compressione sono di due tipi: "a perdita (jpg, mp3, mp4, eccetera)" e "non a perdita" (zip)

Una sequenza di lettere come aaaaaaaa possiede meno entropia di una parola come alfabeto la quale possiede ancora un entropia di una stringa completamente casuale come j3s0vek3. L'entropia può essere vista come la casualità contenuta in una stringa, ed è strettamente collegata al numero minimo di bit necessari per memorizzarla.

Si deve a Claude Shannon lo studio dell'entropia nella teoria dell'informazione, il suo primo lavoro sull'argomento si trova nell'articolo Una teoria matematica della comunicazione del 1948. Nel primo teorema di Shannon, o teorema di Shannon sulla codifica di sorgente, egli dimostrò che una sorgente casuale d'informazione non può essere rappresentata con un numero di bit inferiore alla sua entropia, cioè alla sua autoinformazione media. Tale risultato era implicito nella definizione statistica dell'entropia di John Von Neumann, anche se lo stesso Von Neumann, interrogato al riguardo da Shannon nel forse unico scambio di opinioni tra loro, non ritenne la cosa degna di attenzione. Come ricordò Shannon più tardi a proposito del risultato da lui trovato:

« La mia più grande preoccupazione era come chiamarla. Pensavo di chiamarla informazione, ma la parola era fin troppo usata, così decisi di chiamarla incertezza. Quando discussi della cosa con John Von Neumann, lui ebbe un'idea migliore. Mi disse che avrei dovuto chiamarla entropia, per due motivi: "Innanzitutto, la tua funzione d'incertezza è già nota nella meccanica statistica con quel nome. In secondo luogo, e più significativamente, nessuno sa cosa sia con certezza l'entropia, così in una discussione sarai sempre in vantaggio »

L'entropia di una informazione è uguale a: \mathbb{H}[X]=\mathbb{E}\left[I(X) \right]= \mathbb{E}\left[ - \log_b{ \mathbb{P}(X)}\right], dove I(x) = -\log_b \mathbb{P}(x) è la quantità di informazione presente nel nostro messaggio.

Quindi una sequenza di messaggi emessi da una sorgente possono essere compressi senza perdita d'informazione fino ad un numero minimo di bit per messaggio uguale all'entropia della sorgente. E' anche vero che: 

« N variabili casuali i.i.d., ognuna con entropia H(X) possono essere compresse in più di NH(X) bit con una probabilità di perdita di informazione piccola a piacere, al tendere di N all'infinito; al contrario, se sono compresse in meno di NH(X) bit è virtualmente certo che una parte dell'informazione andrà persa. »

Da questo teorema discendono altri teoremi, di cui quello più importante è quello del campionamento, fondamentale se devo trasformare in bit, grandezze discrete, un 350px Synthesis squarefenomeno continuo. Facciamo il classico esempio della sinusoide. E' una curva semplice, una sola armonica. Entropicamente molto bassa. La posso campionare perfettamente. Ma è impossibile campionare perfettamente un'onda quadra, che è formata di infinite armoniche, cioè è la sovrapposizione di infinite sinusoidi. Il passaggio dall'analogico al digitale indurrà in questo caso delle perdite di informazione, che possono essere rese piccole, ma esisteranno sempre. La musica digitale, ahinoi, è sempre inferiore a quella che sentiamo dal vivo a quella che c'è sui dischi in vinile!

0
0
0
s2sdefault

Portale di Fisica

23 Gennaio 2016
22 Gennaio 2016
01 Gennaio 2016
01 Dicembre 2015
20 Novembre 2015
11 Novembre 2015
10 Novembre 2015
08 Novembre 2015
05 Novembre 2015
04 Novembre 2015
03 Novembre 2015
02 Novembre 2015
21 Ottobre 2015
20 Ottobre 2015
20 Ottobre 2015
20 Ottobre 2015
13 Ottobre 2015
07 Ottobre 2015
04 Ottobre 2015
03 Ottobre 2015
18 Settembre 2015
17 Settembre 2015
© 2015 Il sito di giamod. All Rights Reserved. Designed By JoomShaper

Search