Példamegoldás: InfElm 2x45percben

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

thx to Soos Balazs (B.Joe)

Györfi László- Győri Sándor - Vajda István: Információ- és kódelmélet,
Második bővített kiadás (TypoTex Kiadó, 2002): oldalszámok: 54-59

1.4 (Rossz kódok)

A következő bináris kódok melyike nem lehet semmilyen eloszlás Huffmann-kódja? Mindegyik válaszát indokolja meg, azaz ha nincs ilyen eloszlás, akkor magyarázza meg miért, ha pedig van, akkor adjon meg egy olyat!

a) 0, 10, 111, 101

mo.: nem lehet, mert 10,101 nem prefix

b) 00, 010, 011, 10, 110

mo.: nem lehet, mert ha ábrázoljuk a fát, akkor az 110 kód feleslegesen hosszú, hisz 11 is elég lenne helyette -> ez a kód nem lehet optimális, nem huffman-kód.

c) 1, 000, 001, 010, 011

mo.: OK Pl.: 1/2, 1/8, 1/8, 1/8, 1/8

1.6

Legyen az X={x₁, ..., x_n} forrásábécé ötelemű, a következő valószínűségekkel: 0.4; 0.35; 0.1; 0.1; 0.05 Mennyi az eloszlás entrópiaja?
Konstruálja meg a bináris Shannon-Fano-kódot erre az eloszlásra, illetve konstruáljon bináris prefix kódot az li = felkerekít[-logp(xi)] kódszóhosszakkal az 1.2. lemma bizonyítása szerint (a kód bináris fával való reprezentálásával).
Mennyi az átlagos kódszóhossz?

Bináris Shannon-Fano kódok

Először csökkenő sorba rendezzük a valószínüségeket.
mo.:
[math] p_{1} = 0.4 [/math]
[math] p_{2} = 0.35 [/math]
[math] p_{3} = 0.1 [/math]
[math] p_{4} = 0.1 [/math]
[math] p_{5} = 0.05 [/math]

[math] w_{1}:= 0 [/math]

[math]w_{i}:= \sum\limits_{n=1}^{i-1} p_{i}[/math]

azaz

[math] w_{1} = 0 [/math]
[math] w_{2} = 0,4 [/math]
[math] w_{3} = 0,75 [/math]
[math] w_{4} = 0,85 [/math]
[math] w_{5} = 0,95 [/math]

A bináris Shannon-Fano kódok:

		  .5	.25  .125	.0625
w1=0	 0  +  0
w2=0.4  0  +  1
w3=0.75 1  +  1  +  0  +  0
w4=0.85 1  +  1  +  0  +  1
w5=0.95 1  +  1  +  1

Ezek prefix kódok. Mindegyik annyi bitből áll, amennyi már megkülönbözteti a többitől.
Ezeket felírjuk 2-es számrendszerben.

Entrópia

[math]H = -\sum\limits_{n=1}^{5}(p_{i} \cdot \log(p_i))=...= 1.94[/math]

Átlagos kódszóhossz

[math]E|f(x)|= +\sum\limits_{n=1}^{5} p_{i} \cdot l_{i} = 2.45[/math]

Bináris prefix kód l_i alapján

[math]l_{i}=\lceil -\log(p_{i})\rceil=\{2,2,4,4,5\}[/math]

[math] w_{1} = 0 [/math]
[math] w_{2} = 1 [/math]
[math] w_{3} = 8 [/math]
[math] w_{4} = 9 [/math]
[math] w_{5} = 20 [/math]

  
  / \ 
 /\ /\
	/  \	  
  /\	\
		  \

Eredeti megoldás, ami szerintem rossz: Tehát a kódok: 00, 01, 1000, 1001, 11111.
Nekem jónak tűnő megoldás: 00, 01, 1000, 1001, 10100.
Aki biztos a dolgában, javítson!
-- Yaman - 2005.12.01.
Rohadtul tök mindegy. :) A lényeg, hogy 5 hosszú legyen az utolsó kód. Ennyi. Ha fán tudod ábrázolni, akkor prefix is.
-- Đani - 2005.12.01.
Szerintem azért nem mindegy, mert az 1.2 lemma bizonyítása szerint kéri a kódot, akkor pedig szerintem w₅-re 10100 lesz a kód.
-- Yaman - 2005.12.01.
Hehe, ha te mondod. Átnéztem azt a bizonyítást, mondjuk nem olyan nagyon-nagyon, de számomra nem derült ki, hogy miért az 10100 lesz a nyerő megoldás. Persze ez csak engem minősít...
-- Đani - 2005.12.01.
10100 a jó kód (és nem írom ide, hogy szerintem), mert w₅=20-nak a kettesszámrendszerbeli alakja ennyi (és nem 11111).
-- Tomee

