dr inż. Marek Blok

2009-11-06 12:32:00 (2010-11-04 20:16:00)

Podstawy Systemów Informacyjnych – ćwiczenia

Ćw.5. Kodowanie grupy wiadomości. Entropia warunkowa, łączna i graniczna na symbol

Zagadnienia: wpływ wiedzy „a priori” na ilość informacji, entropia warunkowa, entropia łączna, entropia graniczna na symbol, efekty kodowania przy łączeniu wiadomości w grupy.

Entropia łączna dwóch kolejnych symboli

H ( X , X )

1

2

= −∑∑ P( X 1 = x , X

x ) log P( X

x , X

x )

i

2 =

j

2

1 =

i

2 =

j

∀ i ∀ j

Entropia warunkowa symbolu X2 przy warunku, że X1= xi

H ( X | X

2

1 = x )

P( X

x | X

x ) log P( X

x | X

x )

i

= −∑

2 =

j

1 =

i

2

2 =

j

1 =

i

∀ j

Średnia entropia warunkowa

H ( X | X )

2

1

= ∑ P( X 1 = x ) H ( X | X

x )

P( X

x , X

x ) log P( X

x | X

x )

i

2

1 =

i

= −∑∑

1 =

i

2 =

j

2

2 =

j

1 =

i

∀ i

∀ i ∀ j

Właściwości

H ( X , X ) = H ( X ) + H ( X | X ) 1

2

1

2

1

H ( X | X ) = H ( X ) , gdy X

2

1

2

1 i X 2 są niezależne

H ( X , X ) ≤ H ( X ) + H ( X ) 1

2

1

2

H ( X | X ) ≤ H ( X ) = H ( X ) 2

1

2

Entropia łączna ciągu N symboli X1, X2, ..., XN

H ( X , X ,K, X )

H ( X )

H ( X | X ) K H ( X

| X , X ,K, X

)

1

2

N

=

1

+

2

1

+ +

N

1

2

N −1

N

=

∑ H ( X | X , X ,K, X ) n

1

2

n−1

n=1

tutaj H ( X | X ) = H ( X ) 1

0

1

Entropia na symbol dla ciągu N kolejnych symboli 1

H ( X )

H ( X , X ,K

=

, X )

N

1

2

N

N

Entropia na symbol graniczna

1

H ( X ) = lim H ( X ) = lim H ( X , X ,K, X )

∞

N

1

2

N

N →∞

N →∞ N

H ( X ) = lim H ( X | X , X ,K, X

)

∞

, Gallager (1968)

N

1

2

N 1

−

N →∞

Zad. 1. Dyskretne źródło generuje wiadomości o wyniku N rzutów symetryczną monetą. Obliczyć ilość informacji w wiadomości, że N razy wypadł orzeł oraz ilość informacji w tej samej wiadomości, ale gdy wiemy, że w N- K pierwszych rzutach wypadł orzeł.

(można komplikować: np. na N rzutów k razy wypadł orzeł oraz dla niesymetrycznej monety) Zad. 2. Binarne źródło generuje wiadomość 0 z prawdopodobieństwem p = 10/11. Wyznaczyć entropie łączną ciągu 2, 3 oraz 4 kolejnych symboli wygenerowanych przez to źródło. Wyznaczyć ponadto średnią entropię na symbol ciągu 2, 3 i 4 kolejnych symboli oraz graniczną entropię na symbol.

dr inż. Marek Blok

2009-11-06 12:32:00 (2010-11-04 20:16:00)

Odp. H( X) = 0.4395

Zad. 3. Jak zmienią się wyniki z poprzedniego zadania jeżeli źródło jest dodatkowo opisane następującymi

prawdopodobieństwami

warunkowymi:

P( Xk+1 = 0 | Xk = 0) = 0.99

oraz

P( Xk+1 = 0 | Xk = 1) = 0.1? Jak duże grupy wiadomości należy kodować razem, żeby mieć pewność, że średnia długość kodu na wiadomość byłą nie mniejsza niż (a) 0.4 [bit/wiad.], (b) 0.2 [bit/wiad.]?

Odp. H∞( X) = H( X 2 | X 1) = 0.1161 , H 1( X) = 0.4395, H 2( X) = 0.2778, H 3( X) = 0.2239.

l 1 = 1, R 1 = 1; l 2 = 1.11(81), R 2 = 0.559(09) ; l 3 = 1.1984, R 2 = 0.3995

Kodowanie ciągu symboli źródła opisanego łańcuchem Markowa zerowego rzędu.

Zad. 4. Binarne źródło wiadomości generuje ciąg symboli niezależnych {‘A’, ‘B’}.

Prawdopodobieństwo, że źródło wygeneruje wiadomość A wynosi 0.1. Stosując kodowanie Huffmana utworzyć kod zapewniający średnią długość kodu na wiadomość nie większą niż 0.6

[bit].

Podpowiedź: zaprojektuj kody Huffmana dla N = 1, 2 i 3. Sprawdź średnie długości tych kodów i odnieś je do twierdzenia Shannona o kodowaniu źródłowym.

Odp.

N = 1 ==> R1 = 1, H1(X) = 0.469, eta1 = 0.469

N = 2 ==> R2 = 0.645, H2(X) = 0.469, eta2 = 0.727

N = 3 ==> R3 = 0.533, H2(X) = 0.469, eta2 = 0.881

Kodowanie ciągu symboli źródła opisanego łańcuchem Markowa I rzędu.

Zad. 5. Źródło wiadomości generuje ciąg symboli {‘A’, ‘B’, ‘C’, ‘D’} z rozkładem podanym w poniższej tabeli. Utwórz kod Huffmana dla tego źródła i określ sprawność tego kodera.

xi

P( xi)

A

1/2

B

1/4

C

1/8

D

1/8

Odp. R 1 = 1.75, H( X) = 1.75, eta1 = 100%

Czy można dla tego źródła uzyskać koder, który zapewni średnią długość kodu na symbol równą 1?

Co jeśli dodatkowo wiemy, że

po symbolu ‘A’ możliwe jest nadanie jedynie symbolu ‘A’ albo ‘B’

po symbolu ‘B’ możliwe jest nadanie jedynie symbolu ‘B’ albo ‘C’

po symbolu ‘C’ możliwe jest nadanie jedynie symbolu ‘C’ albo ‘D’

po symbolu ‘D’ możliwe jest nadanie jedynie symbolu ‘D’ albo ‘A’

a prawdopodobieństwa nadania tego samego symbolu są następujące xi

P( X 2 = xi| X 1 = xi)

A

7/8

B

3/4

C

1/2

D

1/2

co odpowiada poniższemu grafowi

dr inż. Marek Blok

2009-11-06 12:32:00 (2010-11-04 20:16:00)

7/8

3/4

A

B

D

C

1/2

1/2

Odp. H( X 2 | X 1) = 0.725, H( X 1, X 2) = 1.237, R 2 = 1.25, H( X) = 1.75, eta2 = 98.98%