Teoria informacji/TI Wykład 12: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m (Zastępowanie tekstu - "\aligned" na "\begin{align}")
m
 
Linia 77: Linia 77:
  
 
<center><math>\begin{align}
 
<center><math>\begin{align}
\frac{1}{N} \sum_{\bar{C}} \, \pr_E ( \Delta , \bar{C} ) & \leq
+
\frac{1}{N} \sum_{\bar{C}} \, _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} \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 )} \\
 
& = \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 )} \\
Linia 87: Linia 87:
 
Jesteśmy tu już blisko celu, gdyż <math>\left(  \frac{\log_2 m}{n} + H(Q + \eta ) - 1 \right)</math> odpowiada „prawie” <math>R(C)-C_{\Gamma}</math>.
 
Jesteśmy tu już blisko celu, gdyż <math>\left(  \frac{\log_2 m}{n} + H(Q + \eta ) - 1 \right)</math> odpowiada „prawie” <math>R(C)-C_{\Gamma}</math>.
  
Konkretniej, do tej pory wiemy, że powyższe równanie jest spełnione dla wystarczająco dużych n, powiedzmy <math> n \ge n_1 </math>, i dla dowolnych <math>2 \le m \le 2^n</math>, <math>0 < \eta < \frac{1}{2} Q</math>. Twierdzimy, że można dobrać <math>n_0 \ge n_1</math> m i <math>\eta</math> w ten sposób, że dla dowolnego <math>n \ge n_0</math> spełnione jest
+
Konkretniej, do tej pory wiemy, że powyższe równanie jest spełnione dla wystarczająco dużych n, powiedzmy <math> n \ge n_1 </math>, i dla dowolnych <math>2 \le m \le 2^n</math>, <math>0 < \eta < \frac{1}{2} - Q</math>. Twierdzimy, że można dobrać <math>n_0 \ge n_1</math> m i <math>\eta</math> w ten sposób, że dla dowolnego <math>n \ge n_0</math> spełnione jest
<center><math>C_{\Gamma } - \varepsilon \leq \frac{\log_2 m}{n} \leq C_{\Gamma } \label{(i)} </math></center>
+
<center><math>C_{\Gamma } - \varepsilon \leq \frac{\log_2 m}{n} \leq C_{\Gamma } {(i)} </math></center>
  
 
<center><math> \frac{\log_2 m}{n}  +  H(Q + \eta ) - 1 \leq - \frac{\varepsilon }{3}</math></center>
 
<center><math> \frac{\log_2 m}{n}  +  H(Q + \eta ) - 1 \leq - \frac{\varepsilon }{3}</math></center>
Linia 97: Linia 97:
  
 
A więc jeśli n jest wystarczająco duże, dostajemy
 
A więc jeśli n jest wystarczająco duże, dostajemy
<center><math> \frac{1}{N} \sum_{\bar{C}} \, \pr_E ( \Delta , \bar{C} ) \leq  
+
<center><math> \frac{1}{N} \sum_{\bar{C}} \, _E ( \Delta , \bar{C} ) \leq  
 
\frac{\delta }{2} + \frac{\delta }{2} =  \delta </math></center>
 
\frac{\delta }{2} + \frac{\delta }{2} =  \delta </math></center>
  

Aktualna wersja na dzień 12:22, 26 wrz 2020

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

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 , . Twierdzimy, że można dobrać m i w ten sposób, że dla dowolnego spełnione jest

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

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

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.