Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel43}} vissza InfelmTetelek-hez ''Azért vettem külön…”

2012-10-21T19:59:52Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel43}} vissza InfelmTetelek-hez <style> li {margin-top: 4px; margin-bottom: 4px;} </style> ''Azért vettem külön…”

Új lap

{{GlobalTemplate|Infoalap|InfElmTetel43}}

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

''Azért vettem külön ezt a tételt a Sannon-Fano kódtól, mert Laci ezt nem kéri.''

Tk. 18. o. 2. BIZONYÍTÁS.

TODO: Ezt teljesen oké, de az nekem nem jött át, hogy maga a kód hogy áll elő. Az rendben van, hogy a kódszóhosszakat megadják az <math>l_i</math>-k, és nyilván optimális a kód, akkor vesszük a két leghosszabbat, és egyiknek a vége 1 lesz a másiknak 0, és haladunk úgy, hogy prefix kódot kapjunk, vagy hogy? :)

VÁLASZ: TODO kérdései furcsák!! legalábbis butaságokat állítanak. <BR>
I.<BR>
Hiányok a végéről:
Shannon-kódnál igaz a lenti jelöléseket követve hogy <math>|f(x_i)| = l_i</math> választással prefix kódot kapunk(Kraft-lemma: <math>\sum_{i=1}^{n} s^{-l_i} \leq 1 </math>) Az egyértelműen detektálható kódok átlagos kódszóhosszát "jól megközelítjük" ezzel a hozzárendeléssel.(<math>E|f(X)| < \frac{H(X)}{log(s)} + 1 </math>)
Az "algoritmus" lépéseit úgy adja meg, hogy a valószínűségekhez kódszóhosszakat rendel. Ezt megtehetjük <math> -log_s p(x_i) \leq l_i \textless -log_s p(x_i)+1 </math>, <math> i = 1, 2, \ldots, n </math>-szerint. A kapott kód teljesíti az előírt feltételünket. Ez a Shannon-kód.<BR>
II.<BR>
A Shannon és Shannon-Fano kód a konstruktív bizonyítás arra, hogy meg lehet közelíteni az átlagos kódszóhosszal az elvi <math>\frac{H(X)}{log(s)}</math> határt. Vagyis elérhetjük hogy <math>E|f(X)| < \frac{H(X)}{log(s)} + 1 </math>. De ez ''nem feltétlenül lesz optimális eljárás''. Egyik sem. Sem a Shannon, sempedig a Shannon-Fano. Az lesz az ''optimális'' ami az '''adott eloszláshoz a legjobb átlagos kódszóhosszat''' adja. Nyilván ez sem lesz egyértelmű, olyan értelemben, hogy az azonos valószínűségekhez tartozó kódszohosszakat kicserélhetjük. Nyilván az is mindegy, hogy egyenlő hosszú kódszavakat megkülönböztetjük -e. DE mindig lesz optimális kód(az egyiket meg tudjuk találni), mivel "jó" kódok halmazával véges számúra szűkítettük a prefix kódok számát(Shannon-Fano és Shannon-kód adja, hogy mindig vannak "jó" kódok)<BR>
Az optimalitást az optimalitásra törekvő Hamming-kód fogja adni. De ott az optimalitást kielégítő feltételeket ellenőrizzük. Azután jött a gondolat, hogy mi van ha nem ismerjük az eloszlást? Becsüljünk a relatív gyakorisággal. Sőt mivel át kell vinni a csatornán a dekódoláshoz szükséges adatokat, legyen adaptív ez az algoritmus. Adaptív? Igen. Az adaptív Hamming kódnál a fejlécet csökkentettük le azzal, hogy mindkét oldalon felépítjük a Hamming-fát, így két entitás számol, de ezzel csökkentjük a csatornán leadandó információ nagyságát(szokásosan valamiféle tár/teljesítmény optimalizálás).

==Shannon kód==

Kódolunk.<BR>
A forrásábécé legyen <math> X = (x_1, x_2, \ldots, x_n) </math>.<BR>
A kódábécé elemszáma legyen <math> s </math>.<BR>

Válasszunk <math>n</math> darab pozitív egész <math> l_i </math> számot, amelyekre igaz, hogy<BR>

<math> -log_s p(x_i) \leq l_i \textless -log_s p(x_i)+1 </math>, <math> i = 1, 2, \ldots, n </math><BR>

A bal oldali egyenlőtlenségből:<BR>
<math> log_s p(x_i) \geq -l_i </math>

<math> -l_i \leq log_s p(x_i) </math>

<math> s^{-l_i} \leq s^{log_s p(x_i)} </math>

<math> \sum_{i=1}^{n}s^{-l_i} \leq \sum_{i=1}^{n} s^{log_s p(x_i)} = \sum_{i=1}^{n} p(x_i) = 1 </math>

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

http://home.mit.bme.hu/~benes/oktatas/dig-jegyz_052/kodolas.pdf 8.oldalon le van írva hogyan is kell ezt a kódolást csinálni

-- [[BalasDani|Dani]] - 2007.06.16.

[[Category:Infoalap]]

InfElmTetel43 - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel43}} vissza InfelmTetelek-hez li {margin-top: 4px; margin-bottom: 4px;} ''Azért vettem külön…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel43}} vissza InfelmTetelek-hez ''Azért vettem külön…”