[math]E(f(x))= 2 \cdot 0,4 + 2 \cdot 0,35 + 2\cdot 4 \cdot 0,1 + 5 \cdot 0,05 = 0,8 + 0,7 + 0,8 + 0,25 = 2,55[/math]

1.7

Egy pénzérmét addig dobunk fel, amíg írást nem kapunk. Jelölje az X valószínűségi változó a dobások számát. Mennyi az X entrópiája?

Entrópia

mo.:
[math]H(x)=-\sum\limits_{n=1}^{\infty} p_{i} \cdot \log p_{i} = - \sum\limits_{n=1}^{\infty} (0,5^{i} \cdot \log(0,5)^{i})= + \sum\limits_{n=1}^{\infty} i \cdot (0,5)^{i} = \frac{1}{1-0.5} = 2 [/math]
Az entrópia igy 2.

  /\
 /\ elsore bejott
/  masodikra jott csak be
..

1.8 (Egyenletes eloszlás entropiája nagyobb)

Mutassa meg, hogy a (p₁, ..., p_i, ..., p_j, ..., p_n) eloszlás entrópiája nem lehet nagyobb, mint a (p₁, ..., p_i/2+p_j/2, ..., p_i/2+p_j/2, ..., p_n)

p1	...	pi	...	pj	...	pn
p1	...	pi/2+pj/2	...	pi/2+pj/2	...	pn

[math]-\sum\limits_{i=1}^{n}p_{i} \cdot \log p_{i} \lt = -\sum\limits_{i=1}^{n} q_{i} \cdot \log q_{i}[/math]

mo.:
[math] H(P): \{p_{1}, \dots, p_{i}, \dots, p_{j}, \dots, p_{n}\} [/math]
[math] H(Q): \{p1, \dots, \frac{p_{i} + p_{j}}{2}, \dots, \frac{p_{i} + p_{j}}{2}, \dots, p_{n}\} [/math]

[math] H(P) = -p_{1} \cdot \log p_{1} - \dots - p_{i} \cdot \log p_{i} - \dots - p_{j} \cdot \log p_{j} - \cdot - p_{n} \cdot \log p_{n} [/math]
[math] H(Q) = -p_{1} \cdot \log p_{1} - \dots - \frac{p_{i} + p_{j}}{2} \log\frac{p_{i} + p_{j}}{2} - \dots - \frac{p_{i} + p_{j}}{2} \log\frac{p_{i} + p_{j}}{2} - \dots - p_{n} \cdot \log p_{n} [/math]

Kell: [math]H(Q)-H(P) \gt = 0[/math]

[math]-2 \cdot \frac{p_{i} + p_{j}}{2} \cdot \log\frac{p_{i} + p_{j}}{2} + p_{i} \cdot \log p_{i} + p_{j} \cdot \log p_{j} \gt = 0[/math]
... balra-jobbra teszegetve, (-1)gyel megszorozva-megkeverve :) kijön, hogy:
[math] p_{i} \cdot \log \frac{1}{p_{i}} + p_{j} \cdot \log \frac{1}{p_{j}} \lt = (p_{i} + p_{j}) \cdot \log\frac{2}{p_{i} + p_{j}}[/math]

Jensen egyenlőtlenségből következik az állítás:
felhasználva, hogy:
a = p_i + p_j (a₁ = p_i, a₂ = pj) és b = 2 (b₁ = 1, b₂ = 1).

1.10 (Információs divergencia)

Definicó alkalmazásával egyértelmű a megoldás...

1.13 (Huffman-kód kószóhosszai)

