Fano inegalitate

În teoria informației , Inegalitatea lui Fano raportează echivocarea unui canal zgomotos cu probabilitatea de eroare în decodarea unui simbol primit. A fost descoperit și dovedit de omul de știință Robert Fano .

Fano inegalitate

Dacă variabilele aleatorii $X=x_{i}$ ${\ displaystyle X = x_ {i}}$ ${\ displaystyle X = x_ {i}}$ Și $Y=y_{j}$ ${\ displaystyle Y = y_ {j}}$ ${\ displaystyle Y = y_ {j}}$ reprezintă simbolurile (extrase dintr-un alfabet de M simboluri posibile) la intrarea și ieșirea unui canal zgomotos și au o densitate de probabilitate comună $P(x,y)$ ${\ displaystyle P (x, y)}$ $P (x, y)$ , canalul este afectat de o probabilitate de eroare

P(e)=\sum _{i=0}^{M-1}\sum _{j\not =i}P(y_{j},x_{i})

{\ displaystyle P (e) = \ sum _ {i = 0} ^ {M-1} \ sum _ {j \ not = i} P (y_ {j}, x_ {i})}

{\ displaystyle P (e) = \ sum _ {i = 0} ^ {M-1} \ sum _ {j \ not = i} P (y_ {j}, x_ {i})}

iar inegalitatea lui Fano este apoi exprimată ca

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

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

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

in care

H\left(X|Y\right)=-\sum _{i,j}P(x_{i},y_{j})\log P\left(x_{i}|y_{j}\right)

{\ displaystyle H \ left (X | Y \ right) = - \ sum _ {i, j} P (x_ {i}, y_ {j}) \ log P \ left (x_ {i} | y_ {j} \ dreapta)}

{\ displaystyle H \ left (X | Y \ right) = - \ sum _ {i, j} P (x_ {i}, y_ {j}) \ log P \ left (x_ {i} | y_ {j} \ dreapta)}

este entropia condițională, numită echivocare, deoarece reprezintă cantitatea medie de informații pierdute în canal; Și

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

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

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

este entropia binară corespunzătoare unei surse binare staționare și fără memorie care emite simbolul 1 cu probabilitate $P(e)$ ${\ displaystyle P (e)}$ ${\ displaystyle P (e)}$ și simbolul 0 cu probabilitate $1-P(e)$ ${\ displaystyle 1-P (e)}$ ${\ displaystyle 1-P (e)}$ .

Inegalitatea Fano oferă deci o limită inferioară a probabilității de eroare; de fapt, se arată că, dacă entropia lui X depășește capacitatea canalului, este imposibil ca informațiile transmise prin canal să fie primite cu o probabilitate de eroare arbitrar scăzută.

Demonstrație

Lasa-i sa fie $X$ ${\ displaystyle X}$ $X$ Și $Da$ ${\ displaystyle Y}$ $Da$ două variabile aleatorii e ${\tilde {X}}=f(Y)$ ${\ displaystyle {\ tilde {X}} = f (Y)}$ ${\ displaystyle {\ tilde {X}} = f (Y)}$ un admirator al $X$ ${\ displaystyle X}$ $X$ obținut din observarea $Da$ ${\ displaystyle Y}$ $Da$ . Este $P(e)=P[X\neq {\tilde {X}}]$ ${\ displaystyle P (e) = P [X \ neq {\ tilde {X}}]}$ ${\ displaystyle P (e) = P [X \ neq {\ tilde {X}}]}$ probabilitatea de eroare.

Luați în considerare variabila aleatoare binară $ȘI$ ${\ displaystyle E}$ $ȘI$ astfel încât:

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

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

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

care are deci o distribuție de tip $p_{E}=(1-P(e),P(e))$ ${\ displaystyle p_ {E} = (1-P (e), P (e))}$ ${\ displaystyle p_ {E} = (1-P (e), P (e))}$ .

Acum ia în considerare entropia:

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

{\ displaystyle H (X, E | Y) = H (X | Y) + H (E | X, Y) = H (E | Y) + H (X | E, Y)}

{\ displaystyle H (X, E | Y) = H (X | Y) + H (E | X, Y) = H (E | Y) + H (X | E, Y)}

$ȘI$ ${\ displaystyle E}$ $ȘI$ este o funcție a $X$ ${\ displaystyle X}$ $X$ Și ${\tilde {X}}$ ${\ displaystyle {\ tilde {X}}}$ ${\ displaystyle {\ tilde {X}}}$ și în consecință a $X$ ${\ displaystyle X}$ $X$ Și $Da$ ${\ displaystyle Y}$ ${\ displaystyle Y}$ , de la care $H(E|X,Y)=0$ ${\ displaystyle H (E | X, Y) = 0}$ ${\ displaystyle H (E | X, Y) = 0}$ .
Se obține astfel

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

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

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

exploatarea inegalității $H(E|Y)\leq H(E)=H(e)$ ${\ displaystyle H (E | Y) \ leq H (E) = H (e)}$ ${\ displaystyle H (E | Y) \ leq H (E) = H (e)}$ .

În acest moment este posibil să rescriem $H(X|E,Y)$ ${\ displaystyle H (X | E, Y)}$ ${\ displaystyle H (X | E, Y)}$ după cum urmează:

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

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

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

pentru care primul termen al membrului din dreapta este anulat deoarece este dat $E=0$ ${\ displaystyle E = 0}$ ${\ displaystyle E = 0}$ incertitudine cu privire la cunoașterea $X$ ${\ displaystyle X}$ $X$ este nul, în timp ce pentru al doilea, știind a priori că există o eroare, inegalitatea se menține

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

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

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

unde este $|{\mathcal {X}}|$ ${\ displaystyle | {\ mathcal {X}} |}$ ${\ displaystyle | {\ mathcal {X}} |}$ este numărul de valori posibile pe care variabila $X$ ${\ displaystyle X}$ $X$ poate presupune. Prin înlocuire ${\mbox{(2)}}$ ${\ displaystyle {\ mbox {(2)}}}$ ${\ displaystyle {\ mbox {(2)}}}$ în ${\mbox{(1)}}$ ${\ displaystyle {\ mbox {(1)}}}$ ${\ displaystyle {\ mbox {(1)}}}$ primesti:

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

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

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

dovedind astfel revendicarea.

Bibliografie

R. Fano, Transmiterea informațiilor; o teorie statistică a comunicațiilor. Cambridge, Mass., MIT Press, 1961.

Elemente conexe

Portal de inginerie : accesați intrările Wikipedia care se ocupă de inginerie