Zad. 1. Dwa dyskretne źródła wiadomości opisane są rozkładami prawdopodobieństwa podanymi w

tabelce. Obliczyć ilość informacji zawartej w każdej z wiadomości oraz dywergencję Kullbacka-Leiblera
D

KL

(P

X

, P

V

).

x

i

a

b

c

P

X

(x

i

)

0.8

0.1

0.1

x

i

a

b

c

P

V

(x

i

)

1/3

1/3

1/3

Rozwiązanie 1:

Ilość informacji zawartą w wiadomości x

i

wyznaczamy wg wzoru:

I(X = x

i

) = − log

2

(P (X = x

i

)) = − ln P (X = x

i

)/ ln 2

W naszym przypadku otrzymujemy (w przybliżeniu)

x

i

a

b

c

I(X = x

i

)

0.32 [bit]

3.32 [bit]

3.32 [bit]

x

i

a

b

c

I(V = x

i

)

1.58 [bit]

1.58 [bit]

1.58 [bit]

Z kolei dywergencja Kulbacka-Leiblera zdefiniowana jest wzorem

D

KL

(P

X

, P

V

) =

X

∀i

P (X = x

i

)· log

2

P (X = x

i

)

P (V = x

i

)

=

X

∀i

P (X = x

i

)· {log

2

P (X = x

i

) − log

2

P (V = x

i

)}

=

X

∀i

P (X = x

i

)·(I(V = x

i

) − I(X = x

i

))

W naszym przypadku :

D

KL

(P

X

, P

V

) ≈ 0.8·(1.58 − 0.32) + 0.1·(1.58 − 3.32)·2 = 0.66

Zauważmy, że zgodnie z właściwościami dywergencji Kulbacka-Leiblera wynik jest ­ 0.

Rozwiązanie 2:

Ilość informacji zawartą w wiadomości x

i

wyznaczamy jak w pierwszym rozwiązaniu. Z

kolei dywergencję Kulbacka-Leiblera można obliczyć inaczej, korzystając z faktu, że rozkład
prawdopodobieństw opisujący źródło V jest rozkładem równomiernym. W takim przypadku
można skorzystać ze wzoru, który był wyprowadzony na ćwiczeniach.

D

KL

(P

X

, P

V

) = H

MAX

− H(X)

gdzie entropia maksymalna dla źródła X równa entropii źródła V ,

H

MAX

= log

2

M = log

2

3 ≈ 1.58 [bit]

a entropia źródła X

H(X) =

3

X

i=1

P (X = x

i

)I(X = x

i

) ≈ 0.8·0.32 + 0.1·3.32·2 [bit] ≈ 0.92 [bit]

Stąd

D

KL

(P

X

, P

V

) ≈ 1.58 − 0.92 = 0.66

Zad. 2.

Stacjonarne

źródło

binarne

generuje

wiadomości

A=„alarm”

i

B=„brak

alarmu”.

Prawdopodobieństwo

pojawienia

się

wiadomości

o

alarmie

wynosi

P (X=A)=1/81.

Prawdopodobieństwo, utrzymania się stanu alarmowego (ponownego nadania wiadomości A) wynosi
1/5, a prawdopodobieństwo pojawienia się sytuacji alarmowej (nadania wiadomości A jeżeli poprzednio
była nadana wiadomość B) wynosi 1/100. Obliczyć entropię graniczną na symbol tego źródła oraz
sprawność kodera kodującego ciągi 3 kolejnych wiadomości tego źródła kodem o stałej długości.

Rozwiązanie:

Ponieważ źródło jest stacjonarne możemy zapisać w ogólności:

P (X

k

= A) = P (X = A) = 1/81

oraz

P (X

k

= B) = 1 − P (X

k

= A) = 80/81

Ponadto na podstawie z treści zadania możemy określić prawdopodobieństwa warunkowe:
przejść ze stanu alarmowego (nadawanie wiadomości A) albo stanu braku alarmu (nadawanie
wiadomości B) do innego stanu lub pozostania w tym samym stanie. Zauważymy, że
prawdopodobieństwo tego, że w k + 1 chwili wiadomość przyjmie określoną postać zależy od
tego jaką postać przyjęła poprzednia wiadomość, a nie zależy od wcześniejszych wiadomości.
Źródło to zatem można opisać łańcuchem Markowa pierwszego rzędu z następującymi
prawdopodobieństwami warunkowymi:

