Teoria informacji
i kodowanie

Ćwiczenia VIII

27. maja 2009 r.

Kody cykliczne, zaawansowane kody wielomianowe

Zadanie 1

Znajdź wszystkie binarne kody cykliczne o długości 5.

Zadanie 2

Określ krotność błędów korygowalnych przez cykliczny kod z wielomianem generującym:

x

4

+ x + 1.

Zadanie 3

Czy można za pomocą wielomianu generującego:

g(x) = x

5

+ x

2

+ 1

skonstruować kod cykliczny korygujący błędy podwójne?

Zadanie 4

Pokaż, że kod Hamminga (7, 4) jest równoważny cyklicznemu kodowi niesystematycznemu o
wielomianie generującym:

1 + x + x

3

.

Narysuj koder tego kodu i prześledź jego działanie dla ciągu informacyjnego:

u = 1111.

Potem narysuj dekoder tego kodu i prześledź jego działanie wraz z korekcją dla ciągu:

1100100.

Zadanie 5

Pokaż, że układ mnożący oparty na wielomianie:

1 + x

2

+ x

3

+ x

4

może posłużyć do wygenerowania kodu dualnego do binarnego kodu Hamminga.

Zadanie 6

(kolokwium z lat poprzednich)

Znajdź wielomian generujący kodu cyklicznego, który wykrywa i koryguje paczki błędów o
długości 4 symboli. (Odp. Kod (42, 31))

Zadanie 7

(kolokwium z lat poprzednich)

Słowo reprezentowane przez wielomian:

1 + x

4

+ x

5

należy do pewnego niesystematycznego kodu cyklicznego. Znajdź długość słów kodowych oraz
wielomian generujący tego kodu, jeśli wiadomo, że to wielomian generujący o najwyższym
możliwym stopniu.

Zadanie 8

(kolokwium z lat poprzednich)

Istnieją trzy różne nietrywialne niesystematyczne kody cykliczne o słowach długości trzy. Znajdź
ich parametery (n, k) i macierze generujące. (Kod trywialny to taki kod, który ma dokładnie
jedno słowo kodowe i jest to ciąg samych zer.)

Strona 1 z 2

Teoria informacji
i kodowanie

Ćwiczenia VIII

27. maja 2009 r.

Zadanie 9

Pokaż, że jeśli wielomian:

g(x) = g

0

+ g

1

x + · · · + g

k

x

k

6= 0

jest wielomianem generującym kodu cyklicznego, to:

g

0

6= 0.

Zadanie 10

(kolokwium z lat poprzednich)

Ciąg 1100101 jest słowem kodowym pewnego kodu cyklicznego o parametrach (7,3). Znajdź
macierz generującą tego kodu.

Zadanie 11

(kolokwium z lat poprzednich)

Wielomian x

4

+x

3

+1 jest wielomianem generującym pewnego kodu cyklicznego. Znajdź macierz

kontroli parzystości dla tego kodu.

Zadanie 12

(*)

Pokaż, że część wspólna dwóch kodów cyklicznych o tej samej długości jest kodem cyklicznym.
Podaj związek między wielomianami generującymi dwóch kodów cyklicznych i wielomianem
generującym ich części wspólnej.

Zadanie 13

(**)

Pokaż, że jeśli kod cykliczny nie zawiera ciągu:

11 . . . 1,

to wszystkie ciągi kodowe tego kodu mają wagę parzystą.

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

.

Wielomiany generujące cyklicznych kodów Hamminga

c

Wielomian generujący

2

x

2

+ x + 1

3

x

3

+ x + 1

4

x

4

+ x + 1

5

x

5

+ x + 1

Zestandaryzowane wielomiany generujące dla różnych CRC

Kod

Wielomian generujący

CRC-4

x

4

+ x

3

+ x

2

+ x + 1

CRC-7

x

7

+ x

6

+ x

4

+ 1

CRC-8

x

8

+ x

7

+ x

6

+ x

4

+ x

2

+ 1

CRC-12

x

12

+ x

11

+ x

3

+ x

2

+ x + 1

CRC-ANSI

x

16

+ x

15

+ x

2

+ 1

CRC-CCITT

x

16

+ x

12

+ x

5

+ 1

CRC-SDLC

x

16

+ x

15

+ x

13

+ x

7

+ x

4

+ x

2

+ x + 1

CRC-24

x

24

+ x

23

+ x

14

+ x

12

+ x

8

+ 1

Strona 2 z 2