Teoria informacji/TI Wykład 7

From Studia Informatyczne

Kanały

Definicja [Kanał komunikacyjny]

Kanałem komunikacyjnym \Gamma nazywamy trójkę:
  • skończony zbiór \mathcal{A} symboli wejściowych
  • skończony zbiór \mathcal{B} symboli wyjściowych
  • mapowanie \mathcal{A} \times \mathcal{B} \to [0,1] określające dla każdej pary (a,b) prawdopodobieństwo P(a \to b) zamiany symbolu a na B, spełniające warunek:
\forall_{a \in \mathcal{A}} \sum_{b \in {\mathcal B}} P (a \to b) = 1


Zmienne losowe A i B o wartościach odpowiednio z \mathcal{A} i \mathcal{B} stanowią parę wejście-wyjście dla kanału \Gamma, jeśli dla dowolnych a \in \mathcal{A},b \in \mathcal{B}

p (B = b | A = a) = P (a \to b)

Kanał taki możemy zobrazować jako

A \tografika:Gamma.PNG\to B


Możemy od razu zauważyć, że

p ( A = a \, \wedge \, B = b)  = P (a \to b) \cdot p ( A = a )

A więc rozkład (A,B) jest jednoznacznie wyznaczony przez A (dla ustalonego \Gamma). W szczególności odpowiednie B zawsze istnieje i jest zdefiniowane jako p (B = b)  = \sum_{a \in {\mathcal A}} P (a \to b) \cdot p ( A = a )

Wiedząc to, można bezpośrednio policzyć H(A,B), H(B|A), I(A;B) itp. (w zależności od \Gamma i A).


Definicja [Przepustowość kanału]

Przepustowość kanału komunikacyjnego definiujemy jako
C_{\Gamma } = \max_{A} I (A;B)

(dla ustalenia uwagi, tutajI=I_2). Maksimum jest tutaj brane po wszystkich rozkładach zmiennej losowej A na \mathcal{A}. Istnieje ono zawsze, ponieważ I(A;B) jest ciągłym odwzorowaniem ze zbioru zwartego \{ p \in [0,1]^{{\mathcal A}} : \sum_{a \in {\mathcal A}} p(a) = 1 \} w \mathbb{R} i dodatkowo ograniczonym (I(A;B) \le H(A) \le \log|\mathcal{A}|).

Jeśli \mathcal{A}= \{ a_1, \ldots , a_m \} i \mathcal{B}= \{ b_1, \ldots , b_n \}, to możemy kanał reprezentować jako macierz :

\left(  \begin{matrix} P_{1 1} & \ldots & P_{1 n} \\ \ldots  & \ldots & \ldots \\ P_{m 1} & \ldots & P_{m n} \end{matrix} \right)

gdzie P_{i j} = p (a_i \to b_j )

W tej postaci wzór na rozkład zmiennej losowej B ma postać:

\left( p (a_1) , \ldots , p (a_m) \right) \cdot \left( \begin{matrix} P_{1 1} & \ldots & P_{1 n} \\ \ldots  & \ldots & \ldots \\ P_{m 1} & \ldots & P_{m n}, \end{matrix} \right) = \left( p (b_1) , \ldots , p (b_n)\right)


Przykłady

Proste kanały łatwo przedstawiać jako dwudzielne grafy skierowane o wierzchołkach z \mathcal{A} i \mathcal{B} oraz krawędziach a \to b etykietowanych przez P(a \to b) (rysowanych o ile P(a \to b) > 0).


Przykład [Wierny (bezszumowy) kanał]

Niech \mathcal{A}=\mathcal{B}=\{0,1\}. Wierny kanał przekazuje informację bez przekłamań:

grafika:faithful.PNG

Macierz reprezentująca ten kanał to

\left( \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} \right)

Skoro A jest zawsze równe B, to I(A;B)=H(A), a więc przepustowość tego kanału jest równa

C_{\Gamma } = \max_{A} I(A;B) =  \max_{A} H(A) = \log_2 |{\mathcal A}| = 1


Przykład [Wierny kanał odwracający]

Kanał analogiczny do poprzedniego, ale odwracający wszystkie przekazywane bity:

grafika:inverse.PNG

Reprezentacja macierzowa to

\left( \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} \right)
przepustowość tak jak w poprzednim przykładzie C_{\Gamma } = 1


Przykład [Kanał zaszumiony bez nakładania]

\mathcal{A}= \{0,1\}, \mathcal{B}=\{0,1,2,3\}

grafika:wooverlap.PNG

Macierz ma postać:

\left( \begin{matrix} \frac{1}{2} & \frac{1}{2} & 0 & 0  \\ 0 & 0 & \frac{1}{3} & \frac{2}{3} \end{matrix} \right)

Jak widać, A jest tutaj funkcją B, a więc I(A;B)=H(A)-H(A|B)=H(A).

Czyli znów C_{\Gamma } = 1


Przykład [Wadliwa maszyna do pisania]

Niech \mathcal{A}=\mathcal{B}=\{a,b,\ldots z\} (załóżmy 26 liter), i

p (\alpha \to \alpha ) = p (\alpha \to \mathit{next} ( \alpha ) ) = \frac{1}{2}

gdzie \mathit{next} (a) = b, \mathit{next} (b) = c, . . . \mathit{next} (y) = z, \mathit{next} (z) = a.

(wyobrażenie sobie reprezentacji grafowej i macierzowej zostawiamy czytelnikowi).

Aby obliczyć przepustowość, zacznijmy od obserwacji:

H(B | \alpha ) = p ( \alpha | \alpha ) \cdot \log \frac{1}{p ( \alpha | \alpha )} + p ( \mathit{next} ( \alpha )| \alpha ) \cdot \log \frac{1}{p ( \mathit{next} (\alpha )| \alpha )} = (\frac{1}{2} + \frac{1}{2}) \cdot \log_ 2 = 1

Skoro tak, możemy łatwo policzyć przepustowość rozpisując ją następująco:

C_{\Gamma } = \max_{A} I(A;B) = \max_{A} H(B) - \underbrace{H(B|A)}_{=1} = \log 26  - 1 = \log 13
(ponieważ możemy uzyskać maksymalną entropię B, np. dla jednostajnego rozkładu prawdopodobieństwa na A).


Czytelnik być może już ma intuicyjne pojęcie przepustowości kanału jako konkretnej liczby, tak jak informacja lub entropia. Zadamy zatem kolejne pytanie: jakie kanały mają zerową przepustowość?


Złe kanały Aby uzyskać C_{\Gamma } = 0, musimy mieć I(A;B)=0 dla dowolnego rozkładu danych wejściowych, czyli pary A i B zawsze muszą być niezależne. Formalnie to wymaganie oznacza, że p(B=b|A=a)=p(B=b), dla wszystkich a \in \mathcal{A}, b \in \mathcal{B}. Przykładowymi złymi kanałami są:

\left( \begin{matrix} \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} \end{matrix} \right)

\left( \begin{matrix} \frac{1}{2} & 0 & \frac{1}{6} &\frac{1}{3}  \\ \frac{1}{2} & 0 & \frac{1}{6} &\frac{1}{3} \end{matrix} \right)

\left( \begin{matrix} 0 & 0 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 1 \end{matrix} \right)

Ostatni przykład przedstawia szczególnie bezużyteczny kanał, który na wyjściu zawsze daje taką samą wartość. W tym przypadku H(B)=0, co pokazuje, że entropia może czasem maleć przy przesyłaniu wiadomości przez kanał. Najbardziej interesujące są jednak przypadki, gdy ta entropia rośnie. Jednym z takich przypadków zajmiemy się teraz dokładniej:


Binarny kanał symetryczny (BSC)

W tym przypadku znów \mathcal{A}=\mathcal{B}=\{0,1\}

grafika:BSC.PNG

Wprowadzając oznaczenie \bar{P}=1-P, macierz kanału możemy zapisać jako:

\left( \begin{matrix} P & \bar{P} \\ \bar{P} & P  \end{matrix} \right)


Fakt

Jeśli (A,B) jest parą wejście-wyjście dla BSC, to
H(B) \ge H(A)

