Inegalitatea Kraft-McMillan

În teoria codificării , inegalitatea Kraft-McMillan oferă o condiție necesară și suficientă pentru existența unor coduri separabile și prefixe care au un set dat de lungimi de cuvinte de cod.

Definiții preliminare

Să fie date două mulțimi finite arbitrare , care sunt numite, respectiv, alfabet codificat și , respectiv, alfabet codificat . Elementele lor sunt numite caractere , iar șirurile (secvențe de lungime finită) de caractere sunt numite cuvinte . Lungimea unui cuvânt este numărul de caractere din care este format.

Ca alfabet de codare, un set este adesea considerat - așa-numitul alfabet binar sau binar. $\{0,1\}$

O schemă de codificare alfabetică (sau pur și simplu cod (alfabetic) ) este orice mapare a caracterelor alfabetului codificat în cuvinte din alfabetul de codificare, care sunt numite cuvinte de cod . Folosind schema de codare, fiecare cuvânt al alfabetului codificat poate fi asociat cu codul său - concatenarea cuvintelor de cod corespunzătoare fiecărui caracter al acestui cuvânt.

Un cod se numește separabil (sau decodabil unic ) dacă nu pot fi asociate două cuvinte din alfabetul codificat cu același cod.

Un cod de prefix este un cod alfabetic în care niciunul dintre cuvintele de cod nu este un prefix al oricărui alt cuvânt de cod. Orice cod de prefix este separabil.

Formulare

Teorema lui Macmillan (1956) .

Să fie date alfabetele codificate și , respectiv, simboluri, și să fie date lungimile dorite de cuvinte de cod: . Atunci o condiție necesară și suficientă pentru existența codurilor separabile și a prefixelor cu un set dat de lungimi de cuvinte de cod este îndeplinirea inegalității: $n$ $d$ $\ell _{1},\ell _{2},\ldots,\ell _{n)$

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

Această inegalitate este cunoscută sub numele de inegalitatea Craft-MacMillan . Acesta a fost derivat pentru prima dată de Leon Kraft în teza sa de master în 1949 [1] , dar el a luat în considerare doar codurile prefixelor, așa că atunci când discutăm despre codurile prefixelor, această inegalitate este adesea denumită pur și simplu inegalitatea lui Kraft . În 1956, Brockway Macmillan a dovedit necesitatea și suficiența acestei inegalități pentru o clasă mai generală de coduri, coduri separabile. [2]

Exemplu

Arbori binari

Orice arbore binar înrădăcinat poate fi văzut ca o descriere grafică a unui cod prefix peste un alfabet binar: caracterele alfabetului codificat corespund frunzelor arborelui, iar calea din arbore de la rădăcină la frunză specifică codul acestuia ( calea constă dintr-o succesiune de mișcări „stânga” și „dreapta” care corespund caracterelor 0 și 1).

Pentru astfel de arbori, inegalitatea Kraft-McMillan afirmă că:

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

unde este setul de frunze ale copacului și este adâncimea frunzei , numărul de margini de pe calea de la rădăcină la . $\mathcal{L}$ $\mathrm {adâncime} (x)$ $X$ $X$

Pentru arborele din figura din dreapta, avem:

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

Note

↑ Kraft, Leon G. (1949), A device for quantizing, grouping, and coding amplitude modulated pulses , Cambridge, MA: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology , < http://dspace.mit.edu/ handle/1721.1/12390 > Arhivat 22 aprilie 2009 la Wayback Machine
↑ McMillan, Brockway (1956), Două inegalități implicate de descifrabilitatea unică , IEEE Trans. Teoria informației vol . 2 (4 ) : 115–116, doi : 10.1109 /TIT.1956.1056818 ,

Literatură

Gashkov, S. B. Sisteme numerice și aplicarea lor . — M. : MTsNMO, 2004. — 52 p. — ISBN 5-94057-146-8 .
Cover, TM, Thomas, JA Elemente de teoria informației. - 2006. - P. 116. - ISBN 0-471-24195-4 .

Link -uri

Inegalitatea lui Kraft (NIST) Arhivat la 27 ianuarie 2009 la Wayback Machine
http://www.codingtheory.gorodok.net/seminars/seminar%2010.pdf Arhivat 5 martie 2016 la Wayback Machine