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

Wersja z 17:56, 23 sie 2006

Kod Hamminga (7,4)

Projektowaniem efektywnych kodów korygujących błędy zajmuje się dziedzina informatyki nazywana teorią kodów. 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.

Definicja [Kod liniowy]

Kod liniowy długości $n$ i rzędu $k$ to dowolna liniowa podprzestrzeń $𝒞$ wymiaru $k$ w przestrzeni wektorowej $𝔽^{n}$ gdzie $𝔽$ jest skończonym ciałem. Przestrzeń $𝒞$ definiuje zestaw poprawnych słów kodowych.

Bazę tej przestrzeni (w postaci

k

wektorów długości

n

) zapisuje się często w postaci macierzy generującej kodu.

Na tych ćwiczeniach bedziemy się zajmować tylko ciałem $Z_{2}$ , czyli operacjami modulo 2. Przykładem prostego kodu liniowego nad ciałem $Z_{2}$ 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%).

Macierz generująca tego kodu wygląda następująco: $G : = (\begin{matrix} 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{matrix})$

Macierz wykrywania błędów dla tego kodu wygląda następująco:

$H_{e} : = (\begin{matrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix})$

Aby zakodować czterobitową wiadomość $m$ mnoży się ją przez macierz $G$ (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 $H_{e}$ , 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.

Ćwiczenie [Dekodowanie kodu (7,4)]

Udowodnij że jeśli nie nastąpiło przekłamanie, iloczyn macierzy wykrywania błędów i przesłanego wektora zawsze jest zerowy.

Rozwiązanie

{{{3}}}

Ćwiczenie [Sygnatura błędu]

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.

Rozwiązanie

{{{3}}}

Ćwiczenie [Jakość przekazu]

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)?

Rozwiązanie

{{{3}}}

Kody liniowe

Ćwiczenie [Idealne kody]

Kodem $(n, k, d)$ nazywamy kod liniowy w którym $k$ -bitowe słowa są zapisywane na $n$ bitach, a minimalna odległość pomiędzy słowami kodowymi wynosi $d$ .

a) Ile maksymalnie błędów może poprawiać taki kod?

b) Jaką nierówność muszą spełniać wartości

n

,

k

i

d

aby taki kod mógł istnieć?

c) Kod nazwiemy idealnym, gdy może poprawiać

r

błędów i każde słowo jest w odległości co najwyżej

r

od najbliższego słowa kodowego. Dla jakich wartości

n

mogą istnieć kody idealne poprawiające 1 błąd?

Rozwiązanie

{{{3}}}

Ćwiczenie [Szacowanie efektywnosci]

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.

Rozwiązanie

{{{3}}}

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 $x_{i_{1}} \oplus \dots \oplus x_{i_{p}} = 0$ , gdzie $x_{i}$ 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.

Ćwiczenie [Kod LDPC jest liniowy]

Udowodnij że kod LDPC jest kodem liniowym.

Rozwiązanie

{{{3}}}

Ćwiczenie [Szybkość kodów LDPC]

Jaka jest oczekiwana liczba słów spełniających wszystkie

k

restrykcji?

Rozwiązanie

{{{3}}}

Ćwiczenie [Wydajność kodów LDPC]

Udowodnij że z dużym prawdopodobieństwem minimalna odległość między dowolną parą słów kodowych wynosi co najmniej

\frac{k}{\log n}

.

@@ Linia 80: / Linia 80: @@
 {{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>.
-* Ile maksymalnie błędów może poprawiać taki kod?
+:a) Ile maksymalnie błędów może poprawiać taki kod?
-* Jaką nierówność muszą spełniać wartości <math>n</math>, <math>k</math> i <math>d</math> aby taki kod mógł istnieć?
+: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ć?
-* 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?}}
+: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">
-* Kod taki może poprawiać maksymalnie <math>r=\frac{d-1}{2}</math> błędów.
+:a) Kod taki może poprawiać maksymalnie <math>r=\frac{d-1}{2}</math> błędów.
-* 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>
+: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>
-* 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>.
+: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).
+: 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>}}
@@ Linia 102: / Linia 102: @@
 <div class="mw-collapsible-content" style="display:none">
 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.
+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>

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

Wersja z 17:56, 23 sie 2006

Kod Hamminga (7,4)

Kody liniowe

LDPC - macierze parzystości małej gęstości

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia