RÉGI TÉTEL: Információelmélet, 15. tétel

Ez az oldal a korábbi SCH wikiről lett áthozva.

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>

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).

$\forall x_{1},...,x_{k}:P(X_{1}=x_{1},...,X_{k}=x_{k})=2^{-kH(X)}$ (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éggel Jelölések A tétel kidolgozása során a következő jelölésekkel dolgozunk: Legyen $\chi$ a forrásábécé. $|\chi |=n$ Legyen $\gamma$ a kódábécé. $|\gamma |=s$ Kódoljunk $k$ hosszúságú blokkokat $m$ hosszúságú kódszavakkal. A kódfüggvény tehát: $f:\chi ^{k}\longmapsto \gamma ^{m}$ Jelölje $L$ az egy forrásbetűre jutó átlagos kódszóhosszt. Elégséges feltétel egyértelműen dekódolható blokkód létezésére Megjegyzé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ú $f:\chi ^{k}\longmapsto \gamma ^{m}$ 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: $s^{m}\geq n^{k}$ $\log s^{m}\geq \log n^{k}$ $m\log s\geq k\log n$ ${\frac {m}{k}}\geq {\frac {\log n}{\log s}}$ Tudjuk, hogy $L={\frac {m}{k}}$ továbbá tudjuk, hogy $H(X)\leq \log n$, ezért $L={\frac {m}{k}}\geq {\frac {\log n}{\log s}}\geq {\frac {H(X)}{\log s}}$ 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ával Egy $\mathbb {X} =X_{1},X_{2},...$ stacionárius forráson értelmezett $f:\chi ^{k}\longmapsto \gamma ^{m}$ kódot akkor mondunk $\epsilon$ hibával dekódolhatónak ($0\leq \epsilon$), ha létezik olyan $f':\gamma ^{m}\longmapsto \chi ^{k}$ függvény, hogy a hibázás valószínűsége nem nagyobb $\epsilon$-nál, vagyis: $P\{f'(f(X_{1},X_{2},...,X_{k}))\neq (X_{1},X_{2},...,X_{k})\}\leq \epsilon$ További pontok TODO -- Sales - 2006.06.24.