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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m (Zastępowanie tekstu - "\endaligned" na "\end{align}")
m (Zastępowanie tekstu - "\aligned" na "\begin{align}")
 
Linia 33: Linia 33:
 
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
 
<center><math>
 
<center><math>
\aligned
+
\begin{align}
 
\ell' (s') & = \ell (s') + 1\\
 
\ell' (s') & = \ell (s') + 1\\
 
\ell' (s) & = \ell (s), \mbox{ dla } s \neq s'
 
\ell' (s) & = \ell (s), \mbox{ dla } s \neq s'

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