Teoria informacji/TI Ćwiczenia 9: Różnice pomiędzy wersjami

Aktualna wersja na dzień 09:30, 20 wrz 2006

Ćwiczenia

Ćwiczenie [Kanał P]

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

P = (\begin{matrix} \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{matrix})

Ć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

P r (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.

m a 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} + 2 a_{2} + \dots + 9 a_{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?

@@ Linia 14: / Linia 14: @@
 {{cwiczenie|[Jeden bit informacji]|jbi|
-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, i 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?}}
+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?}}
 {{cwiczenie|[Kanał z pamięcią]|kzs|
-Rozważmy kanał binarny w którym <math>Y_i=X_i \oplus Z_i</math>, gdzie <math>\oplus</math> oznacza dodawanie modulo 2. Zakładamy że zmienne <math>Z_i</math> mają identyczne rozkłady <math>Pr(Z_i=0)=p</math>, są niezależne od <math>X^n</math> ale poszczególne <math>Z_1, Z_2, \ldots, Z_n</math> nie są niezależne. Pokaż że kanał taki ma wyższą przepustowość niż zwykły symetryczny kanał binarny, tzn <math>max_{p(x_1,\ldots,x_n)}I(X^n;Y^n) > n(1-H(p))</math>.}}
+Rozważmy kanał binarny, w którym <math>Y_i=X_i \oplus Z_i</math>, gdzie <math>\oplus</math> oznacza dodawanie modulo 2. Zakładamy, że zmienne <math>Z_i</math> mają identyczne rozkłady <math>Pr(Z_i=0)=p</math>, są niezależne od <math>X^n</math>, ale poszczególne <math>Z_1, Z_2, \ldots, Z_n</math> nie są niezależne. Pokaż, że kanał taki ma wyższą przepustowość niż zwykły symetryczny kanał binarny, tzn. <math>max_{p(x_1,\ldots,x_n)}I(X^n;Y^n) > n(1-H(p))</math>.}}
+== Zadanie domowe ==
 === Zadanie 1 - ISBN ===
@@ Linia 30: / Linia 32: @@
 <center>0-471-50193-X</center>
-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).
+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?

Teoria informacji/TI Ćwiczenia 9: Różnice pomiędzy wersjami

Aktualna wersja na dzień 09:30, 20 wrz 2006

Ćwiczenia

Zadanie domowe

Zadanie 1 - ISBN

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia