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\ge 2$, istnieje kod $\phi :S\to {\mathrm{\Sigma }}^{*}$ (gdzie $|\mathrm{\Sigma }|=r$), spełniający $L(\phi )\le H_r(S)+1$

W ten sposób mamy

$H_r(S)\le L_r(S)\le 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|\ge 2$. Niech $\ell (s)=\lceil {\log }_r\frac{1}{p(s)}\rceil$

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

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

Rozważmy kilka przypadków. W najprostszym, kiedy $(\mathrm{\forall }s\in S)p(s)>0$, powyższa nierówność odpowiada dokładnie nierówności Krafta, a zatem istnieje kod $\phi$ spełniający $|\phi (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 ({\log }_r\frac{1}{p(s)}+1)=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)}}\le 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 ({\log }_r\frac{1}{p(s)}+1)=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^{\prime })>0$, i zdefiniujmy nowe długości

$\begin{array}{rl}{\ell }^{\prime }(s^{\prime })& =\ell (s^{\prime })+1\\ {\ell }^{\prime }(s)& =\ell (s),\text{ dla }s\ne s^{\prime }\end{array}$

Znów możemy rozszerzyć ${\ell }^{\prime }$ 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)}}\le 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 }^{\prime }$ spełnia

$\sum _{s\in S}p(s)\cdot {\ell }^{\prime }(s)=\sum _{p(s)>0}p(s)\cdot {\ell }^{\prime }(s)=p(s^{\prime })+\sum _{p(s)>0}p(s)\cdot \ell (s)$ $=p(s^{\prime })+H_r(S)$ Ostatecznie $L_r(S)\le H_r(S)+1$ i nierówność nie jest ostra tylko wtedy, gdy nie istnieje żadne $0<p(s^{\prime })<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\ge 2$

$\underset{n\to \mathrm{\infty }}{\lim }\frac{L_r(S^n)}{n}=H_r(S)$.

Dowód

Z poprzedniego twierdzenia

$H_r(S^n)\le L_r(S^n)\le H_r(S^n)+1$

Uwzględniając $H_r(S^n)=n\cdot H_r(S)$, dostajemy

$H_r(S)\le \frac{L_r(S^n)}{n}\le H_r(S)+\frac{1}{n}$