Teoria informacji/TI Ćwiczenia 7

From Studia Informatyczne

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.


Ć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

Macierz PQ. Zgodnie z definicją macierzy kanału, dla wejściowego rozkładu prawdopodobieństwa a otrzymujemy pomiędzy kanałami rozkład postaci a \cdot P i na wyjściu rozkład a \cdot P \cdot Q.


Ćwiczenie 2 [Łączenie BSC]

Załóżmy, że n identycznych binarnych kanałów symetrycznych \Gamma opisywanych macierzą M=\begin{pmatrix} P & \bar{P} \\  \bar{P} & P \end{pmatrix} 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 \to \infty?

Wskazówka

Do obliczenia przepustowości skorzystaj z wartości własnych M (o wartościach 1 i 2P-1)

Rozwiązanie

Zgodnie z poprzednim ćwiczeniem powstały kanał \Gamma^n jest opisywany macierzą M^n. Przez indukcję można pokazać, że M^n ma postać \begin{pmatrix} P_n & \bar{P_n} \\  \bar{P_n} & P_n \end{pmatrix}, więc jest to kanał symetryczny. Wartościami własnymi M^n1 i (2P-1)^n, a więc 2P_n = tr(M^n) = 1+(2P-1)^n. Stąd P_n=\frac{1+(2P-1)^n}{2} i C_{\Gamma^n}=1-H(P_n)=1-H(\frac{1+(2P-1)^n}{2}).

Jeśli P=1 lub P=0, to C_{\Gamma^n}=1 dla wszystkich n.

W pozostałych przypadkach (2P-1)^n \to 0 czyli C_{\Gamma^n} \to 1-H(\frac{1}{2})=0.


Ćwiczenie 3 [Kanał Z]

Kanał Z jest opisywany przez następującą macierz:

Z = \begin{pmatrix} 1 & 0 \\  \frac{1}{2} & \frac{1}{2} \end{pmatrix}
Oblicz przepustowośc tego kanału i znajdź rozkład prawdopodobieństwa na wejściu, który pozwala ją uzyskać.

Rozwiązanie

Dla rozkładu wejściowego A:Pr(x=0)=p otrzymujemy na wyjściu rozkład B:Pr(x=0)=p+\frac{1}{2}(1-p)=\frac{1+p}{2}. Wyliczamy

\aligned H(B) & = H(\frac{1+p}{2})\\ H(B|A) & =0 \cdot p + 1 \cdot (1-p) = 1-p\\ I(A,B) & =H(B)-H(B|A)=H(\frac{1+p}{2})+p-1 \endaligned

Aby znaleźć maksimum wyliczamy punkt, w którym pochodna się zeruje:

\aligned 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})+2\\ \frac{1+p}{2} & =2-2p\\ p & =\frac{3}{5} \endaligned

Optymalny rozkład prawdopodobieństwa na wejściu to Pr(x=0)=\frac{3}{5}. Przepustowość C_{\Gamma}=H(\frac{4}{5})-\frac{2}{5} \approx 0,3219


Ć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 P kanału.

Rozwiązanie

Wykres powinien wyglądać mniej więcej tak:

Grafika:ti_wykres1.jpg


Zadania domowe

Zadanie 1 - Kanał pięciokątny

Rozważmy kanał \Gamma, dla którego \mathcal{A}=\mathcal{B}=\{0,1,2,3,4\} i prawdopodobieństwa przejść wyglądają następująco: p(b|a)=\bigg\{ \begin{matrix} \frac{1}{2} & \mbox{ gdy } & b=a \pm 1 & (\mod 5)\\  0 & \mbox{ wpp.} & & \end{matrix}

Oblicz C_{\Gamma}. 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.}}