dr inż. Marek Blok 2009-11-06 09:34:00 (2010-10-22 12:02:00) Podstawy Systemów Informacyjnych – ćwiczenia Ćw.4b. Kodowanie źródła: kodowanie Huffmana i kodowanie Shannona-Fano.

Pojęcia:

• kod Huffmana

• kod Shannona-Fano Zad. 1. Dla zadanych rozkładów prawdopodobieństwa wyznacz kody Shannona-Fano oraz sprawność źródła, sprawność kodera, rozwlekłość resztkową. Następnie wyznacz kody Huffmana i porównaj je z kodami Shannona-Fano.

xi

P( xi)

xi

P( xi)

xi

P( xi)

A

0.2

A

0.10

A

0.10

B

0.1

B

0.25

B

0.18

C

0.3

C

0.30

C

0.40

D

0.4

D

0.25

D

0.05

E

0.10

E

0.06

F

0.10

G

0.07

H

0.04

Uwaga: Kodowanie Shannona-Fano oraz Huffmana dają identyczne wyniki poza ostatnim źródłem.

Odp. (1) śr. dług. kodu 1.9, H( X) = 1.85, (2) śr. dług. kodu 2.2, (3) śr. dług. kodu H 2.61, SH-F 2.64

Zad. 2. Dla podanych rozkładów częstości albo prawdopodobieństwa wyznacz sprawność źródła, a następnie spróbuj dla każdego z nich utworzyć jak najwięcej kodów Shannona-Fano o różnych strukturach. W kolejnym kroku wyznacz jak najwięcej optymalnych kodów Huffmana o różnych strukturach. Dla utworzonych kodów oblicz i porównaj sprawność kodera oraz rozwlekłość resztkową.

xi

P( xi)

xi

Li

xi

P( xi)

A

0.19

A

111

A

0.1

B

0.19

B

31

B

0.2

C

0.24

C

25

C

0.1

D

0.38

D

13

D

0.2

E

38

E

0.4

Podpowiedź: dla pierwszego i drugiego źródła istnieją dwa rozwiązania a dla trzeciego źródła istnieją aż trzy takie kody.

Uwaga: Kodowanie Shannona-Fano oraz Huffmana dają tutaj identyczne wyniki.