Kodowanie zbior zadan 2011 12 sem letni

background image


Materiały do kursu

Kodowanie – ćwiczenia

Zadania



















Kod kursu ETEK00025C
Semestr letni, rok akad. 2011 / 2012

Przygotował Piotr Kocyan
pok. 331 C-4

background image

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


background image

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

background image

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

background image

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


background image

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

background image

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

background image

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.

background image

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.

background image

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.

background image

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


background image

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


background image

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


background image

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







background image

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

background image

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

background image

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

background image

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

background image

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




background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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

background image

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




Wyszukiwarka

Podobne podstrony:

więcej podobnych podstron