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:

«$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.»

Teorema della codifica di sorgente per simboli di codice

Sia $X$ una variabile casuale a valori in un alfabeto finito $\Sigma _{1}$ e sia $f$ un codice decifrabile (ossia una funzione univoca) da $\Sigma _{1}^{*}$ a $\Sigma _{2}^{*}$, dove $|\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}}\leq \mathbb {E} \left\lbrace S\right\rbrace <{\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 $\varepsilon >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)+\varepsilon )$ bit, in modo che i simboli sorgente $X^{1:n}$ siano recuperabili con probabilità di almeno $1-\varepsilon$.

Dimostrazione di raggiungibilità

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

$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\}$

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}^{\varepsilon }$, tende ad uno. In particolare per un $n$ grande abbastanza,$P(A_{n}^{\varepsilon })>1-\varepsilon$.

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

$2^{-n(H(X)+\varepsilon )}\leq p(x_{1},x_{2},...,x_{n})\leq 2^{-n(H(X)-\varepsilon )}$

Si noti che:

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

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

Prova dell'inverso

L'inverso si dimostra mostrando che qualunque insieme di dimensione inferiore a $A_{n}^{\varepsilon }$, 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,\ldots ,n$). Definito $q_{i}=a^{-s_{i}}/C$, dove $C$ è tale che $\sum q_{i}=1$.

Allora

${\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}}$

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}}\leq 1$ e dunque $\log C\leq 0$.

per la seconda disuguaglianza possiamo imporre

$s_{i}=\lceil -\log _{a}p_{i}\rceil$

in modo che

$-\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1$

e quindi

$a^{-s_{i}}\leq p_{i}$

e

$\sum a^{-s_{i}}\leq \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{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}}$

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

$A_{n}^{\varepsilon }=\;\{x_{1}^{n}:\left|-{\frac {1}{n}}\log p(X_{1},X_{2},...,X_{n})-{\bar {H_{n}}}(X)\right|<\varepsilon \}$

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

Bibliografia

• Thomas Cover, Elements of Information Theory, 2ª edizione, Wiley and Sons, 2006.

Voci correlate

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