A doua teoremă a lui Shannon

În teoria informației , a doua teoremă a lui Shannon , sau teorema de codare a canalului , stabilește că, deși un canal de comunicație este afectat de zgomot , este posibil să se transmită date ( informații ) prin canalul însuși cu probabilitatea de eroare P _și mici, după cum se dorește, până la o frecvență maximă . Acest rezultat surprinzător, cunoscut și sub numele de teorema fundamentală a teoriei informației , a fost prezentat pentru prima dată de Claude Shannon în 1948 .

Capacitatea Shannon a unui canal de comunicație, cunoscută și sub numele de limita Shannon , este rata maximă de transfer de date pe care canalul o poate furniza pentru un anumit raport semnal-zgomot , cu o rată de eroare la fel de mică pe cât se dorește.

Prezentare generală

Teorema, formulată în 1948 de Claude Shannon , descrie eficiența maximă posibilă a oricărei metode de corectare a erorilor în funcție de nivelul de zgomot. Teoria nu explică cum să construim codul optim, ci doar stabilește care este performanța codului optim. A doua teoremă a lui Shannon are numeroase aplicații, atât în domeniul telecomunicațiilor, cât și în cel al stocării datelor . Această teoremă stă la baza teoriei moderne a informației . Shannon a dat doar o urmă a dovezii. Prima dovadă riguroasă se datorează lui Amiel Feinstein în 1954 .

Teorema afirmă că, având în vedere un canal cu capacitatea C , peste care se transmit informații cu o rată R , atunci dacă

R<C

{\ displaystyle R <C}

{\ displaystyle R <C}

există un cod care face posibilă reducerea arbitrară a probabilității de eroare la receptor. Aceasta înseamnă că, teoretic, este posibilă transmiterea informațiilor fără erori ( BER = 0) cu o rată mai mică decât C.

Reversul este, de asemenea, important. De sine

R>C

{\ displaystyle R> C}

{\ displaystyle R> C}

nu este posibil să se obțină o probabilitate mică de eroare după bunul plac. Orice cod ar avea o probabilitate de eroare mai mare decât o anumită valoare mai mare decât zero și această valoare crește odată cu creșterea ratei. Prin urmare, nu este posibil să se garanteze că informațiile vor fi transmise în mod fiabil pe un canal cu o rată peste capacitate . Teorema nu ia în considerare cazul în care R și C sunt egali.

Schemele simple, cum ar fi repetarea codurilor (adică transmite un singur bit de un număr impar de ori și alege cel mai primit bit) sunt metode ineficiente de corectare a erorilor și nu pot aborda limita Shannon. Dimpotrivă, tehnicile avansate, cum ar fi codurile Reed-Solomon sau codurile Turbo , sunt mult mai aproape de limita Shannon, cu prețul unei complexități de calcul ridicate. Folosind cele mai recente coduri Turbo și puterea de calcul disponibilă pe DSP - urile actuale, este acum posibil să vă apropiați de mai puțin de 1/10 decibeli din limita Shannon.

Afirmație

Teorema (Shannon, 1948):

1. Pentru fiecare canal discret fără memorie, capacitatea canalului

C=\max _{P_{X}}\,I(X;Y)

{\ displaystyle C = \ max _ {P_ {X}} \, I (X; Y)}

{\ displaystyle C = \ max _ {P_ {X}} \, I (X; Y)}

are următoarele proprietăți. Pentru fiecare ε> 0 și R <C , pentru un N suficient de mare, există un cod de lungime N și rata ≥ R și un algoritm de decodare, astfel încât probabilitatea maximă de eroare a este ε.

2. Dacă este acceptabilă o probabilitate de eroare bit p _b , se pot realiza rate până la R (p _b ) , unde

R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.

{\ displaystyle R (p_ {b}) = {\ frac {C} {1-H_ {2} (p_ {b})}}.}

{\ displaystyle R (p_ {b}) = {\ frac {C} {1-H_ {2} (p_ {b})}}.}

Și

H_{2}(p_{b})

{\ displaystyle H_ {2} (p_ {b})}

{\ displaystyle H_ {2} (p_ {b})}

este entropia unei surse binare

H_{2}(p_{b})=-\left[p_{b}\log {p_{b}}+(1-p_{b})\log({1-p_{b}})\right]

