Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel37}} ==Aritmetikai kódolás== Tk. 28-30. o. ===Az aritmetikai kódol…”

2012-10-21T19:59:44Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel37}} <style> li {margin-top: 4px; margin-bottom: 4px;} </style> ==Aritmetikai kódolás== Tk. 28-30. o. ===Az aritmetikai kódol…”

Új lap

{{GlobalTemplate|Infoalap|InfElmTetel37}}

<style> li {margin-top: 4px; margin-bottom: 4px;} </style>
==Aritmetikai kódolás==

Tk. 28-30. o.

===Az aritmetikai kódolás előnyei===

A blokkméret növelésével az egy betűre jutó átlagos szóhosszal tetszőlegesen meg tudjuk közelíteni felülről a <math> \frac{H(X)}{log s} </math> határt. Sajnos pl a Huffman kód esetében a blokk kódolásához be kell várnunk a teljes kódolandó blokk beérkezését, hiszen meg kell határoznunk a betűk relatív valószínűségét. Ezen a problémán segít az adaptív Huffman kód, de minkét típusú Huffman kódnál problémát okoz, hogy a blokkméret növekedésével az algoritmus bonyolultsága exponenciálisan növekszik.

Az aritmetikai kódolással a blokkméret növelésével szintén meg tudjuk közelíteni a fenti korlátot, ráadásul ez valós időben történik, és a komplexitás is kezelhető marad.

===Az aritmetikai kódolás===

Particionálás: egy halmaz felosztása diszjunkt részhalmazokra úgy, hogy azok teljesen lefedjék a halmazt.

''Ezt fogjuk csinálni:''
Tekintsük a [0,1) intervallumot, ezt fogjuk partícionálni, majd a partíciók közül egyet kiválasztva azt újrapartícionáljuk, és ezt annyiszor ismételjük meg, ahány elemű blokkot kódolunk. Mindig a legmélyebben egymásbaágyazott partíciók egyikét partícionáljuk tovább. A kód a végén a legmélyebb partíciók egyikébe eső tetszőleges szám lesz.

Vegyük a [0,1) intervallumot, és partícionáljuk úgy, hogy a forrásábécé minden eleméhez rendeljünk egy intervallumot, aminek a nagysága legyen arányos a hozzá rendelt betű valószínűségével.
Legyen a forrásábécé valószínűségi eloszlása: <math> (p_1, p_2, ..., p_n) </math>

<math> q_0 = 0 </math><BR>
<math> q_i = \sum_{j=1}^{i} p_i </math>

Ekkor az i. intervallum a <math> [q_{i-1}, q_i) </math>.

Az első betű kódolásakor kiválasztjuk a hozzá tartozó intervallumot, amit a fentiek szerint ismét partícionálunk, és a kapott intervallumokból kiválasztjuk a második betűhöz tartozót, és így tovább.

A blokk végére jutva elküldtük a blokkhoz tartozó kódot. Ha <math> p(\bold{x}) </math> az <math> \bold{x} </math> üzenetblokk valószínűsége, akkor igazolható, hogy ezt elég <math> \lceil \log \frac{1}{p(\bold{x})} \rceil + 1 </math> biten ábrázolni.

Az átlagos kódszóhossz ebből (k hosszú blokkok esetén):<BR>
<math> E(\lceil \log \frac{1}{p(\bold{X})} \rceil + 1) = \sum_{\bold{x} \epsilon \alpha^{k}} p(\bold{x}) (\lceil \log \frac{1}{p(\bold{x})} \rceil + 1) \leq </math>
<math> \sum_{\bold{x} \epsilon \alpha^{k}} p(\bold{x}) (( \log \frac{1}{p(\bold{x})} + 1) + 1) = </math>
<math> \sum_{\bold{x} \epsilon \alpha^{k}} p(\bold{x}) ( \log \frac{1}{p(\bold{x})} + 2) = </math>
<math> \sum_{\bold{x} \epsilon \alpha^{k}} p(\bold{x}) \log \frac{1}{p(\bold{x})} + 2 \sum_{\bold{x} \epsilon \alpha^{k}} p(\bold{x}) = </math>
<math> -\sum_{\bold{x} \epsilon \alpha^{k}} p(\bold{x})\log p(\bold{x}) + 2 = H(\bold{X}) + 2 </math>

Ha <math> \bold{X} </math> komponensei független azonos eloszlásúak, a betűnkénti átlagos kódszóhossz:

<math> \frac{1}{k}E|f(\bold{X})| \leq H(X_{1}) + \frac{2}{k} </math>

-- [[SzelessZoltanTamas|Sales]] - 2006.06.27.

Itt is van egy elég jó (érthető) leírás: http://www.binaryessence.com/dct/en000119.htm

-- [[ValyiPeter|Pecc]] - 2007.06.15.

[[Category:Infoalap]]

InfElmTetel37 - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel37}} li {margin-top: 4px; margin-bottom: 4px;} ==Aritmetikai kódolás== Tk. 28-30. o. ===Az aritmetikai kódol…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel37}} ==Aritmetikai kódolás== Tk. 28-30. o. ===Az aritmetikai kódol…”