Zad. 1. Dyskretne źródło wiadomości opisane jest rozkładem prawdopodobieństwa podanym w tabelce.

Obliczyć ilość informacji zawartej w każdej z wiadomości oraz rozwlekłość tego źródła.

x

i

a

b

c

d

e

f

g

h

P (X = x

i

)

0.05

0.05

0.1

0.3

0.3

0.1

0.05

0.05

Rozwiązanie:

Ilość informacji zawartą w wiadomości x

i

wyznaczamy wg wzoru:

I(X = x

i

) = − log

2

(P (X = x

i

))

W naszym przypadku mamy trzy grupy wiadomości charakteryzujące się tym, że wszystkie
wiadomości w grupie cechuje to samo prawdopodobieństwo wystąpienia: X

1

= {a, b, g, h},

X

2

= {c, f } i X

3

= {d, e}. Zatem

I

1

= I(X = a) = I(X = b) = I(X = g) = I(X = h) = − log

2

0.05 = −ln 0.05/ln 2 ≈

4.32 [bit]

I

2

= I(X = c) = I(X = f ) = − log

2

0.1 = I

1

− 1 ≈ 3.32 [bit]

Zauważmy, że wiadomość c jest dwa razy bardziej prawdopodobna niż

wiadomości a, stąd zawiera ona dokładnie o jeden bit informacji mniej.

I

3

= I(X = d) = I(X = e) = − log

2

0.3 ≈ 1.74 [bit]

Entropię, czyli średnią ilość informacji zawartą w wiadomości wyznaczamy wg wzoru:

H(X) = E I(X = x

i

) =

X

∀i

P (X = x

i

)I(X = x

i

)

W naszym przypadku powyższy zapis możemy sprowadzić do postaci:

H(X) = 4·0.05·I

1

+ 2·0.1·I

2

+ 2·0.3·I

3

≈ 2.57 [bit]

Pozostało teraz policzyć rozwlekłość rozpatrywanego źródła wg wzoru

ζ =

H

M AX

− H(X)

H

M AX

= 1 −

H(X)

H

M AX

gdzie H

M AX

jest maksymalną entropią jaką może charakteryzować się źródło nadające M

różnych wiadomości (w naszym przypadku M =8)

H

M AX

= log

2

M = log

2

8 = 3 [bit]

Stąd ostatecznie rozwlekłość źródła wynosi

ζ ≈ 1 −

2.57

3

≈ 1 − 0.86 = 0.14 = 14%

Zad. 2.

Stacjonarne

binarne

źródło

wiadomości

jest

opisane

prawdopodobieństwem P (X

1

= 0) = 1/8 oraz grafem przedstawiony

obok. Obliczyć entropię graniczną na symbol oraz średnią entropię na
symbol ciągu 3 kolejnych wiadomości tego źródła.

Rozwiązanie:

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

P (X

k

= 0) = P (X

0

= 0) = 1/8

oraz

P (X

k

= 1) = 1 − P (X

k

= 0) = 7/8

Na podstawie grafu możemy dodatkowo określić prawdopodobieństwa przejść, ze stanu
nadawania jednego symbolu (np. „0”) do stanu nadawania innego symbolu lub pozostania w
stanie nadawania tego samego symbolu. Zauważymy, że prawdopodobieństwo tego, że k + 1
symbol przyjmie określoną postać zależy od tego jaką postać przyjął poprzedni symbol ale
nie zależy od wcześniejszych symboli.

Rozpatrywane źródło można zatem opisać za pomocą łańcucha Markowa pierwszego rzędu z
następującymi prawdopodobieństwami warunkowymi:

P (X

k+1

= 0|X

k

= 0) = 0.2,

P (X

k+1

= 1|X

k

= 0) = 0.8

P (X

k+1

= 1|X

k

= 1) = 0.9,

P (X

k+1

= 0|X

k

= 1) = 0.1

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

= 0) =

−P (X

2

= 0|X

1

= 0) log

2

(P (X

2

= 0|X

1

= 0)) +

−P (X

2

= 1|X

1

= 0) log

2

(P (X

2

= 1|X

1

= 0))

=

−0.2· log

2

(0.2) − 0.8· log

2

(0.8) ≈ 0.72 [bit]

oraz

H(X

2

|X

1

= 1) =

−P (X

2

= 0|X

1

= 1) log

2

(P (X

2

= 0|X

1

= 1)) +

−P (X

2

= 1|X

1

= 1) log

2

(P (X

2

= 1|X

1

= 1))

=

−0.1· log

2

(0.1) − 0.9· log

2

(0.9) ≈ 0.47 [bit]

stąd średnia entropia warunkowa

H(X

2

|X

1

) =

P (X

1

= 0)H(X

2

|X

1

= 0) + P (X

1

= 1)H(X

2

|X

1

= 1)

≈ 1/8·0.72 + 7/8·0.47 ≈ 0.5 [bit]

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

∞

(X) ≈ 0.5 [bit].

Pozostaje jeszcze wyznaczyć średnią entropię na symbol ciągu trzech kolejnych symboli. W ogólnym
przypadku średnia entropia na symbol ciągu N kolejnych symboli wyrażona jest wzorem

H

N

(X) =

1

N

H(X

1

, X

2

, . . . , X

N

)

gdzie łączną entropię 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 źródła opisanego łańcuchem Markowa pierwszego rzędu (dla którego
H(X

N

|X

1

, X

2

, . . . , X

N −1

) = H(X2|X

1

)) można sprowadzić do postaci:

H(X

1

, X

2

, . . . , X

N

) = H(X

1

) + (N − 1)·H(X

2

|X

1

)

Ś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 = 0)· log

2

P (X = 0) − P (X = 1)· log

2

P (X = 1)

=

1/8· log

2

8 + 7/8· log

2

8/7 ≈ 1/8·3 + 7/8·0.19

≈ 0.54 [bit]

Podsumowując średnia entropia 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.54 + 2·0.5) ≈ 0.51 [bit/symbol]