InfElmTetel6

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>

Mcmillan egyenlőtlenség

[math] f: X \longmapsto Y^{*} [/math] egyértelműen dekódolható kód esetén érvényes az alábbi összefüggés (ahol [math]|f(x_i)|[/math] az [math]f(x_i)[/math] kodszó hossza): [math] \sum_{i=1}^{n} s^{-|f(x_{i})|} \leq 1 [/math]

Bizonyítás

Vegyük az összeg N. hatványát: [math] ( \sum_{i=1}^{n} s^{-|f(x_{i})|} )^N = . . . =\sum_{l=1}^{N*Lmax} A_{l}s^{-l} [/math] ahol [math]A_l[/math] az l hosszu, N db kódszó összefűzésével keletkező kódszósorozatok száma, [math]L_max[/math] pedig a kódszóhosszak maximuma.

Egyértelműen dekódolható -> összes l hosszú sorozat különböző -> [math] A_{l} \leq s^{l}[/math] (s a kódABC elemszáma) [math] ( \sum_{i=1}^{n} s^{-|f(x_{i})|} )^N \lt = N*L_{max}[/math] [math] \sum_{i=1}^{n} s^{-|f(x_{i})|} \leq (\sqrt{N})^N*(\sqrt{L_{max}})^N \rightarrow 1, \ ha \ N \rightarrow \infty [/math]

-- Kikki - 2005.12.19.

-- Sales - 2006.06.22.