Teoria informacji/TI Wykład 12

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wracamy do szacowania . Przypomnijmy, że wyprowadzone na poprzednim wykładzie szacowanie obowiązuje dla dowolnego kodu C, o ile n jest wystarczająco duże. Pokażemy teraz, że dla wystarczająco dużych n istnieje kod C, który spełnia warunki Twierdzenia Shannona. W szczególności taki, dla którego drugi składnik szacowania można ograniczyć z góry przez .

Do dowodu użyjemy metody probabilistycznej. Ustalmy . Niech będzie zbiorem wszystkich możliwych m-elementowych sekwencji , takich że są parami różne. Niech .

Od tego miejsca będziemy używać notacji na oznaczenie sekwencji z . Argument probabilistyczny Shannona opiera się na prostej obserwacji. Jeśli

to istnieje kod C, taki że .

Zauważmy, że jeśli jest sekwencją w o wartościach to

Nasze szacowanie daje zatem


Oszacujemy teraz (*) dla ustalonej pary indeksów .

Dla niech oznacza kulę w o promieniu i środku w punkcie e, tzn.

Łatwo zauważyć, że

Zatem

(gdzie oznacza funkcję charakterystyczną: jest spełniona).

Możemy oszacować teraz wartość (**) dla ustalonego e. Z pewnością każdy wektor inny niż pojawia się jako dla pewnej sekwencji , i łatwo zauważyć, że każdy taki wektor pojawia się taką samą liczbę razy, tzn.

dla dowolnych . A zatem każde dodaje do sumy , czyli

Na poprzednim wykładzie dokonaliśmy oszacowania rozmiaru kuli o promieniu , mamy zatem

Możemy już oszacować (**):

Pamiętając, że , otrzymujemy stąd również szacowanie dla (*):


Wracając do głównego szacowania, dostajemy

Jesteśmy tu już blisko celu, gdyż odpowiada „prawie” .

Konkretniej, do tej pory wiemy, że powyższe równanie jest spełnione dla wystarczająco dużych n, powiedzmy , i dla dowolnych , . Twierdzimy, że można dobrać m i w ten sposób, że dla dowolnego spełnione jest

W szczególności druga nierówność implikuje

A więc jeśli n jest wystarczająco duże, dostajemy

Używając argumentu probabilistycznego, wnioskujemy, że musi istnieć kod C rozmiaru m, spełniający . Ponieważ , ten kod spełnia warunki Shannona.

Wybór i spełniający oba konieczne warunki najłatwiej przedstawimy na diagramie

Teoria Informacji diag1.PNG

Używając ciągłości H, wybieramy takie, że . Jeśli n jest wystarczająco duże, potem możemy znaleźć k takie, że . Tym samym oba warunki są spełnione, co kończy dowód.