Teoria informacji/TI Ćwiczenia 9

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Ćwiczenia

Ćwiczenie [Kanał P]

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


Ć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 , gdzie oznacza dodawanie modulo 2. Zakładamy, że zmienne mają identyczne rozkłady , są niezależne od , ale poszczególne nie są niezależne. Pokaż, że kanał taki ma wyższą przepustowość niż zwykły symetryczny kanał binarny, tzn. .


Zadanie domowe

Zadanie 1 - ISBN

Międzynarodowy Standardowy Numer Książki (ang. International Standard Book Number, ISBN) zawiera dziesięć znaków ze zbioru , gdzie 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: . 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?