Teoria informacji/TI Wykład 11

Przedstawimy teraz centralne twierdzenie teorii informacji, autorstwa Claude Shannona. Intuicyjnie mówi ono że transmisja danych przez zaszumiony kanał jest możliwa z dowolnie małym prawdopodobieństwem błędu i z szybkością dowolnie bliską przepustowości kanału. Jedynym warunkiem jest zastosowanie kodów wystarczającej długości. Poniższa wersja odnosi się do kanałów BSC, ale można ją łatwo rozszerzyć na dowolne typy kanałów.

Twierdzenie [Twierdzenie Shannona o kodach]

Niech $\mathrm{\Gamma }$ będzie binarnym kanałem symetrycznym charakteryzowanym przez macierz $\left(\begin{array}{cc}P& Q\\ Q& P\end{array}\right)$, gdzie $P>Q$. Wtedy $\mathrm{\forall }\epsilon ,\delta >0\mathrm{\exists }{n}_0\mathrm{\forall }n\ge n_0\mathrm{\exists }C\subseteq \{0,1{\}}^n$ takie że

$C_{\mathrm{\Gamma }}-\epsilon \le R(C)\le C_{\mathrm{\Gamma }}$

$P{r}_E(\mathrm{\Delta },C)\le \delta$

Dowód Twierdzenia Shannona

Zaczniemy od przedstawienia idei dowodu. Załóżmy że ciąg wejściowy $X=a_1\dots a_n$ jest przekształcany na ciąg wyjściowy $Y=b_1\dots b_n$. Jaka jest oczekiwana odległość Hamminga między X a Y? Odpowiada ona liczbie błędów transmisji. Skoro prawdopodobieństwo każdego błędu wynosi Q, to z Prawa Wielkich Liczb wynika że d(X,Y) będzie dążyło do $Q\cdot n$ dla $n\to \mathrm{\infty }$. Jeśli reguła dekodująca powoduje błąd (czyli $\mathrm{\Delta }(Y)\ne X$), może się to stać z dwóch powodów:

• Y jest „daleko” od X (dalej niż oczekiwana odległość)
• Y jest blisko X, ale któreś $X^{\prime }\ne X$ jest równie blisko jak X

Pierwszy typ błędów jest powodowany przez kanał, ale sama natura go poprawia: Prawo Wielkich Liczb gwarantuje że duża odległość pomiędzy X a Y będzie występować rzadko jeśli n jest duże. Za drugi typ błędów odpowiada sam kod. Aby nie zachodziły takie sytuacje, słowa kodowe muszą być odpowiednio odległe od siebie nawzajem. W naszym przypadku oznacza to że jeśli wyznaczymy wokół każdego ze słów kodowych kulę o promieniu $Q\cdot n$ (w metryce Hamminga), to kule te powinny być parami rozłączne. Pytanie zatem brzmi: ile rozłącznych kul o tym promieniu można zmieścić w $\{0,1{\}}^n$? Objętość każdej z tych kul, co udowodnimy, wynosi w przybliżeniu $\approx 2^{n\cdot H(Q)}$. Oznacza to że maksymalna możliwa liczba kul jest nie większa niż

$m\approx 2^n:2^{n\cdot H(Q)}=2^{n(1-H(Q))}=2^{n\cdot C_{\mathrm{\Gamma }}}$

co odpowiada szybkości transmisji $R(C)\approx C_{\mathrm{\Gamma }}$. Niezwykłość odkrycia Shannona polega na tym że to dolne ograniczenie daje się osiągnąć. Niestety sam dowód jest niekonstruktywny, i pokazuje jedynie że taki kod istnieje.

W dalszej części dowodu będziemy używać małych liter $u,v,w,x,y,\dots$ na oznaczenie wektorów w $\{0,1{\}}^n$, dla odróżnienia od zmiennych losowych. Jak zwykle $\oplus$ oznaczać będzie XOR po współrzędnych. Wybierzemy $\eta >0$ którego zależność od $ϵ$ i $\delta$ wyznaczymy dokładnie później (intuicyjnie, $\eta$ będzie bardzo małe). Niech

$\rho =n(Q+\eta )$

Załóżmy teraz że $C\subseteq \{0,1{\}}^n$ jest kodem z $|C|=m$. Z definicji reguły $\mathrm{\Delta }$, jeśli dla pewnego słowa kodowego $u\in C$ i błędu $e\in \{0,1{\}}^n$ mamy odległość $d(u,u\oplus e)\le \rho$, a ponadto $\mathrm{\forall }v\in C-\{u\}d(v,u\oplus e)>\rho$, to u jest najbliższym słowem kodowym do $u\oplus e$ i z konieczności $\mathrm{\Delta }(u\oplus e)=u$.

Zatem jeśli $\mathrm{\Delta }(u\oplus e)\ne u$ to albo $d(u,u\oplus e)>\rho$, albo dla pewnego $v\in C-\{u\}d(v,u\oplus e)\le \rho$.

Wektor e możemy interpretować jako wartość zmiennej losowej $E=(E_1,\dots ,E_n)$, gdzie $E_i=A_i\oplus B_i$. Zmienne $E_1,\dots ,E_n$ są niezależne i mają identyczny rozkład

$p(E_i=0)=P$

$p(E_i=1)=Q$

Powyższe obserewacje można zatem zapisać jako

$p(\mathrm{\Delta }(u\oplus E)\ne u)\le p(d(u,u\oplus E)>\rho )+\sum _{v\in C-\{u\}}p(d(v,u\oplus E)\le \rho )$

Pierwszy składnik oszacujemy używając następującego faktu

Fakt [Słabe Prawo Wielkich Liczb]

