Teoria informacji/TI Wykład 4

From Studia Informatyczne

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 \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| \ge 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

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

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. image:End_of_proof.gif


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

\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}
image:End_of_proof.gif