Teoria informacji
i kodowanie

Ćwiczenia II

11. marca 2011 r.

Źródła markowowskie, kanały informacyjne, przepustowość

Zadanie 1

Entropia źródła Markowa M-tego rzędu wynosi:

H

L

(X) = −

X

i

X

j

1

· · ·

X

j

L

Pr {x

i

, x

j

1

, . . . , x

j

L

} lg Pr {x

i

|x

j

1

, . . . , x

j

L

} .

Źródło binarne generuje dwie wiadomoci: 0 i 1. Oblicz entropię klasyczną oraz entropię Markowa
źródła przy następujących założeniach:

(a) wiadomości są równoprawdopodobne, źródło jest źródłem z pamięcią, przy czym:

Pr{0|1} = Pr{1|0} =

1

3

;

(Odp. 1

bit

/

symbol

i ok. 0,9

bit

/

symbol

)

(b) źródło jest źródłem z pamięcią, natomiast:

Pr{0} =

3

4

Pr{0|0} =

2

3

Pr{0|1} = 1.

(Odp. Ok. 0,81

bit

/

symbol

i ok. 0,68

bit

/

symbol

)

Zadanie 2

Sporządź wykres stanów źródła Markowa drugiego rzędu, jeśli źródło jest źródłem binarnym,
a prawdopodobieństwa warunkowe wynoszą:

Pr{0|00} = Pr{1|11} = 0,8

Pr{1|00} = Pr{0|11} = 0,2

Pr{0|01} = Pr{0|10} = Pr{1|01} = Pr{1|10} = 0,5.

Następnie oblicz entropię tego źródła, jeśli wiadomo że:

Pr{00} = Pr{11} =

5

14

Pr{01} = Pr{10} =

2

14

.

(Odp. Ok. 0,78

bit

/

symbol

)

Zadanie 3

(kolokwium z lat poprzednich)

Sprawdź czy kaskada binarnych kanałów symetrycznych (kanały są połączone szeregowo: wyj-
ście jednego z wejściem kolejnego; kanały niekoniecznie są identyczne) też jest binarnym kana-
łem symetrycznym.

Zadanie 4

(kolokwium z lat poprzednich)

Mamy do dyspozycji niekoniecznie identyczne binarne kanały symetryczne charakteryzujące się
prawdopodobieństwami błędu:

1

2

¬ p

i

< 1.

W jaki sposób można z nich (niekoniecznie wszystkich) uzyskać binarny kanał symetryczny
charakteryzujący się:

0 < BER ¬

1

2

?

Strona 1 z 3

Teoria informacji
i kodowanie

Ćwiczenia II

11. marca 2011 r.

Zadanie 5

(kolokwium z lat poprzednich)

Informacja złożona z N symboli binarnych jest transmitowana przez binarny kanał symetryczny
o prawdopodobieństwie przekłamania p. Jaka jest wartość oczekiwana liczby bitów przesłanych
poprawnie w tej informacji? Jaka jest przepustowość tego kanału?

Zadanie 6

Dany jest binarny symetryczny kanał z wymazywaniem:

x

1

= 0

x

2

= 1

y

1

= x

1

y

2

= E

y

3

= x

2

Kanał charakteryzuje się następującymi prawdopodobieństwami:






1 − α − β

α

β

β

α

1 − α − β






.

Pokaż, że jego przepustowość da się opisać następującym wzorem:

C = (1 − β)[1 − lg(1 − β)] + (1 − α − β) lg(1 − α − β) + α lg α.

Zadanie 7

(kolokwium z lat poprzednich)

Kanał binarny charakteryzuje się następującymi prawdopodobieństwami przejść:

p(y

1

|x

1

) = 1

p(y

1

|x

2

) = p(y

2

|x

2

) =

1

2

Znajdź przepustowość tego kanału. (Odp. Ok. 0,4

bit

/

wiadomość

)

Zadanie 8

Oblicz, ile wynosi informacja wzajemna I(X; Y ) między wejściem i wyjściem kanału o dwóch
wejściach x

1

, x

2

∈ X i trzech wyjściach y

1

, y

2

, y

3

∈ Y :

x

1

= 0

x

2

= 1

y

1

= 0

y

3

= E

y

2

= 1

1
4

1
2

1
4

jeśli

Pr {x

1

} = Pr {x

2

} =

1

2

.

(Odp. Ok. 0,55

bit

/

wiadomość

)

Strona 2 z 3

Teoria informacji
i kodowanie

Ćwiczenia II

11. marca 2011 r.

Zadanie 9

(kolokwium z lat poprzednich)

Oblicz przepustowość „kanału pięciokątnego”. Przy strzałkach mamy dane prawdopodobień-
stwa przejść p(y

j

|x

i

) =

1
2

: p(y

1

|x

2

) = p(y

1

|x

5

) = p(y

2

|x

1

) = p(y

2

|x

3

) = p(y

3

|x

2

) = p(y

3

|x

4

) =

p(y

4

|x

3

) = p(y

4

|x

5

) = p(y

5

|x

4

) = p(y

5

|x

1

) =

1
2

(kanał jest symetryczny).

1
2
3
4
5

1
2
3
4
5

(Odp. lg 5 − 1

bit

/

wiadomość

)

Zadanie 10

(kolokwium z lat poprzednich)

Binarny kanał asymetryczny jest reprezentowany za pomocą macierzy:

"

1 − a

a

b

1 − b

#

,

gdzie na wejściu i wyjściu mamy symbole ze zbioru {0, 1} oraz a 6= b. Odbiornik otrzymuje na
swoim wejściu symbole 0 i 1 tak samo często. Znajdź rozkład prawdopodobieństwa na wejściu
do tego kanału (czyli na wyjściu z nadajnika) i pokaż, że entropia na wyjściu kanału jest większa
niż na jego wejściu.

Zadanie 11

(kolokwium z lat poprzednich)

1

2

3

4

Uproszczoną klawiaturę numeryczną pokazano na rysunku obok. Ma ona cztery
klawisze (w dwóch rzędach po dwa klawisze). Użytkownik, który chce nacisnąć
klawisz x, naciśnie z prawdopodobieństwem α inny klawisz w tym samym rzę-
dzie lub z prawdopodobieństwem α inny klawisz w tej samej kolumnie. A więc z
prawdopodobieństwem 1 − 2α naciśnie właściwy klawisz x. Taką klawiaturę można
opisywać jako kanał transmisyjny, gdzie na wejściu mamy intencję użytkownika, a
na wyjściu faktycznie naciśnięty klawisz. Zapisz macierz tego kanału i oblicz jego przepustowość.
(Odp. 2 + (1 − 2α) lg(1 − 2α) + 2α lg α

bit

/

wiadomość

)

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

„Legalna ściąga”:

H(X, Y ) = H(X) + H(Y |X) (reguła łańcuchowa)

I(X; Y ) = H(X) − H(X|Y ) = H(Y ) − H(Y |X) = H(X) + H(Y ) − H(X, Y )

X, Y — niezależne: H(X, Y ) = H(X) + H(Y )

Strona 3 z 3