Tegyük fel, hogy a (p₁, ..., p_n) eloszláshoz készítünk optimális bináris prefix kódot, ahol p₁ > p₂ > ... > p_n > 0. Bizonyítsa be, hogy
a) ha p₁ > 2/5, akkor a hozzá tartozó kódszó 1 hosszúságú
b) ha p₁ < 1/3, akkor a hozzá tartozó kódszó legalább 2 hosszú

mo.: ???
annyit tudok, hogy {1 2 3 3} vagy {2 2 2 2} Hosszúságok mindegyik egy optimális Huffmankodot ad.

Én itt arra jöttem rá, hogyha p1 = 0.4, akkor pont meg lehet csinálni, hogy az utolsó összeadásnál ezt adjuk hozzá valami máshoz, így a hozzá tartozó kódszó kettő hosszú lesz. Viszont ha ennél nagyobb, mondjuk 0.41, akkor ahhoz, hogy őt adjuk hozzá valamihez, az kell, hogy az előző összadás során kapott eredmény nála nagyobb legyen. Példának okáért 0.42. Ekkor a maradék valószínűség 0.17. Ezt adnánk hozzá a 0.41-hez. Azonban ez a helyzet nem állhat elő, mert a 0.42-t csak úgy kaphattuk meg, ha az egyik valószínűség legalább 0.21 volt. Nem kaphatjuk meg úgy a 0.42-t, hogy mindkét valószínűség kisebb, mint 0.17, ezért ezt vettük volna az összeadás egyik tagjának.
Nem tudom, hogy érthető volt-e, remélem igen.
A b) részhez ugyanilyen megfontolás szükséges. Ha p1 = 1/3-ad, akkor az utolsó összeadásnál előfordulhat olyan helyzet, hogy 3 1/3-ad valószínűségű elem közül kell választanunk. Tehát ekkor még megoldható, hogy p1-hez 1 hosszú kódszó tartozzon. Ám ha p1 < 1/3, mondjuk 0.3, akkor az utolsó előtti összeadásban szükségszerűen kapunk egy nála nagyobb eredményt, viszont a harmadik tag szükségszerűen kevesebb lesz nála. Így muszáj őket összeadnunk.
Na, ez még zavarosabb volt. :)
-- Đani - 2005.11.27.

a) p₁ > p₂ > ... > p_m > 0 (*) Teljes indukcióval bizonyítunk. n = 1, 2, 3-ra arcpirítóan triviális. Légyen igaz n-ig, hogy ha p₁ > 2/5, akkor a hozzá tartozó kódszó 1 hosszúságú n+1-re p1,p2,....,p(n), p(n+1) A két legkisebb p(n) és p(n+1) (ld. *). Innen két eset van.

 1. Az új, p1,p2,....,p(n-2),p(n)+p(n+1)-ben továbbra is p1 a legnagyobb.Ekkor visszavezettük n-re, azaz az indukciós feltevés miatt  igaz, hogy ha p1>2/5, akkor a hozzá tartozó kódszó 1 hosszú.

 2. Nem p1 a legnagyobb. Ekkor láthatóan p(n)+p(n+1) lenne a legnagyobb. De p(n)+p(n+1)<2*(1-2/5)/n<2*(3/5)/3=2/5. Tehát 2. eset nem is lehet.

Ezzel az állítást béláttuk.

b) n=1,2,3 nem lehet, mert p1 szigorúan a legnagyobb. n=4-re igaz, p1<1/3 és p1>p2>p3>p4 -> p3+p3+p4>2/3 -> p1+p2<2/3 -> p3+p4>1/3 ezek plusz 1.5 tétel -> optimális bináris prefix kód {2,2,2,2} hosszú.

Innen ismét indukció, stb...

-- GelencserGabor - 2005.12.01.

1.14 (Titkosítás)

Legyenek X és Z bináris független valószínűségi változók úgy, hogy P{X=1}=p és P{Z=1}=0.5 Legyen Y=X mod2 Z X felfogható, mint titkosítandó üzenet, Z a titkos kulcs és Y a rejtjelezett üzenet. Számítsa ki a következő mennyiségeket és magyarázza meg jelentésüket a titkosítás szempontjából:
mo.:
[math] H(X) = -p \cdot \log p - (1-p) \cdot \log(1-p) = h(p)[/math]
[math] H(X|Z) = H(X) = h(p)[/math], mert X, és Z független
[math] H(X|Y,Z) = H(f(Y,Z)|Y,Z) = 0[/math], mert X függ Y, és Z-től
[math] H(X|Y) = [/math]

			X  Z  Y
