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)$

Kanał taki możemy zobrazować jako

$A\to$$\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 $\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)$

Wiedzą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

Proste kanały łatwo przedstawiać jako dwudzielne grafy skierowane o wierzchołkach z ${𝒜}$ i ${ℬ}$ 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 ${𝒜}={ℬ}=\{0,1\}$. Wierny kanał przekazuje informację bez przekłamań:

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$

Przykład [Wierny kanał odwracający]

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

Reprezentacja macierzowa to

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

Przykład [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$

Przykład [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$

Skoro tak, 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 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 ${𝒜}={ℬ}=\{0,1\}$

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ść 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

$\begin{array}{rl}H(A)& =-q\log q-\overline{q}\log \overline{q}\\ H(B)& =-r\log r-\overline{r}\log \overline{r}\end{array}$

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$):

$\begin{array}{rl}{h}^{\prime }(x)& =1+\ln x-1-\ln (1-x)\\ h^{″}(x)& =\frac{1}{x}+\frac{1}{1-x}>0\end{array}$

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 $\overline{q}$ (kontretnie $r=Pq+(1-P)\overline{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ść ma miejsce tylko jeśli $P\in \{0,1\}$ lub jeśli $q=q^{\prime }$ (czyli gdy $H(A)=1$).

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

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

Z definicji entropii warunkowej dostajemy:

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

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 maksymalizuje tę wartość (dla $q=\frac{1}{2}$), i otrzymujemy:

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