{\ displaystyle H_ {2} (p_ {b}) = - \ left [p_ {b} \ log {p_ {b}} + (1-p_ {b}) \ log ({1-p_ {b}} ) \ dreapta]}

{\ displaystyle H_ {2} (p_ {b}) = - \ left [p_ {b} \ log {p_ {b}} + (1-p_ {b}) \ log ({1-p_ {b}} ) \ dreapta]}

3. Pentru orice p _b , rate mai mari decât R (p _b ) nu sunt realizabile.

Urmă demonstrativă

Ca și în numeroase alte rezultate fundamentale din teoria informației, dovada celei de-a doua teoreme a lui Shannon include o dovadă a accesibilității și o dovadă a inversului. Aceste două componente servesc pentru a limita, în acest caz, setul de rate posibile la care este posibil să comunicați pe un canal zgomotos și să demonstrați că aceste limite sunt limite în sens strict.

Următoarele piese sunt doar un set de numeroase metode propuse în textele teoriei informației.

Accesibilitate pentru canale discrete fără memorie

Acest detaliu de accesibilitate este similar cu cel utilizat pentru a dovedi proprietatea asimptotică a echipației (AEP).

Această tehnică folosește un argument bazat pe o alegere de cod aleatoriu, pentru care setul de cuvinte de cod (în limba engleză codebook ) este construit la întâmplare; aceasta permite reducerea complexității de calcul, dovedind în același timp existența unui cod care satisface probabilitatea dorită de eroare pentru orice rată mai mică decât capacitatea canalului.

Folosind un argument legat de AEP, dați șiruri de simboluri sursă lungi $X_{1}^{n}$ ${\ displaystyle X_ {1} ^ {n}}$ ${\ displaystyle X_ {1} ^ {n}}$ și n-șiruri lungi de ieșiri de canal $Y_{1}^{n}$ ${\ displaystyle Y_ {1} ^ {n}}$ ${\ displaystyle Y_ {1} ^ {n}}$ , putem defini un set tipic în comun după cum urmează:

$A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}$ ${\ displaystyle A _ {\ varepsilon} ^ {(n)} = \ {(x ^ {n}, y ^ {n}) \ în {\ mathcal {X}} ^ {n} \ times {\ mathcal { Y}} ^ {n}}$ ${\ displaystyle A _ {\ varepsilon} ^ {(n)} = \ {(x ^ {n}, y ^ {n}) \ în {\ mathcal {X}} ^ {n} \ times {\ mathcal { Y}} ^ {n}}$

2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}

{\ displaystyle 2 ^ {- n (H (X) + \ varepsilon)} \ leq p (X_ {1} ^ {n}) \ leq 2 ^ {- n (H (X) - \ varepsilon)}}

{\ displaystyle 2 ^ {- n (H (X) + \ varepsilon)} \ leq p (X_ {1} ^ {n}) \ leq 2 ^ {- n (H (X) - \ varepsilon)}}

2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}

{\ displaystyle 2 ^ {- n (H (Y) + \ varepsilon)} \ leq p (Y_ {1} ^ {n}) \ leq 2 ^ {- n (H (Y) - \ varepsilon)}}

{\ displaystyle 2 ^ {- n (H (Y) + \ varepsilon)} \ leq p (Y_ {1} ^ {n}) \ leq 2 ^ {- n (H (Y) - \ varepsilon)}}

{2^{-n(H(X,Y)+\varepsilon )}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\varepsilon )}\}

{\ displaystyle {2 ^ {- n (H (X, Y) + \ varepsilon)}} \ leq p (X_ {1} ^ {n}, Y_ {1} ^ {n}) \ leq 2 ^ {- n (H (X, Y) - \ varepsilon)} \}}

{\ displaystyle {2 ^ {- n (H (X, Y) + \ varepsilon)}} \ leq p (X_ {1} ^ {n}, Y_ {1} ^ {n}) \ leq 2 ^ {- n (H (X, Y) - \ varepsilon)} \}}

Să spunem două secvențe ${X_{1}^{n}}$ ${\ displaystyle {X_ {1} ^ {n}}}$ ${\ displaystyle {X_ {1} ^ {n}}}$ Și $Y_{1}^{n}$ ${\ displaystyle Y_ {1} ^ {n}}$ ${\ displaystyle Y_ {1} ^ {n}}$ sunt în comun tipice dacă se încadrează în ansamblul tipic în comun tocmai definit.

