Primo teorema di Shannon

Da Wikipedia, l'enciclopedia libera.

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 rischiare di perdere 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.

Indice

1 Codifica di Sorgente
2 Qualità dell'Informazione
- 2.1 Teorema della codifica di sorgente
- 2.2 Teorema dell codifica di sorgente per simboli di codice
3 Dimostrazione: Teorema della codifica di sorgente
4 Dimostrazione: teorema della codifica di sorgente per simboli di codice
5 Estensione a sorgenti indipendenti non-stazionarie
- 5.1 Codifica di sorgente senza perdita a tasso fisso per sorgenti indipendenti discrete e non stazionarie
6 Voci Correlate
7 Bibliografia

[modifica] Codifica di Sorgente

La codifica di sorgente è un mappaggio da una sequenza di simboli generati da una sorgente ad una sequenza ad una sequenza di simboli di un alfabeto (solitamente binario), tale che i simboli sorgenti possono 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.

[modifica] 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 lanco 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, è pesata dai contributi dell'informazione per la sua probabilità: $\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 η= $\frac{H(x)}{L}$ (η assume valori da 0 a 1) e la Ridondanza γ=1-η .

[modifica] 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.

[modifica] Teorema dell 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 $|\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)

[modifica] Dimostrazione: Teorema della codifica di sorgente

Siano $X$ una sorgente di variabili i.i.d. e X₁, ..., 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^\epsilon$ , è definito come

$A_n^\epsilon =\; \left\{x_1^n : \left|-\frac{1}{n} \log p(X_1, X_2, ..., X_n) - H_n(X)\right|<\epsilon \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^\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)} \leq p(x_1, x_2, ..., x_n) \leq 2^{-n(H(X)-\epsilon)}$

Si noti che:

La probabilità che una sequenza di $X$ cada in ${A_\epsilon}^{(n)}$ è maggiore di $1 - ε$

$\left| {A_\epsilon}^{(n)} \right| \leq 2^{n(H(X)+\epsilon)}$ , dato che la probabilità dell'insieme ${A_\epsilon}^{(n)}$ è al massimo uno.

$\left| {A_\epsilon}^{(n)} \right| \geq (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| \leq 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) + ε)$ . 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^\epsilon$ , avrebbe probabilità al limite sicuramente inferiore a 1 .

[modifica] 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$ .

Then

$\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& \mathbb{E}\left\lbrace S\right\rbrace \log_2 a \\ \end{matrix}$

dove la seconda linea deriva dalla disuguaglianza di Gibbs e la quarta dalla disuguaglianza di Kraft: $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$

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

[modifica] Estensione a sorgenti indipendenti non-stazionarie

[modifica] 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 : \left|-\frac{1}{n} \log p(X_1, X_2, ..., X_n) - \bar{H_n}(X)\right|<\epsilon \}$

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

[modifica] Voci Correlate

[modifica] Bibliografia

Cover, Thomas, "Elements of Information Theory", 2^ edizione, Wiley and Sons, 2006

Ingegneria

Progetto Ingegneria - Bar degli ingegneri - L'ingegnere - I materiali - Le unità di misura
Settore Ingegneria Civile e Ambientale Ambiente e territorio - Civile - Geotecnica - Idraulica - Naturalistica - Sicurezza - Sismica - Strutturale - Trasporti	Settore Ingegneria Informazione Acustica - Biomedica - Elettronica - Informatica - Telecomunicazioni	Settore Ingegneria Industriale Aerospaziale - Automazione - Biochimica - Chimica - Elettrica - Energetica - Gestionale - Industriale - Materiali - Meccanica - Navale - Nucleare - Processi di produzione
Categorie ingegneristiche Aerospaziale - Automazione - Biomedica - Chimica - Civile - Comunicazioni - Elettrica - Geotecnica - Gestionale - Idraulica - Industriale - Informatica - Materiali - Meccanica - Navale - Nucleare - Sismica - Strumentale - Strutturale - Termotecnica - Territorio - Trasporti

Estratto da "http://it.wikipedia.org../../../p/r/i/Primo_teorema_di_Shannon_c5ff.html"

Categorie: Telecomunicazioni | Ingegneria delle comunicazioni