Teoria informacji
i kodowanie

Ćwiczenia VI

6. maja 2011 r.

Modyfikacje kodów liniowych, kody łączone oraz iterowane i kody Reeda-Mullera

Zadanie 1

Znajdź syndrom odebranego przez dekoder ciągu:

y = 1011110101,

jeśli wiadomo, że na wejściu kanału pojawiają się słowa skróconego kodu Hamminga. Jaka
będzie decyzja dekodera? (Odp. 1110)

Zadanie 2

Pokaż, że skrócony kod Hamminga (6, 3) nie jest kodem idealnym.

Zadanie 3

Określ konieczną liczbę powtórzeń nienadmiarowego kodu binarnego, pozwalającą na korygo-
wanie błędów jedno- i dwukrotnych. (Odp. Cztery)

Zadanie 4

Określ, jak zwiększą się możliwości korekcyjne kodu z kontrolą parzystości (4, 3), jeśli zastąpi
się go kodem dwukrotnie iterowanym. Określ nadmiar oraz prześledź działanie dekodera przy:

(a) bezbłędnej transmisji,

(b) transmisji z błędem pojedynczym,

(c) transmisji z dwoma błędami,

(d) transmisji z większą liczbą błędów.

Zadanie 5

(kolokwium z lat poprzednich)

Skonstruuj macierz generującą kodu dwukrotnie iterowanego, w którym kolumny i wiersze
zakodowane są kodami o macierzach generujących:

G

1

= G

2

=

"

1

0

1

0

1

1

#

.

Zadanie 6

W misjach kosmicznych w 1969 i 1976 roku NASA używała kodu Reeda-Mullera (32, 6). Znajdź
odległość minimalną tego kodu oraz jego macierz generującą. Następnie policz, jakie jest praw-
dopodobieństwo błędnego zdekodowania ciągu, jeśli kanał transmisyjny jest modelowany jako
binarny bezpamięciowy kanał symetryczny o BER = 0,05. (Odp. Ok. 0,19 × 10

−4

)

Zadanie 7

(kolokwium z lat poprzednich)

Jakie słowa kodowe najkrótszego możliwego kodu Reeda-Mullera odpowiadają ciągom infor-
macyjnym:

u

1

= 1101

u

2

= 1001?

(Odp. 10100101 i 11110000)

Zadanie 8

(kolokwium z lat poprzednich)

Zaprojektuj kod Reeda-Mullera służący do przenoszenia przynajmniej szesnastu wiadomości,
który pozwala na korygowanie wszystkich błędów pojedynczych i podwójnych, podając: jego
parametry, minimalną odległość Hamminga oraz macierz generującą.

Strona 1 z 2

Teoria informacji
i kodowanie

Ćwiczenia VI

6. maja 2011 r.

Informacja dodatkowa:
Na kartkach z zadaniami do kolejnych kolokwiów znajdą Państwo następujące dane:

„Legalna ściąga”:

Kres górny Plotkina: d

min

¬

n2

k−1

2

k

−1

.

Kres górny Eliasa: d

min

¬ 2s

K

K−1

(1 −

s

n

), gdzie: s, K ∈

Z oraz 2

n−k

<

P

s

i=0

n

i

, i K jest najmniejszą liczbą całkowitą

spełniającą zależność: K ­

P

s

i=0

n

i

2

n−k

.

Kres dolny Warszamowa-Gilberta: 2

n−k

>

P

d−2

i=0

n−1

i

.

Wielomiany generujące cyklicznych kodów Hamminga

c

Wielomian generujący

2

x

2

+ x + 1

3

x

3

+ x + 1

4

x

4

+ x + 1

5

x

5

+ x + 1

Zestandaryzowane wielomiany generujące dla różnych CRC

Kod

Wielomian generujący

CRC-4

x

4

+ x

3

+ x

2

+ x + 1

CRC-7

x

7

+ x

6

+ x

4

+ 1

CRC-8

x

8

+ x

7

+ x

6

+ x

4

+ x

2

+ 1

CRC-12

x

12

+ x

11

+ x

3

+ x

2

+ x + 1

CRC-ANSI

x

16

+ x

15

+ x

2

+ 1

CRC-CCITT

x

16

+ x

12

+ x

5

+ 1

CRC-SDLC

x

16

+ x

15

+ x

13

+ x

7

+ x

4

+ x

2

+ x + 1

CRC-24

x

24

+ x

23

+ x

14

+ x

12

+ x

8

+ 1

Strona 2 z 2