Apri il menu principale

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.

Indice

Codifica di SorgenteModifica

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'informazioneModifica

La codifica di sorgente introduce i concetti alla base della "qualità dell'informazione":

  • la Quantità di informazione   è data da  , dove   è 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 , dove   è l'indice di proporzionalità.

  • L'informazione mediata, o entropia, è pesata dai contributi dell'informazione per la sua probabilità:   [bit/simbolo].
  • La velocità di modulazione, o baudrate è la velocità di emissione dei simboli da parte della sorgente: V= , dove   è 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   (ni=lunghezza del codice)
  • Rendimento del codice η= (η assume valori da 0 a 1)
  • Ridondanza γ=1-η .

Teorema della codifica di sorgenteModifica

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 codiceModifica

Sia X una variabile casuale a valori in un alfabeto finito   e sia f un codice decifrabile (ossia una funzione univoca) da   a  , dove  . 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

 

(Shannon 1948)

Dimostrazione: Teorema della codifica di sorgenteModifica

Siano   una sorgente di variabili i.i.d. e X1, ..., Xn 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  , esiste un   abbastanza grande ed un codificatore che prende   uscite i.i.d. della sorgente e le mappa su   bit, in modo che i simboli sorgente   siano recuperabili con probabilità di almeno  .

Dimostrazione di raggiungibilità

Sia fissata una qualche  . L'insieme tipico,  , è definito come

 

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,  , tende ad uno. In particolare per un n grande abbastanza, .

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

 

Si noti che:

  • La probabilità che una sequenza di   cada in   è maggiore di  
  •   , dato che la probabilità dell'insieme   è al massimo uno.
  •  . 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  .

Dato che   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   . Se la sequenza ricade nell'insieme tipico, il che avviene con probabilità di almeno  , 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  , avrebbe probabilità al limite sicuramente inferiore a 1 .

Dimostrazione: teorema della codifica di sorgente per simboli di codiceModifica

Sia   la lunghezza di ogni possibile parola di codice   ( ). Definito  , dove C è tale che  .

Allora

 

dove la seconda linea deriva dalla disuguaglianza di Gibbs e la quarta dalla disuguaglianza di Kraft:   e dunque  .

per la seconda disuguaglianza possiamo imporre

 

in modo che

 

e quindi

 

e

 

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

 

Estensione a sorgenti indipendenti non-stazionarieModifica

Codifica di sorgente senza perdita a tasso fisso per sorgenti indipendenti discrete e non stazionarieModifica

Sia definito l'insieme tipico   come

 

Allora per un dato  , per un n grande abbastanza,  .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  . Quindi, in media,   bitn sono sufficienti per codificare la sequenza con probabilità di corretta decodifica superiore a  , dove   possono essere rese piccole a piacere aumentando n.

BibliografiaModifica

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

Voci correlateModifica

  Portale Ingegneria: accedi alle voci di Wikipedia che trattano di ingegneria