Teoria informacji/TI Ćwiczenia 11: Różnice pomiędzy wersjami
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 13: | Linia 13: | ||
{{cwiczenie|[Kody wykrywające i poprawiające błędy]|kwb| | {{cwiczenie|[Kody wykrywające i poprawiające błędy]|kwb| | ||
Jaka musi być odległość pomiędzy słowami kodowymi aby możliwe było wykrycie <math>r</math> błędów podczas transmisji? | Jaka musi być odległość pomiędzy słowami kodowymi, aby możliwe było wykrycie <math>r</math> błędów podczas transmisji? | ||
Jaka musi być odległość aby możliwe było naprawienie <math>r</math> błędów?}} | Jaka musi być odległość, aby możliwe było naprawienie <math>r</math> błędów?}} | ||
| Linia 21: | Linia 21: | ||
=== Zadanie 1 - Kanał bajtowy === | === Zadanie 1 - Kanał bajtowy === | ||
Kanał Q na wejściu przekształca ośmiobitowe wejście na ośmiobitowe wyjście | 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. | 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. | ||
{{wskazowka||| | {{wskazowka||| | ||
| Linia 36: | Linia 36: | ||
=== Zadanie 2 - Przekazywanie skorelowanych danych === | === Zadanie 2 - Przekazywanie skorelowanych danych === | ||
Wyobraźmy sobie że chcemy przekazywać dane z dwóch źródeł <math>A</math> i <math>B</math> do centrum <math>C</math> przez wierne jednokierunkowe kanały. Sygnały <math>x^{(A)}</math> i <math>x^{(B)}</math> są silnie skorelowane, tak że ich entropia łączna jest niewiele większa niż entropia każdego z nich. Przykładowo <math>C</math> 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 <math>(x^{(A)},x^{(B)})</math> może być następujący: | Wyobraźmy sobie, że chcemy przekazywać dane z dwóch źródeł <math>A</math> i <math>B</math> do centrum <math>C</math> przez wierne jednokierunkowe kanały. Sygnały <math>x^{(A)}</math> i <math>x^{(B)}</math> są silnie skorelowane, tak że ich entropia łączna jest niewiele większa niż entropia każdego z nich. Przykładowo, <math>C</math> 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 <math>(x^{(A)},x^{(B)})</math> może być następujący: | ||
<center><math> | <center><math> | ||
\begin{matrix} | \begin{matrix} | ||
| Linia 52: | Linia 52: | ||
</math></center> | </math></center> | ||
Zależy nam na tym żeby ograniczać komunikację (bo np. jest kosztowna). Zaprojektuj mechanizm kodowania dla źródeł | Zależy nam na tym, żeby ograniczać komunikację (bo np. jest kosztowna). Zaprojektuj mechanizm kodowania dla źródeł | ||
<math>A</math> i <math>B</math> 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? | <math>A</math> i <math>B</math> 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 === | === 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 <math>x^A</math> i <math>x^B</math>, a wyjście <math>y</math> 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ć | 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 <math>x^A</math> i <math>x^B</math>, a wyjście <math>y</math> 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 <math>R_A+R_B=1</math>. Czy da się to zrobić lepiej? Zaprojektuj kod lepiej wykorzystujący ten kanał i znajdź górną granicę na sumaryczną szybkość transmisji źródeł. | Łatwo zaprojektować system kodowania dla A i B który osiąga sumaryczną szybkość transmisji <math>R_A+R_B=1</math>. Czy da się to zrobić lepiej? Zaprojektuj kod lepiej wykorzystujący ten kanał i znajdź górną granicę na sumaryczną szybkość transmisji źródeł. | ||
Aktualna wersja na dzień 10:38, 20 wrz 2006
Ćwiczenia
Ćwiczenie [Kanał Q]
Znajdź optymalny rozkład prawdopodobieństwa wejściowego i przepustowość kanału opisanego macierzą
Ć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 błędów podczas transmisji?
Jaka musi być odległość, aby możliwe było naprawienie 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
Zadanie 2 - Przekazywanie skorelowanych danych
Wyobraźmy sobie, że chcemy przekazywać dane z dwóch źródeł i do centrum przez wierne jednokierunkowe kanały. Sygnały i są silnie skorelowane, tak że ich entropia łączna jest niewiele większa niż entropia każdego z nich. Przykładowo, 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 może być następujący:
Zależy nam na tym, żeby ograniczać komunikację (bo np. jest kosztowna). Zaprojektuj mechanizm kodowania dla źródeł i 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 i , a wyjście 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 . Czy da się to zrobić lepiej? Zaprojektuj kod lepiej wykorzystujący ten kanał i znajdź górną granicę na sumaryczną szybkość transmisji źródeł.
