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 $\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^{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_{\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

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

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

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

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:

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.}}