Disuguaglianza di Fano

Da Wikipedia, l'enciclopedia libera.

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 X=x_i e Y=y_j 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 P(x,y), il canale è affetto da una probabilità di errore

P(e)=\sum_{i=0}^{M-1} \sum_{j\not=i} P(y_j,x_i)

e la disuguaglianza di Fano si esprime allora come

H(X|Y)\leq H(e)+P(e)\log(M-1),

in cui

H\left(X|Y\right)=-\sum_{i,j} P(x_i,y_j)\log P\left(x_i|y_j\right)

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

H\left(e\right)=-P(e)\log P(e)-(1-P(e))\log(1-P(e))

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

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]

Bibliografia[modifica | modifica wikitesto]

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


Voci correlate[modifica | modifica wikitesto]

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