Teoria informacji/TI Wykład 12

Wracamy do szacowania $P{r}_E(\mathrm{\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 ${𝒞}$ będzie zbiorem wszystkich możliwych m-elementowych sekwencji $c_1,\dots ,c_m\in \{0,1{\}}^n$, takich że $c_i$ są parami różne. Niech $N=|{𝒞}|$.

$N=(\genfrac{}{}{0ex}{}{2^n}{m})\cdot m!$

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

$\frac{1}{N}\sum _{\overline{C}}P{r}_E(\mathrm{\Delta },\overline{C})\le \delta$

to istnieje kod C, taki że $P{r}_E(\mathrm{\Delta },C)\le \delta$.

Zauważmy, że jeśli $\overline{C}$ jest sekwencją w ${𝒞}$ o wartościach $C=\{c_1,\dots ,c_m\}$ to

$\sum _{u\in C}\sum _{v\in C-\{u\}}p(d(v,u\oplus E)\le \rho )=\sum _{i=1}^m\sum _{j\ne i}p(d(c_j,c_i\oplus E)\le \rho )$

Nasze szacowanie daje zatem

$\begin{array}{rl}\frac{1}{N}\sum _{\overline{C}}P{r}_E(\mathrm{\Delta },\overline{C})& \le \frac{1}{N}\sum _{\overline{C}}(\frac{\delta }{2}+\frac{1}{m}\sum _{i=1}^m\sum _{j\ne i}p(d(c_j,c_i\oplus E)\le \rho ))\\ & =\frac{\delta }{2}+\frac{1}{m}\sum _{i=1}^m\sum _{j\ne i}\underset{(*)}{\underbrace{\frac{1}{N}\sum _{\overline{C}}p(d(c_j,c_i\oplus E)\le \rho )}}\end{array}$

Oszacujemy teraz (*) dla ustalonej pary indeksów $i\ne 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)\le \rho \}$

Łatwo zauważyć, że

$d(v,u\oplus e)\le \rho ⟺v\oplus u\in S_{\rho }(e)$

Zatem

$\begin{array}{rl}\frac{1}{N}\sum _{\overline{C}}p(d(c_j,c_i\oplus E)\le \rho )& =\frac{1}{N}\sum _{\overline{C}}p(c_i\oplus c_j\in S_{\rho }(E))\\ & =\sum _{e\in \{0,1{\}}^n}p(E=e)\cdot \underset{(**)}{\underbrace{\frac{1}{N}\sum _{\overline{C}}\chi (c_i\oplus c_j\in S_{\rho }(e))}}\end{array}$

(gdzie $\chi$ oznacza funkcję charakterystyczną: $\chi (\phi )=1⟺\phi$ 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 $\overline{C}\in {𝒞}$, i łatwo zauważyć, że każdy taki wektor pojawia się taką samą liczbę razy, tzn.

$|\{\overline{C}:u=c_i\oplus c_j\}|=|\{\overline{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 _{\overline{C}}\chi (c_i\oplus c_j\in S_{\rho }(e))$, czyli

$\sum _{\overline{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\}|\le 2^{n\cdot H(Q+\eta )}$

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

$\frac{1}{N}\sum _{\overline{C}}\chi (c_i\oplus c_j\in S_{\rho }(e))\le \frac{1}{N}\cdot \frac{N}{2^n-1}\cdot 2^{n\cdot H(Q+\eta )}\le \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 (*):

$\begin{array}{rl}\sum _{e\in \{0,1{\}}^n}p(E=e)\cdot \underset{(**)}{\underbrace{\frac{1}{N}\sum _{\overline{C}}\chi (c_i\oplus c_j\in S_{\rho }(e))}}& \le \frac{1}{2^n-1}\cdot 2^{n\cdot H(Q+\eta )}\end{array}$

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ż $(\frac{{\log }_{2}m}{n}+H(Q+\eta )-1)$ odpowiada „prawie” $R(C)-C_{\mathrm{\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$, Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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

Parser nie mógł rozpoznać (nieznana funkcja „\label”): {\displaystyle C_{\Gamma } - \varepsilon \leq \frac{\log_2 m}{n} \leq C_{\Gamma } \label{(i)} } $\frac{{\log }_{2}m}{n}+H(Q+\eta )-1\le -\frac{\epsilon }{3}$

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

$2^{n\cdot (\frac{{\log }_{2}m}{n}+H(Q+\eta )-1)}\le \frac{1}{2^{n\cdot \frac{\epsilon }{3}}}$

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 $P{r}_E(\mathrm{\Delta },C)\le \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

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