Teoria informacji/TI Wykład 7

Kanały

Definicja [Kanał komunikacyjny]

Kanałem komunikacyjnym $\mathrm{\Gamma }$ nazywamy trójkę:

• skończony zbiór ${𝒜}$ symboli wejściowych
• skończony zbiór ${ℬ}$ symboli wyjściowych
• mapowanie ${𝒜}\times {ℬ}\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:

${\mathrm{\forall }}_{a\in {𝒜}}\sum _{b\in {ℬ}}P(a\to b)=1$

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

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

Rysunek TODO

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 $\mathrm{\Gamma }$. W szczególności odpowiednie B zawsze istnieje i jest zdefiniowane jako $p(B=b)=\sum _{a\in {𝒜}}P(a\to b)\cdot p(A=a)$

Więdząc to, można bezpośrednio policzyć H(A,B), H(B|A), I(A;B) itp. (w zależności od $\mathrm{\Gamma }$ i A).

Definicja [Przepustowość kanału]

Przepustowość kanału komunikacyjnego definiujemy jako

$C_{\mathrm{\Gamma }}=\underset{A}{\max }I(A;B)$

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

Jeśli ${𝒜}=\{a_1,\dots ,a_m\}$ i ${ℬ}=\{b_1,\dots ,b_n\}$, to możemy kanał reprezentować jako macierz:

$\left(\begin{array}{ccc}{P}_{11}& \dots & P_{1n}\\ \dots & \dots & \dots \\ P_{m1}& \dots & P_{mn}\end{array}\right)$

gdzie $P_{ij}=p(a_i\to b_j)$

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

$(p(a_1),\dots ,p(a_m))\cdot \left(\begin{array}{ccc}{P}_{11}& \dots & P_{1n}\\ \dots & \dots & \dots \\ P_{m1}& \dots & P_{mn},\end{array}\right)=(p(b_1),\dots ,p(b_n))$

Przykłady

Poste kanały łatwo przestawiać jako dwudzielne grafy skierowane o wierzchołkach z ${𝒜}$ i ${ℬ}$, i krawędziach $a\to b$ etykietowanych przez $P(a\to b)$ (rysowanych o ile $P(a\to b)>0$.

Wierny (bezszumowy) kanał Niech ${𝒜}={ℬ}=\{0,1\}$

Rysunek TODO

Macierz reprezentująca ten kanał to $\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\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_{\mathrm{\Gamma }}=\underset{A}{\max }I(A;B)=\underset{A}{\max }H(A)={\log }_2|{𝒜}|=1$

Wierny kanał odwracający

Rysunek TODO

Reprezentacja macierzowa $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, przepustowość $C_{\mathrm{\Gamma }}=1$

Kanał zaszumiony bez nakładania ${𝒜}=\{0,1\},{ℬ}=\{0,1,2,3\}$

Macierz ma postać: $\left(\begin{array}{cccc}\frac{1}{2}& \frac{1}{2}& 0& 0\\ 0& 0& \frac{1}{3}& \frac{2}{3}\end{array}\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_{\mathrm{\Gamma }}=1$.

Wadliwa maszyna do pisania Niech ${𝒜}={ℬ}=\{a,b,\dots z\}$ (załóżmy 26 liter), i

$p(\alpha \to \alpha )=p(\alpha \to {n}{e}{x}{t}(\alpha ))=\frac{1}{2}$,

Gdzie ${n}{e}{x}{t}(a)=b$, ${n}{e}{x}{t}(b)=c$, . . . ${n}{e}{x}{t}(y)=z$, ${n}{e}{x}{t}(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({n}{e}{x}{t}(\alpha )|\alpha )\cdot \log \frac{1}{p({n}{e}{x}{t}(\alpha )|\alpha )}=(\frac{1}{2}+\frac{1}{2})\cdot {\log }_2=1$

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

$C_{\mathrm{\Gamma }}=\underset{A}{\max }I(A;B)=\underset{A}{\max }H(B)-\underset{=1}{\underbrace{H(B|A)}}=\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_{\mathrm{\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 {𝒜},b\in {ℬ}$. Przykładowymi złymi kanałami są:

$\left(\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& \frac{1}{2}\end{array}\right)$

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

$\left(\begin{array}{ccc}0& 0& 1\\ 0& 0& 1\\ 0& 0& 1\end{array}\right)$

Ostatni przykład przedstawia szczególnie bezużyteczny kanał, który na wejś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 ${𝒜}={ℬ}=\{0,1\}$

Rysunek TODO

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

$\left(\begin{array}{cc}P& \overline{P}\\ \overline{P}& P\end{array}\right)$

Fakt

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

$H(B)\ge H(A)$

Ponadto równości 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)=\overline{q}$, i możemy wyznaczyć rozkład B z formuły:

$(q,\overline{q})\cdot \left(\begin{array}{cc}P& \overline{P}\\ \overline{P}& P\end{array}\right)=(\underset{p(B=0)}{\underbrace{qP+\overline{q}\overline{P}}},\underset{p(B=1)}{\underbrace{q\overline{P}+\overline{q}P}})$

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

$H(A)=-q\log q-\overline{q}\log \overline{q}$

$H(B)=-r\log r-\overline{r}\log \overline{r}$

Przypominamy naszą konwencję (TODO link) $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$):

$h^{\prime }(x)=1+\ln x-1-\ln (1-x)$

$h^{″}(x)=\frac{1}{x}+\frac{1}{1-x}>0$

Zatem na podstawie lematu o funkcjach wypukłych (TODO link), 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 $\overline{q}$ (r=Pq+(1-P)q'), a $h(q)=h(\overline{q})$, otrzymujemy

$q\log q+\overline{q}\log \overline{q}\ge r\log r+\overline{r}\log \overline{r}$

$H(A)\le H(B)$

i równość zachodzi tylko jeśli $P\in \{0,1\}$, lub jeśli q=q' (co zachodzi tylko gdy H(A)=1). QED.

Wyliczymy teraz $C_{\mathrm{\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).

Z definicji entropii warunkowej dostajemy:

$H(B|A)=$

$=p(A=0)\cdot (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)})$

$+p(A=1)\cdot (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)})$

$=p(A=0)\cdot (P\cdot \log \frac{1}{P}+\overline{P}\cdot \log \frac{1}{\overline{P}})+p(A=1)\cdot (\overline{P}\cdot \log \frac{1}{\overline{P}}+P\cdot \log \frac{1}{P})$

$=P\cdot \log \frac{1}{P}+\overline{P}\cdot \log \frac{1}{\overline{P}}$

$=H(P)$

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

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

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

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

$C_{\mathrm{\Gamma }}=\underset{A}{\max }H(B)-H(B|A)=1-H(P)$