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