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