Pași

În stilul argumentului de codificare aleatorie, generăm la întâmplare $2^{nR}$ ${\ displaystyle 2 ^ {nR}}$ ${\ displaystyle 2 ^ {nR}}$ cuvinte codate de lungime n din densitatea de probabilitate Q.
Acest cod este cunoscut atât de emițător, cât și de receptor; se presupune, de asemenea, că ambii cunosc matricea de tranziție $p(y|x)$ ${\ displaystyle p (y | x)}$ ${\ displaystyle p (y | x)}$ pentru canalul utilizat.
Un mesaj W este ales în funcție de distribuția uniformă asupra setului de cuvinte cod posibil. Sau, $Pr(W=w)=2^{-nR},w=1,2,...,2^{nR}$ ${\ displaystyle Pr (W = w) = 2 ^ {- nR}, w = 1,2, ..., 2 ^ {nR}}$ ${\ displaystyle Pr (W = w) = 2 ^ {- nR}, w = 1,2, ..., 2 ^ {nR}}$ .
Mesajul este trimis pe canal.
Receptorul primește mesajul în funcție de distribuție $P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))$ ${\ displaystyle P (y ^ {n} | x ^ {n} (w)) = \ prod _ {i = 1} ^ {n} p (y_ {i} | x_ {i} (w))}$ ${\ displaystyle P (y ^ {n} | x ^ {n} (w)) = \ prod _ {i = 1} ^ {n} p (y_ {i} | x_ {i} (w))}$
Prin trimiterea cuvintelor cod pe canal, primim $Y_{1}^{n}$ ${\ displaystyle Y_ {1} ^ {n}}$ ${\ displaystyle Y_ {1} ^ {n}}$ , și decodăm la un simbol sursă dacă există exact un cuvânt cod care este tipic în comun cu Y. Dacă nu există cuvinte cod comune tipice, sau dacă există mai multe, atunci se face o eroare. De asemenea, apare o eroare atunci când un cuvânt de cod decodat nu se potrivește cu cuvântul de cod trimis. Această tehnică este menționată prin numele de codificare pentru ansamblul tipic .

Probabilitatea de eroare este împărțită în două părți:

În primul rând, poate exista eroare dacă nu există o singură secvență tipică comună X cu secvența Y primită.
În al doilea rând, poate exista o eroare dacă o secvență X incorectă este tipică în comun cu secvența Y primită.

Pe baza ipotezei aleatorii a codului, putem impune că probabilitatea medie de eroare medie pentru toate codurile nu depinde de indicele trimis. Deci putem, fără pierderea generalității, să presupunem W = 1.

Din AEP comun, știm că probabilitatea să nu existe (sau să existe mai multe) secvențe X tipice în comun, tinde la 0 pe măsură ce n crește. Putem limita această probabilitate de sus cu $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ .

De asemenea, din AEP comun, știm probabilitatea ca un anumit $X_{1}^{n(i)}$ ${\ displaystyle X_ {1} ^ {n (i)}}$ ${\ displaystyle X_ {1} ^ {n (i)}}$ iar rezultatul $Y_{1}^{n}$ ${\ displaystyle Y_ {1} ^ {n}}$ ${\ displaystyle Y_ {1} ^ {n}}$ de la W = 1 sunt împreună tipice este $\leq 2^{-n(I(X;Y)-3\varepsilon )}$ ${\ displaystyle \ leq 2 ^ {- n (I (X; Y) -3 \ varepsilon)}}$ ${\ displaystyle \ leq 2 ^ {- n (I (X; Y) -3 \ varepsilon)}}$ .

Definit:

$E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\varepsilon }^{(n)}\},i=1,2,...,2^{nR}$ ${\ displaystyle E_ {i} = \ {(X_ {1} ^ {n} (i), Y_ {1} ^ {n}) \ în A _ {\ varepsilon} ^ {(n)} \}, i = 1,2, ..., 2 ^ {nR}}$ ${\ displaystyle E_ {i} = \ {(X_ {1} ^ {n} (i), Y_ {1} ^ {n}) \ în A _ {\ varepsilon} ^ {(n)} \}, i = 1,2, ..., 2 ^ {nR}}$

