Teoria informacji/TI Ćwiczenia 8: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 2: | Linia 2: | ||
{{cwiczenie|1 [Nieoptymalność reguły maksymalnego podobieństwa]|rmp| | {{cwiczenie|1 [Nieoptymalność reguły maksymalnego podobieństwa]|rmp| | ||
Skonstruuj rozkład <math>A</math> i kanał <math>\Gamma</math> dla którego [[Teoria informacji/TI Wykład 8#maks_podob|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%.}} | Skonstruuj rozkład <math>A</math> i kanał <math>\Gamma</math>, dla którego [[Teoria informacji/TI Wykład 8#maks_podob|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%.}} | ||
{{wskazowka||| | {{wskazowka||| | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
Można znaleźć przykład gdy reguła ta nie odtworzy poprawnie ani jednego symbolu. | Można znaleźć przykład, gdy reguła ta nie odtworzy poprawnie ani jednego symbolu. | ||
</div> | </div> | ||
</div>}} | </div>}} | ||
| Linia 33: | Linia 33: | ||
{{cwiczenie|2 [Wiedza zwiększająca niepewność]|wzn| | {{cwiczenie|2 [Wiedza zwiększająca niepewność]|wzn| | ||
Na wykładzie wcześniej zostało pokazane że <math>H(Y|X) \le H(Y)</math>. | Na wykładzie wcześniej zostało pokazane, że <math>H(Y|X) \le H(Y)</math>. | ||
Pokaż że nie zawsze tak jest w przypadku [[Teoria informacji/TI Ćwiczenia 2#entropia_kolizji|innych miar entropii]]. | Pokaż, że nie zawsze tak jest w przypadku [[Teoria informacji/TI Ćwiczenia 2#entropia_kolizji|innych miar entropii]]. | ||
Znajdź przykład | Znajdź przykład, w którym uzyskanie jakiejś informacji może zwiększyć entropię Shannona innej informacji, tzn. <math>H(Y|X=a) > H(Y)</math>}} | ||
| Linia 51: | Linia 51: | ||
</math></center> | </math></center> | ||
Oblicz przepustowość tego kanału. Naszkicuj | 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.}} | ||
{{rozwiazanie||| | {{rozwiazanie||| | ||
| Linia 75: | Linia 75: | ||
{{cwiczenie|4 [Feedbacku dla kanału wymazującego]|wf| | {{cwiczenie|4 [Feedbacku dla kanału wymazującego]|wf| | ||
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.}} | 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.}} | ||
{{rozwiazanie||| | {{rozwiazanie||| | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
Wystarczy że będzie po każdym symbolu sprawdzał czy dotarł poprawnie, | Wystarczy, że będzie po każdym symbolu sprawdzał, czy dotarł poprawnie, a jeśli został zgubiony, będzie przesyłał go jeszcze raz. | ||
Dla każdego symbolu oczekiwana liczba prób będzie wynosiła <math>\frac{1}{P}</math>, a więc szybkość transmisji będzie równa <math>P</math> | Dla każdego symbolu oczekiwana liczba prób będzie wynosiła <math>\frac{1}{P}</math>, a więc szybkość transmisji będzie równa <math>P</math> | ||
</div> | </div> | ||
| Linia 91: | Linia 91: | ||
Rozważmy kanał z pełną informacją zwrotną, w którym po przesłaniu każdego symbolu nadawca poznaje symbol na wyjściu. | 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ń <math>x_i(W,Y^{i-1})</math> określających kolejny symbol <math>x_i</math> na podstawie przesyłanej wiadomości <math>W</math> i dotychczas dostarczonych symboli <math>Y_1, Y_2, \ldots, Y_{i-1}</math>. | ''Kod z feedbackiem'' definiujemy jako sekwencję mapowań <math>x_i(W,Y^{i-1})</math> określających kolejny symbol <math>x_i</math> na podstawie przesyłanej wiadomości <math>W</math> i dotychczas dostarczonych symboli <math>Y_1, Y_2, \ldots, Y_{i-1}</math>. | ||
''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. | ''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. | Zauważ, że nie jest to sprzeczne z ćwiczeniem 4 - jej wykorzystanie może znacząco uprościć konstrukcję samego kodu. | ||
Wersja z 09:17, 20 wrz 2006
Ć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
{{{3}}}
Rozwiązanie
{{{3}}}
Ć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:
W tym przypadku , . Jego macierz przejść to:
Rozwiązanie
{{{3}}}
Ć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
{{{3}}}
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.
