Teoria informacji/TI Ćwiczenia 10
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
Bazę tej przestrzeni (w postaci i rzędu to dowolna liniowa podprzestrzeń wymiaru w przestrzeni wektorowej , gdzie jest skończonym ciałem. Przestrzeń definiuje zestaw poprawnych słów kodowych. wektorów długości ) zapisuje się często w postaci macierzy generującej kodu.
Na tych ćwiczeniach będziemy się zajmować tylko ciałem , czyli operacjami modulo 2.
Przykładem prostego kodu liniowego nad ciałem 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:
Macierz wykrywania błędów dla tego kodu wygląda następująco:
Aby zakodować czterobitową wiadomość mnoży się ją przez macierz (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 , 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
Ć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
Ćwiczenie [Jakość przekazu]
Rozwiązanie
Kody liniowe
Ćwiczenie [Idealne kody]
Kodem
nazywamy kod liniowy, w którym -bitowe słowa są zapisywane na bitach, a minimalna odległość pomiędzy słowami kodowymi wynosi .- a) Ile maksymalnie błędów może poprawiać taki kod?
- b) Jaką nierówność muszą spełniać wartości , i , aby taki kod mógł istnieć?
- c) Kod nazwiemy idealnym, gdy może poprawiać błędów i każde słowo jest w odległości co najwyżej od najbliższego słowa kodowego. Dla jakich wartości mogą istnieć kody idealne poprawiające 1 błąd?
Rozwiązanie
Ćwiczenie [Szacowanie efektywnosci]
Rozwiązanie
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
, gdzie 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]
Rozwiązanie
Ćwiczenie [Szybkość kodów LDPC]
Rozwiązanie
Ćwiczenie [Wydajność kodów LDPC]