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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycjanastępna edycja →
WizualnieWikikod
Stromy (dyskusja | edycje)
115 edycji
Nie podano opisu zmian
Stromy (dyskusja | edycje)
115 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
=== Kod Hamminga (7,4) ===
== Ćwiczenia ==


Projektowaniem efektywnych kodów korygujących błędy zajmuje się dziedzina informatyki nazywana teorią kodów.
{{cwiczenie|1 [Nieoptymalność reguły maksymalnego podobieństwa]|rmp|
Zwykle projektowanie kodu oznacza znalezienie kompromisu między efektywnością kodu i jego prostotą (mierzoną zarówno jako stopień złożoności samego algorytmu kodowania i dekodowania, jak i mocą obliczeniową potrzebną do tych operacji). Szczególnie użytecznymi kodami, ze względu na zwięzłość ich definicji, są kody liniowe.
Skonstruuj rozkład <math>A</math> i kanał <math>\Gamma</math> dla którego [[Teoria informacji/TI Wykład 8#maks_podob|reguła maksymalnego podobieństwa]] nie jest optymalną regułą. Skonstruuj przykład w którym reguła ta powoduje błąd z prawdopodobieństwem powyżej 90%.}}




{{definicja|[Kod liniowy]|kod_liniowy|
{{cwiczenie|2 [Wiedza zwiększająca niepewność]|wzn|
Kod liniowy długości <math>n</math> i rzędu <math>k</math> to dowolna liniowa podprzestrzeń <math>\mathcal{C}</math> wymiaru <math>k</math> w przestrzeni wektorowej <math>\mathbb{F}^n</math> gdzie <math>\mathbb{F}</math> jest skończonym ciałem. Przestrzeń <math>\mathcal{C}</math> definiuje zestaw poprawnych słów kodowych.
Na wykładzie wcześniej zostało pokazane że <math>H(Y|X) \le H(Y)</math>.
Bazę tej przestrzeni (w postaci <math>k</math> wektorów długości <math>n</math>) zapisuje się często w postaci macierzy generującej kodu.}}
Pokaż że nie zawsze tak jest w przypadku [[Teoria informacji/TI Ćwiczenia 2#entropia_kolizji|innych miar entropii]].
Znajdź przykład gdy uzyskanie jakiejś informacji może zwiększyć entropię Shannona innej informacji, tzn. <math>H(Y|X=a) > H(Y)</math>}}




Na tych ćwiczeniach bedziemy się zajmować tylko ciałem <math>Z_2</math>, czyli operacjami modulo 2.
{{cwiczenie|3 [Binarny kanał wymazujący]|bkg|
Przykładem prostego kodu liniowego nad ciałem <math>Z_2</math> jest Kod Hamminga (7,4). Koduje on czterobitowe wiadomości przy użyciu siedmiobitowych słów, w ten sposób że minimalna odległość Hamminga pomiędzy słowami kodowymi wynosi 3. Dzięki temu przekłamanie jednego bitu w każdym słowie może zostać zawsze wykryte i naprawione (czyli poprawny przekaz wiadomości jest możliwy gdy ilość błędów nie przekroczy 14%).
''Binarny kanał wymazujący'' wygląda następująco:


Macierz generująca tego kodu wygląda następująco:
<center>[[grafika:erasure.PNG]]</center>
<math>G := \begin{pmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 \\
1 & 1 & 0 & 1 \\
\end{pmatrix}</math>


W tym przypadku <math>\mathcal{A}=\{0,1\}</math>, <math>\mathcal{B}=\{0,1,?\}</math>. Jego macierz przejść to:
<center><math>
\begin{pmatrix}
P & 0 & 1-P \\
0 & P & 1-P
\end{pmatrix}
</math></center>


Macierz wykrywania błędów dla tego kodu wygląda następująco:
Oblicz przepustowość tego kanału.}}


<math>H_e := \begin{pmatrix}
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 \\
\end{pmatrix}</math>


{{cwiczenie|4 [Feedbacku dla kanału wymazującego]|wf|
W wielu praktycznych zastosowaniach nadawca może dowiedzieć się od odbiorcy jak przebiega komunikacja. Załóżmy że nadawca dysponujący binarnym kanałem wymazującym, po każdym przesłanym symbolu poznaje wartość symbola wyjściowego. Pokaż jak może wykorzystać tę informację do przesyłania wiadomości bezbłędnie z szybkością odpowiadającą przepustowości kanału.}}


Aby zakodować czterobitową wiadomość <math>m</math> mnoży się ją przez macierz <math>G</math> (wyliczając każdy współczynnik modulo 2). Uzyskane siedmiobitowe słowo przesyła się następnie przez kanał. Odbiorca mnoży otrzymaną wiadomość przez macierz wykrywania błędów <math>H_e</math>, uzyskując wektor o długości trzech bitów. Jeśli ten wektor jest zerowy, oznacza to że nie nastąpiło żadne przekłamanie (bądź nastąpiło ich więcej niż 2, czego przy uzyciu tego kodu może nie dać się wykryć). Jeśli wektor jest różny od zerowego, wektor odczytany jako liczba binarna wskazuje na którym bicie nastąpiło przekłamanie - wystarczy zatem odwrócić wartość tego bitu aby uzyskać pierwotną wiadomość. W przypadku gdy w bloku nastąpiło więcej niż jedno przekłamanie, końcowy wynik może być oczywiście nieprawidłowy.


== Zadania domowe ==


{{cwiczenie|[Dekodowanie kodu (7,4)]|Ćwiczenie 1|
=== Zadanie 1 - Przepustowość kanałów z feedbackiem ===
Udowodnij że jeśli nie nastąpiło przekłamanie, iloczyn macierzy wykrywania błędów i przesłanego wektora zawsze jest zerowy.
}}


{{rozwiazanie|||
Rozważmy kanał z pełną informacją zwrotną, w którym po przesłaniu każdego symbolu nadawca poznaje symbol na wyjściu.
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
''Kod z feedbackiem'' definiujemy jako sekwencję mapowań <math>x_i(W,Y^{i-1})</math> określających kolejny symbol <math>x_i</math> na podstawie przesyłanej wiadomości <math>W</math> i dotychczas dostarczonych symboli <math>Y_1, Y_2, \ldots, Y_{i-1}</math>.  
<div class="mw-collapsible-content" style="display:none">
''Przepustowość kanału z feedbackiem'' jest określana jako maksymalna szybkość transmisji przez kanał przy wykorzystaniu takiego kodu. Udowodnij że ta przepustowość jest równa klasycznej przepustowości kanału, czyli że wykorzystanie informacji zwrotnej nie może zwiększyć szybkości transmisji.
Wystarczy policzyć iloczyn <math>G \cdot H_e</math> nad ciałem <math>Z_2</math>. Wynik jest macierzą zerową, a więc dla każdego wektora wejściowego sygnatura błędu będzie zerowa.
Zauważ że nie jest to sprzeczne z ćwiczeniem 4 - jej wykorzystanie może znacząco uprościć konstrukcję samego kodu.
</div>
</div>
}}
 
 
{{cwiczenie|[Sygnatura błędu]|Ćwiczenie 2|
Pokaż że jeśli nastąpiło jedno przekłamanie, iloczyn macierzy wykrywania błędów i przesłanego wektora wskazuje pozycję na której to przekłamanie nastąpiło.
}}
 
{{rozwiazanie|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<div class="mw-collapsible-content" style="display:none">
Zgodnie z poprzednim ćwiczeniem wynik będzie równy iloczynowi macierzy <math>H_e</math> i wektora błędu, zawierającego jedną jedynkę na przekłamanej pozycji. Wystarczy zauważyć zatem że kolejne komumny <math>H_e</math> są zapisem binarnym kolejnych liczb naturalnych.
</div>
</div>
}}
 
 
{{cwiczenie|[Jakość przekazu]|Ćwiczenie 3|
Załóżmy że prawdopodobieństwo przekłamania każdego bitu wynosi 5%. Jaka byłaby szansa bezbłędnego przekazu czterobitowej wiadomości przy zwykłym przekazywnaiu jej bit po bicie? Jaka jest szansa bezbłędnego przekazania gdy jest zakodowana kodem Hamminga (7,4)?}}
 
{{rozwiazanie|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<div class="mw-collapsible-content" style="display:none">
W przypadku zwykłego przekazu informacja zostałaby przekazana bezbłędnie jeśli wszystkie 4 bity dotarłyby bez zmian. Prawdopodobieństwo tego jest równe <math>0,95^4 \approx 0,815</math>.
Po zakodowaniu informacja dociera poprawnie jeśli wszystkie 7 bitów dociera bez zmian lub następuje tylko jedno przekłamanie. Prawdopodobieństwo tego jest równe <math>0,95^7 + 7 \cdot 0,05 \cdot 0,95^6 \approx 0,956</math>.
</div>
</div>
}}
 
 
=== Kody liniowe ===
 
{{cwiczenie|[Idealne kody]|Ćwiczenie 4|
Kodem <math>(n,k,d)</math> nazywamy kod liniowy w którym <math>k</math>-bitowe słowa są zapisywane na <math>n</math> bitach, a minimalna odległość pomiędzy słowami kodowymi wynosi <math>d</math>.  
:a) Ile maksymalnie błędów może poprawiać taki kod?
:b) Jaką nierówność muszą spełniać wartości <math>n</math>, <math>k</math> i <math>d</math> aby taki kod mógł istnieć?
:c) Kod nazwiemy ''idealnym'', gdy może poprawiać <math>r</math> błędów i każde słowo jest w odległości co najwyżej <math>r</math> od najbliższego słowa kodowego. Dla jakich wartości <math>n</math> mogą istnieć kody idealne poprawiające 1 błąd?}}
 
{{rozwiazanie|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<div class="mw-collapsible-content" style="display:none">
:a) Kod taki może poprawiać maksymalnie <math>r=\frac{d-1}{2}</math> błędów.
:b) Z poprzedniego punktu wynika że dla wokół każdego słowa kodowego isnieje kula z <math>\sum_{i=0}^{r}{n \choose i}</math> słów, które są do niego sprowadzana przy naprawianiu błędów. Tym samym <math>2^n \ge 2^k \cdot \sum_{i=0}^{r}{n \choose i}</math>, czyli <math>n-k \ge \log_2 \sum_{i=0}^{r}{n \choose i}</math>
:c) Dla kodu idealnego <math>n-k = \log_2 \sum_{i=0}^{r}{n \choose i}</math>. Jeśli <math>r=1</math> to <math>n-k = \log_2 (n+1)</math>. Takie kody istnieją dla <math>n=2^j-1</math> i <math>j\ge 2</math>.
: Dwa najmniejsze przykłady już znamy: kod idealny (3,1,3) to trzykrotne powtórzenie każdego bitu, kod idealny (7,4,3) to kod Hamminga (7,4).
</div>
</div>}}
 
 
{{cwiczenie|[Szacowanie efektywnosci]|Ćwiczenie 5|
W zapisie informacji na płytach CD używa się kodu który do każdych 224 bitów dodaje 32 bity korygujące błędy (zapisując całość w bloku 256 bitów). Oszacuj jaka może być dla tego kodu maksymalna ilość korygowanych błędów w każdym bloku.}}
 
{{rozwiazanie|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<div class="mw-collapsible-content" style="display:none">
32 bity korygujące błędy oznaczają że na każde słowo kodowe przypada <math>2^{32}-1</math> słów które nie są kodowe.
Dla każdego słowa kodowego w odległości 1 od niego znajdują się 256 słów, w odległości 2: <math>{256 \choose 2} \approx 2^{31}</math> słów, a w odległości 3 <math>{256 \choose 3} > 2^{45} </math> słów. Przy optymalnym rozmieszczeniu słów kodowych można zatem umożliwić korekcję maksymalnie 2 błędów w każdym bloku 256 bitów. Kod ten zatem nie potrafi poprawnie odczytywać danych już przy 1% szumów.
</div>
</div>
}}
 
 
 
=== LDPC - macierze parzystości małej gęstości ===
Jedną z metod generowania efektywnych kodów blokowych jest metoda LDPC. W metodzie tej na n-bitowe słowo nakładanych jest k losowych restrykcji postaci <math>x_{i_1} \oplus \ldots \oplus x_{i_p} = 0</math>, gdzie <math>x_i</math> oznacza i-ty bit słowa kodowego. Parametry k i p są dobrane tak aby każdego bitu dotyczyła co najmniej jedna restrykcja. Kod tworzony jest tylko przez słowa spełniające wszystkie restrykcje.
 
{{cwiczenie|[Kod LDPC jest liniowy]|Ćwiczenie 6|
Udowodnij że kod LDPC jest kodem liniowym.}}
 
{{rozwiazanie|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<div class="mw-collapsible-content" style="display:none">
Słowo <math>0^n</math> spełnia wszystkie restrykcje, jest zatem słowem kodowym. Jeśli dwa słowa <math>x</math> i <math>y</math> spełniają wszystkie restrykcje, to <math>x \oplus y</math> również je spełnia. Tym samym zbiór słów kodowych jest podprzestrzenią <math>Z_2^n</math>, co należało pokazać.
</div>
</div>
}}
 
 
{{cwiczenie|[Szybkość kodów LDPC]|Ćwiczenie 7|
Jaka jest oczekiwana liczba słów spełniających wszystkie <math>k</math> restrykcji?}}
 
{{rozwiazanie|||
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
<div class="mw-collapsible-content" style="display:none">
Dla losowego słowa prawdopodobieństwo że spełnia on wybraną restrykcję wynosi <math>\frac{1}{2}</math>. Skoro wybór restrykcji jest losowy i niezależny, oczekiwana liczba słów spełniających je wszystkie wynosi <math>2^n \cdot (\frac{1}{2})^k = 2^{n-k}</math>.  
</div>
</div>
}}
 
 
{{cwiczenie|[Wydajność kodów LDPC]|Ćwiczenie 8|
Udowodnij że z dużym prawdopodobieństwem minimalna odległość między dowolną parą słów kodowych wynosi co najmniej <math>\frac{k}{\log n}</math>.}}

Wersja z 13:42, 24 sie 2006

Ćwiczenia

Ćwiczenie 1 [Nieoptymalność reguły maksymalnego podobieństwa]

Skonstruuj rozkład A i kanał Γ dla którego reguła maksymalnego podobieństwa nie jest optymalną regułą. Skonstruuj przykład w którym reguła ta powoduje błąd z prawdopodobieństwem powyżej 90%.


Ćwiczenie 2 [Wiedza zwiększająca niepewność]

Na wykładzie wcześniej zostało pokazane że H(Y|X)≤H(Y). Pokaż że nie zawsze tak jest w przypadku innych miar entropii.

Znajdź przykład gdy uzyskanie jakiejś informacji może zwiększyć entropię Shannona innej informacji, tzn. H(Y|X=a)>H(Y)


Ćwiczenie 3 [Binarny kanał wymazujący]

Binarny kanał wymazujący wygląda następująco:

W tym przypadku 𝒜={0,1}, ℬ={0,1,?}. Jego macierz przejść to:

(P01−P0P1−P)
Oblicz przepustowość tego kanału.


Ćwiczenie 4 [Feedbacku dla kanału wymazującego]

W wielu praktycznych zastosowaniach nadawca może dowiedzieć się od odbiorcy jak przebiega komunikacja. Załóżmy że nadawca dysponujący binarnym kanałem wymazującym, po każdym przesłanym symbolu poznaje wartość symbola wyjściowego. Pokaż jak może wykorzystać tę informację do przesyłania wiadomości bezbłędnie z szybkością odpowiadającą przepustowości kanału.


Zadania domowe

Zadanie 1 - Przepustowość kanałów z feedbackiem

Rozważmy kanał z pełną informacją zwrotną, w którym po przesłaniu każdego symbolu nadawca poznaje symbol na wyjściu. Kod z feedbackiem definiujemy jako sekwencję mapowań xi(W,Yi−1) określających kolejny symbol xi na podstawie przesyłanej wiadomości W i dotychczas dostarczonych symboli Y1,Y2,…,Yi−1. Przepustowość kanału z feedbackiem jest określana jako maksymalna szybkość transmisji przez kanał przy wykorzystaniu takiego kodu. Udowodnij że ta przepustowość jest równa klasycznej przepustowości kanału, czyli że wykorzystanie informacji zwrotnej nie może zwiększyć szybkości transmisji. Zauważ że nie jest to sprzeczne z ćwiczeniem 4 - jej wykorzystanie może znacząco uprościć konstrukcję samego kodu.

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