RÉGI TÉTEL: Információelmélet, 15. tétel
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
<style> li {margin-top: 4px; margin-bottom: 4px;} </style>
Tartalomjegyzék
információstabilis forrás
TK-ban van benne:) ...
AEP tulajdonság
AEP: Asymphtotic Equipartition Property, Aszimptotikus Ekvipartíció tulajdonság azaz "majdnem minden esemény majdnem ugyanolyan váratlan" (Cover-Thomas könyv egyenes fordítása).
[math] \forall x_1, ..., x_k : P(X_1=x_1, ..., X_k=x_k) = 2^{-kH(X)} [/math] (TODO: a kettes alap helyett egy másik helyen x szerepel, melyik a jó???)
TODO: formázni a következőt: A C X^k (C: részhalmaza jel), P(A) hullámos= 1, X eleme A -> -1/k*log p(x) hullámos= H(X) p(x) hullámos= 2^(-kH(X)
A hullámos= 2^(k*H(X))
raxxk−∀,...,1a P(X1=x1,…,Xk=xk) = 2-kH(X) -- Sales - 2006.06.24. wikipedia link az AEP tulajdonság definíciójára Forráskódolás előírt hibavalószínűséggelJelölésekA tétel kidolgozása során a következő jelölésekkel dolgozunk: Legyen [math] \chi [/math] a forrásábécé. [math] |\chi|= n [/math] Elégséges feltétel egyértelműen dekódolható blokkód létezéséreMegjegyzés: Fix kódszóhosszúságú kódszavakat alkalmazunk, az ilyen kódok minden esetben prefix kódok, hiszen két azonos hosszúságú szó közül egyik sem lehet a másiknak prefixe. Egy fix kódszóhosszúságú [math] f:\chi^k\longmapsto\gamma^m [/math] blokkód csak akkor lehet egyértelműen dekódolható, ha a lehetséges forrásszavak száma nem nagyobb a lehetséges kódszavak számánál: [math] s^m \geq n^k [/math] [math] \log s^m \geq \log n^k [/math] [math] m \log s \geq k \log n [/math] [math] \frac{m}{k} \geq \frac{\log n}{\log s} [/math] Tudjuk, hogy [math] L = \frac{m}{k} [/math] továbbá tudjuk, hogy [math] H(X) \leq \log n [/math], ezért
[math] L = \frac{m}{k} \geq \frac{\log n}{\log s} \geq \frac{H(X)}{\log s} [/math] Az átlagos kódszohossz ebben az esetben sem csökkenthető egy adott határ alá. Ez elégséges feltétel is egyértelműen dekódolható kód létezésére. Dekódolás adott hibávalEgy [math] \mathbb{X}=X_1, X_2, ... [/math] stacionárius forráson értelmezett [math] f:\chi^k\longmapsto\gamma^m [/math] kódot akkor mondunk [math]\epsilon[/math] hibával dekódolhatónak ([math] 0 \leq \epsilon [/math]), ha létezik olyan [math] f':\gamma^m\longmapsto\chi^k [/math] függvény, hogy a hibázás valószínűsége nem nagyobb [math]\epsilon[/math]-nál, vagyis: [math] P\{ f'(f(X_1, X_2, ..., X_k)) \neq (X_1, X_2, ..., X_k) \} \leq \epsilon [/math]
További pontokTODO -- Sales - 2006.06.24. |