(1-p)/2  0  0  0
  p/2	 1  0  1	==>	 p(Y=0)=.5	p(Y=1)=.5	fuggetlen mindentol
(1-p)/2  0  1  1
  p/2	 1  1  0

[math]H(X|Y) = H(X) = h(p)[/math]

1.17 (Futamhossz kódolás)

Legyenek X₁, ..., X_n bináris valószínűségi változók. Jelölje R = (R₁, R₂, ...) az egyes szimbólumok előfordulásainak futamhosszait. Tehát pl. az 1110010001111 sorozathoz R=(3,2,1,3,4) tartozik. Hogyan viszonyul egymáshoz H(X₁, ..., X_n), H(R) és H(R, X_n)?

mo.:
X=(x1,...xn)
R=(R1,R2,...)
X=00101110 ==> R={3 2 2 3 1}

R=f(x1,...xn)
H(x)>=H(f(x)) Megj.: ha f() invertálható akkor pont =
H(x1,...xn)>=H(R), mert nem tudjuk mivel kezdődik a kód 0/1 ?
H(x1,...xn)>=H(R,Xn)

1.18 (Markov-lánc entrópiája)

Legyen XX (<-duppla_vastagX) =X1,X2,... egy bináris, stacionárius Markov-lánc, amelynek állapotátmenetei a következők:
P(X2=0|X1=0} = p,
P(X2=1|X1=0} = 1-p,
P(X2=0|X1=1} = (1-p)/2,
P(X2=1|X1=1} = (1+p)/2
Mennyi P(X1=0)=? Mennyi a forrás entropiája?

mo.:

Ezen a helyen volt linkelve a 1_18.JPG nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

[p0 p1]

[p0 p1]	p	1-p
	(1-p)/2	(1+p)/2

p0+p1 =1
p0= p0*p+(1-p)/2*p1
p1= (1-p)*p0+(1+p)p1
____________________

p0(1-p) = (1-p)/2*p1
p0= p1/2
p0+ 2p0 = 1
p0=1/3

[math] \sum\limits_{x1} \sum\limits_{x2} p(x1)* p(x2|x1)*log (p((x2|x1))) = [/math]
[math] -\lgroup 1/3[p*log(p)+(1-p*log(1-p))]+2/3*[(1-p)/2*log((1-p)/2)+(1+p)/2*log((1+p)/2)]\rgroup = [/math]

Defínició szerint:
[math]\frac{1}{3} \cdot h(p) + \frac{2}{3} \cdot h(\frac{1-p}{2}) [/math]

Általános stacionárius eset

[math]1-\alpha[/math]	[math]\alpha[/math]
[math]\beta[/math]	[math]1-\beta[/math]

mátrix esetén a [math] p0= \beta /(\alpha+\beta) [/math] és [math] p1 =\alpha /(\alpha+\beta) [/math]

stacionárius eloszlás esetén.

[math]H(XX) =p0* h(\alpha) + p1 * h(\beta))[/math] .

1.20 (Vissza a jövőbe)

[math]H(X_0 | X_{-1}, X_{-2}, ..., X_{-n}) = H(X_0 | X_1,X_2, ..., X_n)[/math]

segédtudomány:
[math]H(X, Y) = H(X) +H(Y|X) =\gt H(Y|X)= H(X, Y)- H(X)[/math]

[math]H(X_0, X_{-1}, X_{-2}, ..., X_{-n}) - H(X_{-1}, X_{-2}, ..., X_{-n})[/math] = [math]H(X_0, X_1,X_2, ..., X_n) - H(X_1,X_2, ..., X_n)[/math]

