i kodowanie
Ćwiczenia
27. lutego 2008 r.
Źródła markowowskie, kanały informacyjne, przepustowość Zadanie 1
Entropia źródła Markowa M -tego rzędu wynosi: X X
HL( X) =
· · · X Pr {xi, xj , . . . , x } lg Pr {x
, . . . , x } .
1
jL
i|xj 1
jL
i
j 1
jL
Ź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: 1
Pr { 0 | 1 } = Pr { 1 | 0 } =
;
3
(b) źródło jest źródłem z pamięcią, natomiast: 3
2
Pr { 0 } =
Pr { 0 | 0 } =
Pr { 0 | 1 } = 1 .
4
3
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: 5
2
Pr { 00 } = Pr { 11 } =
Pr { 01 } = Pr { 10 } =
.
14
14
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ństwem błędu:
1 ¬ pi < 1 .
2
W jaki sposób można z nich (niekoniecznie wszystkich) uzyskać binarny kanał symetryczny charakteryzujący się:
1
0 < BER ¬
?
2
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?
Strona 1 z 2
i kodowanie
Ćwiczenia
27. lutego 2008 r.
Zadanie 6
Dany jest binarny symetryczny kanał z wymazywaniem: x
y
1 = 0
1 = x 1
y 3 = E
x
y
2 = 1
2 = 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ść: 1
p( y 1 |x 1) = 1
p( y 1 |x 2) = p( y 2 |x 2) = 2
Znajdź przepustowość tego kanału.
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 : 1
4
x 1 = 0
y 1 = 0
1
2
y 3 = E
1
1
4
x 2 = 1
y 2 = 1
jeśli
1
Pr {x 1 } = Pr {x 2 } =
.
2
Zadanie 9
(kolokwium z lat poprzednich)
Oblicz przepustowość „kanału pięciokątnego”. Przy strzałkach mamy dane prawdopodobień-
stwa przejść p( yj|xi) = 1 : p( y 2
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 (kanał jest symetryczny).
2
1
1
2
2
3
3
4
4
5
5
Strona 2 z 2