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.

Il teorema stabilisce che, per una serie di variabili aleatorie 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 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 $I(x)$ è data da $I(x)=-{\log }_{2}P(x)$, dove $P(x)$ è 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: $1bit=K{\log }_2(1/2)$, dove $K$ è l'indice di proporzionalità.

• L'informazione mediata, o entropia, $H(x)$ è pesata dai contributi dell'informazione per la sua probabilità: $H(x)=\sum _{i=1}^{n}P(x)*I(x)$ [bit/simbolo].
• La velocità di modulazione, o baudrate è la velocità di emissione dei simboli da parte della sorgente: $V=\frac{1}{Ts}$, dove $Ts$ è la durata del simbolo.
• La velocità di trasmissione media dell'informazione del sistema, o bitrate, si calcola con: $R=V*H(x)$.

Altri parametri importanti si riassumono in:

• Lunghezza media del simbolo $\sum _{i=1}^{n}P(x)*ni$ (ni=lunghezza del codice)
• Rendimento del codice $\eta =\frac{H(x)}{L}$(η assume valori da 0 a 1)
• Ridondanza $\gamma =1-\eta$.

Teorema della codifica di sorgente

In teoria dell'informazione il teorema della codifica di sorgente (Claude Shannon, 1948) stabilisce che: Template:Citazione

Teorema della codifica di sorgente per simboli di codice

Sia $X$ una variabile casuale a valori in un alfabeto finito ${\mathrm{\Sigma }}_1$ e sia $f$ un codice decifrabile (ossia una funzione univoca) da ${\mathrm{\Sigma }}_1^{*}$ a ${\mathrm{\Sigma }}_2^{*}$, dove $|{\mathrm{\Sigma }}_2|=a$. Sia S la risultante lunghezza della parola di codice $f(X)$.

Se $f$ è ottima nel senso che ha la minima lunghezza attesa per la parola di codice $X$, allora

$\frac{H(X)}{{\log }_{2}a}\le 𝔼\left\{S\right\}<\frac{H(X)}{{\log }_{2}a}+1$

(Shannon 1948)

Dimostrazione: teorema della codifica di sorgente

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

Dimostrazione di raggiungibilità

Sia fissata una qualche $\epsilon >0$. L'insieme tipico, $A_n^{\epsilon }$, è definito come

$A_n^{\epsilon }=\{x_1^n:|-\frac{1}{n}\log p(X_1,X_2,...,X_n)-H_n(X)|<\epsilon \}$

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

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

$2^{-n(H(X)+\epsilon )}\le p(x_1,x_2,...,x_n)\le 2^{-n(H(X)-\epsilon )}$

Si noti che:

• La probabilità che una sequenza di $X$ cada in ${A_{\epsilon }}^{(n)}$ è maggiore di $1-\epsilon$
• $\left|{A_{\epsilon }}^{(n)}\right|\le 2^{n(H(X)+\epsilon )}$ , dato che la probabilità dell'insieme ${A_{\epsilon }}^{(n)}$ è al massimo uno.
• $\left|{A_{\epsilon }}^{(n)}\right|\ge (1-\epsilon )2^{n(H(X)-\epsilon )}$. 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 ${A_{\epsilon }}^{(n)}$.

Dato che $\left|{A_{\epsilon }}^{(n)}\right|\le 2^{n(H(X)+\epsilon )},n.(H(X)+\epsilon )$ 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 $n.(H(X)+\epsilon )$ . Se la sequenza ricade nell'insieme tipico, il che avviene con probabilità di almeno $1-\epsilon$, il codificatore non commette errori. Quindi la probabilità di errore del codificatore è inferiore a $\epsilon$.

Prova dell'inverso

L'inverso si dimostra mostrando che qualunque insieme di dimensione inferiore a $A_n^{\epsilon }$, avrebbe probabilità al limite sicuramente inferiore a 1 .

Dimostrazione: teorema della codifica di sorgente per simboli di codice

Sia $s_i$ la lunghezza di ogni possibile parola di codice $x_i$ ($i=1,\dots ,n$). Definito $q_i=a^{-s_i}/C$, dove $C$ è tale che $\sum q_i=1$.

Allora

$\begin{array}{ccc}H(X)& =& -\sum _{i=1}^n{p}_i{\log }_2{p}_i\\ & & \\ & \le & -\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\\ & & \\ & \le & -\sum _{i=1}^n-s_i{p}_i{\log }_{2}a\\ & & \\ & \le & 𝔼\left\{S\right\}{\log }_{2}a\end{array}$

dove la seconda linea deriva dalla disuguaglianza di Gibbs e la quarta dalla disuguaglianza di Kraft-McMillan: $C=\sum _{i=1}^n{a}^{-s_i}\le 1$ e dunque $\log C\le 0$.

per la seconda disuguaglianza possiamo imporre

$s_i=\lceil -{\log }_a{p}_i\rceil$

in modo che

$-{\log }_a{p}_i\le s_i<-{\log }_a{p}_i+1$

e quindi

$a^{-s_i}\le p_i$

e

$\sum a^{-s_i}\le \sum p_i=1$

e dalla disuguaglianza di Kraft, esiste una codice univoco con parole di codice aventi tale lunghezza. Quindi il minimo $S$ soddisfa

$\begin{array}{ccc}𝔼\left\{S\right\}& =& \sum p_i{s}_i\\ & & \\ & <& \sum p_i(-{\log }_a{p}_i+1)\\ & & \\ & =& \sum -p_i\frac{{\log }_2{p}_i}{{\log }_{2}a}+1\\ & & \\ & =& \frac{H(X)}{{\log }_{2}a}+1\end{array}$

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 $A_n^{\epsilon }$ come

$A_n^{\epsilon }=\{x_1^n:|-\frac{1}{n}\log p(X_1,X_2,...,X_n)-\overline{H_n}(X)|<\epsilon \}$

Allora per un dato $\delta >0$, per un $n$ grande abbastanza, $\mathrm{Pr}(A_n^{\epsilon })>1-\delta$.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 $2^{n(\overline{H_n}(X)+\epsilon )}$. Quindi, in media, $\overline{H_n}(X)+\epsilon$ bitn sono sufficienti per codificare la sequenza con probabilità di corretta decodifica superiore a $1-\delta$, dove $\epsilon \text{ e }\delta$ possono essere rese piccole a piacere aumentando $n$.

Bibliografia

• Template:Cita libro

Voci correlate

• Codifica di canale
• Compressione dei dati
• Secondo teorema di Shannon