Teoria informacji

i kodowanie

Ćwiczenia

20. lutego 2008 r.

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 prawdopodobne, 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)?

Zadanie 2

Jaką maksymalną nieokreśloność może zawierać fotografia 6 × 9 cm2, jeśli rozmiar ziarna jest równy 0 , 01 × 0 , 01 cm2, a każde ziarno może mieć trzy odcienie: biały, czarny i szary?

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.

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?

Zadanie 5

Pokaż, że dla niezależnych zmiennych losowych X, Y entropia łączna wynosi: H( X, Y ) = H( X) + H( Y ) .

Zadanie 6

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 7

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 ) Strona 1 z 2

Teoria informacji

i kodowanie

Ćwiczenia

20. lutego 2008 r.

Zadanie 8

Zmienna losowa X przebiega z takim samym prawdopodobieństwem wartości całkowitoliczbowe 1 , 2 , . . . , 2 N . 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 9

(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ść?

Zadanie 10

(*)

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

x − 1 ,

gdy x = 1

ln x =

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 pi, to entropia tego źródła charakteryzuje się następującą właściwością:

H( X) = H( p 1 , p 2 , . . . , pN ) ¬ lg N, przy czym równość zachodzi wtedy i tylko wtedy gdy ∀ipi = 1 .

N

Zadanie 11

(**)

Pokaż, że źródło informacji X generujące wiadomości x 0 , x 2 , . . . , xN zgodnie z rozkładem dwu-mianowym (rozkładem Bernoulliego), tj. dla 0 ¬ k ¬ N , 0 < p < 1 oraz q = 1 − p:

!

N

Pr {X = xi} =

piqN−i,

i

charakteryzuje się entropią:

H( X) ¬ −N ( p log2 p + q log2 q) .

Informacja dodatkowa:

Na kartkach z zadaniami do kolejnych kolokwiów znajdą Państwo następujące dane: 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 2 z 2