Teoria informacji
i kodowanie

Ćwiczenia V

8. kwietnia 2011 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 C

i

ma parametry (n, k

i

) 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

1

FC

2

= {(u, u ⊕ u

0

)|u ∈ C

1

, u

0

∈ C

2

}

ma parametry (2n, k

1

+ k

2

) oraz odległość minimalną:

d

min

C1FC2

= min(2d

min

1

, d

min

2

)

Udowodnij, że jeśli kody C

i

są liniowe, to kod C

1

FC

2

również jest liniowy.

Zadanie 3

Poszukiwany jest kod liniowy kodujący 16 wiadomości, korygujący błędy jednokrotne. Skon-
struuj 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 R

n

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

|

{z

}

n

1 → 11 . . . 1

|

{z

}

n

.

Sprawdź czy R

n

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 Hammin-
ga (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? (Odp. Ok. 2,093 × 10

−5

i 0,9969)

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? (Odp. 1110)

Strona 1 z 3

Teoria informacji
i kodowanie

Ćwiczenia V

8. kwietnia 2011 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. (Odp. Kod (8, 4), wykrywa i koryguje błędy
pojedyncze)

Zadanie 9

(kolokwium z lat poprzednich)

Udowodnij, że jeśli kody C i C

0

są kodami liniowymi zawartymi w przestrzeni liniowej V , to

wtedy kody:

C ∩ C

0

oraz

C + C

0

= {u ⊕ u

0

|u ∈ C, u

0

∈ C

0

}

również są kodami liniowymi. Czy kod C ∪ C

0

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ć:

s =

h

y

1

+ y

3

+ y

5

y

1

+ y

2

+ y

6

y

3

+ y

4

+ y

6

i

.

przy czym dekoder oblicza go na podstawie otrzymanego ciągu y, gdzie y

i

oznaczają warto-

ści y na pozycjach i. Znajdź parametry tego kodu oraz określ jego właściwości korekcyjne i
detekcyjne. (Odp. Kod (6, 3), wykrywa i koryguje błędy pojedyncze)

Zadanie 11

Pokaż, że skrócony kod Hamminga (6, 3) nie jest kodem idealnym.

Zadanie 12

Kody C i C

0

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 + C

0

oraz macierz kontroli parzystości kodu C ∩ C

0

,

gdzie:

C + C

0

= {u ⊕ u

0

|u ∈ C, u

0

∈ C

0

},

C ∩ C

0

= {u|u ∈ C ∧ u ∈ C

0

}.

Zadanie 13

Pokaż, że kod liniowy (n, k) korygujący t błędów ma przynajmniej 2t 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

Teoria informacji
i kodowanie

Ćwiczenia V

8. kwietnia 2011 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. (Odp. 10111, 01101 i 11010)

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.

Zadanie 19

(kolokwium z lat poprzednich)

Określ liczbę słów kodowych o wadze trzy w kodzie Hamminga, w którym liczba pozycji nad-
miarowych wynosi sześć. (Odp. 165)

Zadanie 20

(kolokwium z lat poprzednich)

Do zbioru ciągów kodowych pewnego kodu liniowego, który jest w stanie wykrywać przekła-
mania, należą m.in. następujące ciągi: 0011010, 0100110, 0101111, 0110101, 0111100 i 1001101.
Ile jest różnych ciągów błędów niewykrywalnych przez ten kod?

Zadanie 21

(kolokwium z lat poprzednich)

Znajdź kod liniowy charakteryzujący się sprawnością o wartości 0,75 i korygujący błędy co
najmniej pojedyncze, o najkrótszej możliwej długości słowa kodowego, podając: podstawowe
parametry kodu, minimalną odległość Hamminga, zależność między bitami informacyjnymi i
nadmiarowymi oraz jego macierz generującą. (Odp. Kod (20, 15))

Informacja dodatkowa:
Na kartkach z zadaniami do kolejnych kolokwiów znajdą Państwo następujące dane:

„Legalna ściąga”:

Kres górny Plotkina: d

min

¬

n2

k−1

2

k

−1

.

Kres górny Eliasa: d

min

¬ 2s

K

K−1

(1 −

s

n

), gdzie: s, K ∈

Z oraz 2

n−k

<

P

s

i=0

n

i

, i K jest najmniejszą liczbą całkowitą

spełniającą zależność: K ­

P

s

i=0

n

i

2

n−k

.

Kres dolny Warszamowa-Gilberta: 2

n−k

>

P

d−2

i=0

n−1

i

.

Strona 3 z 3