Kraft-McMillanova nerovnost

V teorii kódování dává Kraft -McMillanova nerovnost nezbytnou a dostatečnou podmínku pro existenci oddělitelných a prefixových kódů , které mají danou sadu délek kódových slov.

Předběžné definice

Nechť jsou dány dvě libovolné konečné množiny , které se nazývají kódovaná abeceda a kódovaná abeceda . Jejich prvky se nazývají znaky a řetězce (sekvence konečné délky) znaků se nazývají slova . Délka slova je počet znaků, ze kterých se skládá.

Za kódovací abecedu je často považována množina - tzv. binární neboli binární abeceda. $\{0,1\}$

Abecední kódovací schéma (nebo jednoduše (abecední) kód ) je jakékoli mapování znaků kódované abecedy na slova kódovací abecedy, která se nazývají kódová slova . Pomocí kódovacího schématu může být každé slovo kódované abecedy spojeno s jeho kódem - zřetězením kódových slov odpovídajících každému znaku tohoto slova.

Kód se nazývá oddělitelný (nebo jedinečně dekódovatelný ), pokud žádná dvě slova kódované abecedy nemohou být spojena se stejným kódem.

Prefixový kód je abecední kód, ve kterém žádné z kódových slov není prefixem žádného jiného kódového slova. Jakýkoli prefixový kód je oddělitelný.

Formulace

Macmillanova věta (1956) .

Nechť jsou uvedeny kódované a kódovací abecedy sestávající z a symboly a požadované délky kódových slov: . Pak nezbytnou a postačující podmínkou pro existenci oddělitelných a prefixových kódů s danou sadou délek kódových slov je splnění nerovnosti: $n$ $d$ ${\displaystyle \ell _{1},\ell _{2},\ldots ,\ell _{n))$

\sum _{i=1}^{n}d^{\,-\ell _{i}}\leqslant 1.

Tato nerovnost je známá jako Craft-MacMillanova nerovnost . Poprvé ji odvodil Leon Kraft ve své diplomové práci v roce 1949 [1] , ale zvažoval pouze předponové kódy, takže při diskuzi o předponových kódech se tato nerovnost často nazývá jednoduše Kraftova nerovnost . V roce 1956 Brockway Macmillan dokázal nezbytnost a dostatečnost této nerovnosti pro obecnější třídu kódů, oddělitelné kódy. [2]

Příklad

Binární stromy

Na jakýkoli zakořeněný binární strom lze nahlížet jako na grafický popis kódu předpony přes binární abecedu: znaky kódované abecedy odpovídají listům stromu a cesta ve stromu od kořene k listu určuje jeho kód ( dráha se skládá ze sledu pohybů „doleva“ a „doprava“, které odpovídají znakům 0 a 1).

Pro takové stromy Kraft-McMillanova nerovnost uvádí, že:

\sum _{x\in {\mathcal {L}}}2^{-\mathrm {depth} (x)}\leqslant 1,

kde je sada listů stromu a je hloubka listu , počet hran na cestě od kořene k . $\mathcal{L}$ $\mathrm {hloubka} (x)$ $X$ $X$

Pro strom na obrázku vpravo máme:

{\frac {1}{4}}+4\left({\frac {1}{8}}\right)={\frac {3}{4}}\leqslant 1.

Poznámky

↑ Kraft, Leon G. (1949), Zařízení pro kvantování, seskupování a kódování amplitudově modulovaných pulzů , Cambridge, MA: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology , < http://dspace.mit.edu/ handle/1721.1/12390 > Archivováno 22. dubna 2009 na Wayback Machine
↑ McMillan, Brockway (1956), Dvě nerovnosti implikované jedinečnou dešifrovatelností , IEEE Trans. Information Theory , svazek 2 (4 ) : 115–116, doi : 10.1109 /TIT.1956.1056818 ,

Literatura

Gashkov, S. B. Číselné soustavy a jejich aplikace . — M. : MTsNMO, 2004. — 52 s. — ISBN 5-94057-146-8 .
Obálka, TM, Thomas, JA Základy teorie informace. - 2006. - S. 116. - ISBN 0-471-24195-4 .

Odkazy

Kraftova nerovnost (NIST) Archivováno 27. ledna 2009 na Wayback Machine
http://www.codingtheory.gorodok.net/seminars/seminar%2010.pdf Archivováno 5. března 2016 na Wayback Machine