Teoria informacji/TI Ćwiczenia 7: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 1: | Linia 1: | ||
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 | 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ściem 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ę: | 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) | * 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) | * informacja wzajemna między wejściem a wyjściem (czerwony wykres). | ||
Maksimum czerwonej krzywej | Maksimum czerwonej krzywej 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"> | <applet code="PSAplecik" archive="images/d/dd/PSApplet.jar" width="600" height="480"> | ||
| Linia 15: | Linia 15: | ||
{{cwiczenie|1 [Łączenie kanałów]|łk| | {{cwiczenie|1 [Łączenie kanałów]|łk| | ||
Przypuśćmy że łączymy szeregowo kanały opisywane macierzami <math>P</math> i <math>Q</math>, tak że wyjście z kanału <math>P</math> jest wejściem do kanału <math>Q</math>. Jaka macierz opisuje kanał w ten sposób utworzony?}} | Przypuśćmy, że łączymy szeregowo kanały opisywane macierzami <math>P</math> i <math>Q</math>, tak że wyjście z kanału <math>P</math> jest wejściem do kanału <math>Q</math>. Jaka macierz opisuje kanał w ten sposób utworzony?}} | ||
{{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"> | ||
Macierz <math>PQ</math>. Zgodnie z [[Teoria informacji/TI Wykład 7#macierz_kanału|definicją macierzy kanału]] dla wejściowego rozkładu prawdopodobieństwa <math>a</math> otrzymujemy pomiędzy kanałami rozkład postaci <math>a \cdot P</math> i na wyjściu rozkład <math>a \cdot P \cdot Q</math>.</div> | Macierz <math>PQ</math>. Zgodnie z [[Teoria informacji/TI Wykład 7#macierz_kanału|definicją macierzy kanału]], dla wejściowego rozkładu prawdopodobieństwa <math>a</math> otrzymujemy pomiędzy kanałami rozkład postaci <math>a \cdot P</math> i na wyjściu rozkład <math>a \cdot P \cdot Q</math>.</div> | ||
</div> | </div> | ||
}} | }} | ||
| Linia 26: | Linia 26: | ||
{{cwiczenie|2 [Łączenie BSC]|łbsc| | {{cwiczenie|2 [Łączenie BSC]|łbsc| | ||
Załóżmy że <math>n</math> identycznych binarnych kanałów symetrycznych <math>\Gamma</math> opisywanych macierzą <math> | Załóżmy, że <math>n</math> identycznych binarnych kanałów symetrycznych <math>\Gamma</math> opisywanych macierzą <math> | ||
M=\begin{pmatrix} P & \bar{P} \\ | M=\begin{pmatrix} P & \bar{P} \\ | ||
\bar{P} & P \end{pmatrix} | \bar{P} & P \end{pmatrix} | ||
</math> 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 <math>n \to \infty</math>?}} | </math> 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 <math>n \to \infty</math>?}} | ||
{{wskazowka|||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | {{wskazowka|||<div class="mw-collapsible mw-made=collapsible mw-collapsed"> | ||
| Linia 41: | Linia 41: | ||
<div class="mw-collapsible-content" style="display:none"> | <div class="mw-collapsible-content" style="display:none"> | ||
Zgodnie z poprzednim ćwiczeniem powstały kanał <math>\Gamma^n</math> jest opisywany macierzą | Zgodnie z poprzednim ćwiczeniem powstały kanał <math>\Gamma^n</math> jest opisywany macierzą | ||
<math>M^n</math>. Przez indukcję można pokazać że <math>M^n</math> ma postać | <math>M^n</math>. Przez indukcję można pokazać, że <math>M^n</math> ma postać | ||
<math>\begin{pmatrix} P_n & \bar{P_n} \\ | <math>\begin{pmatrix} P_n & \bar{P_n} \\ | ||
\bar{P_n} & P_n \end{pmatrix}</math>, więc jest to kanał symetryczny. Wartościami własnymi <math>M^n</math> są <math>1</math> i <math>(2P-1)^n</math>, a więc <math>2P_n = tr(M^n) = 1+(2P-1)^n</math>. Stąd <math>P_n=\frac{1+(2P-1)^n}{2}</math> i <math>C_{\Gamma^n}=1-H(P_n)=1-H(\frac{1+(2P-1)^n}{2})</math>. | \bar{P_n} & P_n \end{pmatrix}</math>, więc jest to kanał symetryczny. Wartościami własnymi <math>M^n</math> są <math>1</math> i <math>(2P-1)^n</math>, a więc <math>2P_n = tr(M^n) = 1+(2P-1)^n</math>. Stąd <math>P_n=\frac{1+(2P-1)^n}{2}</math> i <math>C_{\Gamma^n}=1-H(P_n)=1-H(\frac{1+(2P-1)^n}{2})</math>. | ||
| Linia 57: | Linia 57: | ||
Z = \begin{pmatrix} 1 & 0 \\ | Z = \begin{pmatrix} 1 & 0 \\ | ||
\frac{1}{2} & \frac{1}{2} \end{pmatrix}</math></center> | \frac{1}{2} & \frac{1}{2} \end{pmatrix}</math></center> | ||
Oblicz przepustowośc tego kanału i znajdź rozkład prawdopodobieństwa na wejściu który pozwala ją uzyskać.}} | Oblicz przepustowośc tego kanału i znajdź rozkład prawdopodobieństwa na wejściu, który pozwala ją uzyskać.}} | ||
{{rozwiazanie||| | {{rozwiazanie||| | ||
| Linia 72: | Linia 72: | ||
</math></center> | </math></center> | ||
Aby znaleźć maksimum wyliczamy punkt w którym pochodna się zeruje: | Aby znaleźć maksimum wyliczamy punkt, w którym pochodna się zeruje: | ||
<center><math>\aligned | <center><math>\aligned | ||
| Linia 104: | Linia 104: | ||
=== Zadanie 1 - Kanał pięciokątny === | === Zadanie 1 - Kanał pięciokątny === | ||
Rozważmy kanał <math>\Gamma</math> dla którego <math>\mathcal{A}=\mathcal{B}=\{0,1,2,3,4\}</math> i prawdopodobieństwa przejść wyglądają następująco: | Rozważmy kanał <math>\Gamma</math>, dla którego <math>\mathcal{A}=\mathcal{B}=\{0,1,2,3,4\}</math> i prawdopodobieństwa przejść wyglądają następująco: | ||
<math>p(b|a)=\bigg\{ \begin{matrix} \frac{1}{2} & \mbox{ gdy } & b=a \pm 1 & (\mod 5)\\ | <math>p(b|a)=\bigg\{ \begin{matrix} \frac{1}{2} & \mbox{ gdy } & b=a \pm 1 & (\mod 5)\\ | ||
0 & \mbox{ wpp.} & & \end{matrix}</math> | 0 & \mbox{ wpp.} & & \end{matrix}</math> | ||
Oblicz <math>C_{\Gamma}</math>. 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.}} | Oblicz <math>C_{\Gamma}</math>. 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.}} | ||
Wersja z 08:56, 20 wrz 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ściem 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 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 i , tak że wyjście z kanału jest wejściem do kanału . Jaka macierz opisuje kanał w ten sposób utworzony?
Rozwiązanie
{{{3}}}
Ćwiczenie 2 [Łączenie BSC]
Załóżmy, że identycznych binarnych kanałów symetrycznych opisywanych macierzą 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 ?
Wskazówka
{{{3}}}
Rozwiązanie
{{{3}}}
Ćwiczenie 3 [Kanał Z]
Kanał jest opisywany przez następującą macierz:
Rozwiązanie
{{{3}}}
Ćwiczenie 4 [Informacja wzajemna dla BSC]
Narysuj trójwymiarowy wykres informacji pomiędzy wejściem a wyjściem w kanale BSC w zależności od rozkładu prawdopodobieństwa na wejściu i parametru kanału.
Rozwiązanie
{{{3}}}
Zadania domowe
Zadanie 1 - Kanał pięciokątny
Rozważmy kanał , dla którego i prawdopodobieństwa przejść wyglądają następująco:
Oblicz . 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.}}
