Teoria informacji/TI Wykład 11

Z Studia Informatyczne
< Teoria informacji
Wersja z dnia 12:33, 9 cze 2020 autorstwa Luki (dyskusja | edycje) (Zastępowanie tekstu - "\endaligned" na "\end{align}")
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 będzie binarnym kanałem symetrycznym, charakteryzowanym przez macierz , gdzie . Wtedy takie że

oraz


Dowód Twierdzenia Shannona

Zaczniemy od przedstawienia idei dowodu. Załóżmy, że ciąg wejściowy jest przekształcany na ciąg wyjściowy . 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 dla . Jeśli reguła dekodująca powoduje błąd (czyli ), 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ś 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 (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 ? Objętość każdej z tych kul, co udowodnimy, wynosi w przybliżeniu . Oznacza to, że maksymalna możliwa liczba kul jest nie większa niż

co odpowiada szybkości transmisji . 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 na oznaczenie wektorów w dla odróżnienia od zmiennych losowych. Jak zwykle oznaczać będzie XOR po współrzędnych. Wybierzemy , którego zależność od i wyznaczymy dokładnie później (intuicyjnie, będzie bardzo małe). Niech

Załóżmy teraz, że jest kodem z . Z definicji reguły , jeśli dla pewnego słowa kodowego i błędu mamy odległość , a ponadto , to jest najbliższym słowem kodowym do i z konieczności .

Zatem jeśli , to albo , albo dla pewnego .

Wektor e możemy interpretować jako wartość zmiennej losowej , gdzie . Zmienne są niezależne i mają identyczny rozkład

Powyższe obserewacje można zatem zapisać jako

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


Fakt [Słabe Prawo Wielkich Liczb]

Niech będą zmiennymi losowymi takimi, że każda sekwencja jest parami niezależna, i mają ten sam rozkład nad skończonym zbiorem liczb rzeczywistych. Niech . Wtedy dla dowolnego


W naszym przypadku stosujemy ten fakt do sekwencji . Wiemy, że . Zatem dla i dostajemy

dla wystarczająco dużych n.


Przypomnijmy, że szacujemy , które możemy przedstawić jako sumę

Z definicji , a więc

Zatem

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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{align} }

Ponadto (z założenia rozkład X jest jednorodny).

Łącząc te wyniki, dostajemy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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{align} }

dla wystarczająco dużych n.


Zanim przejdziemy dalej, oszacujmy najpierw objętość kuli o promieniu , gdzie . Konkretnie pokażemy, że

Niech . Zauważmy najpierw, że

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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{align} }

Wystarczy zatem, że pokażemy, że dla dowolnych

Wtedy

a więc

jak zakładaliśmy.


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

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