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