P (X

k+1

= A|X

k

= A) = 1/5,

P (X

k+1

= B|X

k

= A) = 4/5

P (X

k+1

= A|X

k

= B) = 1/100,

P (X

k+1

= B|X

k

= B) = 99/100

W przypadku stacjonarnego źródła dającego się opisać łańcuchem Markowa pierwszego rzędu
entropia graniczna na symbol H

∞

jest równa średniej entropii warunkowej bieżącego symbolu X

2

pod warunkiem, że znany jest symbol poprzedni X

1

.

H

∞

(X) = H(X

2

|X

1

) =

X

∀i

P (X

1

= x

i

)·H(X

2

|X

1

= x

i

)

gdzie entropia warunkowa symbolu X

2

pod warunkiem, że poprzedni symbol X

1

przyjął postać x

i

jest wyrażona wzorem:

H(X

2

|X

1

= x

i

) = −

X

∀j

P (X

2

= x

j

|X

1

= x

i

) log

2

(P (X

2

= x

j

|X

1

= x

i

))

W naszym przypadku:

H(X

2

|X

1

= A)

=

−P (X

2

= A|X

1

= A) log

2

(P (X

2

= A|X

1

= A)) +

−P (X

2

= B|X

1

= A) log

2

(P (X

2

= B|X

1

= A))

=

−

1

5

log

2

1

5

−

4

5

log

2

4

5

≈ 0.72 [bit]

oraz

H(X

2

|X

1

= B)

=

−P (X

2

= A|X

1

= B) log

2

(P (X

2

= A|X

1

= B)) +

−P (X

2

= B|X

1

= B) log

2

(P (X

2

= B|X

1

= B))

=

−

1

100

log

2

1

100

−

99

100

log

2

99

100

≈ 0.08 [bit]

stąd średnia entropia warunkowa

H(X

2

|X

1

)

=

P (X

1

= A)H(X

2

|X

1

= A) + P (X

1

= B)H(X

2

|X

1

= B)

≈

1

81

0.72 +

80

81

0.08 ≈ 0.088 [bit]

Czyli graniczna entropia na symbol rozpatrywanego źródła H

∞

(X) ≈ 0.088 [bit].

Sprawność kodera kodującego ciąg N kolejnych wiadomości źródła X jest zdefiniowana
następująco

η

N

=

H

N

(X)

R

N

gdzie H

N

(X) jest średnią entropią na symbol ciągu N kolejnych wiadomości źródła X, a R

N

jest średnią długością kodu na symbol, przy kodowaniu N kolejnych wiadomości źródła X.
Zauważmy, że

H

N

(X) =

1

N

H(X

1

, X

2

, . . . , X

N

)

(1)

gdzie łączną ciągu N kolejnych symboli można wyznaczyć ze wzoru

H(X

1

, X

2

, . . . , X

N

) = H(X

1

) + H(X

2

|X

1

) + . . . + H(X

N

|X

1

, X

2

, . . . , X

N −1

)

który w przypadku stacjonarnego źródła opisanego łańcuchem Markowa pierwszego rzędu
(dla którego H(X

N

|X

1

, X

2

, . . . , X

N −1

) = H(X

2

|X

1

)) można sprowadzić do postaci:

H(X

1

, X

2

, . . . , X

N

) = H(X

1

) + (N − 1)·H(X

2

|X

1

)

(2)

Średnia entropia warunkowa H(X

2

|X

1

) jest już obliczona, musimy zatem jeszcze obliczyć

entropię źródła H(X

1

) = H(X)

H(X

1

) = H(X) = −P (X = A)· log

2

P (X = A) − P (X = B)· log

2

P (X = B)

=

1

81

log

2

81 +

80

81

log

2

81

80

≈

1

81

6.34 +

80

81

0.018

= 0.096 [bit]

Podstawiając (2) do wzoru (1) możemy teraz wyznaczyć średnią entropię na symbol ciągu
trzech kolejnych wiadomości wynosi

H

3

(X) =

1

3

(H(X) + 2·H(X

2

|X

1

)) ≈

1

3

(0.096 + 2·0.088) ≈ 0.09 [bit/symbol]

Średnia długość kodu na symbol w przypadku źródła binarnego jest zawsze równa 1. Stąd
sprawność kodera o stałej długości kodu kodującego ciąg 3 kolejnych symboli wynosi

η

3

=

H

3

(X)

R

3

≈ 0.09 = 9%