Teoria informacji i kodowanie:
ćwiczenia VII

Wstęp do kodów wielomianowych

Piotr Chołda

Katedra Telekomunikacji Akademii Górniczo-Hutniczej

Kraków, 13. maja 2011 r.

Zadanie powtórzeniowe I

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.

TIiK: ćwiczenia

2/9

Zadanie powtórzeniowe II

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,
narysuj ich kodery oraz prześledź ich pracę przy kodowaniu u(x ).

TIiK: ćwiczenia

3/9

Zadanie powtórzeniowe III

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?

TIiK: ćwiczenia

4/9

Zadanie 1

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

.

TIiK: ćwiczenia

5/9

Zadanie 2

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?

TIiK: ćwiczenia

6/9

Zadanie 3

Dla danych k = 4 i wielomianu generującego:

g (x ) = x

3

+ x

2

+ 1,

skonstruuj macierze generujące oraz narysuj kodery i dekodery dla:

(a)

niesystematycznego,

(b)

systematycznego

kodu wielomianowego.
Prześledź działanie koderów i dekoderów, analizując przetwarzanie
ciągów o odpowiedniej długości złożonych z samych jedynek.

TIiK: ćwiczenia

7/9

Zadanie 4

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?
Czy to jest kod cykliczny? Znajdź jego macierz generującą, narysuj
schemat kodera (opartego 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).

TIiK: ćwiczenia

8/9

Pytania? Dziękuję za

uwagę! Za dwa tygodnie

zaawansowane kody

wielomianowe: kody

cykliczne, cykliczne kody

Hamminga, kody CRC,

kody Fire’a, BCH,. . .

—

Wykłady 9 i 10

TIiK: ćwiczenia

9/9