evenimentul în care un mesaj este tipic în comun cu secvența primită atunci când mesajul 1 este trimis.

$P(error)=P(error|W=1)\leq P(E_{1}^{c})+\sum _{i=2}^{2^{nR}}P(E_{i})$ ${\ displaystyle P (eroare) = P (eroare | W = 1) \ leq P (E_ {1} ^ {c}) + \ sum _ {i = 2} ^ {2 ^ {nR}} P (E_ { }}}$ ${\ displaystyle P (eroare) = P (eroare | W = 1) \ leq P (E_ {1} ^ {c}) + \ sum _ {i = 2} ^ {2 ^ {nR}} P (E_ { }}}$

\leq \varepsilon +2^{-n(I(X;Y)-R-3\varepsilon )}

{\ displaystyle \ leq \ varepsilon +2 ^ {- n (I (X; Y) -R-3 \ varepsilon)}}

{\ displaystyle \ leq \ varepsilon +2 ^ {- n (I (X; Y) -R-3 \ varepsilon)}}

Putem observa că să tindem spre infinitul lui n, dacă $R<I(X;Y)$ ${\ displaystyle R <I (X; Y)}$ ${\ displaystyle R <I (X; Y)}$ pentru canal, probabilitatea de eroare tinde la zero.

În cele din urmă, după ce am arătat că setul mediu de cuvinte cod este „bun”, există cu siguranță un set de cuvinte cod a căror performanță este mai bună decât cea medie și acest lucru ne satisface nevoia de a avea o probabilitate de eroare la fel de mică pe cât ne place. pe canalul zgomotos.

Rezistență inversă slabă pentru canalele discrete fără memorie

Să presupunem că avem un cod format din $2^{nR}$ ${\ displaystyle 2 ^ {nR}}$ ${\ displaystyle 2 ^ {nR}}$ . Fie W desenat uniform pe acest set ca index. Lasa-i sa fie $X^{n}$ ${\ displaystyle X ^ {n}}$ $X ^ n$ Și $Y^{n}$ ${\ displaystyle Y ^ {n}}$ $Y ^ {n}$ cuvintele cod și respectiv cele primite

$nR=H(W)=H(W|Y^{n})+I(W;Y^{n})\;$ ${\ displaystyle nR = H (W) = H (W | Y ^ {n}) + I (W; Y ^ {n}) \;}$ ${\ displaystyle nR = H (W) = H (W | Y ^ {n}) + I (W; Y ^ {n}) \;}$ folosind egalități legate de entropie și informații reciproce .
$\leq H(W|Y^{n})+I(X^{n}(W);Y^{n})$ ${\ displaystyle \ leq H (W | Y ^ {n}) + I (X ^ {n} (W); Y ^ {n})}$ ${\ displaystyle \ leq H (W | Y ^ {n}) + I (X ^ {n} (W); Y ^ {n})}$ întrucât X este o funcție a lui W
$\leq 1+P_{e}^{(n)}nR+I(X^{n}(W);Y^{n})$ ${\ displaystyle \ leq 1 + P_ {e} ^ {(n)} nR + I (X ^ {n} (W); Y ^ {n})}$ ${\ displaystyle \ leq 1 + P_ {e} ^ {(n)} nR + I (X ^ {n} (W); Y ^ {n})}$ folosind inegalitatea Fano
$\leq 1+P_{e}^{(n)}nR+nC$ ${\ displaystyle \ leq 1 + P_ {e} ^ {(n)} nR + nC}$ ${\ displaystyle \ leq 1 + P_ {e} ^ {(n)} nR + nC}$ datorită faptului că capacitatea este maximul de informații reciproce.

Rezultatul acestor pași este că $P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}$ ${\ displaystyle P_ {e} ^ {(n)} \ geq 1 - {\ frac {1} {nR}} - {\ frac {C} {R}}}$ ${\ displaystyle P_ {e} ^ {(n)} \ geq 1 - {\ frac {1} {nR}} - {\ frac {C} {R}}}$ . Pe măsură ce tindem de la lungimea n la infinit, obținem acest lucru $P_{e}^{(n)}$ ${\ displaystyle P_ {e} ^ {(n)}}$ ${\ displaystyle P_ {e} ^ {(n)}}$ este delimitat mai sus de 0 dacă R este mai mare decât C; pe de altă parte, putem obține rate de eroare la fel de mici pe cât ne place dacă R este mai mic decât C.

