Teoria informacji/TI Ćwiczenia 9

From Studia Informatyczne

Ćwiczenia

Ćwiczenie [Kanał P]

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

P = \begin{pmatrix} \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{pmatrix}


Ć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, \ldots, Z_n nie są niezależne. Pokaż, że kanał taki ma wyższą przepustowość niż zwykły symetryczny kanał binarny, tzn. max_{p(x_1,\ldots,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 \ldots a_{10} ze zbioru \{0,1, \ldots, 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 + \ldots + 9a_9 (\mod 11). 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?