dr inż. Marek Blok

2006-03-09 09:58:00 (2010-10-11 09:30:00) Nauka o Informacji – ćwiczenia Ćw.3b. Entropia źródła dyskretnego Zagadnienia: obliczanie entropii źródła dyskretnego, maksymalna entropia źródła Przypomnienie definicji entropii źródła dyskretnego.

H ( X ) = −∑ P( X = x )log P( X

x )

P( X

x ) I ( X

x )

i

2

= i = ∑

= i

= i

∀ i

i

Właściwości: H( X) ≥ 0

Maksymalna entropii źródła dyskretnego o M wiadomościach H

= log M

MAX

2

Zad. 1. Źródło dyskretne bezpamięciowe jako wiadomość nadaje sumę oczek z dwóch kolejnych rzutów kostką sześcienną.

a) obliczyć ilość informacji w poszczególnych wiadomościach (na początek: w najmniej i w najbardziej prawdopodobnej wiadomości) b) oblicz entropię tego źródła

Zad. 2. (bazuje ma zadaniu z poprzedniego ćwiczenia) Za pomocą kostki sześciennej losujemy liczbę od 1 do 6. Następnie losujemy drugą liczbę nie mniejszą od pierwszej wylosowanej liczby (rzucamy kostką sześcienną tak długo aż wypadnie liczba równa lub większa od pierwszej liczby).

Tak uzyskana (uporządkowana) para liczb stanowi wiadomość elementarną. Oblicz entropię tego źródła.

dodatkowo: tak jak w powyższym zadaniu ale dla wiadomości postaci ( i, j, k), gdzie i i j to wylosowane liczby, a k to liczba rzutów kostką, która była potrzebna do wylosowania tych liczb.

Zad. 3. Dla bezpamięciowego źródła binarnego wypełnij tabelkę p

0

1/32

0.11

1/4

1/2

3/4

0.89

31/32

1

I( X= ‘0’)

I( X= ‘1’)

H( X)

a następnie wykreśl entropię tego źródła w funkcji prawdopodobieństwa pojawienia się jednej z wiadomości.

Zad. 4. (bazuje na poprzednim zadaniu) Model binarnego źródła bezpamięciowego jest następujący: w urnie znajduje się 100 kul — 99 czarnych i jedna biała. Losujemy kulę i nadajemy jakiego jest ona koloru. Zwracamy kulę do urny mieszamy i powtarzamy losowanie.

a) obliczyć średnią ilość informacji (na wiadomość elementarną) w długim ciągu tak wygenerowanych wiadomości

b) jaka proporcja kul czarnych do białych zapewniłaby średnią ilość informacji ok. 0.5 bit (na wiadomość)?

Zad. 5. Wykazać, że H( X) ≤ log 2 K, gdzie K jest liczbą różnych wiadomości elementarnych jaką może wygenerować źródło X.

dr inż. Marek Blok

2006-03-09 09:58:00 (2010-10-11 09:30:00) Zad. 6. Oblicz entropię źródła, które jako wiadomość elementarną podaje liczbę rzutów niesymetryczną monetą potrzebnych do wyrzucenia ciągu samych orłów zakończonego wyrzuceniem reszki.

∞

k

x

podpowiedź: ∑ x k =

=

−

k

(

)2

1

1 x