Teoria informacji/TI Wykład 4

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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