Teoria informacji/TI Ćwiczenia 7

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 $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 $\mathrm{\Gamma }$ opisywanych macierzą $M=\left(\begin{array}{cc}P& \overline{P}\\ \overline{P}& P\end{array}\right)$ 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 \mathrm{\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ł ${\mathrm{\Gamma }}^n$ jest opisywany macierzą $M^n$. Przez indukcję można pokazać, że $M^n$ ma postać $\left(\begin{array}{cc}{P}_n& \overline{P_n}\\ \overline{P_n}& P_n\end{array}\right)$, więc jest to kanał symetryczny. Wartościami własnymi $M^n$ są $1$ 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_{{\mathrm{\Gamma }}^n}=1-H(P_n)=1-H(\frac{1+(2P-1{)}^n}{2})$.

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

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

Ćwiczenie 3 [Kanał Z]

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

$Z=\left(\begin{array}{cc}1& 0\\ \frac{1}{2}& \frac{1}{2}\end{array}\right)$ 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

$\begin{array}{rl}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\end{array}$

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

$\begin{array}{rl}{I}^{\prime }(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}\end{array}$

Optymalny rozkład prawdopodobieństwa na wejściu to $Pr(x=0)=\frac{3}{5}$. Przepustowość $C_{\mathrm{\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:

Zadania domowe

Zadanie 1 - Kanał pięciokątny

Rozważmy kanał $\mathrm{\Gamma }$, dla którego ${𝒜}={ℬ}=\{0,1,2,3,4\}$ i prawdopodobieństwa przejść wyglądają następująco: $p(b|a)=\{\begin{array}{cccc}\frac{1}{2}& \text{ gdy }& b=a\pm 1& (mod5)\\ 0& \text{ wpp.}& & \end{array}$

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