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\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 _{s: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ę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^{\prime })>0$ i zdefiniujmy nowe długości

${\ell }^{\prime }(s^{\prime })=\ell (s^{\prime })+1$

${\ell }^{\prime }(s)=\ell (s),\text{ dla }s\ne s^{\prime }$

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