Teoria informacji/TI Wykład 4

Z Studia Informatyczne
< Teoria informacji
Wersja z dnia 09:25, 16 lip 2006 autorstwa Stromy (dyskusja | edycje)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 . QED.


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

QED.