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.