Teoria informacji/TI Wykład 4

Aby oszacować ${\frac {L_{r}(S^{n})}{n}}-H_{r}(S)$, zaczniemy od uzupełnienia naszej nierówności o górne ograniczenie.

Twierdzenie [Kod Shannona-Fano]

Dla dowolnej skończonej przestrzeni probabilistycznej S i $r\geq 2$, istnieje kod $\varphi :S\to \Sigma ^{*}$ (gdzie $|\Sigma |=r$), spełniający

$L(\varphi )\leq H_{r}(S)+1$

W ten sposób mamy

$H_{r}(S)\leq L_{r}(S)\leq H_{r}(S)+1$

Dodatkowo, ścisła nierówność $L_{r}(S)<H_{r}(S)+1$ jest prawdziwa za wyjątkiem przypadku $p(s)=1$ dla pewnego $s\in S$ (wtedy $H_{r}(S)=0$).

Dowód

Dla $|S|=1$ mamy trywialnie $H_{r}(S)=0$ i $L_{r}(S)=1$. Załóżmy że $|S|\geq 2$. Niech

${\ell }(s)=\left\lceil \log _{r}{\frac {1}{p(s)}}\right\rceil$

dla tych $s\in S$ dla których $p(s)>0$. Wtedy

$\sum _{s:p(s)>0}{\frac {1}{r^{\ell (s)}}}\leq \sum _{p(s)>0}p(s)=\sum _{s\in S}p(s)=1$

Rozważmy kilka przypadków. W najprostszym, kiedy $(\forall s\in S)\,p(s)>0$, powyższa nierówność odpowiada dokładnie nierówności Krafta, a zatem istnieje kod $\varphi$ spełniający $|\varphi (s)|=\ell (s)$ dla wszystkich $s\in S$. Uwzględniając że ${\ell }(s)<\log _{r}{\frac {1}{p(s)}}+1$ dostajemy

$\sum _{s\in S}p(s)\cdot {\ell }(s)<\sum _{s\in S}p(s)\cdot \left(\log _{r}{\frac {1}{p(s)}}+1\right)=H_{r}(S)+1$.

Załóżmy zatem że $p(s)$ może być równe 0. Jeśli

$\sum _{p(s)>0}{\frac {1}{r^{\ell (s)}}}<1$

to łatwo możemy rozszerzyć definicję $\ell$ na wszystkie s, tak że nierówność Krafta $\sum _{s\in S}{\frac {1}{r^{\ell (s)}}}\leq 1$ dalej będzie spełniona. Będzie zatem istniał kod o długościach $\ell$ spełniający ${\ell }(s)<\log _{r}{\frac {1}{p(s)}}+1$ zawsze gdy $p(s)>0$, a więc

$\sum _{s\in S}p(s)\cdot {\ell }(s)<\sum _{s\in S}p(s)\cdot \left(\log _{r}{\frac {1}{p(s)}}+1\right)=H_{r}(S)+1$

(Pamiętając naszą konwencję $0\cdot \log {\frac {1}{0}}=0$.)

Ostatni przypadek to taki gdy

$\sum _{p(s)>0}{\frac {1}{r^{\ell (s)}}}=1$

Wybierzmy s’ takie że $p(s')>0$ i zdefiniujmy nowe długości

$\ell '(s')=\ell (s')+1$

$\ell '(s)=\ell (s),{\mbox{ dla }}s\neq s'$

Znów możemy rozszerzyć $\ell '$ na wszystkie s w taki sposób żeby zachować nierówność Krafta. Żeby obliczyć średnią długość kodu, zauważmy że w tym przypadku mieliśmy zawsze $\ell (s)=\log _{r}{\frac {1}{p(s)}}$ gdy tylko $p(s)>0$. (Wynika to z tego że z definicji $\ell$ musi być ${\frac {1}{r^{\ell (s)}}}\leq p(s)$ i $1=\sum _{p(s)>0}{\frac {1}{r^{\ell (s)}}}=\sum _{p(s)>0}p(s)$, a więc $p(s)={\frac {1}{r^{\ell (s)}}}$ gdy $p(s)>0$.) Kod o długości $\ell '$ spełnia

$\sum _{s\in S}p(s)\cdot {\ell }'(s)=\sum _{p(s)>0}p(s)\cdot {\ell }'(s)=p(s')+\sum _{p(s)>0}p(s)\cdot {\ell }(s)=p(s')+H_{r}(S)$

Ostatecznie $L_{r}(S)\leq H_{r}(S)+1$ i nierówność nie jest ostra tylko gdy nie istnieje żadne $0<p(s')<1$.

Jesteśmy gotowi do sformułowania pierwszego z głównych twierdzeń tego wykładu

Twierdzenie [Pierwsze Twierdzenie Shannona]

Dla każdej skończonej przestrzeni probabilistycznej S i $r\geq 2$

$\lim _{n\to \infty }{\frac {L_{r}(S^{n})}{n}}=H_{r}(S)$.

Dowód

Z poprzedniego twierdzenia

$H_{r}(S^{n})\leq L_{r}(S^{n})\leq H_{r}(S^{n})+1$

Uwzględniając $H_{r}(S^{n})=n\cdot H_{r}(S)$ dostajemy

$H_{r}(S)\leq {\frac {L_{r}(S^{n})}{n}}\leq H_{r}(S)+{\frac {1}{n}}$