Teoria informacji
i kodowanie

Ćwiczenia IV

1. kwietnia 2011 r.

Końcówka kompresji, wstęp do nadmiarowych kodów kanałowych, odległość Ham-

minga, kresy związane z kodami nadmiarowymi

Zadanie 1

Skompresuj za pomocą kodu arytmetycznego sekwencję (

2

 oznacza koniec sekwencji):

BUFFALO BILL

2

Rozkład źródła znajdź na podstawie podanej sekwencji (w razie potrzeby można zaokrąglić do
dwóch miejsc po przecinku dla uproszczenia obliczeń). Zbadaj efektywność kodu.

Zadanie 2

Przy zadanej w tabeli statystyce źródła sprawdź, jaką wiadomość zakodowano za pomocą na-
stępującej sekwencji bitów używając kodowania arytmetycznego (

2

 oznacza koniec sekwencji):

001110110010011010001011011

Wiadomość

Prawdopodobieństwo skumulowane

A

[0,0; 0,1)

I

[0,1; 0,2)

M

[0,2; 0,4)

S

[0,4; 0,6)

Z

[0,6; 0,8)
[0,8; 0,9)

2

[0,9; 1,0)

(Odp. MISZ MASZ

2

)

Zadanie 3

Skompresuj za pomocą adaptacyjnego (dynamicznego) kodu Huffmana sekwencję:

GŻEGŻÓŁKA JEŻA

Zadanie 4

Udowodnij, że odległość Hamminga dla dowolnych ciągów kodowych v

1

, v

2

, v

3

o długościach

słowa n charakteryzuje się następującymi właściwościami:

1. 0 ¬ d(v

1

, v

2

) ¬ n,

2. d(v

1

, v

1

) = 0,

3. jeśli d(v

1

, v

2

) = 0, to v

1

= v

2

,

4. d(v

1

, v

2

) = d(v

2

, v

1

),

5. d(v

1

, v

2

) ¬ d(v

1

, v

3

) + d(v

3

, v

2

).

Zadanie 5

Policz prawdopodobieństwo błędnego zdekodowania informacji kodowanej w binarnym kodzie
z kontrolą parzystości, w którym długości poszczególnych słów kodowych wynoszą cztery sym-
bole, zaś informacja jest transmitowana przez binarny bezpamięciowy kanał symetryczny cha-
rakteryzujący się BER = ε. (Odp. 6ε

2

(1 − ε)

2

+ ε

4

)

Strona 1 z 3

Teoria informacji
i kodowanie

Ćwiczenia IV

1. kwietnia 2011 r.

Zadanie 6

Binarny kod z powtarzaniem R

n

polega na kodowaniu 0 ciągiem n zer i analogicznie dla 1:

0 → 00 . . . 0

|

{z

}

n

1 → 11 . . . 1

|

{z

}

n

.

Policz prawdopodobieństwo błędnego zdekodowania informacji kodowanej w kodzie R

3

, jeśli

informacja jest transmitowana binarnym bezpamięciowym kanałem symetrycznym charaktery-
zującym się BER = ε i stosujemy regułę decyzyjną największego prawdopodobieństwa. (Odp.
3ε

2

− 2ε

3

)

Zadanie 7

Co najmniej ile pozycji kontrolnych ma binarny kod blokowy o minimalnej odległości Hamminga
d

min

= 4, przeznaczony do zakodowania 8 wiadomości? (Odp. Osiem)

Zadanie 8

Określ maksymalną liczbę pozycji informacyjnych binarnego kodu nadmiarowego o długości
n = 16, jeśli minimalna odległość Hamminga wynosi d

min

= 4. (Odp. Dziewięć)

Zadanie 9

Skonstruuj najkrótszy blokowy binarny kod nadmiarowy do zakodowania 32 wiadomości w
słowa kodowe o wadze 3. Jaka jest minimalna odległość Hamminga? (Odp. d

min

= 2)

Zadanie 10

Udowodnij, że jeśli istnieje kod binarny (n, k) o odległości minimalnej d

min

= 2k, to istnieje rów-

nież kod binarny o tych samych parametrach (n, k) i niegorszych właściwościach korekcyjnych,
którego wszystkie słowa mają wagę parzystą.

Zadanie 11

Pewien bezpamięciowy kanał binarny zawsze poprawnie transmituje zero, natomiast jedyn-
kę transmituje poprawnie z prawdopodobieństwem P . Zapisz macierz tego kanału oraz oblicz
prawdopodobieństwo błędnego zdekodowania symbolu, jeśli 0 jest wysyłane z prawdopodobień-
stwem p. Następnie, zakładając że stosuje się kod z powtarzaniem R

3

(def. w zad. 6), znajdź

prawdopodobieństwo błędnego zdekodowania, jeśli stosuje się regułę decyzyjną największego
prawdopodobieństwa. (Odp. (1 − p) 2P

3

+ 3P

2

)

Zadanie 12

(kolokwium z lat poprzednich)

Jeśli to możliwe, skonstruuj kod binarny o ciągach kodowych długości 7, służący do zakodowania
ośmiu wiadomości i korygujący błędy dwukrotne.

Zadanie 13

(kolokwium z lat poprzednich)

Mamy dany konkretny ciąg kodowy binarnego kodu nadmiarowego (n, k). Oblicz dla 0 ¬ i ¬ n,
ile istnieje ciągów, których odległość Hamminga od tego ciągu wynosi i. Pokaż, że ich suma po
i = 0, 1, . . . , n jest równa liczbie wszystkich binarnych ciągów n-elementowych.

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

Strona 2 z 3

Teoria informacji
i kodowanie

Ćwiczenia IV

1. kwietnia 2011 r.

„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

.

Strona 3 z 3