Teoria informacji/TI Wykład 4

Minimalna długość kodu - kontynuacja

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 _{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ętamy o naszej konwencji $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

${\begin{aligned}\ell '(s')&=\ell (s')+1\\\ell '(s)&=\ell (s),{\mbox{ dla }}s\neq s'\end{aligned}}$

Znów możemy rozszerzyć $\ell '$ na wszystkie $s$ w taki sposób, żeby zachować nierówność Krafta. Aby obliczyć średnią długość kodu musimy zauważyć, ż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 wtedy, 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}}$