Visualizza wikitesto di Primo teorema di Shannon

Nella [[teoria dell'informazione]], il '''primo teorema di Shannon''' (o '''teorema della codifica di sorgente'''), stabilisce dei limiti alla massima compressione possibile di un insieme di dati e definisce il significato operativo dell'[[Entropia (teoria dell'informazione)|entropia]].

Il teorema stabilisce che, per una serie di [[variabile aleatoria|variabili aleatorie]] [[Variabili indipendenti e identicamente distribuite|indipendenti ed identicamente distribuite]] (i.i.d.) di lunghezza che tende ad infinito, non è possibile comprimere i dati in un messaggio più corto dell'entropia totale senza perdita di [[informazione]]. Al contrario, compressioni arbitrariamente vicine al valore di entropia sono possibili, con probabilità di perdita di informazione piccola a piacere.

Il teorema della [[codifica di sorgente]] per simboli di codice, stabilisce un limite inferiore e superiore alla minima lunghezza attesa di una serie di parole di codice, in funzione dell'entropia della parola in ingresso (vista come una [[variabile aleatoria]]) e della dimensione dell'alfabeto in esame.

== Codifica di sorgente ==
La codifica di sorgente è un mappaggio da una sequenza di simboli generati da una [[Teoria dell'informazione|sorgente]] ad una sequenza di simboli di un alfabeto (solitamente binario), tale che i simboli sorgenti possano essere esattamente recuperati dai bit (codifica senza perdite) o recuperati con qualche distorsione (codifica con perdite). Questo è il concetto che sta alla base della [[compressione dei dati]].

In altre parole si può dire che è la modalità con la quale ciascun evento associato ad una sorgente discreta viene codificato mediante una sequenza di simboli.

== Qualità dell'informazione ==
La codifica di sorgente introduce i concetti alla base della "qualità dell'informazione":
* la quantità di informazione <math>I(x)</math> è data da <math>I(x)=-{\log_2 P(x)}</math>, dove <math>P(x)</math> è la probabilità dell'informazione. Si può quindi dire che tra l'informazione stessa e la sua probabilità vi è una relazione inversamente proporzionale (un'alta probabilità porta ad una bassa quantità di informazione e viceversa).

Volendo, ora, stabilire un'unità di misura è opportuno far riferimento al caso in cui si ha bisogno dell'informazione minima per prendere una decisione.
Trascurando il caso limite (quando l'evento è certo) nel quale esiste un solo risultato, il caso con il minimo bisogno di informazione è quello in cui esistono due possibili risultati equiprobabili (es.: il lancio di una moneta).

Si definisce con bit la quantità di informazione necessaria, e sufficiente, per discriminare e decidere tra due soli eventi equiprobabili: <math>1 bit=K{\log_2 (1/2)}</math>, dove <math>K</math> è l'indice di proporzionalità.
* L'informazione mediata, o entropia, <math>H(x)</math> è pesata dai contributi dell'informazione per la sua probabilità: <math>H(x)=\sum_{i=1}^n P(x) * I(x)</math> [bit/simbolo].
* La velocità di modulazione, o baudrate è la velocità di emissione dei simboli da parte della sorgente: <math>V=\frac{1}{Ts}</math>, dove <math>Ts</math> è la durata del simbolo.
* La [[velocità di trasmissione]] media dell'informazione del sistema, o ''bitrate'', si calcola con: <math>R=V*H(x)</math>.

Altri parametri importanti si riassumono in:
* Lunghezza media del simbolo <math>\sum_{i=1}^n P(x) * ni</math> (ni=lunghezza del codice)
* Rendimento del codice <math>\eta=\frac{H(x)}{L}</math>(η assume valori da 0 a 1)
* Ridondanza <math>\gamma=1-\eta</math>.

=== Teorema della codifica di sorgente ===
In teoria dell'informazione il teorema della codifica di sorgente ([[Claude Shannon]], [[1948]]) stabilisce che:
{{citazione|<math>N</math> variabili casuali i.i.d., ognuna con entropia <math>H(X)</math> possono essere compresse in più di <math>NH(X)</math> [[bit]] con una probabilità di perdita di informazione piccola a piacere, al tendere di <math>N</math> all'infinito; al contrario, se sono compresse in meno di <math>NH(X)</math> bit è virtualmente certo che una parte dell'informazione andrà persa.}}

=== Teorema della codifica di sorgente per simboli di codice ===
Sia <math>X</math> una variabile casuale a valori in un alfabeto finito <math>\Sigma_1</math> e sia <math>f</math> un codice decifrabile (ossia una funzione univoca) da <math>\Sigma_1^*</math> a <math>\Sigma_2^*</math>, dove <math>|\Sigma_2|=a</math>. Sia S la risultante lunghezza della parola di codice <math>f(X)</math>.

Se <math>f</math> è ottima nel senso che ha la minima lunghezza attesa per la parola di codice <math>X</math>, allora
:<math>\frac{H(X)}{\log_2 a} \leq \mathbb{E}\left\lbrace S\right\rbrace < \frac{H(X)}{\log_2 a} +1</math>
(Shannon 1948)

== Dimostrazione: teorema della codifica di sorgente ==
Siano <math>X</math> una sorgente di variabili i.i.d. e <math>X_1, ..., X_n</math> una serie di uscite con entropia <math>H(X)</math> nel caso discreto ed uguale [[entropia differenziale]] nel caso continuo. Il teorema della codifica di sorgente stabilsce che per ogni
<math>\varepsilon > 0</math>, esiste un <math>n</math> abbastanza grande ed un codificatore che prende <math>n</math> uscite i.i.d. della sorgente e le mappa su <math>n.(H(X)+\varepsilon)</math> bit, in modo che i simboli sorgente <math>X^{1:n}</math> siano recuperabili con probabilità di almeno <math>1 - \varepsilon</math>.

; Dimostrazione di raggiungibilità
Sia fissata una qualche <math>\varepsilon > 0</math>. L'insieme tipico, <math>A_n^\varepsilon</math>, è definito come

<math>A_n^\varepsilon =\; \left\{x_1^n : \left|-\frac{1}{n} \log p(X_1, X_2, ..., X_n) - H_n(X)\right|<\varepsilon \right\}</math>

La [[proprietà di equipartizione asintotica]] (AEP), mostra che per un <math>n</math> largo abbastanza, la probabilità che una sequenza generata dalla sorgente cada nell'insieme tipico, <math>A_n^\varepsilon</math>, tende ad uno. In particolare per un <math>n</math> grande abbastanza,<math>P(A_n^\varepsilon)>1-\varepsilon</math>.

La definizione di insieme tipico, implica che le sequenze che cadono nell'insieme tipico soddisfano la condizione

:<math>
2^{-n(H(X)+\varepsilon)} \leq p(x_1, x_2, ..., x_n) \leq 2^{-n(H(X)-\varepsilon)}
</math>

Si noti che:
* La probabilità che una sequenza di <math>X</math> cada in <math>{A_\varepsilon}^{(n)}</math> è maggiore di <math>1-\varepsilon</math>
*<math>\left| {A_\varepsilon}^{(n)} \right| \leq 2^{n(H(X)+\varepsilon)}</math> , dato che la probabilità dell'insieme <math>{A_\varepsilon}^{(n)}</math> è al massimo uno.
*<math>\left| {A_\varepsilon}^{(n)} \right| \geq (1-\varepsilon)2^{n(H(X)-\varepsilon)}</math>. Per la prova è sufficiente utilizzare il limite superiore della probabilità di ogni termine nell'insieme tipico ed il limite inferiore sulla probabilità dell'insieme set <math>{A_\varepsilon}^{(n)}</math>.

Dato che <math>\left| {A_\varepsilon}^{(n)} \right| \leq 2^{n(H(X)+\varepsilon)}, n.(H(X)+\varepsilon)\;</math> bit sono sufficienti per rappresentare ogni stringa nell'insieme.

L'algoritmo di codifica: il codificatore controlla che la sequenza di ingresso cada nell'insieme tipico; se sì produce in uscita l'indice della sequenza d'ingresso nell'insieme tipico; se no, il codificatore produce un arbitrario unumero binario <math>n.(H(X)+\varepsilon)</math> . Se la sequenza ricade nell'insieme tipico, il che avviene con probabilità di almeno <math>1-\varepsilon</math>, il codificatore non commette errori. Quindi la probabilità di errore del codificatore è inferiore a <math>\varepsilon</math>.

;Prova dell'inverso
L'inverso si dimostra mostrando che qualunque insieme di dimensione inferiore a <math>A_n^\varepsilon</math>, avrebbe probabilità al limite sicuramente inferiore a 1 .

== Dimostrazione: teorema della codifica di sorgente per simboli di codice ==
Sia <math>s_i</math> la lunghezza di ogni possibile parola di codice <math>x_i</math> (<math>i=1,\ldots,n</math>). Definito <math>q_i = a^{-s_i}/C</math>, dove <math>C</math> è tale che <math>\sum q_i = 1</math>.

Allora
:<math>
\begin{array}{rcl}
H(X) &=& - \sum_{i=1}^n p_i \log_2 p_i \\
&& \\
&\leq& - \sum_{i=1}^n p_i \log_2 q_i \\
&& \\
&=& - \sum_{i=1}^n p_i \log_2 a^{-s_i} + \sum_{i=1}^n \log_2 C \\
&& \\
&\leq& - \sum_{i=1}^n - s_i p_i \log_2 a \\
&& \\
&\leq& \mathbb{E}\left\lbrace S\right\rbrace \log_2 a \\
\end{array}
</math>

dove la seconda linea deriva dalla [[disuguaglianza di Gibbs]] e la quarta dalla [[disuguaglianza di Kraft-McMillan]]: <math>C = \sum_{i=1}^n a^{-s_i} \leq 1</math> e dunque 
<math>\log C \leq 0</math>.

per la seconda disuguaglianza possiamo imporre
:<math>s_i = \lceil - \log_a p_i \rceil</math>

in modo che
:<math>- \log_a p_i \leq s_i < -\log_a p_i + 1</math>

e quindi
:<math>a^{-s_i} \leq p_i</math>

e
:<math>\sum a^{-s_i} \leq \sum p_i = 1</math>

e dalla disuguaglianza di Kraft, esiste una codice univoco con parole di codice aventi tale lunghezza. Quindi il minimo <math>S</math> soddisfa
:<math>
\begin{matrix}
\mathbb{E}\left\lbrace S\right\rbrace & = & \sum p_i s_i \\
&& \\
& < & \sum p_i \left( -\log_a p_i +1 \right) \\
&& \\
& = & \sum - p_i \frac{\log_2 p_i}{\log_2 a} +1 \\
&& \\
& = & \frac{H(X)}{\log_2 a} +1 \\
\end{matrix}
</math>

== Estensione a sorgenti indipendenti non-stazionarie ==
=== Codifica di sorgente senza perdita a tasso fisso per sorgenti indipendenti discrete e non stazionarie===
Sia definito l'insieme tipico <math>A_n^\varepsilon</math> come
: <math>A_n^\varepsilon =\; \{x_1^n : \left|-\frac{1}{n} \log p(X_1, X_2, ..., X_n) - \bar{H_n}(X)\right|<\varepsilon \}</math>

Allora per un dato <math>\delta>0</math>, per un <math>n</math> grande abbastanza, <math>\Pr(A_n^\varepsilon)> 1-\delta</math>.Ora ci limitiamo a codificare le sequenze nell'insieme tipico ed il solito metodo di codifica mostra che la [[cardinalità]] di questo insieme è inferiore a <math>2^{n(\bar{H_n}(X)+\varepsilon)}</math>. Quindi, in media, <math>\bar{H_n}(X)+\varepsilon</math> bitn sono sufficienti per codificare la sequenza con probabilità di corretta decodifica superiore a <math>1-\delta</math>, dove <math>\varepsilon\; \mbox{ e }\; \delta</math> possono essere rese piccole a piacere aumentando <math>n</math>.

== Bibliografia ==
* {{cita libro|autore=Thomas Cover|titolo=Elements of Information Theory|url=https://archive.org/details/elementsofinform0000cove_m4w2|edizione=2ª edizione|editore=Wiley and Sons|anno=2006}}

== Voci correlate ==
* [[Codifica di canale]]
* [[Compressione dei dati]]
* [[Secondo teorema di Shannon]]

{{Portale|ingegneria|matematica}}

[[Categoria:Teoria dell'informazione]]
[[Categoria:Compressione dei dati]]