Teoria informacji
i kodowanie

Ćwiczenia VII

13. maja 2011 r.

Wstęp do kodów wielomianowych

Zadanie 1

Wykonaj na wielomianach:

a(x) = x

6

+ x

5

+ x

4

+ x

2

+ x,

b(x) = x

3

+ x

2

+ x,

następujące działania:

a(x) + b(x)

a(x)b(x)

a(x)

b(x)

.

Następnie wykonaj te działania na ciągach binarnych.

Zadanie 2

Wykonaj następujące działania na ciągach binarnych:

(x

4

+ x

2

+ 1) × (1 + x + x

3

),

(x

6

+ x

5

+ x

4

+ x

3

+ x

2

+ x) × (x + x

3

),

(x

15

+ 1) : (x

8

+ x

7

+ x

6

+ x

4

+ 1),

x

4

+ x

3

+ x + 1

x + 1

.

Zadanie 3

(kolokwium z lat poprzednich)

Jakie słowa kodowe

(a) niesystematycznego,

(b) systematycznego

kodu określonego przez wielomian generujący:

x

3

+ x + 1

odpowiadają ciągowi informacyjnemu określonemu przez wielomian:

u(x) = x

2

+ x?

Przyjmujemy że k = 3. Znajdź macierze generujące obu kodów, ich kodery oraz prześledź ich
pracę przy kodowaniu u(x).

Zadanie 4

Które z poniżej otrzymanych ciągów są przekłamane:

0011010,

1100101,

1010011,

jeśli wiadomo, że na wejściu kanału pojawiają się słowa kodu, którego wielomian generujący
ma postać:

g(x) = x

3

+ x

2

+ 1?

Strona 1 z 2

Teoria informacji
i kodowanie

Ćwiczenia VII

13. maja 2011 r.

Zadanie 5

Które z poniżej otrzymanych ciągów są przekłamane:

0101111000,

0001011001,

1101111000,

jeśli wiadomo, że na wejściu kanału pojawiają się słowa kodu, którego wielomian generujący
ma postać

g(x) = x

5

+ x

3

+ x

2

+ x + 1?

Zadanie 6

Dla danych k = 4 i wielomianu generującego:

g(x) = x

3

+ x

2

+ 1,

skonstruuj macierze generujące oraz kodery i dekodery dla:

(a) niesystematycznego,

(b) systematycznego

kodu wielomianowego.

Zadanie 7

(kolokwium z lat poprzednich)

Kod z kontrolą parzystości o ośmiobitowej długości słowa kodowego można zrealizować jako
kod wielomianowy. Dlaczego? Znajdź jego macierz generującą, narysuj schemat kodera (opar-
tego na rejestrze przesuwającym) i objaśnij jego działanie opisując proces kodowania ciągu
reprezentującego wiadomość (jako ciąg reprezentujący wiadomość użyj binarnej czterobitowej
reprezentacji ostatniej cyfry numeru własnego indeksu [np. dla 5 będzie to 0101] uzupełnionej
z przodu odpowiednią liczbą jedynek).

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