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]

Siano X e Y due variabili casuali e \tilde{X} = f(Y) un estimatore di X ottenuto dall'osservazione di Y. Sia P(e)=P[X\neq\tilde{X}] la probabilità di errore.

Si consideri la variabile casuale binaria E tale che:

E=\begin{cases} 1 & \mbox{se } X\neq\tilde{X} \\ 0 & \mbox{se } X=\tilde{X} \end{cases}

che ha quindi una distribuzione del tipo p_E=(1-P(e), P(e)).

Si consideri ora l'entropia:

H(X,E|Y) = H(X|Y) + H(E|X,Y) = H(E|Y) + H(X|E,Y)


E è funzione di X e \tilde{X} e di conseguenza di X e  Y, da cui H(E|X,Y) = 0.
Si ottiene quindi

H(X|Y) = H(E|Y) + H(X|E,Y) \leq H(e) + H(X|E,Y) \ \ \ \  \mbox{   (1)}

sfruttando la disuguaglianza H(E|Y)\leq H(E)=H(e).

A questo punto è possibile riscrivere H(X|E,Y) come segue:

H(X|E,Y)=p_E(0)H(X|Y, E=0)+p_E(1)H(X|Y, E=1) \ \ \ \  \mbox{  (2)}

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

H(X|Y, E=1) \leq \log(|\mathcal{X}|-1)

dove  |\mathcal{X}| è il numero di valori possibili che la variabile X può assumere. Sostituendo \mbox{(2)} in \mbox{(1)} si ottiene:

H(X|Y) \leq H(e) + p(e)\log(|\mathcal{X}|-1)

dimostrando quindi l'asserto.

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