InfElmTetel6

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.

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

Mcmillan egyenlőtlenség

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

Bizonyítás

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

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

-- Kikki - 2005.12.19.

-- Sales - 2006.06.22.