Primo teorema di Shannon

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

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

[modifica | modifica wikitesto]

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

[modifica | modifica wikitesto]

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: , 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: , dove è la durata del simbolo.
  • La velocità di trasmissione media dell'informazione del sistema, o bitrate, si calcola con: .

Altri parametri importanti si riassumono in:

  • Lunghezza media del simbolo (ni=lunghezza del codice)
  • Rendimento del codice (η assume valori da 0 a 1)
  • Ridondanza .

Teorema della codifica di sorgente

[modifica | modifica wikitesto]

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

« variabili casuali i.i.d., ognuna con entropia possono essere compresse in più di bit con una probabilità di perdita di informazione piccola a piacere, al tendere di all'infinito; al contrario, se sono compresse in meno di bit è virtualmente certo che una parte dell'informazione andrà persa.»

Teorema della codifica di sorgente per simboli di codice

[modifica | modifica wikitesto]

Sia una variabile casuale a valori in un alfabeto finito e sia un codice decifrabile (ossia una funzione univoca) da a , dove . Sia S la risultante lunghezza della parola di codice .

Se è ottima nel senso che ha la minima lunghezza attesa per la parola di codice , allora

(Shannon 1948)

Dimostrazione: teorema della codifica di sorgente

[modifica | modifica wikitesto]

Siano una sorgente di variabili i.i.d. e una serie di uscite con entropia 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 largo abbastanza, la probabilità che una sequenza generata dalla sorgente cada nell'insieme tipico, , tende ad uno. In particolare per un 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 codice

[modifica | modifica wikitesto]

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

Allora

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

Estensione a sorgenti indipendenti non-stazionarie

[modifica | modifica wikitesto]

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

[modifica | modifica wikitesto]

Sia definito l'insieme tipico come

Allora per un dato , per un 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 .

Voci correlate

[modifica | modifica wikitesto]