Teoria informacji/TI Wykład 4
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwaniaAby 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
Dowód: Dla
mamy trywialnie i . Załóżmy że . Niechdla tych
dla których . WtedyRozważ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ślito ł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ściZnó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łniaOstatecznie
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
dostajemyQED.