Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel9}} vissza InfelmTetelek-hez ==Shannon-Fano kód== S…”

2012-10-21T20:00:00Z

Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel9}} vissza InfelmTetelek-hez <style> li {margin-top: 4px; margin-bottom: 4px;} </style> ==Shannon-Fano kód== S…”

Új lap

{{GlobalTemplate|Infoalap|InfElmTetel9}}

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

==Shannon-Fano kód==

Szeretnénk kódolni egy <math> X </math> valószínűségi változót, amelynek eloszlása a következő. (Ha a következő nem teljesül, átindexeljük.)

Feltesszük, hogy <math>p(x_1) \geq p(x_2) \geq \ldots \geq p(x_n) > 0</math>.

''<math>w_i</math> az (i-1) legnagyobb valószínűségű érték valószínűségeinek összege, amire a kódoláshoz szükségünk lesz.'' <BR>
Legyen <BR>
<math> w_1 = 0 </math><BR>
<math> w_i = \sum_{l=1}^{i-1}{p(x_l)} </math><BR>
ahol <math>i = 2 \ldots n</math>.

Felírjuk <math>w_i</math> számokat <math>s</math>-alapú számrendszerben, a <math>w_j</math>-hez tartozó törtet olyan pontosságig, ahol először különbözik a többi <math>w_i</math>, <math>w_i \neq w_j</math> felírástól. Az így kapott <math>n</math> db véges hosszú törtből elhagyjuk az egészrészt, ez lesz <math>f(x_i)</math>. Az így kapott kód prefix, és
<math>
E|f(X)| < \frac{H(X)}{\log{s}} + 1
</math>

Látható, hogy minden kódolásnál kevesebb mint egy kódbetű "veszik el", ezért célszerű minél nagyobb blokkméretet használni. A blokkméret növelésével az átlagos kódszóhosszra vonatkozó alsó határ tetszőlegesen megközelíthető.
-- [[SzelessZoltanTamas|Sales]] - 2006.06.23.

TODO:
ez nem bizonyítás! Én nem is fogom ideírni:) TK-ban megvan illetve: [http://www.crysys.hu/courses/kodolastechnika/bscinfkod.pdf jogvédett, de elektronikus formában elérhető anyag] <BR>Algoritmus másképpen, ahogy digitből is tanultuk és ahogy könyebb elképzelni:<BR>
*0/1 kiegészítgetés*: <BR> A Shannon-Fano kód konstruálása során fát építhetünk(Legyen bináris a fa; s = 2). A valószínűségeken rendezés adott, ahogy a Shannon-kódnál. A rendezett sorozatot kétfelé vágjuk, hogy a két rész összsúlya(valószínűségek összege) a lehető legközelebb legyen egymáshoz. A két szakaszt jelezzük 0-val illetve 1-el a fa két új csúcsában(a gyökér alá téve ezeket) ami a sorozatot reprezentálja ezek után. Ez rekurzívan (a sorozat szétbontása a sorozathoz tartozó csúcs alá kerül, mint új gyökér alá) amíg egy elemű sorozatokat kapunk. A kódszavakat kiolvashatjuk, ha a gyökértől a levélekig bejárjuk az utakat, és kiolvassuk a csúcsokba írt számot(0/1).

-- [[PeresztegiAdam|hippi]] - 2007.06.13.

[[Category:Infoalap]]

InfElmTetel9 - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel9}} vissza InfelmTetelek-hez li {margin-top: 4px; margin-bottom: 4px;} ==Shannon-Fano kód== S…”

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoalap|InfElmTetel9}} vissza InfelmTetelek-hez ==Shannon-Fano kód== S…”