Teoria informacji/TI Ćwiczenia 9

Ćwiczenia

Ćwiczenie [Kanał P]

Znajdź optymalny rozkład prawdopodobieństwa wejściowego i przepustowość kanału opisanego macierzą

$P=\left(\begin{array}{ccc}\frac{1}{2}& 0& 0\\ \frac{1}{2}& \frac{1}{2}& 0\\ 0& \frac{1}{2}& \frac{1}{2}\\ 0& 0& \frac{1}{2}\end{array}\right)$

Ćwiczenie [Jeden bit informacji]

Rozważmy następującą sytuację. Gracze A i B są połączeni wiernym kanałem binarnym. Gracz A może jednak użyć tego kanału tylko do przesłania jednego bitu - potem kanał jest wyłączany. Gracze A i B mają jednak do dyspozycji zegary zsynchronizowane z dokładnością do sekundy, a gracz A może wybrać, w której sekundzie wyśle wiadomość do B. Ile bitów informacji A jest w stanie przekazać B, jeśli musi wysłać wiadomość w ciągu co najwyżej 1000 sekund? Ile bitów informacji byłby w stanie przekazać, mogąc wysłać przez kanał 2,3 lub ogólnie n takich wiadomości?

Ćwiczenie [Kanał z pamięcią]

Rozważmy kanał binarny, w którym $Y_i=X_i\oplus Z_i$, gdzie $\oplus$ oznacza dodawanie modulo 2. Zakładamy, że zmienne $Z_i$ mają identyczne rozkłady $Pr(Z_i=0)=p$, są niezależne od $X^n$, ale poszczególne $Z_1,Z_2,\dots ,Z_n$ nie są niezależne. Pokaż, że kanał taki ma wyższą przepustowość niż zwykły symetryczny kanał binarny, tzn. $ma{x}_{p(x_1,\dots ,x_n)}I(X^n;Y^n)>n(1-H(p))$.

Zadanie domowe

Zadanie 1 - ISBN

Międzynarodowy Standardowy Numer Książki (ang. International Standard Book Number, ISBN) zawiera dziesięć znaków $a_1\dots a_{10}$ ze zbioru $\{0,1,\dots ,9,X\}$, gdzie $X$ oznacza dziesiątkę. Pierwsze dziewięć znaków zawiera informacje o książce: kraj pochodzenia, wydawca i numer publikacji. Ostatni znak jest sumą kontrolną, zdefiniowaną jako suma poprzednich znaków pomnożonych przez ich pozycje, modulo 11: $a_{10}=a_1+2a_2+\dots +9a_9(mod11)$. Przykładowy poprawny ISBN wygląda następująco:

0-471-50193-X

Udowodnij, że taki kod pozwala wykryć dowolne przekłamanie jednego znaku lub zamianę miejscami dwóch znaków (dwa najczęściej popełniane w czasie przepisywania błędy).

Czy wyliczanie ostatniego znaku modulo 10 (zamiast 11) również pozwalałoby wykrywać te błędy?