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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
m (Zastępowanie tekstu - "\aligned" na "\begin{align}")
 
(Nie pokazano 7 wersji utworzonych przez 4 użytkowników)
Linia 1: Linia 1:
 +
===Minimalna długość kodu - kontynuacja===
 +
 +
 
Aby oszacować <math>\frac{L_r (S^n )}{n} - H_r (S)</math>, zaczniemy od uzupełnienia naszej nierówności o górne ograniczenie.
 
Aby oszacować <math>\frac{L_r (S^n )}{n} - H_r (S)</math>, zaczniemy od uzupełnienia naszej nierówności o górne ograniczenie.
 
  
 
{{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>).}}
  
'''Dowód''': 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_{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 [[Teoria informacji/TI Wykład 1#kraft|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ętamy o naszej konwencji <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>
+
\begin{align}
 +
\ell' (s') & = \ell (s') + 1\\
 +
\ell' (s) & = \ell (s), \mbox{ dla } s \neq s'
 +
\end{align}
 +
</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 <math>s</math> 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 <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>.)  
:<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>
 
  
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>.
 
QED.
 
  
 +
Kod o długości <math>\ell'</math> spełnia
 +
<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) </math></center>
  
Jesteśmy gotowi do sformułowania pierwszego z głównych twierdzeń tego wykładu
+
<center><math> =  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 wtedy, gdy nie istnieje żadne <math>0 < p(s') <1</math>.}}
 +
 
 +
 
 +
Jesteśmy gotowi do sformułowania pierwszego z głównych twierdzeń tego wykładu:
  
  
 
{{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>}}
  
'''Dowód'''
+
{{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
 
:<math>H_r (S) \leq \frac{L_r (S^n )}{n} \leq H_r (S) + \frac{1}{n}</math>
 
  
QED.
+
Uwzględniając <math>H_r (S^n) = n \cdot H_r(S)</math>, dostajemy
 +
<center><math>H_r (S) \leq \frac{L_r (S^n )}{n} \leq H_r (S) + \frac{1}{n}</math></center>}}

Aktualna wersja na dzień 12:40, 9 cze 2020

Minimalna długość kodu - kontynuacja

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ętamy o naszej konwencji .)

Ostatni przypadek to taki, gdy

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

Znów możemy rozszerzyć na wszystkie 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 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 wtedy, 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