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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 1: Linia 1:
 
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
Linia 8: Linia 7:
 
:<math>H_r (S) \leq L_r (S) \leq H_r (S) + 1</math>
 
:<math>H_r (S) \leq L_r (S) \leq H_r (S) + 1</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>.}}
+
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>
 
:<math>{\ell }(s) = \left\lceil \log_r \frac{1}{p(s)} \right\rceil</math>
  
Linia 36: Linia 35:
 
:<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>
 
:<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>.  
+
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.
 
  
  
Linia 47: Linia 45:
 
:<math>\lim_{n \to \infty } \frac{L_r (S^n)}{n} = H_r (S)</math>.}}
 
:<math>\lim_{n \to \infty } \frac{L_r (S^n)}{n} = H_r (S)</math>.}}
  
'''Dowód'''
+
{{dowod|||
 
Z poprzedniego twierdzenia
 
Z poprzedniego twierdzenia
 
:<math>H_r (S^n) \leq L_r (S^n ) \leq H_r (S^n) + 1</math>
 
:<math>H_r (S^n) \leq L_r (S^n ) \leq H_r (S^n) + 1</math>
  
 
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>
+
:<math>H_r (S) \leq \frac{L_r (S^n )}{n} \leq H_r (S) + \frac{1}{n}</math>}}
 
 
QED.
 

Wersja z 06:41, 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

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