Materiały do kursu
Kodowanie – ćwiczenia
Zadania
Kod kursu ETEK00025C
Semestr letni, rok akad. 2011 / 2012
Przygotował Piotr Kocyan
pok. 331 C-4
Materiały do kursu
Kodowanie – ćwiczenia
Zadania
Kod kursu ETEK00025C
Semestr letni, rok akad. 2011 / 2012
Przygotował Piotr Kocyan
pok. 331 C-4
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
1
Spis treści
UWAGA WSTĘPNA .............................................................................................................................................................................. 2
TEST NR 1 — ZADANIA ...................................................................................................................................................................... 2
Z
ADANIE
1. ........................................................................................................................................................................................... 2
Z
ADANIE
2. ........................................................................................................................................................................................... 2
Z
ADANIE
11. ......................................................................................................................................................................................... 3
Z
ADANIE
12. ......................................................................................................................................................................................... 4
TEST NR 1 — WYNIKI ZADAŃ ......................................................................................................................................................... 5
Z
ADANIE
1. ........................................................................................................................................................................................... 5
Z
ADANIE
2. ........................................................................................................................................................................................... 5
Z
ADANIE
11. ......................................................................................................................................................................................... 6
Z
ADANIE
12. ......................................................................................................................................................................................... 6
TEST NR 2 — ZADANIA ...................................................................................................................................................................... 7
Z
ADANIE
1. ........................................................................................................................................................................................... 7
Z
ADANIE
2. ......................................................................................................................................................................................... 10
Z
ADANIE
3. ......................................................................................................................................................................................... 10
Z
ADANIE
4. ......................................................................................................................................................................................... 11
TEST NR 2 — WYNIKI ZADAŃ ....................................................................................................................................................... 14
Z
ADANIE
1. ......................................................................................................................................................................................... 14
Z
ADANIE
2. ......................................................................................................................................................................................... 15
Z
ADANIE
3. ......................................................................................................................................................................................... 16
Z
ADANIE
4. ......................................................................................................................................................................................... 18
TEST NR 3 — ZADANIA .................................................................................................................................................................... 19
Z
ADANIE
2. ......................................................................................................................................................................................... 19
Z
ADANIE
3. ......................................................................................................................................................................................... 20
TEST NR 3 — WYNIKI ZADAŃ ....................................................................................................................................................... 26
Z
ADANIE
2. ......................................................................................................................................................................................... 26
Z
ADANIE
3. ......................................................................................................................................................................................... 27
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
2
Uwaga wstępna
Zadania umieszczone w niniejszym opracowaniu pozwalają na sprawdzenie i rozwijanie umiejętności
obliczeniowych niezbędnych do prawidłowego rozwiązania zadań na testach. ZłoŜoność obliczeniowa
wszystkich podanych tutaj przykładów jest większa niŜ złoŜoność zadań na testach.
Test nr 1 — zadania
Zadanie 1.
Obliczyć wynik i resztę z dzielenia wielomianu u przez wielomian v. Wyniki podać w zapisie wielomianowym.
Przykład
u
v
a
11000101010001000111000000001
10100111010000010001
b
10011101011100011000011101110
11010011101000001000
c
1000101101001100110000111011
1110100111010000010
d
101011000111011001110011100
111010011101000001
e
1000101111000110101000000001
1110001110100111010
f
10100110011111000110001111
11100011101001110
g
10010101011001100100100100011
11011010000000000111
h
10110111111101111011010100111
11101101000000000011
i
11100010001101101101100101010
11110110100000000001
j
1101000011110000000111000010
1111101101000000000
Zadanie 2.
Obliczyć wynik i resztę z dzielenia wielomianu u(x) przez wielomian v(x). Wyniki podać w zapisie bitowym.
Przykł.
u(x)
v(x)
a
x
26
+x
25
+x
22
+x
21
+x
20
+x
19
+x
17
+x
16
+x
12
+x
11
+x
7
+x
6
+x
5
+1
x
17
+x
16
+x
15
+x
14
+x
13
+x
11
+x
10
+x
8
b
x
24
+x
23
+x
21
+x
20
+x
19
+x
18
+x
17
+x
15
+x
11
+x
9
+x
8
+x
7
+x
5
+x
4
+x
3
x
15
+x
14
+x
13
+x
12
+x
11
+x
9
+x
8
+x
6
c
x
28
+x
26
+x
24
+x
22
+x
21
+x
20
+x
18
+x
15
+x
11
+x
10
+x
8
+x
7
+x
4
+x
3
+x
2
x
19
+x
14
+x
13
+x
12
+x
11
+x
10
+x
8
+x
7
+x
5
d
x
28
+x
26
+x
25
+x
24
+x
23
+x
22
+x
21
+x
20
+x
19
+x
17
+x
15
+x
12
+x
11
+x
10
+x
8
+x
3
+x
2
+x
x
19
+x
18
+x
13
+x
12
+x
11
+x
10
+x
9
+x
7
+x
6
+x
4
e
x
26
+x
24
+x
23
+x
22
+x
21
+x
18
+x
17
+x
16
+x
14
+x
12
+x
11
+x
3
+x
2
+1
x
17
+x
16
+x
15
+x
14
+x
13
+x
8
+x
7
+x
6
+x
5
+x
4
+x
2
+x
f
x
25
+x
23
+x
20
+x
19
+x
15
+x
14
+x
12
+x
11
+x
8
+x
6
+x
x
16
+x
15
+x
14
+x
13
+x
12
+x
7
+x
6
+x
5
+x
4
+x
3
+x+1
g
x
23
+x
20
+x
18
+x
16
+x
15
+x
13
+x
12
+x
11
+x
10
+x
8
+x
7
+x
4
+x
x
14
+x
13
+x
12
+x
11
+x
10
+x
5
+x
4
+x
3
+x
2
+x
h
x
22
+x
20
+x
19
+x
16
+x
14
+x
11
+x
10
+x
8
+x
2
+1
x
13
+x
12
+x
11
+x
10
+x
9
+x
4
+x
3
+x
2
+x+1
i
x
21
+x
19
+x
14
+x
8
+x
4
+x
3
+x
2
+1
x
12
+x
11
+x
10
+x
9
+x
8
+x
3
+x
2
+x+1
j
x
20
+x
19
+x
17
+x
10
+x
5
+x
3
+x
2
+x+1
x
11
+x
10
+x
9
+x
8
+x
7
+x
2
+x+1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
3
Zadanie 11.
PoniŜej podano 5 słów o długości n. Pierwsze słowo naleŜy do kodu cyklicznego (n, 5), a w czterech
pozostałych wystąpiły błędy w części nadmiarowej. Wykorzystując właściwości liniowości i cykliczności
zaznaczyć przekłamane bity. Część informacyjna jest umieszczona na najbardziej znaczących pozycjach słów
kodowych.
Przykład a
Przykład b
n
31
31
c
0011011111010001001010110000111
1010010001011111011001110000110
u
1
1000011001110011110110000010101
0011100010101010010001001101111
u
2
1100001111111011111110011001110
1001110000110101010100101110001
u
3
1110011011110001001001010110011
1100111100011010110100011110010
u
4
0111011101111111000100100011000
0110011100001100001000001111111
Przykład c
Przykład d
n
31
31
c
0100111110111000101011010000110
1010100011101111100100110000101
u
1
1011011000110010011111000000000
0111110000001000001110101000110
u
2
1101110001010111000000100110110
1011101011101100001111011100011
u
3
1110111000100001011000111000011
0101101010101110011110011001100
u
4
1111011100100101111000001001011
0010110111000100111111000001100
Przykład e
Przykład f
n
31
31
c
0111011000111110011010010000101
1011001111100011011101010000100
u
1
0001011110011010111111011010110
1001011101111010011010001010000
u
2
1000110110001010111000101011001
0100101100101110000001110101001
u
3
0100001010011011000101101001010
1010000001111100111110101101100
u
4
0010010001011101100010101001111
0101000110011110010110000110110
Przykład g
Przykład h
n
30
30
c
011001010000111011001010000111
000110000110000110000110000110
u
1
101010110001001101001111001001
000011100111100111000001000011
u
2
110100111010101100101111100100
100001000001110001101011100000
u
3
011010011101010011010101110110
110000010000110100110001010001
u
4
001101011000001001011011100001
111001111011110001011000101001
Przykład i
Przykład j
n
30
31
c
001101110000101001101110000101
0110111110100010010101100001110
u
1
011101010010011011100001000001
0110010011001101111101010100001
u
2
001111010010110011110010110110
1011010111100010101110100000010
u
3
100111111100010110010111001010
1101111100010100101011001000100
u
4
110010000111110110010101010010
1110110011010101010011110011011
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
4
Zadanie 12.
Dane jest słowo kodowe kodu cyklicznego (n, 4). Obliczyć odległość minimalną tego kodu. Podać wagi
Hamminga wszystkich słów kodowych.
Przykład
n
c
a
30
011110101100100011110101100100
b
30
001110001110001110001110001110
c
30
000110001100011000110001100011
d
30
010100010100010100010100010100
e
30
100110101111000100110101111000
f
28
0110100011010001101000110100
g
28
0010110001011000101100010110
h
28
1000100010001000100010001000
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
5
Test nr 1 — wyniki zadań
Zadanie 1.
Przykład
Wynik dzielenia
Reszta
a
x
9
+x
8
+x
7
+x
6
+x
5
+x
4
+x
3
+x
2
x
9
+x
5
+x
4
+x
3
+x
2
+1
b
x
9
+x
8
+x
7
+x
6
+x
5
+x
4
+x
3
+x
2
+x
x
9
+x
8
+x
4
+x
3
+x
2
+x
c
x
9
+x
8
+x
6
+x
5
+x
4
+x
3
+x
2
+x
x
8
+x
7
+x
6
+x
2
+x+1
d
x
9
+x
8
+x
7
+x
5
+x
4
+x
3
+x
2
+x+1
x
9
+x
7
+x
6
+x
5
+x+1
e
x
9
+x
8
+x
6
+x
4
+x
3
+x
2
+x+1
x
9
+x
8
+x
6
+x
4
+x
2
+x+1
f
x
9
+x
8
+x
7
+x
5
+x
3
+x
2
+x+1
x
9
+x
8
+x
7
+x
6
+x
4
+x
2
+1
g
x
9
+x
8
+x
7
+x
6
+x
5
+x
3
+x
2
+x
x
9
+x
7
+x
5
+x
3
+1
h
x
9
+x
8
+x
7
+x
6
+x
5
+x
4
+x
3
+x+1
x
9
+x
7
+x
5
+x
3
+x
i
x
9
+x
6
+x
5
+x
4
+x
3
+x
2
+x+1
x
8
+x
6
+x
4
+x
2
+1
j
x
9
+x
7
+x
6
+x
5
+x
4
+x
3
+x
2
+1
x
9
+x
8
+x
7
+x
6
+x
Zadanie 2.
Przykład
Wynik dzielenia
Reszta
a
1010111111
1111100001
b
1011011101
1111111000
c
1010110111
1111111100
d
1101011011
111111110
e
1110010111
1110101111
f
1111001011
111010111
g
1101100111
1101101000
h
1110110011
1110110100
i
1111011001
1111011010
j
1011110110
111101101
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
6
Zadanie 11.
Przykład a
Przykład b
u
1
1000011001110011110110000010101
0011100010101010010001001101111
u
2
1100001111111011111110011001110
1001110000110101010100101110001
u
3
1110011011110001001001010110011
1100111100011010110100011110010
u
4
0111011101111111000100100011000
0110011100001100001000001111111
Przykład c
Przykład d
u
1
1011011000110010011111000000000
0111110000001000001110101000110
u
2
1101110001010111000000100110110
1011101011101100001111011100011
u
3
1110111000100001011000111000011
0101101010101110011110011001100
u
4
1111011100100101111000001001011
0010110111000100111111000001100
Przykład e
Przykład f
u
1
0001011110011010111111011010110
1001011101111010011010001010000
u
2
1000110110001010111000101011001
0100101100101110000001110101001
u
3
0100001010011011000101101001010
1010000001111100111110101101100
u
4
0010010001011101100010101001111
0101000110011110010110000110110
Przykład g
Przykład h
u
1
101010110001001101001111001001
000011100111100111000001000011
u
2
110100111010101100101111100100
100001000001110001101011100000
u
3
011010011101010011010101110110
110000010000110100110001010001
u
4
001101011000001001011011100001
111001111011110001011000101001
Przykład i
Przykład j
u
1
011101010010011011100001000001
0110010011001101111101010100001
u
2
001111010010110011110010110110
1011010111100010101110100000010
u
3
100111111100010110010111001010
1101111100010100101011001000100
u
4
110010000111110110010101010010
1110110011010101010011110011011
Zadanie 12.
Wagi Hamminga
Przykład
c
0000
c
0001
c
0010
c
0011
c
0100
c
0101
c
0110
c
0111
c
1000
c
1001
c
1010
c
1011
c
1100
c
1101
c
1110
c
1111
d
min
a
0
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
b
0
15
10
15
10
15
20
15
15
10
15
20
15
20
15
30
10
c
0
12
12
12
12
12
12
24
12
12
12
24
12
24
24
24
12
d
0
10
10
20
10
10
20
20
10
20
10
20
20
20
20
20
10
e
0
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
16
f
0
12
16
12
12
16
12
16
12
16
12
16
16
12
16
28
12
g
0
12
12
16
16
12
12
16
12
16
16
12
12
16
16
28
12
h
0
7
7
14
7
14
14
21
7
14
14
21
14
21
21
28
7
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
7
Test nr 2 — zadania
Zadanie 1.
Przykład a) PoniŜej podano sześć wielomianów.
g
1
(x) = x
25
+x
24
+x
23
+x
21
+x
18
+x
17
+x
16
+x
14
+x
11
+x
10
+x
9
+x
7
+x
4
+x
3
+x
2
+1
g
2
(x) = x
25
+x
24
+1
g
3
(x) = x
24
+x
2
+x
g
4
(x) = x
24
+x+1
g
5
(x) = x
24
+x
23
+x
21
+x
17
+x
16
+x
14
+x
10
+x
9
+x
7
+x
3
+x
2
+1
g
6
(x) = x
25
+x
2
+x
Zaznacz odpowiedzi na następujące pytania:
Które wielomiany mogą generować kod liniowy?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany mogą generować kod cykliczny?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany nie mogą generować kodu liniowego (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany nie mogą generować kodu cyklicznego (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod liniowy (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod cykliczny (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
UWAGA! Na pytania oznaczone ♦ naleŜy odpowiedzieć bez wykonywania dzielenia.
Przykład b) PoniŜej podano sześć wielomianów.
g
1
(x) = x
25
+x
2
+x
g
2
(x) = x
25
+x
24
+1
g
3
(x) = x
25
+x
23
+x
22
+x
21
+x
18
+x
16
+x
15
+x
14
+x
11
+x
9
+x
8
+x
7
+x
4
+x
2
+x+1
g
4
(x) = x
24
+x
22
+x
21
+x
17
+x
15
+x
14
+x
10
+x
8
+x
7
+x
3
+x+1
g
5
(x) = x
24
+x
2
+x
g
6
(x) = x
24
+x+1
Zaznacz odpowiedzi na następujące pytania:
Które wielomiany mogą generować kod liniowy?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany mogą generować kod cykliczny?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany nie mogą generować kodu liniowego (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany nie mogą generować kodu cyklicznego (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod liniowy (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod cykliczny (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
UWAGA! Na pytania oznaczone ♦ naleŜy odpowiedzieć bez wykonywania dzielenia.
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
8
Przykład c) PoniŜej podano sześć wielomianów.
g
1
(x) = x
25
+x
2
+x
g
2
(x) = x
26
+x
2
+x
g
3
(x) = x
25
+x
24
+x
19
+x
18
+x
13
+x
12
+x
7
+x
6
+x+1
g
4
(x) = x
25
+x+1
g
5
(x) = x
26
+x
25
+x
24
+x
23
+x
21
+x
19
+x
18
+x
15
+x
11
+x
10
+x
9
+x
8
+x
6
+x
4
+x
3
+1
g
6
(x) = x
26
+x
25
+x+1
Zaznacz odpowiedzi na następujące pytania:
Które wielomiany mogą generować kod liniowy?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany mogą generować kod cykliczny?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany nie mogą generować kodu liniowego (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany nie mogą generować kodu cyklicznego (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod liniowy (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod cykliczny (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
UWAGA! Na pytania oznaczone ♦ naleŜy odpowiedzieć bez wykonywania dzielenia.
Przykład d) PoniŜej podano sześć wielomianów.
g
1
(x) = x
27
+x+1
g
2
(x) = x
27
+x
24
+x
21
+x
18
+x
15
+x
12
+x
9
+x
6
+x
3
+1
g
3
(x) = x
26
+x
2
+x
g
4
(x) = x
26
+x
23
+x
22
+x
20
+x
18
+x
17
+x
16
+x
15
+x
11
+x
8
+x
7
+x
5
+x
3
+x
2
+x+1
g
5
(x) = x
26
+x
25
+x+1
g
6
(x) = x
27
+x
2
+x
Zaznacz odpowiedzi na następujące pytania:
Które wielomiany mogą generować kod liniowy?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany mogą generować kod cykliczny?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany nie mogą generować kodu liniowego (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany nie mogą generować kodu cyklicznego (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod liniowy (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod cykliczny (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
UWAGA! Na pytania oznaczone ♦ naleŜy odpowiedzieć bez wykonywania dzielenia.
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
9
Przykład e) PoniŜej podano sześć wielomianów.
g
1
(x) = x
25
+x
2
+x
g
2
(x) = x
26
+x
25
+x+1
g
3
(x) = x
26
+x
24
+x
22
+x
21
+x
20
+x
18
+x
17
+x
13
+x
12
+x
11
+x
10
+x
9
+x
6
+x
5
+x
3
+1
g
4
(x) = x
25
+x
24
+x
23
+x
20
+x
16
+x
14
+x
12
+x
11
+x
10
+x
9
+x
7
+x
6
+x
4
+x+1
g
5
(x) = x
26
+x
2
+x
g
6
(x) = x
25
+x+1
Zaznacz odpowiedzi na następujące pytania:
Które wielomiany mogą generować kod liniowy?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany mogą generować kod cykliczny?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany nie mogą generować kodu liniowego (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany nie mogą generować kodu cyklicznego (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod liniowy (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod cykliczny (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
UWAGA! Na pytania oznaczone ♦ naleŜy odpowiedzieć bez wykonywania dzielenia.
Przykład f) PoniŜej podano sześć wielomianów.
g
1
(x) = x
26
+x
23
+x
21
+x
20
+x
17
+x
16
+x
15
+x
14
+x
13
+x
9
+x
8
+x
6
+x
5
+x
4
+x
2
+1
g
2
(x) = x
26
+x
25
+x+1
g
3
(x) = x
25
+x
24
+x
21
+x
19
+x
18
+x
16
+x
15
+x
14
+x
13
+x
11
+x
9
+x
5
+x
2
+x+1
g
4
(x) = x
26
+x
2
+x
g
5
(x) = x
25
+x+1
g
6
(x) = x
25
+x
2
+x
Zaznacz odpowiedzi na następujące pytania:
Które wielomiany mogą generować kod liniowy?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany mogą generować kod cykliczny?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany nie mogą generować kodu liniowego (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany nie mogą generować kodu cyklicznego (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod liniowy (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod cykliczny (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
UWAGA! Na pytania oznaczone ♦ naleŜy odpowiedzieć bez wykonywania dzielenia.
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
10
Zadanie 2.
Dany jest wielomian generujący kod liniowy g(x) oraz wielomian informacyjny m(x). Oblicz metodą
wielomianową słowo kodowe kodu systematycznego opartego na wielomianie g(x) odpowiadające informacji
m(x). Wyniki podać w zapisie wielomianowym.
Przykład
g(x)
m(x)
a
x
16
+x
14
+x
13
+x
12
+x
10
+x
7
+x
5
+1
x
15
+x
13
+x
12
+x
7
+x
6
+x
4
+x
2
+1
b
x
16
+x
15
+x
8
+x
7
+x
5
+x
4
+x
2
+1
x
13
+x
12
+x
11
+x
10
+x
5
+x
4
+x+1
c
x
15
+x
13
+x
12
+x
11
+x
9
+x
6
+x
2
+1
x
16
+x
15
+x
12
+x
9
+x
7
+x
3
+x+1
d
x
13
+x
12
+x
11
+x
10
+x
6
+x
5
+x
2
+1
x
16
+x
15
+x
9
+x
8
+x
7
+x
5
+x
4
e
x
10
+x
9
+x
8
+x
6
+x
4
+x
2
+x+1
x
16
+x
15
+x
13
+x
12
+x
11
+x
10
+x
7
+x
6
+x
4
f
x
15
+x
14
+x
13
+x
12
+x
10
+x
7
+x
2
+1
x
16
+x
15
+x
14
+x
13
+x
12
+x
8
+x
4
+x
3
+x
2
+x
Zadanie 3.
Dany jest wielomian g(x) generujący kod liniowy o długości n. Obliczyć macierz generującą systematyczny
kod liniowy oparty na tym wielomianie.
Przykład
g(x)
n
a
x
17
+x
15
+x
14
+x
13
+x
10
+x
9
+x
8
+x
7
+x
5
+x
4
+x
3
+x
2
+1
25
b
x
17
+x
16
+x
15
+x
14
+x
13
+x
7
+x
6
+x+1
23
c
x
18
+x
17
+x
13
+x
9
+x
8
+x
6
+x
2
+x+1
26
d
x
15
+x
13
+x
12
+x
11
+x
10
+x
6
+x+1
29
e
x
17
+x
16
+x
12
+x
10
+x
9
+x
7
+x
2
+x+1
30
f
x
17
+x
15
+x
14
+x
13
+x
12
+x
11
+x
9
+x
7
+1
30
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
11
Zadanie 4.
Dana jest macierz G generująca systematyczny kod liniowy. Obliczyć metodą macierzową słowo kodowe tego
kodu odpowiadające informacji m(x). Wynik podać w zapisie wielomianowym.
Przykład a)
m(x) = x
9
+x
8
+x
6
+x
3
+x
G =
1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1
0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1
0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 1 0 0 1 1
0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 0 1
0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 0 0 0 0 1 1
0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0
0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1
0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1
0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1
Przykład b)
m(x) = x
8
+x
7
+x
5
+x
2
+1
G =
1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1
0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 0 0 1
0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 1 0 0 0 1
0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 1 0 0 1
0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
12
Przykład c)
m(x) = x
8
+x
7
+x
6
+x
4
+x
G =
1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 1 0 1 0 1 1
0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 0 0 1 0 1 0 1 1
0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1
0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 1 1
0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 0 1 0 1 1
0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1
0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1
0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1
0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1
Przykład d)
m(x) = x
11
+x
9
+x
7
+x
6
+x
5
+x
3
+1
G =
1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 0 1 1
0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1
0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1
0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 1
0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 1 1 0 1 0 0 0 0 1 1 0 1
0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 1
0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 0 1
0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
13
Przykład e)
m(x) = x
10
+x
8
+x
6
+x
5
+x
4
+x
2
G =
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 0 1 1 0 1 0 0 1 1
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 0 1
0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 1 1 1
0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 1 0 0 1 1
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0 0 0 1 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1
Przykład f)
m(x) = x
9
+x
7
+x
5
+x
4
+x
3
+x
G =
1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 1
0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 0 1 1
0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 1 1 1
0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 0 1
0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0
0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1
0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1
0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 1 1
0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 1 1 1 1 0 1 0 1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
14
Test nr 2 — wyniki zadań
Zadanie 1.
Przykład a)
Które wielomiany mogą generować kod liniowy?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany mogą generować kod cykliczny?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany nie mogą generować kodu liniowego (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany nie mogą generować kodu cyklicznego (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod liniowy (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod cykliczny (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Przykład b)
Które wielomiany mogą generować kod liniowy?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany mogą generować kod cykliczny?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany nie mogą generować kodu liniowego (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany nie mogą generować kodu cyklicznego (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod liniowy (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod cykliczny (28, 3)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Przykład c)
Które wielomiany mogą generować kod liniowy?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany mogą generować kod cykliczny?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany nie mogą generować kodu liniowego (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany nie mogą generować kodu cyklicznego (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod liniowy (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod cykliczny (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
15
Przykład d)
Które wielomiany mogą generować kod liniowy?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany mogą generować kod cykliczny?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany nie mogą generować kodu liniowego (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany nie mogą generować kodu cyklicznego (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod liniowy (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod cykliczny (30, 4)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Przykład e)
Które wielomiany mogą generować kod liniowy?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany mogą generować kod cykliczny?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany nie mogą generować kodu liniowego (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany nie mogą generować kodu cyklicznego (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod liniowy (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod cykliczny (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Przykład f)
Które wielomiany mogą generować kod liniowy?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany mogą generować kod cykliczny?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany nie mogą generować kodu liniowego (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
♦ Które wielomiany nie mogą generować kodu cyklicznego (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod liniowy (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Które wielomiany generują kod cykliczny (31, 5)?
g
1
(x) g
2
(x) g
3
(x) g
4
(x) g
5
(x) g
6
(x) Ŝaden
Zadanie 2.
Przykład Część informacyjna wielomianu kodowego
Wielomian kodowy
a
x
31
+x
29
+x
28
+x
23
+x
22
+x
20
+x
18
+x
16
x
31
+x
29
+x
28
+x
23
+x
22
+x
20
+x
18
+x
16
+x
14
+x
11
+x
10
+x
8
+x
3
+x
b
x
29
+x
28
+x
27
+x
26
+x
21
+x
20
+x
17
+x
16
x
29
+x
28
+x
27
+x
26
+x
21
+x
20
+x
17
+x
16
+x
15
+x
8
+x
7
+x
5
+x+1
c
x
31
+x
30
+x
27
+x
24
+x
22
+x
18
+x
16
+x
15
x
31
+x
30
+x
27
+x
24
+x
22
+x
18
+x
16
+x
15
+x
14
+x
11
+x
6
+x
2
d
x
29
+x
28
+x
22
+x
21
+x
20
+x
18
+x
17
x
29
+x
28
+x
22
+x
21
+x
20
+x
18
+x
17
+x
9
+x
5
+x
3
e
x
26
+x
25
+x
23
+x
22
+x
21
+x
20
+x
17
+x
16
+x
14
x
26
+x
25
+x
23
+x
22
+x
21
+x
20
+x
17
+x
16
+x
14
+x
9
+x
5
+x
3
+x
2
+x
f
x
31
+x
30
+x
29
+x
28
+x
27
+x
23
+x
19
+x
18
+x
17
+x
16
x
31
+x
30
+x
29
+x
28
+x
27
+x
23
+x
19
+x
18
+x
17
+x
16
+x
12
+x
9
+x
8
+x
5
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
16
Zadanie 3.
Przykład a)
G =
1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 0 0 0
0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 0 0
0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0 0
0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 0
0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1
0 0 0 0 0 1 0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 0 0 1
0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 0
0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1
Przykład b)
G =
1 0 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 0 1 0 0 1 1
0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0
0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0
0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 1
Przykład c)
G =
1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 1 0
0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 1
0 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1 0
0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1
0 0 0 0 1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1 1 0 1 1 0 1
0 0 0 0 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1
0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0 1 0 0 1
0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
17
Przykład d)
G =
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 1 1 1 0 1 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 0 1 1 1 1 0 1
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 1 1 1
0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 1 0 1 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 1 0 1 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1
Przykład e)
G =
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 1
0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1
0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 1
0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 1 1
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1
0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 1 1 0 1 1 1 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 1 1 1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
18
Przykład f)
G =
1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 1
0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1
0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 0 0 1 1 0 1 1 1
0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 1
0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 1 1 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 0 1 1
0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 0 1 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 0 1 0 0 0 0 0 0 1
Zadanie 4.
Przykład
Wielomian kodowy
a
x
25
+x
24
+x
22
+x
19
+x
17
+x
14
+x
12
+x
11
+x
10
+x
7
+x
6
+x
4
+x
2
+1
b
x
24
+x
23
+x
21
+x
18
+x
16
+x
15
+x
14
+x
11
+x
10
+x
9
+x
6
+x
3
c
x
24
+x
23
+x
22
+x
20
+x
17
+x
15
+x
14
+x
13
+x
11
+x
10
+x
8
+x
6
+x
5
+x
2
+x+1
d
x
27
+x
25
+x
23
+x
22
+x
21
+x
19
+x
16
+x
15
+x
14
+x
12
+x
11
+x
9
+x
8
+x
7
+x
4
+x
e
x
26
+x
24
+x
22
+x
21
+x
20
+x
18
+x
15
+x
13
+x
12
+x
11
+x
10
+x
7
+x
6
+x
5
+x
4
+x
2
+1
f
x
25
+x
23
+x
21
+x
20
+x
19
+x
17
+x
15
+x
14
+x
9
+x
8
+x
2
+x+1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
19
Test nr 3 — zadania
Zadanie 2.
Dane jest słowo odebrane u(x) przez dekoder systematycznego kodu cyklicznego o długości 21. Odległość
minimalna kodu wynosi d, wielomian generujący kod g(x) podano poniŜej. Obliczyć wektor błędu, nadane
słowo kodowe oraz nadaną informację. Syndromy otrzymane w trakcie obliczeń wpisać w odpowiednie pola.
Indeksy przy poszczególnych syndromach odpowiadają liczbie przesunięć cyklicznych w lewo słowa
odebranego, na podstawie którego został obliczony dany syndrom. Wyniki podać w postaci wielomianowej –
wyniki podane w postaci bitowej nie będą uwzględniane!
Przykład a)
d = 12
u(x) = x
20
+x
19
+x
18
+x
16
+x
15
+x
14
+x
12
+x
11
+x
9
+x
8
+x
5
+x
2
+x+1
g(x) = x
18
+x
17
+x
16
+x
14
+x
11
+x
10
+x
9
+x
7
+x
4
+x
3
+x
2
+1
Przykład b)
d = 12
u(x) = x
20
+x
19
+x
18
+x
17
+x
16
+x
14
+x
13
+x
12
+x
7
+x
6
+x
5
+x
4
+x
2
g(x) = x
18
+x
16
+x
15
+x
14
+x
11
+x
9
+x
8
+x
7
+x
4
+x
2
+x+1
Przykład c)
d = 9
u(x) = x
18
+x
17
+x
16
+x
11
+x
9
+x
5
+x
4
g(x) = x
17
+x
16
+x
14
+x
10
+x
9
+x
7
+x
3
+x
2
+1
Przykład d)
d = 9
u(x) = x
17
+x
13
+x
10
+x
6
+x
4
+x
3
g(x) = x
17
+x
15
+x
14
+x
10
+x
8
+x
7
+x
3
+x+1
Przykład e)
d = 10
u(x) = x
20
+x
19
+x
18
+x
17
+x
16
+x
14
+x
13
+x
12
+x
11
+x
10
+x
8
+x
5
+x
4
+x
g(x) = x
16
+x
15
+x
14
+x
13
+x
12
+x
10
+x
8
+x
5
+x
4
+1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
20
Zadanie 3.
Dane jest słowo odebrane u(x) przez dekoder systematycznego kodu cyklicznego. Macierz korekcyjna
transponowana H
T
jest podana poniŜej, odległość minimalna kodu wynosi d. Obliczyć wektor błędu, nadane
słowo kodowe oraz nadaną informację. Indeksy przy poszczególnych syndromach odpowiadają liczbie
przesunięć cyklicznych w lewo słowa odebranego, na podstawie którego został obliczony dany syndrom.
Wektor błędu, nadane słowo kodowe oraz nadaną informację podać w postaci wielomianowej, syndromy
podać w postaci bitowej. Wyniki podane niezgodnie z powyŜszymi wymaganiami nie będą uwzględniane!
Przykład a)
d = 7
u(x) = x
20
+x
19
+x
16
+x
12
+x
10
+x
9
+x
5
+x
3
+x
2
+x
H
T
=
1 1 1 1 0 1 1 1 0 0 1 1 0 1 0
0 1 1 1 1 0 1 1 1 0 0 1 1 0 1
1 1 0 0 1 0 1 0 1 1 1 1 1 0 0
0 1 1 0 0 1 0 1 0 1 1 1 1 1 0
0 0 1 1 0 0 1 0 1 0 1 1 1 1 1
1 1 1 0 1 1 1 0 0 1 1 0 1 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
21
Przykład b)
d = 8
u(x) = x
20
+x
19
+x
18
+x
17
+x
15
+x
9
+x
8
+x
3
+x
2
H
T
=
1 1 0 1 0 0 1 1 0 0 1 0 0 1 0
0 1 1 0 1 0 0 1 1 0 0 1 0 0 1
1 1 1 0 0 1 1 1 1 1 1 0 1 1 0
0 1 1 1 0 0 1 1 1 1 1 1 0 1 1
1 1 1 0 1 0 1 0 1 1 0 1 1 1 1
1 0 1 0 0 1 1 0 0 1 0 0 1 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
22
Przykład c)
d = 8
u(x) = x
17
+x
14
+x
13
+x
11
+x
10
+x
9
+x
8
+x
7
+x
6
+x
3
+x
2
+x
H
T
=
1 1 0 0 0 1 1 1 0 1 1 1 0 0
0 1 1 0 0 0 1 1 1 0 1 1 1 0
0 0 1 1 0 0 0 1 1 1 0 1 1 1
1 1 0 1 1 1 1 1 1 0 0 1 1 1
1 0 1 0 1 0 0 0 1 0 1 1 1 1
1 0 0 1 0 0 1 1 0 0 1 0 1 1
1 0 0 0 1 1 1 0 1 1 1 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
23
Przykład d)
d = 8
u(x) = x
20
+x
17
+x
15
+x
14
+x
12
+x
11
+x
10
+x
9
+x
5
+x
4
+x
2
+x+1
H
T
=
1 1 1 1 0 0 0 1 0 1 0 1
1 0 0 0 1 0 0 1 1 1 1 1
1 0 1 1 0 1 0 1 1 0 1 0
0 1 0 1 1 0 1 0 1 1 0 1
1 1 0 1 1 1 0 0 0 0 1 1
1 0 0 1 1 1 1 1 0 1 0 0
0 1 0 0 1 1 1 1 1 0 1 0
0 0 1 0 0 1 1 1 1 1 0 1
1 1 1 0 0 0 1 0 1 0 1 1
1 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
24
Przykład e)
d = 8
u(x) = x
22
+x
21
+x
20
+x
19
+x
18
+x
16
+x
14
+x
12
+x
10
+x
8
+x
7
+x
4
+x
3
+x
2
+x
H
T
=
1 1 1 1 1 0 0 1 0 0 1 0
0 1 1 1 1 1 0 0 1 0 0 1
1 1 0 0 0 1 1 1 0 1 1 0
0 1 1 0 0 0 1 1 1 0 1 1
1 1 0 0 1 0 0 0 1 1 1 1
1 0 0 1 1 1 0 1 0 1 0 1
1 0 1 1 0 1 1 1 1 0 0 0
0 1 0 1 1 0 1 1 1 1 0 0
0 0 1 0 1 1 0 1 1 1 1 0
0 0 0 1 0 1 1 0 1 1 1 1
1 1 1 1 0 0 1 0 0 1 0 1
1 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
25
Przykład f)
d = 7
u(x) = x
22
+x
19
+x
14
+x
12
+x
11
+x
9
+x
8
+x
7
+x
3
+x
H
T
=
1 1 0 0 0 1 1 1 0 1 0
0 1 1 0 0 0 1 1 1 0 1
1 1 1 1 0 1 1 0 1 0 0
0 1 1 1 1 0 1 1 0 1 0
0 0 1 1 1 1 0 1 1 0 1
1 1 0 1 1 0 0 1 1 0 0
0 1 1 0 1 1 0 0 1 1 0
0 0 1 1 0 1 1 0 0 1 1
1 1 0 1 1 1 0 0 0 1 1
1 0 1 0 1 0 0 1 0 1 1
1 0 0 1 0 0 1 1 1 1 1
1 0 0 0 1 1 1 0 1 0 1
1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
26
Test nr 3 — wyniki zadań
Zadanie 2.
Przykład a)
s
0
(x) = x
15
+x
14
+x
13
+x
8
+x
6
+x
4
+x+1
s
1
(x) = x
16
+x
15
+x
14
+x
9
+x
7
+x
5
+x
2
+x
s
2
(x) = x
17
+x
16
+x
15
+x
10
+x
8
+x
6
+x
3
+x
2
s
3
(x) = x
14
+x
10
+x
2
+1
e(x) = x
20
+x
18
+x
11
+x
7
c(x) = x
19
+x
16
+x
15
+x
14
+x
12
+x
9
+x
8
+x
7
+x
5
+x
2
+x+1
m(x) = x
Przykład b)
s
0
(x) = x
17
+x
16
+x
15
+x
14
+x
11
+x
8
+x
7
+x
2
+x
s
1
(x) = x
17
+x
14
+x
12
+x
11
+x
7
+x
4
+x
3
+x+1
s
2
(x) = x
16
+x
14
+x
13
+x
12
+x
11
+x
9
+x
7
+x
5
+1
s
3
(x) = x
17
+x
15
+x
14
+x
13
+x
12
+x
10
+x
8
+x
6
+x
s
4
(x) = x
13
+x
8
+x
4
+x+1
e(x) = x
18
+x
17
+x
9
+x
4
+1
c(x) = x
20
+x
19
+x
16
+x
14
+x
13
+x
12
+x
9
+x
7
+x
6
+x
5
+x
2
+1
m(x) = x
2
+x
Przykład c)
s
0
(x) = x
16
+x
15
+x
10
+x
9
+x
8
+x
5
+x
3
+x
s
1
(x) = x
14
+x
11
+x
7
+x
6
+x
4
+x
3
+1
s
2
(x) = x
15
+x
12
+x
8
+x
7
+x
5
+x
4
+x
s
3
(x) = x
16
+x
13
+x
9
+x
8
+x
6
+x
5
+x
2
s
4
(x) = x
16
+x
6
+x
2
+1
e(x) = x
19
+x
17
+x
12
+x
2
c(x) = x
19
+x
18
+x
16
+x
12
+x
11
+x
9
+x
5
+x
4
+x
2
m(x) = x
2
+x
Przykład d)
s
0
(x) = x
15
+x
14
+x
13
+x
8
+x
7
+x
6
+x
4
+x+1
s
1
(x) = x
16
+x
15
+x
14
+x
9
+x
8
+x
7
+x
5
+x
2
+x
s
2
(x) = x
16
+x
14
+x
9
+x
7
+x
6
+x
2
+x+1
s
3
(x) = x
14
+x
2
+1
e(x) = x
20
+x
18
+x
11
c(x) = x
20
+x
18
+x
17
+x
13
+x
11
+x
10
+x
6
+x
4
+x
3
m(x) = x
3
+x+1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
27
Przykład e)
s
0
(x) = x
13
+x
11
+x
10
+x
9
+x
5
+x
s
1
(x) = x
14
+x
12
+x
11
+x
10
+x
6
+x
2
s
2
(x) = x
15
+x
13
+x
12
+x
11
+x
7
+x
3
s
3
(x) = x
15
+x
10
+x
5
+1
e(x) = x
18
+x
12
+x
7
+x
2
c(x) = x
20
+x
19
+x
17
+x
16
+x
14
+x
13
+x
11
+x
10
+x
8
+x
7
+x
5
+x
4
+x
2
+x
m(x) = x
4
+x
3
+x+1
Zadanie 3.
Przykład a)
s
0
= 100100100100110
s
1
= 110010101111001
s
2
= 011110111000111
s
3
= 111101110001110
s
4
= 000000000101001
e(x) = x
20
+x
17
+x
c(x) = x
19
+x
17
+x
16
+x
12
+x
10
+x
9
+x
5
+x
3
+x
2
m(x) = x
4
+x
2
+x
Przykład b)
s
0
= 100011101111111
s
1
= 101110111011011
s
2
= 110100010010011
s
3
= 000001000000011
e(x) = x
19
+x
18
+x
6
c(x) = x
20
+x
17
+x
15
+x
9
+x
8
+x
6
+x
3
+x
2
m(x) = x
5
+x
2
+1
Przykład c)
s
0
= 11101110010000
s
1
= 01010010011001
s
2
= 10100100110010
s
3
= 11000111011101
s
4
= 00000000000011
e(x) = x
18
+x
17
c(x) = x
18
+x
14
+x
13
+x
11
+x
10
+x
9
+x
8
+x
7
+x
6
+x
3
+x
2
+x
m(x) = x
4
+1
Zadania do kursu Kodowanie — ćwiczenia (2011/2012)
28
Przykład d)
s
0
= 011110101010
s
1
= 111101010100
s
2
= 000010000011
e(x) = x
20
+x
19
+x
5
c(x) = x
19
+x
17
+x
15
+x
14
+x
12
+x
11
+x
10
+x
9
+x
4
+x
2
+x+1
m(x) = x
7
+x
5
+x
3
+x
2
+1
Przykład e)
s
0
= 110110000100
s
1
= 010000101101
s
2
= 100001011010
s
3
= 111110010001
s
4
= 000000000111
e(x) = x
21
+x
20
+x
19
c(x) = x
22
+x
18
+x
16
+x
14
+x
12
+x
10
+x
8
+x
7
+x
4
+x
3
+x
2
+x
m(x) = x
10
+x
6
+x
4
+x
2
+1
Przykład f)
s
0
= 00001100011
s
1
= 00011000110
s
2
= 00110001100
s
3
= 01100011000
s
4
= 11000110000
s
5
= 00000010101
e(x) = x
22
+x
20
+x
18
c(x) = x
20
+x
19
+x
18
+x
14
+x
12
+x
11
+x
9
+x
8
+x
7
+x
3
+x
m(x) = x
9
+x
8
+x
7
+x
3
+x+1