Kraft-McMillan egyenlőtlenség

A kódoláselméletben a Kraft-McMillan egyenlőtlenség szükséges és elégséges feltételt ad az elválasztható és előtag kódok létezéséhez, amelyek adott kódszóhosszúsággal rendelkeznek.

Előzetes meghatározások

Adjunk meg két tetszőleges véges halmazt , amelyeket rendre kódolt ábécének és kódolt ábécének nevezünk . Elemeiket karaktereknek , a karakterláncokat (véges hosszúságú sorozatokat) pedig szavaknak nevezzük . Egy szó hossza a szó karaktereinek száma.

Kódoló ábécéként gyakran egy halmazt tekintenek - az úgynevezett bináris vagy bináris ábécét. $\{0,1\}$

Az alfabetikus kódolási séma (vagy egyszerűen (alfabetikus) kód ) a kódolt ábécé karaktereinek bármilyen leképezése a kódoló ábécé szavaira, amelyeket kódszavaknak nevezünk . A kódolási séma használatával a kódolt ábécé minden szava társítható a kódjához - a szó minden karakterének megfelelő kódszavak összefűzésével .

Egy kódot elválaszthatónak (vagy egyedileg dekódolhatónak ) nevezünk, ha a kódolt ábécé két szava nem társítható ugyanahhoz a kódhoz.

Az előtag kód olyan alfabetikus kód, amelyben a kódszavak egyikesem más kódszó előtagja . Bármely előtag kód elválasztható.

Megfogalmazás

Macmillan tétele (1956) .

Legyen megadva a és szimbólumokból álló kódolt és kódoló ábécé , valamint a kódszavak kívánt hosszúsága: . Ekkor az adott kódszóhosszúságú elválasztható és előtag kódok létezésének szükséges és elégséges feltétele az egyenlőtlenség teljesülése: $n$ $d$ ${\displaystyle \ell _{1},\ell _{2},\ldots ,\ell _{n))$

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

Ezt az egyenlőtlenséget Craft-MacMillan egyenlőtlenségnek nevezik . Leon Kraft származtatta először 1949-es diplomamunkájában [1] , de ő csak az előtagkódokat vette figyelembe, így az előtagkódok tárgyalásakor ezt az egyenlőtlenséget gyakran egyszerűen Kraft-egyenlőtlenségnek nevezik . 1956-ban Brockway Macmillan bebizonyította ennek az egyenlőtlenségnek a szükségességét és elégségességét a kódok általánosabb osztályához, az elkülöníthető kódokhoz. [2]

Példa

Bináris fák

Bármilyen gyökeres bináris fa tekinthető egy bináris ábécé feletti előtagkód grafikus leírásának: a kódolt ábécé karakterei a fa leveleinek felelnek meg, és a fában a gyökértől a levélig vezető útvonal határozza meg a kódját ( az útvonal a 0 és 1 karaktereknek megfelelő „balra” és „jobbra” mozgássorozatból áll.

Az ilyen fák esetében a Kraft-McMillan egyenlőtlenség kimondja, hogy:

\sum _{x\in {\mathcal {L}}}2^{-\mathrm {mélység} (x)}\leqslant 1,

ahol a fa leveleinek halmaza, és a levél mélysége , a gyökértől a felé vezető úton lévő élek száma . $\mathcal{L}$ $\mathrm {mélység} (x)$ $x$ $x$

A jobb oldali ábrán látható fához a következők tartoznak:

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

Jegyzetek

↑ Kraft, Leon G. (1949), Eszköz amplitúdómodulált impulzusok kvantálására, csoportosítására és kódolására , Cambridge, MA: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology , < http://dspace.mit.edu/ handle/1721.1/12390 > Archiválva : 2009. április 22. a Wayback Machine -nél
↑ McMillan, Brockway (1956), Az egyedi megfejthetőségből fakadó két egyenlőtlenség , IEEE Trans. Információelmélet 2. kötet (4 ) : 115–116, doi : 10.1109 /TIT.1956.1056818 ,

Irodalom

Gashkov, S. B. Számrendszerek és alkalmazása . — M. : MTsNMO, 2004. — 52 p. — ISBN 5-94057-146-8 .
Cover, TM, Thomas, JA Az információelmélet elemei. - 2006. - P. 116. - ISBN 0-471-24195-4 .

Linkek

Kraft egyenlőtlensége (NIST) archiválva : 2009. január 27. a Wayback Machine -nél
http://www.codingtheory.gorodok.net/seminars/seminar%2010.pdf Archiválva : 2016. március 5. a Wayback Machine -nél