Dovadă inversă puternică pentru canale discrete fără memorie

O puternică teoremă inversă, demonstrată de Wolfowitz în 1957 ^[1] , afirmă că

P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-n(R-C)}

{\ displaystyle P_ {e} \ geq 1 - {\ frac {4A} {n (RC) ^ {2}}} - e ^ {- n (RC)}}

{\ displaystyle P_ {e} \ geq 1 - {\ frac {4A} {n (R-C) ^ {2}}} - e ^ {- n (R-C)}}

pentru o constantă pozitivă $LA$ ${\ displaystyle A}$ $LA$ . În timp ce inversul slab stabilește că probabilitatea de eroare este strict mai mare decât 0 la tendința de $n$ ${\ displaystyle n}$ $n$ la infinit, teorema puternică afirmă că eroarea tinde exponențial la 1. Prin urmare, $C.$ ${\ displaystyle C}$ $C.$ este un prag care se împarte între comunicarea perfect fiabilă și comunicarea complet nesigură.

Teorema de codare a canalelor pentru canale nestatiare fără memorie

Presupunem că canalul nu are memorie, dar că probabilitățile sale de tranziție variază în funcție de timp, într-un mod cunoscut atât de emițător, cât și de receptor.

Capacitatea canalului este dată de

$C=\lim \;\inf \;\;\max _{p^{(}X_{1}),p^{(}X_{2}),...}{\frac {1}{n}}\sum _{i=1}^{n}I(X_{i};Y_{i})$ ${\ displaystyle C = \ lim \; \ inf \; \; \ max _ {p ^ {(} X_ {1}), p ^ {(} X_ {2}), ...} {\ frac {1 } {n}} \ sum _ {i = 1} ^ {n} I (X_ {i}; Y_ {i})}$ ${\ displaystyle C = \ lim \; \ inf \; \; \ max _ {p ^ {(} X_ {1}), p ^ {(} X_ {2}), ...} {\ frac {1 } {n}} \ sum _ {i = 1} ^ {n} I (X_ {i}; Y_ {i})}$

Maximul se obține pentru distribuțiile care ating capacitatea fiecărui canal, adică

$C=\lim \;\inf \;\;{\frac {1}{n}}\sum _{i=1}^{n}C_{i}$ ${\ displaystyle C = \ lim \; \ inf \; \; {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} C_ {i}}$ ${\ displaystyle C = \ lim \; \ inf \; \; {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} C_ {i}}$

unde este $C_{i}$ ${\ displaystyle C_ {i}}$ $Acolo}$ este capacitatea canalului i.

Urmă demonstrativă

Dovada urmează practic aceiași pași ca în prima teoremă a lui Shannon . Accesibilitatea provine din codarea aleatorie, fiecare simbol ales aleatoriu din distribuția atingând capacitatea pentru un anumit canal. Argumentele bazate pe tipicitate utilizează definiția dată a setului tipic pentru sursele ne staționare definite în AEP.

Limita inferioară intră în joc atunci când ${\frac {1}{n}}\sum _{i=1}^{n}C_{i}$ ${\ displaystyle {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} C_ {i}}$ ${\ displaystyle {\ frac {1} {n}} \ sum _ {i = 1} ^ {n} C_ {i}}$ nu converge.

Notă

^(RO) Robert Gallager. Teoria informației și comunicarea fiabilă. New York: John Wiley și Sons, 1968. ISBN 0-471-29048-3

Bibliografie

Claude E. Shannon , A Mathematical Theory of Urban Communication , IL: University of Illinois Press, 1949 (retipărit 1998).
Robert M. Fano , Transmiterea informațiilor; o teorie statistică a comunicațiilor. , Presa MIT, 1961.
Thomas Cover , Joy Thomas , „Elements of Information Theory”, ediția a II-a, Wiley & Sons, 2006

Elemente conexe

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

[1] (RO) Robert Gallager. Teoria informației și comunicarea fiabilă. New York: John Wiley și Sons, 1968. ISBN 0-471-29048-3

[1]