Teoria informacji/TI Wykład 11

Przedstawimy teraz centralne twierdzenie teorii informacji, autorstwa Claude'a 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 $\Gamma$ będzie binarnym kanałem symetrycznym, charakteryzowanym przez macierz $\left({\begin{matrix}P&Q\\Q&P\end{matrix}}\right)$, gdzie $P>Q$. Wtedy $\forall \varepsilon ,\delta >0\,\exists n_{0}\forall n\geq n_{0}\exists C\subseteq \{0,1\}^{n}$ takie że

$C_{\Gamma }-\varepsilon \leq R(C)\leq C_{\Gamma }$

oraz

$Pr_{E}(\Delta ,C)\leq \delta$

Dowód Twierdzenia Shannona

Zaczniemy od przedstawienia idei dowodu. Załóżmy, że ciąg wejściowy $X=a_{1}\ldots a_{n}$ jest przekształcany na ciąg wyjściowy $Y=b_{1}\ldots 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 \infty$. Jeśli reguła dekodująca powoduje błąd (czyli $\Delta (Y)\neq 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'\neq 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_{\Gamma }}$

co odpowiada szybkości transmisji $R(C)\approx C_{\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,\ldots$ 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 $\epsilon$ 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 $\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)\leq \rho$, a ponadto $\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 $\Delta (u\oplus e)=u$.

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

Wektor e możemy interpretować jako wartość zmiennej losowej $E=(E_{1},\ldots ,E_{n})$, gdzie $E_{i}=A_{i}\oplus B_{i}$. Zmienne $E_{1},\ldots ,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(\Delta (u\oplus E)\neq u)\leq p(d(u,u\oplus E)>\rho )+\sum _{v\in C-\{u\}}p(d(v,u\oplus E)\leq \rho )$

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

Fakt [Słabe Prawo Wielkich Liczb]

Niech $X_{1},X_{2},\ldots$ będą zmiennymi losowymi takimi, że każda sekwencja $X_{1},X_{2},\ldots ,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$

$\lim _{n\to \infty }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},\ldots$. 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 \infty$ i dostajemy

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

dla wystarczająco dużych n.

Przypomnijmy, że szacujemy $Pr_{E}(\Delta ,C)$, które możemy przedstawić jako sumę

$Pr_{E}(\Delta ,C)=\sum _{u\in C}p(X=u)\cdot p(\Delta \circ Y\neq u|X=u)$

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

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

Zatem

${\begin{aligned}p(\Delta \circ Y\neq u|X=u)&=\sum _{v:\Delta (v)\neq u}p(Y=v|X=u)\\&=\sum _{e:\Delta (u\oplus e)\neq u}p(Y=u\oplus e)|X=u)\\&=\sum _{e:\Delta (u\oplus e)\neq u}p(E=e)\\&=p(\Delta (u\oplus E)\neq u)\end{aligned}}$

Ponadto $p(X=u)={\frac {1}{m}}$ (z założenia rozkład X jest jednorodny).

Łącząc te wyniki, dostajemy

${\begin{aligned}Pr_{E}(\Delta ,C)&\leq {\frac {1}{m}}\sum _{u\in C}\left(p(d(u,u\oplus E)>\rho )+\sum _{v\in C-\{u\}}p(d(v,u\oplus E)\leq \rho )\right)\\&\leq {\frac {\delta }{2}}+{\frac {1}{m}}\sum _{u\in C}\sum _{v\in C-\{u\}}p(d(v,u\oplus E)\leq \rho )\end{aligned}}$

dla wystarczająco dużych n.

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

$\sum _{i\leq \lambda \cdot n}{n \choose i}\leq 2^{n\cdot H(\lambda )}$

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

${\begin{aligned}\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 )\end{aligned}}$

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

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

Wtedy

$1\geq \sum _{i\leq \lambda \cdot n}{n \choose i}\lambda ^{i}\kappa ^{n-i}\geq \sum _{i\leq \lambda \cdot n}{n \choose i}\lambda ^{\lambda n}\cdot \kappa ^{\kappa n}$

a więc

$\sum _{i\leq \lambda \cdot n}{n \choose i}\leq {\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 +\Delta \lambda$, $\kappa n=\lfloor \kappa n\rfloor +\Delta \kappa$, $\lfloor \lambda n\rfloor +\lfloor \kappa n\rfloor =n-1$ i $\Delta \lambda +\Delta \kappa =1$. Z założenia $\kappa \geq \lambda$, i mamy dla dowolnego $i\leq \lambda n$

$\lambda ^{i}\kappa ^{n-i}\geq \lambda ^{\lfloor \lambda n\rfloor }\cdot \kappa ^{\lfloor \kappa n\rfloor +1}=\lambda ^{\lfloor \lambda n\rfloor }\cdot \kappa ^{\lfloor \kappa n\rfloor }\underbrace {\kappa ^{\Delta \lambda +\Delta \kappa }} _{\geq \lambda ^{\Delta \lambda }\cdot \kappa ^{\Delta \kappa }}\geq \lambda ^{\lambda n}\cdot \kappa ^{\kappa n}$

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