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 ${\displaystyle I(x)}$ è data da ${\displaystyle I(x)=-{\log _{2}P(x)}}$, dove ${\displaystyle 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: ${\displaystyle 1bit=K{\log _{2}(1/2)}}$, dove ${\displaystyle K}$ è l'indice di proporzionalità.

• L'informazione mediata, o entropia, ${\displaystyle H(x)}$ è pesata dai contributi dell'informazione per la sua probabilità: ${\displaystyle 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: ${\displaystyle V={\frac {1}{Ts}}}$, dove ${\displaystyle Ts}$ è la durata del simbolo.
• La velocità di trasmissione media dell'informazione del sistema, o bitrate, si calcola con: ${\displaystyle R=V*H(x)}$.

Altri parametri importanti si riassumono in:

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

Teorema della codifica di sorgente

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

Teorema della codifica di sorgente per simboli di codice

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

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

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

Dimostrazione di raggiungibilità

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

${\displaystyle 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 ${\displaystyle n}$ largo abbastanza, la probabilità che una sequenza generata dalla sorgente cada nell'insieme tipico, ${\displaystyle A_{n}^{\varepsilon }}$, tende ad uno. In particolare per un ${\displaystyle n}$ grande abbastanza,${\displaystyle P(A_{n}^{\varepsilon })>1-\varepsilon }$.

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

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

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

Prova dell'inverso

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

Dimostrazione: teorema della codifica di sorgente per simboli di codice

Sia ${\displaystyle s_{i}}$ la lunghezza di ogni possibile parola di codice ${\displaystyle x_{i}}$ (${\displaystyle i=1,\ldots ,n}$). Definito ${\displaystyle q_{i}=a^{-s_{i}}/C}$, dove ${\displaystyle C}$ è tale che ${\displaystyle \sum q_{i}=1}$.

Allora

${\displaystyle {\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: ${\displaystyle C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1}$ e dunque ${\displaystyle \log C\leq 0}$.

per la seconda disuguaglianza possiamo imporre

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

in modo che

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

e quindi

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

e

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

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

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