InfElmTetel43

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>

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.
I.
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)| \lt \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.
II.
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)| \lt \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)
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.
A forrásábécé legyen [math] X = (x_1, x_2, \ldots, x_n) [/math].
A kódábécé elemszáma legyen [math] s [/math].

Válasszunk [math]n[/math] darab pozitív egész [math] l_i [/math] számot, amelyekre igaz, hogy

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

A bal oldali egyenlőtlenségből:
[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]

-- 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

-- Dani - 2007.06.16.