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: $1 b i t = 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}{T s}$ , dove $T s$ è 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) * n i$ (ni=lunghezza del codice)
Rendimento del codice $η = \frac{H (x)}{L}$ (η assume valori da 0 a 1)
Ridondanza $γ = 1 - η$ .

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

N H (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

N H (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 $Σ_{1}$ e sia $f$ un codice decifrabile (ossia una funzione univoca) da $Σ_{1}^{*}$ a $Σ_{2}^{*}$ , dove $| Σ_{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 𝔼 {S} < \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 $ε > 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) + ε)$ bit, in modo che i simboli sorgente $X^{1 : n}$ siano recuperabili con probabilità di almeno $1 - ε$ .

Dimostrazione di raggiungibilità

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

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

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

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

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

Si noti che:

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

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

Prova dell'inverso

L'inverso si dimostra mostrando che qualunque insieme di dimensione inferiore a $A_{n}^{ε}$ , 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{matrix} 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 & 𝔼 {S} \log_{2} a \end{matrix}

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} = ⌈ - \log_{a} p_{i} ⌉

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} 𝔼 {S} & = & \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{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}^{ε}$ come

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

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

Bibliografia

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

Voci correlate

Portale Ingegneria

Portale Matematica