InfElmTetel13

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>

Stacionárius forrás változó szóhosszúságú kódolása

Ráhangolódás

Ha egy stacionárius forrást k hosszúságú blokkokban tömörítünk, akkor k növelésével az egy forrásbetűre jutó átlagos kódszóhosszt csökkenthetjük, és tetszőlegesen megközelíthetjük az [math] \frac{H(X_1)}{log s} [/math] hányadost, de az alá nem juthatunk. A blokkhossz növelésének a gyakorlatban határt szab, hogy a nagyobb blokkokhoz több adatot kell összevárni, ami növeli a késleltetést. A nagyobb blokkok több erőforrást is igényelnek.

Formális alak

Kódoljuk az [math] \mathbb{X}=X_1, X_2, ... [/math] forrást az [math] f:\alpha^k\longmapsto\beta^{*} [/math] EGYÉRTELMŰEN DEKÓDOLHATÓ(*) kóddal k hosszúságú blokkokban. Legyen [math]L = \frac{1}{k}E|f(X_1, X_2, ..., X_k)|[/math] egy blokkhoz tartozó kódszó átlagos hosszának egy forrásbetűre jutó értéke. Mivel [math] \mathbb{X} [/math] stacionárius, ezért ez az érték azonos tetszőleges [math]k[/math] db egymás után következő forrásbetűhöz rendelt kódszó esetén.

Ekkor [math]L \geq \frac{H(X_1)}{log s}[/math] mindig fennáll.
Ha a k blokkhosszt növeljük, akkor tetszőleges [math]0\leq\epsilon[/math]-ra igaz, hogy: [math] L \leq \frac{H(X_1)}{log s} + \epsilon [/math]

Megjegyzések

(*) A kódnak egyértelműen dekódolhatónak kell lennie, egyébként tetszőlegesen rövid átlagos kódszóhossz elérhető lenne, és az alsó korlát nem lenne érvényes.

-- Sales - 2006.06.24.