i kodowanie
Ćwiczenia V
27. marca 2009 r.
Kody liniowe, kody Hamminga
Zadanie 1
Czy jeśli wektory x, y i z, należące do binarnej przestrzeni wektorowej nad ciałem Galois GF ( q), są liniowo niezależne, to można to samo orzec o następujących trzech wektorach: x ⊕ y
y ⊕ z
x ⊕ z?
Zadanie 2
Pokaż, że jeśli binarny kod systematyczny Ci ma parametry ( n, ki) i odległość minimalną d min , i
to kod otrzymany w wyniku specjalnego złożenia poszczególnych słów kodowych (np. dla ciągów kodowych 00 i 11: (00 , 11) = 0011):
C 1F C 2 = {(u , u ⊕ u 0) |u ∈ C 1 , u 0 ∈ C 2 }
ma parametry (2 n, k 1 + k 2) oraz odległość minimalną:
d min
= min(2 d
, d
)
C
min
min
1F C 2
1
2
Udowodnij, że jeśli kody Ci są liniowe, to kod C 1F C 2 również jest liniowy.
Zadanie 3
Poszukiwany jest kod liniowy kodujący 16 wiadomości, korygujący błędy jednokrotne. Skonstruuj jego dowolną macierz generującą G. Podaj sposób korygowania błędu i podaj macierz kontroli parzystości H dla tego kodu.
Zadanie 4
(kolokwium z lat poprzednich)
Czy ciągi kodowe:
01101 11010 10111 11100
mogą wszystkie na raz być ciągami kodowymi (niekoniecznie systematycznego) binarnego kodu liniowego (5 , 2)?
Zadanie 5
(kolokwium z lat poprzednich)
Binarny kod z powtarzaniem Rn polega na kodowaniu wiadomości będącej 0 ciągiem n zer i analogicznie dla wiadomości będącej 1:
0 → 00 . . . 0
1 → 11 . . . 1 .
|
{z
}
|
{z
}
n
n
Sprawdź czy Rn jest kodem liniowym. Jeśli tak, to podaj jego macierz generującą oraz macierz testów parzystości. Pokaż również, że R 1527 jest kodem szczelnie upakowanym.
Zadanie 6
Określ prawdopodobieństwo podjęcia błędnej decyzji korekcyjnej przez dekoder kodu Hamminga (7 , 4), jeśli prawdopodobieństwa przekłamania pojedynczego bitu w słowie kodowym podczas transmisji są niezależne i wynoszą 10 − 3. Jaki jest stosunek prawdopodobieństwa wystąpienia błędów korygowalnych przez dekoder do prawdopodobieństwa wystąpienia przekłamania słowa podczas transmisji?
Zadanie 7
Znajdź syndrom odebranego przez dekoder ciągu:
y = 1011110101 ,
jeśli wiadomo, że na wejściu kanału pojawiają się słowa skróconego kodu Hamminga. Jaka będzie decyzja dekodera?
Strona 1 z 3
i kodowanie
Ćwiczenia V
27. marca 2009 r.
Zadanie 8
(kolokwium z lat poprzednich)
Do zbioru ciągów kodowych pewnego systematycznego kodu liniowego należą między innymi następujące ciągi:
10011011 00101110 01001101 11010110 00010111 01110100 .
Określ, jakie taki kod może mieć parametry ( n, k), jeśli k ma być najmniejsze z możliwych, oraz ustal jego właściwości korekcyjne i detekcyjne.
Zadanie 9
(kolokwium z lat poprzednich)
Udowodnij, że jeśli kody C i C0 są kodami liniowymi zawartymi w przestrzeni liniowej V , to wtedy kody:
C ∩ C0
oraz
C + C0 = {u ⊕ u 0|u ∈ C, u 0 ∈ C0}
również są kodami liniowymi. Czy kod C ∪ C0 jest liniowy w każdej sytuacji? Jeśli nie, to jakie muszą być spełnione warunki, żeby był liniowy?
Zadanie 10
(kolokwium z lat poprzednich)
Syndrom obliczany dla pewnego nadmiarowego kodu binarnego ma postać:
h
i
s =
y 1 + y 3 + y 5
y 1 + y 2 + y 6
y 3 + y 4 + y 6
.
przy czym dekoder oblicza go na podstawie otrzymanego ciągu y, gdzie yi oznaczają warto-
ści y na pozycjach i. Znajdź parametry tego kodu oraz określ jego właściwości korekcyjne i detekcyjne.
Zadanie 11
Pokaż, że skrócony kod Hamminga (6 , 3) nie jest kodem idealnym.
Zadanie 12
Kody C i C0 są kodami liniowymi zawartymi w przestrzeni liniowej V rozpiętej nad binarnym ciałem Galois GF (2) o macierzach generujących oraz kontroli parzystości odpowiednio G, H i G 0, H 0. Znajdź macierz generującą kodu C + C0 oraz macierz kontroli parzystości kodu C ∩ C0, gdzie:
C + C0 = {u ⊕ u 0|u ∈ C, u 0 ∈ C0}, C ∩ C0 = {u |u ∈ C ∧ u ∈ C0}.
Zadanie 13
Pokaż, że kod liniowy ( n, k) korygujący t błędów ma przynajmniej 2 t pozycji kontrolnych.
Zadanie 14
(kolokwium z lat poprzednich)
Mamy dany konkretny ciąg kodowy binarnego kodu nadmiarowego ( n, k). Oblicz dla 0 ¬ i ¬ n, ile istnieje ciągów, których odległość Hamminga od tego ciągu wynosi i. Pokaż, że ich suma po i = 0 , 1 , . . . , n jest równa liczbie wszystkich binarnych ciągów n-elementowych.
Zadanie 15
(kolokwium z lat poprzednich)
Jeśli to możliwe, skonstruuj kod binarny o ciągach kodowych długości 7, służący do zakodowania ośmiu wiadomości i korygujący błędy dwukrotne.
Strona 2 z 3
i kodowanie
Ćwiczenia V
27. marca 2009 r.
Zadanie 16
(kolokwium z lat poprzednich)
Każdy ciąg kodowy pewnego kodu liniowego jest zaburzany w trakcie transmisji na tej samej pozycji. Odebrano następujące ciągi:
10011 01001 11110
Odtwórz zbiór nadanych ciągów kodowych.
Zadanie 17
(kolokwium z lat poprzednich)
Blokowy nietrywialny binarny kod idealny (szczelnie upakowany) C o parametrach ( n, k > 1) charakteryzuje się minimalną odległością Hamminga d min( C) = 7. Jaka jest długość słowa kodowego?
Zadanie 18
Pokaż, że w liniowej przestrzeni wektorowej V rozpiętej nad ciałem Galois GF (2), w której wektor ma długość c pozycji, maksymalna liczność zbioru wektorów, takiego że żadna para zawartych w nim wektorów nie jest liniowo zależna, wynosi:
2 c − 1 .
Pokaż, że jeśli taki zbiór wyznacza kolumny macierzy kontroli parzystości, to otrzymany kod liniowy jest szczelnie upakowany oraz pozwala skorygować wszystkie błędy pojedyncze.
Strona 3 z 3