Disuguaglianza di Fano

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

Nella teoria dell'informazione, la Disuguaglianza di Fano mette in relazione l'equivocazione di un canale rumoroso con la probabilità d'errore nella decodifica di un simbolo ricevuto. È stata scoperta e dimostrata dallo scienziato Robert Fano.

Disuguaglianza di Fano

[modifica | modifica wikitesto]

Se le variabili aleatorie e rappresentano i simboli (estratti da un alfabeto di M possibili simboli) in ingresso ed in uscita ad un canale rumoroso ed hanno una densità di probabilità congiunta , il canale è affetto da una probabilità di errore

e la disuguaglianza di Fano si esprime allora come

in cui

è l'entropia condizionata, detta equivocazione in quanto rappresenta la quantità d'informazione media persa nel canale; e

è l'entropia binaria corrispondente ad una sorgente binaria stazionaria e senza memoria che emette il simbolo 1 con probabilità ed il simbolo 0 con probabilità .

La disuguaglianza di Fano fornisce quindi un limite inferiore alla probabilità d'errore; si mostra infatti che se l'entropia di X eccede la capacità del canale è impossibile che l'informazione trasmessa attraverso il canale sia ricevuta con probabilità d'errore arbitrariamente piccola.

Dimostrazione

[modifica | modifica wikitesto]

Siano e due variabili casuali e un estimatore di ottenuto dall'osservazione di . Sia la probabilità di errore.

Si consideri la variabile casuale binaria tale che:

che ha quindi una distribuzione del tipo .

Si consideri ora l'entropia:

è funzione di e e di conseguenza di e , da cui .
Si ottiene quindi

sfruttando la disuguaglianza .

A questo punto è possibile riscrivere come segue:

per il quale il primo termine del membro di destra si annulla perché dato l'incertezza sulla conoscenza di è nulla, mentre per il secondo, sapendo a priori di avere un errore, vale la disuguaglianza

dove è il numero di valori possibili che la variabile può assumere. Sostituendo in si ottiene:

dimostrando quindi l'asserto.

  • R. Fano, Transmission of information; a statistical theory of communications. Cambridge, Mass., M.I.T. Press, 1961.

Voci correlate

[modifica | modifica wikitesto]
  Portale Ingegneria: accedi alle voci di Wikipedia che trattano di ingegneria