Teoria informacji/TI Ćwiczenia 7: 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
Nie podano opisu zmian
Linia 61: Linia 61:
<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">
Dla rozkładu wejściowego A:<math>Pr(x=0)=p</math> otrzymujemy na wyjściu rozkład B:<math>Pr(x=0)=\frac{1+p}{2}</math>.  
Dla rozkładu wejściowego A:<math>Pr(x=0)=p</math> otrzymujemy na wyjściu rozkład B:<math>Pr(x=0)=p+\frac{1}{2}(1-p)=\frac{1+p}{2}</math>.  
Wyliczamy  
Wyliczamy  


Linia 74: Linia 74:


<center><math>\aligned
<center><math>\aligned
I'(A,B) & = -\log(\frac{1+p}{2})+\log(\frac{1-p}{2})+1\\
I'(A,B) & = (-\log \frac{1-p}{2}+\log\frac{1+p}{2}) \cdot \frac{1}{2}+1\\
\log(\frac{1+p}{2}) & =\log(\frac{1-p}{2})+1\\
\log(\frac{1+p}{2}) & =\log(\frac{1-p}{2})+2\\
\frac{1+p}{2} & =1-p\\
\frac{1+p}{2} & =2-2p\\
p & =\frac{1}{3}
p & =\frac{3}{5}
\endaligned
\endaligned
</math></center>
</math></center>


Optmalny rozkład prawdopodobieństwa na wejściu to <math>Pr(x=0)=\frac{1}{3}</math>. Przepustowość <math>C_{\Gamma}=H(\frac{2}{3})-\frac{2}{3} \approx 0,2516</math>
Optmalny rozkład prawdopodobieństwa na wejściu to <math>Pr(x=0)=\frac{3}{5}</math>. Przepustowość <math>C_{\Gamma}=H(\frac{4}{5})-\frac{2}{5} \approx 0,3219</math>
</div>
</div>
</div>}}
</div>}}

Wersja z 15:12, 24 sie 2006

Mając daną macierz opisującą kanał, można obliczyć dla jakiego wejściowego rozkładu prawdopodobieństwa informacja wzajemna między wejściem a wyjściej jest największa i tym samym obliczyć przepustowość tego kanału.

Poniższy interaktywny wykres pozwala prześledzić jak ta przepustowość się zmienia w zależności od charakterystyki kanału. Przy pomocy dolnych suwaków można uzyskać charakterystykę dowolnego kanału binarnego (w prawym dolnym rogu). Wykres pokazuje jak dla takiego kanału w zależności od rozkładu prawodpodbieństwa na wejściu (parametr p określa prawdopodobieństwo wysłania 0), zmienia się:

  • rozkład prawdopodobieństwa na wyjściu (zielony wykres - prawdopodobieństwo uzyskania 0 na wyjściu)
  • informacja wzajemna między wejściem a wyjściem (czerwony wykres)

Maksimum czerwonej krzywej określa pokazuje jaki jest optymalny rozkład na wejściu i jaka jest przepustowość takiego kanału.

<applet code="PSAplecik" archive="images/d/dd/PSApplet.jar" width="600" height="480"> <param name="TITLE" value="Informacja wzajemna dla kanału binarnego"> </applet>


Ćwiczenia

Ćwiczenie 1 [Łączenie kanałów]

Przypuśćmy że łączymy szeregowo kanały opisywane macierzami P i Q, tak że wyjście z kanału P jest wejściem do kanału Q. Jaka macierz opisuje kanał w ten sposób utworzony?

Rozwiązanie

{{{3}}}


Ćwiczenie 2 [Łączenie BSC]

Załóżmy że n identycznych binarnych kanałów symetrycznych Γ opisywanych macierzą M=(PP¯P¯P) zostało połączonych szeregowo. Udowodnij że tak powstały kanał również jest BSC, i oblicz jego przepustowość. Jaka zachowuje się ta przepustowość dla n→∞?

Wskazówka

{{{3}}}

Rozwiązanie

{{{3}}}


Ćwiczenie 3 [Kanał Z]

Kanał Z jest opisywany przez następującą macierz (101212)

Oblicz przepustowośc tego kanału i znajdź rozkład prawdopodobieństwa na wejściu który pozwala ją uzyskać.

Rozwiązanie

{{{3}}}


Zadania domowe

Zadanie 1 - Kanał pięciokątny

Rozważmy kanał Γ dla którego 𝒜=ℬ={0,1,2,3,4} i prawdopodobieństwa przejść wyglądają następująco: p(b|a)={12 gdy b=a±1(mod5)0 wpp.

Oblicz CΓ. Kanał ten można wykorzystać do bezbłędnego przesyłania wiadomości z szybkością transmisji 1 bitu/znak, wysyłając tylko znaki 0 i 1. Opracuj metodę wysyłania danych tak aby uzyskać większą szybkość transmisji, zachowując zerowe prawdopodobieństwo błędu.}}

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