Teoria informacji/TI Ćwiczenia 8

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia

Ćwiczenie 1 [Nieoptymalność reguły maksymalnego podobieństwa]

Skonstruuj rozkład i kanał , dla którego reguła maksymalnego podobieństwa nie jest optymalną regułą. Skonstruuj przykład, w którym reguła ta powoduje błąd z prawdopodobieństwem powyżej 90%.

Wskazówka

Rozwiązanie


Ćwiczenie 2 [Wiedza zwiększająca niepewność]

Na wykładzie wcześniej zostało pokazane, że . Pokaż, że nie zawsze tak jest w przypadku innych miar entropii.

Znajdź przykład, w którym uzyskanie jakiejś informacji może zwiększyć entropię Shannona innej informacji, tzn.


Ćwiczenie 3 [Binarny kanał wymazujący]

Binarny kanał wymazujący wygląda następująco:

Erasure.PNG

W tym przypadku , . Jego macierz przejść to:

Oblicz przepustowość tego kanału. Naszkicuj wykres informacji wzajemnej między wejściem a wyjściem w zależności od P i od rozkładu prawdopodobieństwa na wejściu.

Rozwiązanie


Ćwiczenie 4 [Feedbacku dla kanału wymazującego]

W wielu praktycznych zastosowaniach nadawca może dowiedzieć się od odbiorcy, jak przebiega komunikacja. Załóżmy, że nadawca, dysponujący binarnym kanałem wymazującym, po każdym przesłanym symbolu poznaje wartość symbolu wyjściowego. Pokaż, jak może wykorzystać tę informację do przesyłania wiadomości bezbłędnie z szybkością odpowiadającą przepustowości kanału.

Rozwiązanie

Zadania domowe

Zadanie 1 - Przepustowość kanałów z feedbackiem

Rozważmy kanał z pełną informacją zwrotną, w którym po przesłaniu każdego symbolu nadawca poznaje symbol na wyjściu. Kod z feedbackiem definiujemy jako sekwencję mapowań określających kolejny symbol na podstawie przesyłanej wiadomości i dotychczas dostarczonych symboli . Przepustowość kanału z feedbackiem jest określana jako maksymalna szybkość transmisji przez kanał przy wykorzystaniu kodu takiej postaci. Udowodnij, że ta przepustowość jest równa klasycznej przepustowości kanału, czyli że wykorzystanie informacji zwrotnej nie może zwiększyć szybkości transmisji. Zauważ, że nie jest to sprzeczne z ćwiczeniem 4 - jej wykorzystanie może znacząco uprościć konstrukcję samego kodu.