Teoria informacji/TI Wykład 12

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})\leq \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

${\begin{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 )} _{(*)}\end{aligned}}$

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

${\begin{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))} _{(**)}\end{aligned}}$

(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 (*):

${\begin{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 )}\end{aligned}}$

Wracając do głównego szacowania, dostajemy

${\begin{aligned}{\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}}\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{aligned}}$

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\geq n_{1}$, i dla dowolnych $2\leq m\leq 2^{n}$, $0<\eta <{\frac {1}{2}}-Q$. Twierdzimy, że można dobrać $n_{0}\geq n_{1}$ m i $\eta$ w ten sposób, że dla dowolnego $n\geq n_{0}$ spełnione jest

$C_{\Gamma }-\varepsilon \leq {\frac {\log _{2}m}{n}}\leq C_{\Gamma }{(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}}\,_{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

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.