Teoria informacji/TI Ćwiczenia 8: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Stromy (dyskusja | edycje)
115 edycji
Nie podano opisu zmian
Stromy (dyskusja | edycje)
115 edycji
Linia 3: Linia 3:
{{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|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<div class="mw-collapsible-content" style="display:none">
Można znaleźć przykład gdy reguła ta nie odtworzy poprawnie ani jednego symbolu.
</div>
</div>}}
{{rozwiazanie|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<div class="mw-collapsible-content" style="display:none">
Przykładem może być kanał opisywany następującą macierzą:
<center><math>
\begin{pmatrix}
0.9 & 0 & 0 & 0 & 0.1 \\
0 & 0.9 & 0 & 0 & 0.1 \\
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1
\end{pmatrix}
</math></center>
i rozkład <math>A = \langle 0.5, 0.5, 0, 0, 0 \rangle</math>, czyli używający tylko dwóch pierwszych symboli.
Reguła największego podobieństwa zawsze zinterpretuje sygnał jako któryś z ostatnich trzech symboli.
</div>
</div>}}




Linia 24: Linia 51:
</math></center>
</math></center>


Oblicz przepustowość tego kanału.}}
Oblicz przepustowość tego kanału. Naszkicuj wyres informacji wzajemnej między wejściem a wyjściem, w zależności od P oraz od rozkładu prawdopodobieństwa na wejściu.}}
 
{{rozwiazanie|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<div class="mw-collapsible-content" style="display:none">
Rozpisujemy
<center><math>I(A;B)=H(B)-H(B|A)</math></center>
 
Wynik możemy traktować jako [[Teoria informacji/TI Ćwiczenia 2#ke|kombinację źródeł]] - z prawdopodobieństwem <math>P</math> zwracamy wartość na wejściu (o entropii <math>H(A)</math>), a z prawdopodobieństwem <math>1-P</math> zwracamy wartość ''?'' (o entropii 0).
 
<center><math>H(B)=H(P) + P \cdot H(A) + (1-P) \cdot 0</math></center>
 
Gdy znamy symbol wejściowy, entropia <math>B</math> jest zawsze taka sama, równa <math>H(P)</math>. Tym samym
<center><math>I(A;B) = H(P) + P \cdot H(A) - H(P) = P \cdot H(A)</math></center>
 
<center><math>C_\Gamma = max_A (P \cdot H(A)) = P</math></center>
 
Wykres informacji wzajemnej w zależności od P oraz od rozkładu prawdopodobieństwa na wejściu powinien wyglądać mniej więcej tak:
<center>[[Grafika:wykres3.jpg]]</center>
</div>
</div>}}




Linia 30: Linia 77:
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|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<div class="mw-collapsible-content" style="display:none">
Wystarczy że będzie po każdym symbolu sprawdzał czy dotarł poprawnie, i jeśli został zgubiony 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>
</div>
</div>}}


== Zadania domowe ==
== Zadania domowe ==

Wersja z 12:57, 1 wrz 2006

Ćwiczenia

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

Skonstruuj rozkład A 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 H(Y|X)≤H(Y). Pokaż że nie zawsze tak jest w przypadku innych miar entropii.

Znajdź przykład gdy uzyskanie jakiejś informacji może zwiększyć entropię Shannona innej informacji, tzn. H(Y|X=a)>H(Y)


Ćwiczenie 3 [Binarny kanał wymazujący]

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

W tym przypadku 𝒜={0,1}, ℬ={0,1,?}. Jego macierz przejść to:

(P01−P0P1−P)
Oblicz przepustowość tego kanału. Naszkicuj wyres informacji wzajemnej między wejściem a wyjściem, w zależności od P oraz od rozkładu prawdopodobieństwa na wejściu.

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ń xi(W,Yi−1) określających kolejny symbol xi na podstawie przesyłanej wiadomości W i dotychczas dostarczonych symboli Y1,Y2,…,Yi−1. 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.

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji/TI_Ćwiczenia_8&oldid=38346”