Teoria informacji/TI Wykład 11: Różnice pomiędzy wersjami
m (Zastępowanie tekstu - "\endaligned" na "\end{align}") |
m (Zastępowanie tekstu - "\aligned" na "\begin{align}") |
||
Linia 60: | Linia 60: | ||
Zatem | Zatem | ||
− | <center><math>\ | + | <center><math>\begin{align} |
p (\Delta \circ Y \neq u | X = u) & = \sum_{v:\Delta (v) \neq u} p ( Y = v | X = u)\\ | 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 ( Y = u \oplus e) | X = u) \\ | ||
Linia 71: | Linia 71: | ||
Łącząc te wyniki, dostajemy | Łącząc te wyniki, dostajemy | ||
− | <center>{{kotwica|metoda_prob|}}<math>\ | + | <center>{{kotwica|metoda_prob|}}<math>\begin{align} |
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) \\ | 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 ) | & \leq \frac{\delta }{2} + \frac{1}{m} \sum_{u \in C} \sum_{v \in C - \{ u \}} p ( d (v,u \oplus E) \leq \rho ) | ||
Linia 86: | Linia 86: | ||
Niech <math>\kappa = 1 - \lambda</math>. Zauważmy najpierw, że | Niech <math>\kappa = 1 - \lambda</math>. Zauważmy najpierw, że | ||
− | <center><math>\ | + | <center><math>\begin{align} |
\log_2 (\lambda^{\lambda n} \cdot \kappa^{\kappa n}) & = n \cdot ( \lambda \cdot \log_2 \lambda + \kappa \cdot \log_2 \kappa )\\ | \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 ) | & = - n \cdot H(\lambda ) |
Wersja z 12:43, 9 cze 2020
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 żeoraz
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ładPowyż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ęcZatem
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, żeWystarczy 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.