Mivel [math]H(X_0, X_1,X_2, ..., X_n)[/math] stacionárius valószínűségi változó sorozat (folyamat, információforrás) ezért a [math](X_{i+0}, X_{i+1}, X_{i+2}, ... , X_{i+n})[/math] együttes eloszlása egyezik [math](X_{j+0}, X_{j+1}, X_{j+2}, ... , X_{j+n})[/math] együttes eloszlásával, minden i-re és j-re, vagyis elmozoghatunk a sorozat mentén. Ha az eloszlás egyezik, az entrópia is. thx to Main.BergmannGabor.

(i+n eltolással, ahol i=0... -n)

[math]P(X_0 ,X_{-1}, X_{-2}, ..., X_{-n}) = P(X_0 ,X_1,X_2, ..., X_n)[/math]

Tehát a vizsgált összegekben a tagok külön külön egyenlőek:

[math]H(X_0 ,X_{-1}, X_{-2}, ..., X_{-n}) = H(X_0 ,X_1,X_2, ..., X_n)[/math]

és (i+n+1 es eltolás) [math]H(X_{-1}, X_{-2}, ..., X_{-n}) = H(X_1,X_2, ..., X_n)[/math]

1.21

Legyenek a ZZ stacionárius Markov-lánc állapotai a 0, 1, ..., 255 számok, és tegyük fel, hogy az állapotátmenet valószínűségek az alábbi 256x256-os

Ezen a helyen volt linkelve a 256matrix.JPG nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

mátrixszal adottak (a mátrix i-edik sorának j-edik oszlopában a P{Z₂=j|Z₁=i} valószínűség található). Mi a Markov-lánc stacionárius eloszlása? Mennyi a forrás entropiája? Készítsen jó, egyertelműen dekódolható, változó szóhosszúságú blokk-kódot!
mo.:

		 /\
  marad /\
	  1-t	2-t jobbra
	  balra

pl: 0 0 2 3 5 5 6 ==> 0111011010
E|f(x)=summa pi*li=.5*1+ 2*.25*2 = 1.5
pi=1/256
H(ZZ)=H(Z2,Z1)=-summa[z1=...]P(Z1=z1)*summa[z2=...](Z2=z2|Z1=z1)logP(Z2=z2Z1=z1)= =1/256)* (-256*.5*log.5 -512*.25*log.5) = .5log2+2/4*log4 = 1.5

Tehát a kódunk tökéletes volt.

1.22

Az alábbi ábra egy ZZ=Z₁, Z₂, ... Markov-lánc működését írja le. Tegyük fel, hogy a láncot a stacionárius eloszlásból indítjuk.

Ezen a helyen volt linkelve a 1_18.JPG nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

[math] P(X_1=0 | X_0=0)=p [/math]
[math] P(X_1=1 | X_0=0)=1-p [/math]
[math] P(X_1=0 | X_0=1)=\frac{1-p}{2} [/math]
[math] P(X_1=1 | X_0=1)=\frac{1+p}{2} [/math]

Legyen továbbá Y₁,Y₂, ... független azonos eloszlásu bináris valószínűségi változok sorozata, ahol P(Y_i=0) =1/3. Definiáljuk az XX=X₁, X₂, ... forrást az X_i=2Z_i+Y_i egyenlettel. Mennyi XX forrás entrópiája feltéve, ha Z₁,Z₂ független Y₁, Y₂, ...-tól?

mo.: [math]H(XX)= H(Z_2|Z_1)+H(X_1|Z_1)[/math]
[math]H(Z_2|Z_1) =1/3h(p) +2/3h(1/2-p/2)[/math] [math]H(X_1|Z_1)= -(1/3*(1/3*log(1/3)+2/3*log(2/3))+2/3*(1/3*log(1/3)+2/3*log(2/3)))=H(Y_1)= h(1/3)[/math] [math]lim[n-\gt inf] 1/n*H(Z_1...Z_n|X_1...X_n)=lim 1/n*H(f(x_1..x_n)|X_1..X_n))[/math]

1.23. LZ78

Adjunk meg a 36 darab nullából álló sztring LZ78-kódját.

0 00 000 0000 00000 ...
1+2+3+4+5...+ ? =36
Sorozat összege: n*(n+1)/2 =36 => n=8. Tehát nyolc darab index kerül bele a szótárba

Kódoló üzenete	Szótár
index,f{next char}	index	érték
0,f{0}	1	0
1,f{0}	2	00
...	...	...
7,f{0}	8	00000000