InfElmTetel12

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

vissza InfelmTetelek-hez <style> li {margin-top: 4px; margin-bottom: 4px;} </style>

Forrásentrópia

Egy betűre eső átlagos kódszóhossz

Legyen [math] f:\alpha\longmapsto\beta^* [/math] egyértelműen dekódolható kód, ezzel szeretnénk az [math] \mathbb{X} [/math] forrást kódolni. Ha k karaktert kódolunk, akkor az egy karakterre eső átlagos kódszóhossz [math] X_i [/math] valószínűségi változók azonos eloszlása miatt független k-tól.

Felső korlát egy betűre jutó kódszóhosszra

Blokk kódolás esetén, tehát amikor a kódfüggvény több betűből álló csoportokat kódol, akkor létezik olyan prefix kód, hogy az egy betűre jutó átlagos kódszóhosszra a következő felső korlát adható:

[math] \frac{1}{k} E(|f(X_1, X_2, ..., X_n)|) \leq \frac{1/k*H(X_1, X_2, ..., X_n)}{log s} + \frac{1}{k} [/math]

Forrásentrópia

Egy [math] \mathbb{X} = X_1, X_2, ... [/math] forrás forrásentrópiája megmutatja, hogy hogyan alakul az egy betűre jutó entrópia, ha az üzenet hosszát minden határon túl növeljük.
A forrásentrópiát megadja a következő határérték: (amennyiben létezik)

[math] H(\mathbb{X}) = \lim_{k\rightarrow\infty} \frac{1}{k} H(X_1, X_2, ..., X_k) [/math]

Stacionárius forrás forrásentrópiája

Ha [math] \mathbb{X} = X_1, X_2, ... [/math] stacionárius forrás, akkor az entrópiája biztosan létezik és a következő módon is számítható:

[math] H(\mathbb{X}) = \lim_{k\rightarrow\infty} H(X_k | X_1, X_2, ..., X_{k-1}) [/math]

Emlékezet nélküli stacionárius forrás forrásentrópiája

Emlékezet nélküli stacionárius forrás forrásentrópiája biztosan létezik, és értéke a következő:

[math] H(\mathbb{X}) = \lim_{k\rightarrow\infty} \frac{1}{k} H(X_1, X_2, ..., X_k) = [/math]
mivel a forrás emlékezet nélküli, ezért az [math] X_i [/math] változók függetlenek, tehát az együttes entrópia felírható az egyes változók entrópiájának összegeként, amiből:
[math] = \lim_{k\rightarrow\infty} \frac{1}{k} \sum_{i=1}^{k} H(X_i) = [/math]
mivel a forrás stacionárius, ezért a véges együttes eloszlások invariánsak az időeltolásra, így az egyes változók eloszlása azonos, ezért az eloszlásokat helyettesíthetjük pl [math] X_1 [/math] eloszlásával, így:
[math] = \lim_{k\rightarrow\infty} \frac{1}{k} k * H(X_1) = [/math] [math] \lim_{k\rightarrow\infty} H(X_1) = [/math] [math] H(X_1) [/math]

-- Sales - 2006.06.23.