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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
następna edycja →
WizualnieWikikod
Stromy (dyskusja | edycje)
115 edycji
Nie podano opisu zmian
 
Stromy (dyskusja | edycje)
115 edycji
Nie podano opisu zmian
Linia 14: Linia 14:


{{cwiczenie|[Jeden bit informacji]|jbi|
{{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, 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? Ile bitów informacji byłby w stanie przekazać mogąc wysłać przez kanał 2,3 lub ogólnie ''n'' takich wiadomości?}}




Linia 20: Linia 20:
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 ===
=== Zadanie 1 - ISBN ===

Wersja z 11:51, 1 wrz 2006

Ćwiczenia

Ćwiczenie [Kanał P]

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

P=(120012120012120012)


Ć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, 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? 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 Yi=Xi⊕Zi, gdzie ⊕ oznacza dodawanie modulo 2. Zakładamy że zmienne Zi mają identyczne rozkłady Pr(Zi=0)=p, są niezależne od Xn ale poszczególne Z1,Z2,…,Zn nie są niezależne. Pokaż że kanał taki ma wyższą przepustowość niż zwykły symetryczny kanał binarny, tzn maxp(x1,…,xn)I(Xn;Yn)>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 a1…a10 ze zbioru {0,1,…,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: a10=a1+2a2+…+9a9(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?

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Teoria_informacji/TI_Ćwiczenia_9&oldid=38240”