Teoria informacji/TI Wykład 12

Z Studia Informatyczne
< Teoria informacji
Wersja z dnia 09:55, 1 sie 2006 autorstwa Stromy (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wracamy do szacowania . Przypomnijmy że (link TODO) obowiązuje dla dowolnego kodu C, o ile n jest wystarczająco duże. Pokażemy teraz że dla wystarczająco dużych n istnieje kod C który spełnia warunki Twierdzenia Shannona. W szczególności taki dla którego drugi składnik (link TODO) można ograniczyć z góry przez .

Do dowodu użyjemy metody probabilistycznej. Ustalmy . Niech będzie zbiorem wszystkich możliwych m-elementowych sekwencji takich że są parami różne. Niech .

Od tego miejsca będziemy używać notacji na oznaczenie sekwencji z . Argument probabilistyczny Shannona opiera się na prostej obserwacji. Jeśli

to istnieje kod C taki że .

Zauważmy że jeśli jest sekwencją w o wartościach Parser nie mógł rozpoznać (nieznana funkcja „\c”): {\displaystyle C=\{c_1, \ldots, \c_m \}} to

A z (link TODO) dostajemy

Parser nie mógł rozpoznać (nieznana funkcja „\pr”): {\displaystyle \frac{1}{N} \sum_{\bar{C}} \pr_E ( \Delta , \bar{C} ) \leq \frac{1}{N} \sum_{\bar{C}} \left( \frac{\delta }{2} + \frac{1}{m} \sum_{i = 1}^m \sum_{j \neq i} \, p ( d (c_j,c_i \oplus E) \leq \rho ) \right) }


Oszacujemy teraz (*) dla ustalonej pary indeksów .

Dla niech oznacza kulę w o promieniu i środku w punkcie e, tzn.

Łatwo zauważyć że

Zatem

(gdzie oznacza funkcję charakterystyczną ).

Możemy oszacować teraz wartość (**) dla ustalonego e. Z pewnością każdy wektor inny niż pojawia się jako dla pewnej sekwencji , i łatwo zauważyć że każdy taki wektor pojawia się taką samą liczbę razy

dla dowolnych . A zatem każde dodaje do sumy , czyli

Możemy to teraz zsumować po możliwych wartościach e:

Znamy ponadto objętość , więc

Wracając do równania (link TODO) daje to

Parser nie mógł rozpoznać (nieznana funkcja „\pr”): {\displaystyle \frac{1}{N} \sum_{\bar{C}} \, \pr_E ( \Delta , \bar{C} ) \leq \frac{\delta }{2} + \frac{1}{m} \sum_{i = 1}^m \sum_{j \neq i} \frac{1}{2^n - 1} \cdot 2^{n \cdot H(Q + \eta )}}

Jesteśmy tu już blisko celu, gdyż odpowiada „prawie” .

Konkretniej, do tej pory wiemy że powyższe równanie jest spełnione dla wystarczająco dużych n, np. , i dla , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 < \eta < \frac{1}{2} – Q} . Twierdzimy że można dobrać m i </math>\eta</math> w ten sposób że dla dowolnego spełnione jest

Parser nie mógł rozpoznać (nieznana funkcja „\label”): {\displaystyle C_{\Gamma } - \varepsilon \leq \frac{\log_2 m}{n} \leq C_{\Gamma } \label{(i)} }

W szczególności druga nierówność implikuje

A więc jeśli n jest wystarczająco duże, to dostajemy

Parser nie mógł rozpoznać (nieznana funkcja „\pr”): {\displaystyle \frac{1}{N} \sum_{\bar{C}} \, \pr_E ( \Delta , \bar{C} ) \leq \frac{\delta }{2} + \frac{\delta }{2} = \delta }

Używając argumentu probabilistycznego wnioskujemy że musi istnieć kod C rozmiaru m, spełniający . Ponieważ , ten kod spełnia warunki Shannona.

Wybór spełniający warunki (link TODO) najłatwiej przedstawić na diagramie

(Rysunek TODO)

Używając ciągłości H, wybieramy takie że . Jeśli n jest wystarczająco duże, to potem możemy znaleźć k takie że . Tym samym oba warunki są spełnione, co kończy dowód.