Teoria informacji/TI Wykład 12

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

Wracamy do szacowania . Przypomnijmy, że wyprowadzone na poprzednim wykładzie szacowanie 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 szacowania 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 to

Nasze szacowanie daje zatem


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ą: jest spełniona).

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, tzn.

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

Na poprzednim wykładzie dokonaliśmy oszacowania rozmiaru kuli o promieniu , mamy zatem

Możemy już oszacować (**):

Pamiętając, że , otrzymujemy stąd również szacowanie dla (*):


Wracając do głównego szacowania, dostajemy

Parser nie mógł rozpoznać (nieznana funkcja „\pr”): {\displaystyle \begin{align} \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 )} \\ & = \frac{\delta }{2} + \frac{1}{m} \cdot m \cdot \underbrace{(m-1) \cdot \frac{1}{2^n - 1}}_{\leq \frac{m}{2^n}} \cdot 2^{n \cdot H(Q + \eta )} \\ & \leq \frac{\delta }{2} + \frac{m}{2^n} \cdot 2^{n \cdot H(Q + \eta )} \\ & = \frac{\delta }{2} + 2^{ n \cdot \left( \frac{\log_2 m}{n} + H(Q + \eta ) - 1 \right) } \end{align} }

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, powiedzmy , i dla dowolnych , Parser nie mógł rozpoznać (błąd składni): {\displaystyle 0 < \eta < \frac{1}{2} – Q} . Twierdzimy, że można dobrać m i 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, 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 i spełniający oba konieczne warunki najłatwiej przedstawimy na diagramie

Teoria Informacji diag1.PNG

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