Teoria informacji/TI Wykład 11

From Studia Informatyczne

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) \le \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

\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) \endaligned

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

Łącząc te wyniki, dostajemy

\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 ) \endaligned

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

\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 ) \endaligned

Wystarczy zatem, że pokażemy, że dla dowolnych i \le \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 \ge \lambda, i mamy dla dowolnego i \le \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.