2009-11-19 11:22:00 (2010-11-14 20:45:00)
Podstawy Systemów Informacyjnych – ćwiczenia Ćw. 6. Modele kanału dyskretnego - ilość informacji wzajemnej Zagadnienia: podstawowe modele kanału dyskretnego, ilość informacji wzajemnej, pojemność informacyjna symbolu przesyłanego przez kanał.
Podstawowe modele kanału:
a) binarny kanał symetryczny z przekłamaniem
1− Pb
S = s = 0
Y = y = 0
1
1
Pb
Pb
S = s = 1
Y = y = 1
2
1− P
2
b
M = 2
M = 2
S
Y
b) binarny kanał symetryczny z wymazaniem
1− Pe
S = s = 0
Y = y = 0
1
1
Pe
Y = y
3 = ?
Pe
S = s = 1
Y = y = 1
2
1− P
2
e
M = 2
M = 3
S
Y
c) Kanał binarny skrajnie asymetryczny
1
S = s = 0
Y = y = 0
1
1
Pb
S = s = 1
Y = y = 1
2
1− P
2
b
M = 2
M = 2
S
Y
d) binarny kanał symetryczny z przekłamaniem i wymazywaniem
Kanał stacjonarny.
Średnia entropia warunkowa:
z punktu widzenia strony nadawczej H( Y|S) – określa jaka jest nasza niepewność na temat Y, gdy znane jest S
H Y
( | S ) = −∑∑ P( S = s , Y
y ) log P Y
(
y | S
s )
P( S
s ) H Y
( | S
s )
i
= j
2
= j
= i = ∑
= i
= i
∀ i ∀ j
∀ i
z punktu widzenia strony odbiorczej H( S|Y) – określa jaka jest nasza niepewność na temat S, gdy znane jest Y
H ( S | Y ) = −∑ ∑ P( S = s , Y
y ) log P( S
s | Y
y )
P Y
(
y ) H ( S | Y
y )
i
= j
2
= i
= j = ∑
= i
= i
∀ i ∀ j
∀ j
W przypadku modelu kanału na ogół dane jest P( Y = y | S = s ) oraz P( S = s ) stąd j
i
i
P( S = s , Y = y ) = P( Y = y | S = s ) P( S = s ) i
j
j
i
i
2009-11-19 11:22:00 (2010-11-14 20:45:00)
P Y
( = y )
P( S
s , Y
y )
j
= ∑
= i = j
∀ i
P( S = s | Y = y ) P( Y = y | S = s ) i
j
=
j
i
P( Y = y )
j
Ilość informacji wzajemnej zmiennych losowych S i Y (interpretowanych jako sygnały wejściowe i wyjściowe kanałów dyskretnych): ilość informacji z zmiennej losowej Y dostarczana przez zmienną losową S – punkt widzenia strony nadawczej – I( Y; S) ilość informacji z zmiennej losowej S dostarczana przez zmienną losową Y – punkt widzenia strony odbiorczej – I( S; Y) I ( Y ; S ) := H ( Y ) − H ( Y | S )
=
H ( S ) − H ( S | Y ) :
= I( S; Y)
P( s , y )
I ( S; Y ) = ∑ P( s , y ) log
i
j
: D P P P
i
j
= KL SY S Y ≥
2
( ,
) 0
∀
P s P y
i, j
( ) (
)
i
j
Pojemność informacyjna symbolu przesyłanego przez kanał: C := max I ( S; Y ) [ bit / symbol]
P
∀ S
C
= log M - dla kanału idealnego
MAX
2
Szybkość transmisji symboli: ν bodów
(Informacyjna) przepustowość kanału:
1
F
C =
C
[ bit / s]
symb
Ts
Prędkość transmisji:
F
C
= F
log M
[ bit / ]
symb
MAX
symb
2
s
Uwaga: przepustowość kanału nie przekracza prędkości transmisji F
C ≤ F
log M
symb
symb
2
Zad. 1. Dla binarnego kanału symetrycznego z przekłamaniem a) obliczyć i wykreślić średnią entropię warunkową H(Y|S) - niepewność co do tego co pojawi się na wyjściu kanału, jeżeli znane jest to co podano na wejście kanału, b) obliczyć i wykreślić średnią entropię warunkową H(S|Y) - niepewność co do tego co podano na wejście kanału, jeżeli znane jest to co pojawiło się na wyjściu kanału, dla I. Pb = 0,
II. Pb = 1/2,
III. Po = 1/2,
IV. Po = 1/9,
V. Po = 1/24,
VI. Po = 0,
gdzie S – zmienna losowa reprezentująca sygnał na wejściu kanału, Y – zmienna losowa reprezentująca sygnał na wyjściu kanału, Pb – prawdopodobieństwo przekłamania, a Po –
prawdopodobieństwo, że nadano wiadomość „0”. Wyniki zinterpretować.
Zad.2. Dla kanału z zad. 1, w oparciu o wyznaczone w zad. 1 średnie entropie warunkowe, obliczyć i wykreślić
2009-11-19 11:22:00 (2010-11-14 20:45:00)
a) ilość informacji o zmiennej losowej Y dostarczanej przez zmienną losową S – punkt widzenia strony nadawczej: I(Y;S),
b) ilość informacji o zmiennej losowej S dostarczanej przez zmienną losową Y – punkt widzenia strony odbiorczej: I(S;Y),
c) powtórzyć obliczenia korzystając ze wzoru na dywergencję Kullbacka-Leiblera.
Obliczenia wykonać dla:
I. Pb = 0,
II. Pb = 1/2,
III. Po = 1/2,
IV. Po = 1/9,
V. Po = 1/24,
VI. Po = 0,
W oparciu o wyniki obliczeń określić pojemność informacyjną symbolu przesyłanego przez ten kanał.
Zad.3. Dla modelu kanału pokazanego na rysunku, gdzie P( S = A) = 1/4, P( S = B) = 1/2, P( S = C) = 1/4 oraz prawdopodobieństwo przekłamania Pb = 1/8, wyznacz ilość informacji wzajemnej.
1− Pb
S = s = A
Y = y = a
1
1
Pb
P / 2
b
1− Pb
S = s
2 = B
Y = y
2 = b
P
P / 2
b
b
S = s = C
Y = y = c
3
1− P
3
b
M = 3
M = 3
S
Y
Powtórz obliczenia dla przypadku, w którym po stronie nadawczej zastosowano inne kodowanie źródła, dla którego P( S = A) = P( S = B) = P( S = C) = 1/3. Skomentuj wyniki.