Teoria informacji/TI Wykład 12

From Studia Informatyczne

Wracamy do szacowania Pr_E(\Delta, C). 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 \frac{\delta}{2}.

Do dowodu użyjemy metody probabilistycznej. Ustalmy m < 2^n. Niech \mathcal{C} będzie zbiorem wszystkich możliwych m-elementowych sekwencji c_1, \ldots, c_m \in \{0,1\}^n, takich że c_i są parami różne. Niech N = |\mathcal{C}|.

N = {2^n \choose m}  \cdot m!

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

\frac{1}{N} \sum_{\bar{C}} Pr_E ( \Delta , \bar{C}) \leq \delta

to istnieje kod C, taki że Pr_E(\Delta,{C}) \le \delta.

Zauważmy, że jeśli \bar{C} jest sekwencją w \mathcal{C} o wartościach C=\{c_1, \ldots, c_m \} to

\sum_{u \in C} \sum_{v \in C - \{ u \}} p ( d (v,u \oplus E) \leq \rho ) = \sum_{i = 1}^m \sum_{j \neq i} \, p ( d (c_j,c_i \oplus E) \leq \rho )

Nasze szacowanie daje zatem

\aligned \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) \\ & = \frac{\delta }{2} + \frac{1}{m} \sum_{i = 1}^m \sum_{j \neq i} \underbrace{\frac{1}{N} \sum_{\bar{C}} p ( d (c_j,c_i \oplus E) \leq \rho )}_{(*)} \endaligned


Oszacujemy teraz (*) dla ustalonej pary indeksów i \neq j.

Dla e \in \{0,1\}^n niech S_{\rho } (e) oznacza kulę w \{0,1\}^n o promieniu \rho i środku w punkcie e, tzn.

S_{\rho } (e) = \{ v \in \{ 0,1 \}^n  : d(v,e) \leq \rho \}

Łatwo zauważyć, że

d (v, u \oplus e ) \leq \rho \Longleftrightarrow v \oplus u \in S_{\rho } (e)

Zatem

\aligned \frac{1}{N} \sum_{\bar{C}} p ( d (c_j,c_i \oplus E) \leq \rho ) & = \frac{1}{N} \sum_{\bar{C}} p \left( c_i \oplus c_j \in S_{\rho } (E) \right) \\ & = \sum_{e \in \{ 0, 1 \}^n } p (E = e)  \cdot \underbrace{\frac{1}{N} \sum_{\bar{C}}   \chi (c_i \oplus c_j \in S_{\rho } (e) )}_{(**)} \endaligned

(gdzie \chi oznacza funkcję charakterystyczną: \chi(\varphi)=1 \Longleftrightarrow \varphi jest spełniona).

Możemy oszacować teraz wartość (**) dla ustalonego e. Z pewnością każdy wektor inny niż 0^n pojawia się jako c_i \oplus c_j dla pewnej sekwencji \bar{C} \in \mathcal{C}, i łatwo zauważyć, że każdy taki wektor pojawia się taką samą liczbę razy, tzn.

| \{ \bar{C} : u = c_i \oplus c_j \} |  = | \{ \bar{C} : v = c_i \oplus c_j \} |  = \frac{N}{2^n - 1}

dla dowolnych u,v \in \{0,1\}^n-\{0^n\}. A zatem każde u \in S_{\rho}(e) - \{0^n\} dodaje \frac{N}{2^n-1} do sumy \sum_{\bar{C}}  \chi (c_i \oplus c_j \in S_{\rho } (e) ), czyli

\sum_{\bar{C}}   \chi (c_i \oplus c_j \in S_{\rho } (e) ) = \frac{N}{2^n - 1} | S_{\rho } (e) - \{ 0^n \} |

Na poprzednim wykładzie dokonaliśmy oszacowania rozmiaru kuli o promieniu \rho = n \cdot (Q + \eta ), mamy zatem

| S_{\rho } (e) - \{ 0^n \} | \leq  2^{n \cdot H(Q + \eta )}

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

\frac{1}{N} \sum_{\bar{C}} \chi (c_i \oplus c_j \in S_{\rho } (e) ) \leq  \frac{1}{N} \cdot \frac{N}{2^n - 1} \cdot 2^{n \cdot H(Q + \eta )} \leq  \frac{1}{2^n - 1} \cdot 2^{n \cdot H(Q + \eta )}

Pamiętając, że \sum_{e \in \{ 0, 1 \}^n } p (E = e) = 1, otrzymujemy stąd również szacowanie dla (*):

\aligned \sum_{e \in \{ 0, 1 \}^n } p (E = e)  \cdot \underbrace{\frac{1}{N} \sum_{\bar{C}}  \chi (c_i \oplus c_j \in S_{\rho } (e) )}_{(**)} & \leq \frac{1}{2^n - 1} \cdot 2^{n \cdot H(Q + \eta )} \endaligned


Wracając do głównego szacowania, dostajemy

\aligned \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) } \endaligned

Jesteśmy tu już blisko celu, gdyż \left(  \frac{\log_2 m}{n} + H(Q + \eta ) - 1 \right) odpowiada „prawie” R(C)-C_{\Gamma}.

Konkretniej, do tej pory wiemy, że powyższe równanie jest spełnione dla wystarczająco dużych n, powiedzmy n \ge n_1, i dla dowolnych 2 \le m \le 2^n, 0 < \eta < \frac{1}{2} – Q. Twierdzimy, że można dobrać n_0 \ge n_1 m i \eta w ten sposób, że dla dowolnego n \ge n_0 spełnione jest

C_{\Gamma } - \varepsilon \leq \frac{\log_2 m}{n} \leq C_{\Gamma } \label{(i)}
\frac{\log_2 m}{n}   +  H(Q + \eta ) - 1 \leq - \frac{\varepsilon }{3}

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

2^{ n \cdot \left( \frac{\log_2 m}{n} + H(Q + \eta ) - 1 \right) } \leq \frac{1}{2^{n \cdot \frac{\varepsilon }{3}}}

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

\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 Pr_E(\Delta,C) \leq \delta. Ponieważ R(C)=\frac{\log_2 m}{n}, ten kod spełnia warunki Shannona.

Wybór \eta i m spełniający oba konieczne warunki najłatwiej przedstawimy na diagramie

grafika:Teoria_Informacji_diag1.PNG

Używając ciągłości H, wybieramy \eta takie, że C_ {\Gamma } - \frac{1}{3} \cdot \varepsilon \leq 1 - H(Q + \eta ) \leq C_ {\Gamma }. Jeśli n jest wystarczająco duże, potem możemy znaleźć k takie, że C_ {\Gamma } - \varepsilon \leq \frac{k}{n} \leq C_ {\Gamma } - \frac{2}{3}\cdot \varepsilon. Tym samym oba warunki są spełnione, co kończy dowód.