Studijní materiály

Zpět

Hromadně přidat materiály

TI - příklady

A0B01PSI - Pravděpodobnost, statistika a teorie informace

Hodnocení materiálu:

Vyučující: Ing. Tomáš Kroupa Ph.D.

Popisek: Řešené příklady od Tomáše Kroupy z teorie informace. Typovky do písemky.

Zjednodušená ukázka:

Stáhnout celý tento materiál

Tedy
H(X2jX1) =
2∑
i=0
pi(0) H(X2jX1 = i) = 25 H
(1
2;
1
2
)
= 25:
Maximální rychlost entropie markovského zdroje pro tento zdroj je maximum entropie na tříprv-
kové množině, neboť H(X2jX1) je konvexní kombinací podmíněných entropií na tříprvkových
množinách. V našem případě tedy log3 := 1:585.
Příklad 6. Huﬀmanův kód pro zdroj X:
f00;10;11;010;011g:
Ovšem jiný Huﬀmanův kód pro zdroj X dostaneme bitovou inverzí ve všech kódových slovech:
f11;01;00;101;100g:
Chceme ukázat, že Huﬀmanův kód s délkami kódových slov
2;2;2;3;3
je optimální i pro zdroj Y s rovnoměrnou pravděpodobnostní funkcí. Ten má entropii
H(Y ) = log5 := 2:32:
4
Střední délka uvažovaného Huﬀmanova kódu je pro tuto rovnoměrnou pravděpodobnostní funkci
3 2 15 + 2 3 15 = 125 :
Střední délka libovolného instantního kódu s délkami kódových slov ℓ1;:::;ℓ5 pro Y však musí
splňovat nerovnost
1
5
5∑
i=1
ℓi H(Y );
čemuž vyhovuje každý instantní kód, jehož délky kódových slov splňují
5∑
i=1
ℓi 12:
Jelikož je součet délek slov Huﬀmanova kódu pro X právě 12, je tento kód optimální i pro zdroj Y .
Příklad 7. a) Uvedený kód je optimální, neboť je instantní a délky ℓi jeho kódových slov splňují
ℓi = log2 ni; ni 2 N
přičemž
4∑
i=1
2 ni = 1:
Volbou n1 = 1, n2 = 2, n3 = n4 = 3 tak dostaneme optimání kód pro informační zdroj popsaný
pravděpodobnostmi (
1
2;
1
4;
1
8;
1
8
)
:
Uvedený kód je ovšem Huﬀmanův (a tudíž optimální) i např. pro zdroj popsaný pravděpodob-
nostmi (1
2;
3
8;
1
16;
1
16
)
:
b) Výsledný kód nemůže být jednoznačně dekódovatelný, neboť délky jeho kódových slov nesplňují
Kraftovu nerovnost:
2 1 + 2 2 2 + 2 3 ≰ 1:
Příklad 8. Pro délky kódových slov
3;4;4;4;4;5
ověříme Kraftovu nerovnost:
2 3 + 4 2 4 + 2 5 = 1332 < 1:
Tedy existuje jednoznačně dekódovatelný binární kód s takto zadaným délkami kódových slov,
je to např. kód zadaný tabulkou 1.
Ovšem kód C jednoznačně dekódovatelný není, neboť zprávy cd a af jsou zakódovány shodně.
Příklad 9. Určíme entropie p a q:
H(p) = 1:875;
H(q) = 2:
5
a 000
b 0010
c 0011
d 0100
e 0101
f 01100
Tabulka 1: Jednoznačně dekódovatelný kód
Avšak střední délka kódu C1 je 1:875, střední délka kódu C2 je 2: oba kódy jsou optimální.
Střední délka Lq(C1) kódu C1 použitého na zdroj s pravděpodobnostní funkcí q je
1
2 + (2 + 3)
1
8 + 2 4
1
8 = 2:125:
Kód C1 tedy není pro q optimální: za nevhodné kódování zaplatíme chybou o velikosti rozdílu
Lq(C1) H(q) = 0:125;
což je právě hodnota informační divergence D(qjjp).
Reference
[1] J. Adámek. Stochastické procesy a teorie informace - úlohy. Vydavatelství ČVUT, 1989.
[2] T. M. Cover and J. A. Thomas. Elements of information theory. Wiley-Interscience [John
Wiley & Sons], Hoboken, NJ, second edition, 2006.
6

Stáhnout celý tento materiál

Předchozí

1 2 3

Vloženo: 28.01.2011

Velikost: 63,78 kB

Stáhnout celý tento materiál

Komentáře

Tento materiál neobsahuje žádné komentáře.

Mohlo by tě zajímat:

Skupina předmětu A0B01PSI - Pravděpodobnost, statistika a teorie informace
Reference vyučujících předmětu A0B01PSI - Pravděpodobnost, statistika a teorie informace
Reference vyučujícího Ing. Tomáš Kroupa Ph.D.

Podobné materiály