Teoria informacji/TI Ćwiczenia 11

From Studia Informatyczne

Spis treści

Ćwiczenia

Ćwiczenie [Kanał Q]

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

Q = \begin{pmatrix} 1 & 0 & 0 \\ 0 & \frac{2}{3} & \frac{1}{3} \\ 0 & \frac{1}{3} & \frac{2}{3} \end{pmatrix}


Ćwiczenie [Kody wykrywające i poprawiające błędy]

Jaka musi być odległość pomiędzy słowami kodowymi, aby możliwe było wykrycie r błędów podczas transmisji?

Jaka musi być odległość, aby możliwe było naprawienie r błędów?


Zadania domowe

Zadanie 1 - Kanał bajtowy

Kanał Q na wejściu przekształca ośmiobitowe wejście na ośmiobitowe wyjście w ten sposób, że zawsze dokładnie jeden bit z ośmiu zostanie odwrócony. Każdy bit ma taką samą szansę na bycie odwróconym, a pozostałe 7 bitów jest przekazywanych poprawnie. Oblicz przepustowość tego kanału.

Zaprojektuj kod, który pozwala przekazywać bezbłędnie (z zerowym prawdopodobieństwem błędu) informacje przez ten kanał z szybkością 5 bitów/słowo.

Wskazówka

Spróbuj rozbudować kod Hamminga (7,4). Jakie zależności między słowami kodowymi tutaj muszą być spełnione?


Zadanie 2 - Przekazywanie skorelowanych danych

Wyobraźmy sobie, że chcemy przekazywać dane z dwóch źródeł A i B do centrum C przez wierne jednokierunkowe kanały. Sygnały x^{(A)} i x^{(B)} są silnie skorelowane, tak że ich entropia łączna jest niewiele większa niż entropia każdego z nich. Przykładowo, C może być centrum meteorologicznym, które chce otrzymywać w sposób ciągły informacje z dwóch niezbyt odległych punktów A i B, dotyczące tego, czy w danym punkcie pada, czy nie. Rozkład prawdopodobieństwa pary (x^{(A)},x^{(B)}) może być następujący:

\begin{matrix}           & x^{(A)} \\  x^{(B)} & \begin{matrix}  \\ 0 \\ 1 \end{matrix} \left| \begin{matrix}  0 & 1 \\ \hline  0,49 & 0,01\\ 0,01 & 0,49 \end{matrix} \end{matrix}

Zależy nam na tym, żeby ograniczać komunikację (bo np. jest kosztowna). Zaprojektuj mechanizm kodowania dla źródeł A i B taki, który wykorzystuje sumarycznie mniej niż dwa bity na każdą przekazaną parę. Jaka jest minimalna wymagana liczba bitów/parę, które muszą przekazać źródła żeby centrum mogło odtworzyć wartości obu zmiennych?


Zadanie 3 - Kanał z wieloma wejściami

Wyobraźmy sobie kanał, który ma dwa wejścia i jedno wyjście - na przykład dzieloną linię telefoniczną. W najprostszym modelu wejścia będą binarne x^A i x^B, a wyjście y trynarne, równe sumie wejść: 0, 1 lub 2. Nie ma żadnych zakłóceń transmisji. Nadawcy A i B nie mogą się ze sobą komunikować i nie słyszą wyjścia z kanału. Jeśli na wyjściu jest 0, odbiorca wie na pewno, że oba wejścia mają wartość 0. Podobnie jeśli na wyjściu jest 2 - oba wejścia musiały być ustawione na 1. Ale jeśli na wyjściu jest 1, wejściowy stan może być (0,1) lub (1,0). Łatwo zaprojektować system kodowania dla A i B który osiąga sumaryczną szybkość transmisji R_A+R_B=1. Czy da się to zrobić lepiej? Zaprojektuj kod lepiej wykorzystujący ten kanał i znajdź górną granicę na sumaryczną szybkość transmisji źródeł.