Niech $X_1,X_2,\dots$ będą zmiennymi losowymi takimi że każda sekwencja $X_1,X_2,\dots ,X_n$ jest parami niezależna, i $X_i$ mają ten sam rozkład nad skończonym zbiorem liczb rzeczywistych. Niech $\mu =E(X_i)$. Wtedy dla dowolnego $\alpha >0$

$\underset{n\to \mathrm{\infty }}{\lim }p(|\frac{1}{n}\sum _{i=1}^n{X}_i-\mu |>\alpha )=0$

W naszym przypadku stosujemy ten fakt do sekwencji $E_1,E_2,\dots$. Wiemy że $E(E_i)=0\cdot P+1\cdot Q=Q$. Zatem $p(|\frac{1}{n}\cdot \sum _{i=1}^n{E}_i-Q|>\eta )\to 0$ dla $n\to \mathrm{\infty }$ i dostajemy

$p(d(u,u\oplus E)>\rho )\le p(\frac{1}{n}\cdot \sum _{i=1}^n{E}_i>Q+\eta )\le p(|\frac{1}{n}\cdot \sum _{i=1}^n{E}_i-Q|>\eta )\le \frac{\delta }{2}$

dla wystarczająco dużych n.

Przypomnijmy że szacujemy $P{r}_E(\mathrm{\Delta },C)$, które możemy przedstawić jako sumę

$P{r}_E(\mathrm{\Delta },C)=\sum _{u\in C}p(X=u)\cdot p(\mathrm{\Delta }\circ Y\ne u|X=u)$.

Z definicji $Y=X\oplus E$ a więc

$p(Y=w|X=u)=p(E=w\oplus u)$

Zatem

$p(\mathrm{\Delta }\circ Y\ne u|X=u)=\sum _{v:\mathrm{\Delta }(v)\ne u}p(Y=v|X=u)$

$=\sum _{e:\mathrm{\Delta }(u\oplus e)\ne u}p(Y=u\oplus e)|X=u)$

$=\sum _{e:\mathrm{\Delta }(u\oplus e)\ne u}p(E=e)$

$=p(\mathrm{\Delta }(u\oplus E)\ne u)$

Ponadto $p(X=u)=\frac{1}{m}$ (z założenia rozkład X jest jednorodny). Razem z (link TODO) daje nam to $P{r}_E(\mathrm{\Delta },C)\le \frac{1}{m}\sum _{u\in C}(p(d(u,u\oplus E)>\rho )+\sum _{v\in C-\{u\}}p(d(v,u\oplus E)\le \rho ))$

$\le \frac{\delta }{2}+\frac{1}{m}\sum _{u\in C}\sum _{v\in C-\{u\}}p(d(v,u\oplus E)\le \rho )$

dla wystarczająco dużych n.

Zanim przejdziemy dalej, oszacujmy najpierw objętość kuli o promieniu $\lambda \cdot n$, gdzie $\lambda \le \frac{1}{2}$. Konkretnie pokażemy że

$\sum _{i\le \lambda \cdot n}(\genfrac{}{}{0ex}{}{n}{i})\le 2^{n\cdot H(\lambda )}$

gdzie H jest zdefiniowane jak (link TODO).

Niech $\kappa =1-\lambda$. Zauważmy najpierw że

${\log }_2({\lambda }^{\lambda n}\cdot {\kappa }^{\kappa n})=n\cdot (\lambda \cdot {\log }_2\lambda +\kappa \cdot {\log }_2\kappa )$

$=-n\cdot H(\lambda )$

Wystarczy zatem że pokażemy że dla dowolnych $i\le \lambda n$

${\lambda }^i{\kappa }^{n-i}\ge {\lambda }^{\lambda n}\cdot {\kappa }^{\kappa n}$

Wtedy

$1\ge \sum _{i\le \lambda \cdot n}(\genfrac{}{}{0ex}{}{n}{i}){\lambda }^i{\kappa }^{n-i}\ge \sum _{i\le \lambda \cdot n}(\genfrac{}{}{0ex}{}{n}{i}){\lambda }^{\lambda n}\cdot {\kappa }^{\kappa n}$

w więc

$\sum _{i\le \lambda \cdot n}(\genfrac{}{}{0ex}{}{n}{i})\le \frac{1}{{\lambda }^{\lambda n}\cdot {\kappa }^{\kappa n}}=2^{n\cdot H(\lambda )}$

jak zakładaliśmy.

Jeśli $\lambda n$ jest całkowite, nasza nierówność jest po prostu równością. Jeśli nie, mamy $\lambda n=\lfloor \lambda n\rfloor +\mathrm{\Delta }\lambda$, $\kappa n=\lfloor \kappa n\rfloor +\mathrm{\Delta }\kappa$, $\lfloor \lambda n\rfloor +\lfloor \kappa n\rfloor =n-1$ i $\mathrm{\Delta }\lambda +\mathrm{\Delta }\kappa =1$. Z założenia $\kappa \ge \lambda$, i mamy dla dowolnego Parser nie mógł rozpoznać (nieznana funkcja „\n”): {\displaystyle i \le \lambda \n }

${\lambda }^i{\kappa }^{n-i}\ge {\lambda }^{\lfloor \lambda n\rfloor }\cdot {\kappa }^{\lfloor \kappa n\rfloor +1}={\lambda }^{\lfloor \lambda n\rfloor }\cdot {\kappa }^{\lfloor \kappa n\rfloor }\underset{\ge {\lambda }^{\mathrm{\Delta }\lambda }\cdot {\kappa }^{\mathrm{\Delta }\kappa }}{\underbrace{{\kappa }^{\mathrm{\Delta }\lambda +\mathrm{\Delta }\kappa }}}\ge {\lambda }^{\lambda n}\cdot {\kappa }^{\kappa n}$.

co kończy dowód szacowania objętości.