Teoria informacji/TI Wykład 12
Wracamy do szacowania 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 .
. Przypomnijmy, że wyprowadzone na poprzednim wykładzieDo 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ślito istnieje kod C, taki że
.Zauważmy, że jeśli
jest sekwencją w o wartościach toNasze 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 , czyliNa 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 jestW 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 diagramieUż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.