InfElmTetel37

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>

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 $\frac{H(X)}{logs}$ 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: $(p_1,p_2,...,p_n)$

$q_0=0$
$q_i=\sum _{j=1}^i{p}_i$

Ekkor az i. intervallum a $[q_{i-1},q_i)$.

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 $p(\mathbf{x})$ az $\mathbf{x}$ üzenetblokk valószínűsége, akkor igazolható, hogy ezt elég $\lceil \log \frac{1}{p(\mathbf{x})}\rceil +1$ biten ábrázolni.

Az átlagos kódszóhossz ebből (k hosszú blokkok esetén):
$E(\lceil \log \frac{1}{p(\mathbf{X})}\rceil +1)=\sum _{\mathbf{x}ϵ{\alpha }^k}p(\mathbf{x})(\lceil \log \frac{1}{p(\mathbf{x})}\rceil +1)\le$ $\sum _{\mathbf{x}ϵ{\alpha }^k}p(\mathbf{x})((\log \frac{1}{p(\mathbf{x})}+1)+1)=$ $\sum _{\mathbf{x}ϵ{\alpha }^k}p(\mathbf{x})(\log \frac{1}{p(\mathbf{x})}+2)=$ $\sum _{\mathbf{x}ϵ{\alpha }^k}p(\mathbf{x})\log \frac{1}{p(\mathbf{x})}+2\sum _{\mathbf{x}ϵ{\alpha }^k}p(\mathbf{x})=$ $-\sum _{\mathbf{x}ϵ{\alpha }^k}p(\mathbf{x})\log p(\mathbf{x})+2=H(\mathbf{X})+2$

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

$\frac{1}{k}E|f(\mathbf{X})|\le H(X_1)+\frac{2}{k}$

-- Sales - 2006.06.27.

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

-- Pecc - 2007.06.15.