Teoria informacji/TI Wykład 10

Efektywne kodowanie wiadomości

Dla pary wejście-wyjście (A,B), rozważmy dodatkową zmienną losową

E=A\oplus B

możemy ją interpretować jako sygnaturę błędu w czasie transmisji. Zachodzi równość

p(b|a)=p(E=a\oplus b)

Wynika to z definicji BSC:

p(b|a)={\begin{matrix}P&a=b&(a\oplus b=0)\\Q&a\neq b&(a\oplus b=1)\end{matrix}}

i zauważenia że

p(E=0)=p(A=0)\cdot p(0\to 0)+p(A=1)\cdot p(1\to 1)=P

p(E=1)=p(A=0)\cdot p(0\to 1)+p(A=1)\cdot p(1\to q)=Q

Rozważmy teraz sekwencję par wejście-wyjście $(A_{1},B_{1}),\ldots ,(A_{k},B_{k})$ , zachowującą niezależność symboli. Implikuje to że zmienne losowe $E_{1},\ldots ,E_{k}$ (gdzie $E_{i}=A_{i}\oplus B_{i}$ są niezależne (zauważmy że implikacja w drugą stronę nie zawsze zachodzi): Używając notacji $p({\vec {E}}={\vec {e}})$ lub po prostu $p({\vec {e}}$ na oznaczenie $p(E_{1}=e_{1}\wedge \ldots \wedge E_{k}=e_{k})$ możemy to zapisać

p(e_{1}\ldots e_{k})=\sum _{\vec {a}}p({\vec {A}}={\vec {a}}\wedge {\vec {B}}={\vec {a}}\oplus {\vec {e}})=\sum _{\vec {a}}p({\vec {A}}={\vec {a}})\cdot p({\vec {B}}={\vec {a}}\oplus {\vec {e}}|{\vec {A}}={\vec {a}})

.

Używając niezależności symboli oraz TODO dostajemy

$p({\vec {B}}={\vec {a}}\oplus {\vec {e}}|{\vec {A}}={\vec {a}})=p(B_{1}=a_{1}\oplus e_{1}|A_{1}=a_{1})\cdot \ldots \cdot p(B_{k}=a_{k}\oplus e_{k}|A_{k}=a_{k})$

=p(E_{1}=e_{1})\cdot \ldots \cdot p(E_{k}=e_{k})

dla dowolnego ${\vec {a}}$ . A więc

p(e_{1}\ldots e_{k})=p(e_{1})\cdot \ldots \cdot p(e_{k})

Załóżmy że dysponujemy opisanym wyżej symetrycznym kanałem $\Gamma$ w którym P>Q, i chcemy przesyłać nim wartości zmiennej losowej X o wartościach z ${\mathcal {X}}=\{x_{1},\ldots ,x_{m}\}$ . We wcześniejszych wykładach poznaliśmy techniki efektywnego kodowania wartości. Jeśli kanał jest wierny, wystarczy że znajdziemy optymalne kodowanie $\varphi :{\mathcal {X}}\to \{0,1\}^{*}$ i będziemy wysyłać bit po bicie. Oczekiwana długość (czas) transmisji będzie ograniczony wtedy przez H(X)+1 (link TODO). Z drugiej strony, zawsze możemy zakodować ${\mathcal {X}}$ używając ciągów długości $\lceil \log m\rceil$ , co daje nam ograniczenie na pesymistyczny czas transmisji (te dwa ograniczenia mogą nie dać się zachować jednocześnie dla żadnego kodowania).

Jeśli jednak kanał nie jest wierny, ta metoda będzie prowadziła do błędów. Przykład TODO pokazuje że będziemy musieli użyć redundantnego, a więc nieoptymalnego kodowania. Zajmiemy się teraz szukaniem metod pogodzenia tych dwóch przeciwstawnych celów:

używaniem jak najmniejszej redundancji
zmiejszenia prawdopodobieństwa błędu do jak najniższego poziomu

Ogólny schemat postępowania będzie następujący

Algorytm transmisji

(dla zmiennej losowej X o wartościach w  ${\mathcal {X}}=\{x_{1},\ldots ,x_{m}\}$  i kanału  $\Gamma$ )
1. Wybierz  $n\in \mathbb {N}$  i  $C\subseteq \{0,1\}^{n}$  takie że  $|C|=m$ 
2. Ustal bijekcję  $\varphi :{\mathcal {X}}\to C$  (oczywiście taki kod będzie bezprefiksowy). 
3. Prześlij ciąg znaków  $\varphi (X)=a_{1}\ldots a_{n}$  przez kanał  $\Gamma$  bit po bicie, 
otrzymując na wyjściu  $Y=b_{1}\ldots b_{n}$ .
4. Aby odkodować wiadomość wybierz  $a_{1}\ldots a_{n}\in C$  takie dla którego  $p(b_{1}\ldots b_{n}|a_{1}\ldots a_{n})$  jest maksymalne

Zakładając że kanał jest bezstanowy i pozbawiony feedbacku (link TODO), mamy

p(b_{1}\ldots b_{k}|a_{1}\ldots a_{k})=Q^{d({\vec {a}},{\vec {b}})}\cdot P^{1-d({\vec {a}},{\vec {b}})}

Użyta reguła dekodowania wskazuje zatem dla każdego ciągu $b_{1}\ldots b_{n}$ ciąg $\Delta (b_{1}\ldots b_{n})\in C$ , najbliższy możliwy w sensie odległości Hamminga (jeśli jest kilka równie odległych to wybierany jest któryś z nich). Jest to tak zwana reguła dobrosąsiedzka.

Dla uproszczenia możemy utożsamić ${\mathcal {X}}$ z C (za pomocą bijekcji $\varphi$ ) i traktować X jako zmienną losową o wartościach w C.

Na opisaną powyżej procedurę możemy patrzeć jak na nowy kanał (z C do C):

C\ni a_{1}\ldots a_{n}\to \Gamma \to b_{1}\ldots b_{n}\to \Delta (b_{1}\ldots b_{n})\in C

z prawdopodobieństwem błędu

Pr_{E}(\Delta ,X)=p(\Delta \circ Y\neq X)

Naszą pierwszą obserwacją będzie fakt że najgorszym możliwym rozkładem X jest rozkład jednostajny ( $p(x)={\frac {1}{m}}$ dla $x\in C$ )

Fakt

Niech X i U będą dwiema zmiennymi losowymi o wartościach w

C\subseteq \{0,1\}^{n}

. U niech będzie miała rozkład losowy, a X dowolny. Wtedy istnieje permutacja

\varphi :C\to C

taka że

Pr_{E}(\Delta ,\varphi \circ X)\leq Pr_{E}(\Delta ,U)

Dowód

TODO

Przy analizowaniu jakości naszych metod możemy zatem bez utraty ogólności zakładać że rozkład X jest jednostajny. W takim przypadku $Pr_{E}(\Delta ,X)$ zależy jedynie od C, a więc możemy używać notacji $Pr_{E}(\Delta ,C)$ .

Redundancję mierzymy porównując entropię C (o wartości $\log _{2}|C|$ ) (link TODO), z faktyczną długością kodu (w naszym przypadku n).

Definicja [Szybkość transmisji]

Szybkością transmisji kodu $C\subseteq \{0,1\}^{n}$ nazywamy wartość

R(C)={\frac {\log _{2}|C|}{n}}

Intuicyjnie możemy rozumieć że aby przesłać $\log _{2}|C|$ bitów informacji, używamy faktycznie n bitów, a więc przesyłamy bity z szybkością ${\frac {\log _{2}|C|}{n}}$ </math> bitów na znak.

Dwa warunki jakie postawiliśmy w TODO oznaczają teraz że chcemy zminimalizować zarówno $Pr_{E}(\Delta ,C)$ jak i R(C).

Przykład [Wadliwa maszyna do pisania]

Wrócimy do przykładu wadliwej maszyny do pisania (link TODO). Z pewnością taki kanał generuje bardzo dużo błędów. Jednak jeśli użyjemy tylko nieparzystych liter ( $a,c,e,g,\ldots$ ) to będziemy mogli zawsze odkodować wiernie otrzymane znaki.

Czy możemy użyć tej obserwacji do przesyłania dowolnych wiadomości?

Najprostszym pomysłem jest kodowanie liter jako par, używając wciąż tylko połowy znaków, np.:

${\begin{matrix}a&&aa\\b&&ac\\c&&cc\\d&&ce\\\ldots &&\end{matrix}}$

Szybkość transmisji w tym przypadku wynosi ${\frac {1}{2}}$ . Czy można to zrobić lepiej?

Jeśli mielibyśmy dodatkowy symbol, np. #, który potrafilibyśmy odkodować bezbłędnie, moglibyśmy zakodować symbole w następujący sposób:

${\begin{matrix}a&&a\\b&&\#a\\c&&c\\d&&\#c\\\ldots &&\end{matrix}}$

Średnia długość kodu wynosi tu

{\frac {1}{2}}\cdot 1+{\frac {1}{2}}\cdot 2={\frac {3}{2}}

, a więc szybkość transmisji wynosi

{\frac {2}{3}}

. Możemy tę metodę wykorzystać bez rozszerzania alfabetu, wybierając jedną literę, np. a, aby grała rolę #, i kodując a przez aa, b przez ca i c przez cc (aby zachować bezprefiksowość kodu). Uzyskamy wtedy szybkość transmisji niewiele mniejszą niż

{\frac {2}{3}}

. Rozwinięcie tej metody pozwala podnieść szybkość transmisji do wartości bliskiej 1 (TODO ćwiczenie).

Przykład [Wielokrotny BSC]

W tym przykładzie rozważmy kanał BSC i poprawienie jego jakości przez wysłanie każdego bitu wielokrotnie (link TODO). Niech

n=k\cdot l

i niech

m=2^{k}

. Wtedy dowolny ciąg bitów

a_{1}\ldots a_{k}

możemy zakodować jako

a_{1}^{l}\ldots a_{k}^{l}\in \{0,1\}^{n}

, uzyskując kod o szybkości transmisji

{\frac {1}{l}}

. Podobna analiza jak (link TODO) pokazuje że dla dowolnego k jesteśmy w stanie zmniejszyć

Pr_{E}(\Delta ,C)

do dowolnie małej wartości, wystarczająco wydłużając l. Oznacza to że teoretycznie, o ile kanał nie jest całkowicie chaotyczny (czyli

P\neq Q

), możemy nim przesyłać wiadomości z dowolnie małym prawdopodobieństwem błędu - ale ceną za to jest spowalnianie prędkości transmisji prawie do zera.

Główne Twierdzenie Shannona mówi że sytuacja w rzeczywistości jest o wiele lepsza. Możemy osiągnąć to samo zachowując szybkość transmisji bliską pewnej stałej, konkretnie (link TODO) przepustowości kanału $C_{\Gamma }$ .

Zanim przejdziemy do samego twierdzenie pokażemy dolne ograniczenie, dowodzące że lepszej szybkości transmisji w ogólności nie da się uzyskać. Zaczniemy od dowiedzenia tego gdy prawdopodobieństwo błędu musi być zerowe, i w dalszej części pokażemy jak ten dowód rozszerza się na dodatnie prawdopodobieństwa. Tutaj $\Gamma$ może być dowolnym kanałem, ale jak zwykle zakładamy niezależność symboli.

Fakt [Przepustowość kanału]

Jeśli $Pr_{E}(\Delta ,C)=0$ to

R(C)\leq C_{\Gamma }

Dowód

Niech

X=(A_{1},\ldots A_{n})

i

Y=(B_{1},\ldots B_{n})

będą zmiennymi z (link TODO) algortymu transmisji. Używając niezależności symboli możemy łatwo policzyć że

H(Y|X)=H(B_{1}|A_{1})+\ldots +H(B_{n}|A_{n})

.

Wiemy ponadto (link TODO) że

H(Y)\leq H(B_{1})+\ldots +H(B_{n})

Czyli $I(X,Y)=H(Y)-H(Y|X)$

\leq \sum _{i=1}^{n}H(B_{i})-\sum _{i=1}^{n}H(B_{i}|A_{i})

=\sum _{i=1}^{n}\underbrace {(H(B_{i})-H(B_{i}|A_{i}))} _{=I(A_{i},B_{i})}

\leq n\cdot C_{\Gamma }

(z definicji $C_{\Gamma }$ )

Z drugiej strony mamy

I(X,Y)=H(X)-\underbrace {H(X|Y)} _{=0}=\log _{2}m

(gdzie $m=|C|$ ). Tutaj $H(X|Y)$ ma wartość zero, ponieważ założenie $Pr_{E}(\Delta ,C)=0$ implikuje że X jest funkcją Y (konkretnie $X=\Delta (Y)$ . Ponadto $H(X)=\log _{2}m$ gdyż X ma rozkład jednostajny. Ostatecznie zatem