Ponadto równość zachodzi wyłącznie jeśli P \in \{0,1\} (czyli kanał jest wierny lub wierny-odwracający) lub jeśli H(A)=1 (czyli entropia A jest maksymalna).

Dowód

Niech q=p(A=0). Wtedy p(A=1)=\bar{q}, i możemy wyznaczyć rozkład B z formuły:
\left( q, \bar{q} \right) \cdot \left( \begin{matrix} P & \bar{P} \\ \bar{P} & P \end{matrix} \right) = ( \underbrace{q P +\bar{q} \bar{P}}_{p(B = 0)},   \underbrace{q \bar{P} + \bar{q} P}_{p(B = 1)} )

Wprowadźmy oznaczenie r=p(B=0). Wtedy

\aligned H(A)& =-q \log q - \bar{q} \log \bar{q}\\ H(B)& =-r \log r - \bar{r} \log \bar{r} \endaligned

Przypominamy naszą konwencję 0 \log_r 0 = 0 \log_r \frac{1}{0} = 0 i oznaczamy przez h funkcję

h(x)=x \ln x + (1-x) \ln (1-x)

Dla 0 \le x \le 1. Łatwo możemy policzyć (dla 0<x<1):

\aligned h'(x)& =1+\ln x -1 -\ln (1-x)\\ h''(x)&=\frac{1}{x}+\frac{1}{1-x} > 0  \endaligned

Zatem na podstawie lematu o funkcjach wypukłych funkcja h(x) jest ściśle wypukła na przedziale [0,1], a więc wypukła jest też funkcja

\log_2 e \cdot h(x) = x \log_2 x + (1-x) \log_2 (1-x)

Korzystając teraz z faktu, że zdefiniowane wyżej r jest kombinacją liniową q i \bar{q} (kontretnie r=Pq+(1-P)\bar{q}), a h(q)=h(\bar{q}), otrzymujemy

q \log q + \bar{q} \log \bar{q} \ge r \log r + \bar{r} \log \bar{r}


H(A) \le H(B)
i równość ma miejsce tylko jeśli P \in \{0,1\} lub jeśli q=q' (czyli gdy H(A)=1). image:End_of_proof.gif


Wyliczymy teraz C_{\Gamma }. Wygodnie będzie nam używać notacji

H(s) = - s \log_2 s - (1-s) \log_2 (1-s)

(co interpretujemy jako entropię zmiennej binarnej o prawdopodobieństwach s i 1-s).

Funkcja ta przyjmuje maksimum równe 1 dla s=\frac{1}{2}. Jej wykres wygląda następująco:

Grafika:Entropia.PNG


Z definicji entropii warunkowej dostajemy:

\aligned H (B |A)& = p(A = 0) \cdot \left( p (B = 0 | A = 0) \cdot \log \frac{1}{p (B = 0 | A = 0)} + p (B = 1 | A = 0) \cdot \log \frac{1}{p (B = 1 | A = 0)} \right)\\ & + p(A = 1)  \cdot \left( p (B = 0 | A = 1) \cdot \log \frac{1}{p (B = 0 | A = 1)} + p (B = 1 | A = 1) \cdot \log \frac{1}{p (B = 1 | A = 1)} \right)\\ & = p(A = 0) \cdot \left( P \cdot \log \frac{1}{P} + \bar{P} \cdot \log \frac{1}{\bar{P}} \right) + p(A = 1) \cdot \left( \bar{P} \cdot \log \frac{1}{\bar{P}} + P \cdot \log \frac{1}{P} \right)\\ & = P \cdot \log \frac{1}{P} + \bar{P} \cdot \log \frac{1}{\bar{P}}\\ & = H(P)  \endaligned

A zatem H(B|A) nie zależy od A.


Korzystając z powyższego wyliczenia rozkładu B, mamy

H(B)=H(qP+\bar{q}\bar{P})

Możemy teraz znaleźć rozkład A, który maksymalizuje tę wartość (dla q=\frac{1}{2}), i otrzymujemy:

C_{\Gamma}= \max_{A} H(B) - H(B|A) = 1 - H(P)