Teoria informacji/TI Wykład 11

Z Studia Informatyczne
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

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

Łącząc te wyniki, dostajemy

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

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

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