Teoria informacji/TI Wykład 4: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 2: Linia 2:
  
 
{{twierdzenie|[Kod Shannona-Fano]|shannon_fano|Dla dowolnej skończonej przestrzeni probabilistycznej ''S'' i <math>r \ge 2</math>, istnieje kod <math>\varphi : S \to \Sigma^*</math> (gdzie <math>|\Sigma| = r</math>), spełniający
 
{{twierdzenie|[Kod Shannona-Fano]|shannon_fano|Dla dowolnej skończonej przestrzeni probabilistycznej ''S'' i <math>r \ge 2</math>, istnieje kod <math>\varphi : S \to \Sigma^*</math> (gdzie <math>|\Sigma| = r</math>), spełniający
:<math> L (\varphi ) \leq H_r (S) + 1</math>
+
<center><math> L (\varphi ) \leq H_r (S) + 1</math></center>
  
 
W ten sposób mamy
 
W ten sposób mamy
:<math>H_r (S) \leq L_r (S) \leq H_r (S) + 1</math>
+
<center><math>H_r (S) \leq L_r (S) \leq H_r (S) + 1</math></center>
  
 
Dodatkowo, ścisła nierówność <math>L_r (S) < H_r (S) + 1</math> jest prawdziwa za wyjątkiem przypadku <math>p(s)=1</math> dla pewnego <math> s \in S</math> (wtedy <math>H_r(S) =0</math>).}}
 
Dodatkowo, ścisła nierówność <math>L_r (S) < H_r (S) + 1</math> jest prawdziwa za wyjątkiem przypadku <math>p(s)=1</math> dla pewnego <math> s \in S</math> (wtedy <math>H_r(S) =0</math>).}}
  
 
{{dowod||| Dla <math>|S|=1</math> mamy trywialnie <math>H_r(S)=0</math> i <math>L_r(S)=1</math>. Załóżmy że <math>|S| \ge 2</math>. Niech
 
{{dowod||| Dla <math>|S|=1</math> mamy trywialnie <math>H_r(S)=0</math> i <math>L_r(S)=1</math>. Załóżmy że <math>|S| \ge 2</math>. Niech
:<math>{\ell }(s) = \left\lceil \log_r \frac{1}{p(s)} \right\rceil</math>
+
<center><math>{\ell }(s) = \left\lceil \log_r \frac{1}{p(s)} \right\rceil</math></center>
  
 
dla tych <math>s \in S</math> dla których <math>p(s)>0</math>. Wtedy
 
dla tych <math>s \in S</math> dla których <math>p(s)>0</math>. Wtedy
:<math>\sum_{s: p(s) > 0} \frac{1}{r^{\ell (s)}} \leq \sum_{p(s) > 0} p(s) = \sum_{s \in S} p(s) = 1</math>
+
<center><math>\sum_{s: p(s) > 0} \frac{1}{r^{\ell (s)}} \leq \sum_{p(s) > 0} p(s) = \sum_{s \in S} p(s) = 1</math></center>
  
 
Rozważmy kilka przypadków. W najprostszym, kiedy <math>(\forall s \in S) \, p(s) > 0</math>, powyższa nierówność odpowiada dokładnie nierówności Krafta, a zatem istnieje kod <math>\varphi</math> spełniający <math>| \varphi (s)| = \ell (s)</math> dla wszystkich <math>s \in S</math>. Uwzględniając że <math>{\ell }(s) < \log_r \frac{1}{p(s)} +1</math> dostajemy
 
Rozważmy kilka przypadków. W najprostszym, kiedy <math>(\forall s \in S) \, p(s) > 0</math>, powyższa nierówność odpowiada dokładnie nierówności Krafta, a zatem istnieje kod <math>\varphi</math> spełniający <math>| \varphi (s)| = \ell (s)</math> dla wszystkich <math>s \in S</math>. Uwzględniając że <math>{\ell }(s) < \log_r \frac{1}{p(s)} +1</math> dostajemy
:<math>\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</math>.
+
<center><math>\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</math>.</center>
  
 
Załóżmy zatem że <math>p(s)</math> może być równe 0. Jeśli
 
Załóżmy zatem że <math>p(s)</math> może być równe 0. Jeśli
:<math>\sum_{p(s) > 0} \frac{1}{r^{\ell (s)}} <1</math>
+
<center><math>\sum_{p(s) > 0} \frac{1}{r^{\ell (s)}} <1</math></center>
 
to łatwo możemy rozszerzyć definicję <math>\ell</math> na wszystkie ''s'', tak że nierówność Krafta <math>\sum_{s \in S}  \frac{1}{r^{\ell (s)}} \leq 1</math> dalej będzie spełniona. Będzie zatem istniał kod o długościach <math>\ell</math> spełniający <math>{\ell }(s) < \log_r \frac{1}{p(s)} +1</math> zawsze gdy <math>p(s)>0</math>, a więc
 
to łatwo możemy rozszerzyć definicję <math>\ell</math> na wszystkie ''s'', tak że nierówność Krafta <math>\sum_{s \in S}  \frac{1}{r^{\ell (s)}} \leq 1</math> dalej będzie spełniona. Będzie zatem istniał kod o długościach <math>\ell</math> spełniający <math>{\ell }(s) < \log_r \frac{1}{p(s)} +1</math> zawsze gdy <math>p(s)>0</math>, a więc
:<math>\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 </math>
+
<center><math>\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 </math></center>
  
 
(Pamiętając naszą konwencję <math>0 \cdot \log \frac{1}{0} = 0</math>.)
 
(Pamiętając naszą konwencję <math>0 \cdot \log \frac{1}{0} = 0</math>.)
  
 
Ostatni przypadek to taki gdy
 
Ostatni przypadek to taki gdy
:<math>\sum_{ p(s) > 0} \frac{1}{r^{\ell (s)}}= 1</math>
+
<center><math>\sum_{ p(s) > 0} \frac{1}{r^{\ell (s)}}= 1</math></center>
  
 
Wybierzmy ''s’'' takie że <math>p(s')>0</math> i zdefiniujmy nowe długości
 
Wybierzmy ''s’'' takie że <math>p(s')>0</math> i zdefiniujmy nowe długości
:<math>\ell' (s') = \ell (s') + 1</math>
+
<center><math>
:<math>\ell' (s) = \ell (s), \mbox{ dla } s \neq s'</math>
+
\aligned
 +
\ell' (s') & = \ell (s') + 1\\
 +
\ell' (s) & = \ell (s), \mbox{ dla } s \neq s'
 +
\endaligned
 +
</math></center>
  
 
Znów możemy rozszerzyć <math>\ell'</math> 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 <math>\ell (s) = \log_r \frac{1}{p(s) }</math> gdy tylko <math>p(s) > 0</math>. (Wynika to z tego że z definicji <math>\ell</math> musi być <math>\frac{1}{r^{\ell (s)}} \leq p(s)</math> i <math>1 = \sum_{p(s) > 0} \frac{1}{r^{\ell (s)}} = \sum_{p(s) > 0} p(s)</math>, a więc <math> p(s) = \frac{1}{r^{\ell (s)}}</math> gdy <math>p(s) > 0</math>.) Kod o długości <math>\ell'</math> spełnia
 
Znów możemy rozszerzyć <math>\ell'</math> 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 <math>\ell (s) = \log_r \frac{1}{p(s) }</math> gdy tylko <math>p(s) > 0</math>. (Wynika to z tego że z definicji <math>\ell</math> musi być <math>\frac{1}{r^{\ell (s)}} \leq p(s)</math> i <math>1 = \sum_{p(s) > 0} \frac{1}{r^{\ell (s)}} = \sum_{p(s) > 0} p(s)</math>, a więc <math> p(s) = \frac{1}{r^{\ell (s)}}</math> gdy <math>p(s) > 0</math>.) Kod o długości <math>\ell'</math> spełnia
:<math>\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)</math>
+
<center><math>\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)</math></center>
  
 
Ostatecznie <math>L_r (S) \leq H_r (S) + 1</math> i nierówność nie jest ostra tylko gdy nie istnieje żadne <math>0 < p(s') <1</math>.}}
 
Ostatecznie <math>L_r (S) \leq H_r (S) + 1</math> i nierówność nie jest ostra tylko gdy nie istnieje żadne <math>0 < p(s') <1</math>.}}
Linia 43: Linia 47:
 
{{twierdzenie|[Pierwsze Twierdzenie Shannona]|pierwsze|
 
{{twierdzenie|[Pierwsze Twierdzenie Shannona]|pierwsze|
 
Dla każdej skończonej przestrzeni probabilistycznej ''S'' i <math>r \ge 2</math>
 
Dla każdej skończonej przestrzeni probabilistycznej ''S'' i <math>r \ge 2</math>
:<math>\lim_{n \to \infty } \frac{L_r (S^n)}{n} = H_r (S)</math>.}}
+
<center><math>\lim_{n \to \infty } \frac{L_r (S^n)}{n} = H_r (S)</math>.</center>}}
  
{{dowod|||
+
{{dowod||dw_pierwsze|
 
Z poprzedniego twierdzenia
 
Z poprzedniego twierdzenia
:<math>H_r (S^n) \leq L_r (S^n ) \leq H_r (S^n) + 1</math>
+
<center><math>H_r (S^n) \leq L_r (S^n ) \leq H_r (S^n) + 1</math></center>
  
 
Uwzględniając <math>H_r (S^n) = n \cdot H_r(S)</math> dostajemy
 
Uwzględniając <math>H_r (S^n) = n \cdot H_r(S)</math> dostajemy
:<math>H_r (S) \leq \frac{L_r (S^n )}{n} \leq H_r (S) + \frac{1}{n}</math>}}
+
<center><math>H_r (S) \leq \frac{L_r (S^n )}{n} \leq H_r (S) + \frac{1}{n}</math></center>}}

Wersja z 11:55, 2 sie 2006

Aby oszacować , zaczniemy od uzupełnienia naszej nierówności o górne ograniczenie.

Twierdzenie [Kod Shannona-Fano]

Dla dowolnej skończonej przestrzeni probabilistycznej S i , istnieje kod (gdzie ), spełniający

W ten sposób mamy

Dodatkowo, ścisła nierówność jest prawdziwa za wyjątkiem przypadku dla pewnego (wtedy ).

Dowód

Dla mamy trywialnie i . Załóżmy że . Niech

dla tych dla których . Wtedy

Rozważmy kilka przypadków. W najprostszym, kiedy , powyższa nierówność odpowiada dokładnie nierówności Krafta, a zatem istnieje kod spełniający dla wszystkich . Uwzględniając że dostajemy

.

Załóżmy zatem że może być równe 0. Jeśli

to łatwo możemy rozszerzyć definicję na wszystkie s, tak że nierówność Krafta dalej będzie spełniona. Będzie zatem istniał kod o długościach spełniający zawsze gdy , a więc

(Pamiętając naszą konwencję .)

Ostatni przypadek to taki gdy

Wybierzmy s’ takie że i zdefiniujmy nowe długości

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \ell' (s') & = \ell (s') + 1\\ \ell' (s) & = \ell (s), \mbox{ dla } s \neq s' \endaligned }

Znów możemy rozszerzyć 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 gdy tylko . (Wynika to z tego że z definicji musi być i , a więc gdy .) Kod o długości spełnia

Ostatecznie i nierówność nie jest ostra tylko gdy nie istnieje żadne . 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

.

Dowód

Z poprzedniego twierdzenia

Uwzględniając dostajemy

End of proof.gif