Kraft-McMillan ojämlikhet

I kodningsteorin ger Kraft-McMillan-ojämlikheten ett nödvändigt och tillräckligt villkor för existensen av separerbara koder och prefixkoder som har en given uppsättning kodordslängder.

Preliminära definitioner

Låt två godtyckliga ändliga uppsättningar ges , som kallas respektive det kodade alfabetet och det kodade alfabetet . Deras element kallas tecken , och strängar (sekvenser av ändlig längd) av tecken kallas ord . Längden på ett ord är antalet tecken det består av.

Som ett kodningsalfabet betraktas ofta en uppsättning - det så kallade binära eller binära alfabetet. $\{0,1\}$

Ett alfabetiskt kodningsschema (eller helt enkelt (alfabetisk) kod ) är varje mappning av tecknen i det kodade alfabetet till ord i kodningsalfabetet, som kallas kodord . Med hjälp av kodningsschemat kan varje ord i det kodade alfabetet associeras med dess kod - sammanlänkningen av kodord som motsvarar varje tecken i detta ord.

En kod kallas separerbar (eller unikt avkodbar ) om inte två ord i det kodade alfabetet kan associeras med samma kod.

En prefixkod är en alfabetisk kod där inget av kodorden är ett prefix till något annat kodord. Alla prefixkoder kan separeras.

Formulering

Macmillans teorem (1956) .

Låt de kodade och kodande alfabeten som består av respektive symboler anges och de önskade längderna på kodorden anges: . Då är ett nödvändigt och tillräckligt villkor för att det finns separerbara koder och prefixkoder med en given uppsättning kodordslängder uppfyllandet av olikheten: $n$ $d$ ${\displaystyle \ell _{1},\ell _{2},\ldots ,\ell _{n))$

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

Denna ojämlikhet är känd som Craft-MacMillan ojämlikhet . Det härleddes först av Leon Kraft i sin masteruppsats 1949 [1] , men han betraktade endast prefixkoder, så när man diskuterar prefixkoder kallas denna ojämlikhet ofta helt enkelt som Krafts ojämlikhet . 1956 bevisade Brockway Macmillan nödvändigheten och tillräckligheten av denna ojämlikhet för en mer allmän klass av koder, separerbara koder. [2]

Exempel

Binära träd

Alla rotade binära träd kan ses som en grafisk beskrivning av en prefixkod över ett binärt alfabet: tecknen i det kodade alfabetet motsvarar trädets löv, och sökvägen i trädet från roten till bladet anger dess kod ( banan består av en sekvens av rörelser "vänster" och "höger" som motsvarar tecknen 0 och 1).

För sådana träd säger Kraft-McMillan ojämlikheten att:

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

var är trädets lövuppsättning, och är bladets djup , antalet kanter på banan från roten till . $\mathcal{L}$ $\mathrm {djup} (x)$ $x$ $x$

För trädet i figuren till höger har vi:

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

Anteckningar

↑ Kraft, Leon G. (1949), En anordning för att kvantisera, gruppera och koda amplitudmodulerade pulser , Cambridge, MA: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology , < http://dspace.mit.edu/ handle/1721.1/12390 > Arkiverad 22 april 2009 på Wayback Machine
↑ McMillan, Brockway (1956), Two inequalities implied by unique dechifferability , IEEE Trans. Information Theory vol 2 (4 ) : 115–116, doi : 10.1109 /TIT.1956.1056818 ,

Litteratur

Gashkov, S. B. Nummersystem och deras tillämpning . — M. : MTsNMO, 2004. — 52 sid. — ISBN 5-94057-146-8 .
Cover, TM, Thomas, JA Inslag av informationsteori. - 2006. - S. 116. - ISBN 0-471-24195-4 .

Länkar

Krafts ojämlikhet (NIST) Arkiverad 27 januari 2009 på Wayback Machine
http://www.codingtheory.gorodok.net/seminars/seminar%2010.pdf Arkiverad 5 mars 2016 på Wayback Machine