Teoria informacji i kodowanie

Ćwiczenia

Sem. letni 2011/2012

Wstęp do teorii informacji: informacja, niepewność, entropia

Zadanie 1

Która z poniższych sekwencji niesie większą informację:

1. 10 liter alfabetu łacińskiego (zakładamy, że wystąpienie każdej z 32 liter jest równie praw-

dopodobne, nie interesuje nas rozróżnienie między wielkimi a małymi literami),

2. 32 cyfry (zakładamy, że wystąpienie każdej z dziesięciu cyfr jest równoprawdopodobne)?

(Odp. Sekwencja cyfr niesie o ok. 56

bitów

/

sekwencję

więcej)

Zadanie 2

Jaką maksymalną nieokreśloność może zawierać fotografia 6 × 9 cm

2

, jeśli rozmiar ziarna jest

równy 0, 01 × 0, 01 cm

2

, a każde ziarno może mieć trzy odcienie: biały, czarny i szary? (Odp.

Ok. 855 880

bitów

/

fotografię

)

Zadanie 3

Źródło generuje wiadomości według następującego schematu:

1. losowane są 0 oraz 1 (odpowiednio z prawdopodobieństwem p

0

= p, p

1

= 1 − p);

2. losowanie kończy się w chwili wylosowania pierwszej jedynki;

3. źródło wysyła informację, za którym razem to nastąpiło.

Znajdź entropię takiego źródła. (Odp.

p lg

1

p(1−p)1−p

1−p

)

Zadanie 4

(kolokwium z lat poprzednich)

Źródło Z jest zdefiniowane w sposób następujący:

1. mamy dwa źródła X i Y o entropiach odpowiednio H(X) i H(Y );

2. wiadomości generowane przez te źródła nie pokrywają się (np. jedno generuje litery, a

drugie — cyfry);

3. ze źródła Z wysyłamy informację na tej zasadzie, że z prawdopodobieństwem p podajemy

na jego wyjście wiadomość ze źródła X, a z prawdopodobieństwem (1 − p) — wiadomość
ze źródła Y .

Jaka jest entropia Z? (Odp.

H(Z) = pH(X) + (1 − p)H(Y ))

Zadanie 5

Używając właściwości logarytmu naturalnego:

ln x =

x − 1,

gdy x = 1

y < x − 1,

gdy x 6= 1

udowodnij następujące twierdzenie: Jeśli źródło generuje N ­ 1 wiadomości (1, . . . , N ), każdą z
prawdopodobieństwem odpowiednio p

i

, to entropia tego źródła charakteryzuje się następującą

właściwością:

H(X) = H (p

1

, p

2

, . . . , p

N

) ¬ lg N,

przy czym równość zachodzi wtedy i tylko wtedy gdy ∀

i

p

i

=

1

N

.

Strona 1 z 3

Teoria informacji i kodowanie

Ćwiczenia

Sem. letni 2011/2012

Zadanie 6

Pokaż, że źródło informacji X generujące wiadomości x

0

, x

2

, . . . , x

N

zgodnie z rozkładem dwu-

mianowym (rozkładem Bernoulliego), tj. dla 0 ¬ k ¬ N , 0 < p < 1 oraz q = 1 − p:

Pr{X = x

i

} =

N

i

!

p

i

q

N −i

,

charakteryzuje się entropią:

H(X) ¬ −N (p log

2

p + q log

2

q).

Zadanie 7

Pokaż, że dla niezależnych zmiennych losowych X, Y entropia łączna wynosi:

H(X, Y ) = H(X) + H(Y ).

Zadanie 8

Dla połączonych doświadczeń X i Y entropia warunkowa H(Y |X) jest definiowana jako wartość
średnia entropii Y pod warunkiem znanej realizacji zmiennej X. Wyprowadź wzór na entropię
warunkową oraz udowodnij następującą właściwość (reguła łańcuchowa):

H(X, Y ) = H(X) + H(Y |X).

Zadanie 9

Udowodnij że dla informacji wzajemnej (transinformacji ) zachodzą poniższe tożsamości:

I(X; Y ) = I(Y ; X)

= H(X) − H(X|Y )

= H(Y ) − H(Y |X)

= H(X) + H(Y ) − H(X, Y )

Zadanie 10

Zmienna losowa X przebiega z takim samym prawdopodobieństwem wartości całkowitoliczbowe
1, 2, . . . , 2N . Zmienna losowa Y jest zdefiniowana jako równa 0, gdy wartość X jest parzysta,
natomiast Y = 1, gdy wartość X jest nieparzysta. Udowodnij, że w takim przypadku zachodzi
następująca zależność dla entropii warunkowej :

H(X|Y ) = H(X) − 1.

Następnie pokaż, że zachodzi również:

H(Y |X) = 0.

Zadanie 11

(kolokwium z lat poprzednich)

Emitowanie wiadomości ze źródeł W i F jest wzajemnie zależne statystycznie. Wiadomo,
że entropia pierwszego z nich wynosi osiem bitów, a drugiego — 12 bitów. Narysuj wykres
H(W|F ) = f (H(F |W)), tj. zależności H(W|F ) jako funkcji zmian H(F |W) od wartości mi-
nimalnej do maksymalnej.

Strona 2 z 3

Teoria informacji i kodowanie

Ćwiczenia

Sem. letni 2011/2012

Zadanie 12

(kolokwium z lat poprzednich)

Nasz kolega wykonuje w ukryciu trzy rzuty niesfałszowaną monetą, po czym mówi nam, ile
w sumie wypadło orłów. Jaka jest nasza niepewność na temat wyniku pierwszego rzutu po
uzyskaniu takiej informacji? (Odp. Ok. 0,44 bit.)

Zadanie 13

(kolokwium z lat poprzednich)

Dana jest dyskretna zmienna losowa X. Inna zmienna losowa zdefiniowana jest przez funkcję:

Y = g(X),

gdzie g(·) jest dowolną funkcją. Jaka zależność ogólna zachodzi między H(Y ) i H(X):

H(Y ) ¬ H(X),

H(Y ) ­ H(X)?

Przy jakich warunkach nałożonych na funkcję g(·) zachodzi równość?

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