Kraft – McMillanova nerovnost - Kraft–McMillan inequality

v teorie kódování, Kraft – McMillanova nerovnost dává nezbytnou a dostatečnou podmínku pro existenci a kód předpony^[1] (ve verzi Leon G. Kraft) nebo jedinečně dekódovatelný kód (v Brockway McMillan verze pro danou sadu kódové slovo délky. Jeho aplikace pro prefixové kódy a stromy často nacházejí použití v počítačová věda a teorie informace.

Kraftova nerovnost byla zveřejněna v Kraft (1949). Kraftův článek však pojednává pouze o předponových kódech a připisuje analýze vedoucí k nerovnosti Raymond Redheffer. Výsledek byl nezávisle objeven v McMillan (1956). McMillan dokazuje výsledek pro obecný případ jednoznačně dekódovatelných kódů a verzi pro prefixové kódy připisuje mluvenému pozorování v roce 1955 Joseph Leo Doob.

Aplikace a intuice

Kraftova nerovnost omezuje délky kódových slov v a kód předpony: pokud si člověk vezme exponenciální délky každého platného kódového slova musí výsledná sada hodnot vypadat jako a funkce pravděpodobnostní hmotnosti, to znamená, že musí mít celkovou míru menší nebo rovnou jedné. Kraftovu nerovnost lze považovat za omezený rozpočet na kódová slova, přičemž kratší kódová slova jsou dražší. Mezi užitečné vlastnosti vyplývající z nerovnosti patří následující prohlášení:

Pokud Kraftova nerovnost platí s přísnou nerovností, kód nějaké má nadbytek.
Pokud Kraftova nerovnost platí s rovností, jedná se o úplný kód.
Pokud Kraftova nerovnost neplatí, kód není jedinečně dekódovatelné.
Pro každý jednoznačně dekódovatelný kód existuje předponový kód se stejnou distribucí délky.

Formální prohlášení

Nechte každý zdrojový symbol z abecedy

{ displaystyle S = {, s_ {1}, s_ {2}, ldots, s_ {n} , }}

být zakódovány do jednoznačně dekódovatelného kódu v abecedě velikosti ${ displaystyle r}$ s délkou kódového slova

{ displaystyle ell _ {1}, ell _ {2}, ldots, ell _ {n}.}

Pak

{ displaystyle sum _ {i = 1} ^ {n} r ^ {- ell _ {i}} leqslant 1.}

Naopak pro danou množinu přirozených čísel ${ displaystyle ell _ {1}, ell _ {2}, ldots, ell _ {n}}$ uspokojující výše uvedenou nerovnost, existuje jednoznačně dekódovatelný kód přes abecedu velikosti ${ displaystyle r}$ s těmi délkami kódového slova.

Příklad: binární stromy

9, 14, 19, 67 a 76 jsou listové uzly v hloubkách 3, 3, 3, 3, respektive 2.

Žádný binární strom lze považovat za definování kódu předpony pro listy stromu. Kraftova nerovnost to říká

{ displaystyle sum _ { ell in { text {listy}}} 2 ^ {- { text {depth}} ( ell)} leqslant 1.}

Zde je součet převzat listy stromu, tj. Uzly bez dětí. Hloubka je vzdálenost od kořenového uzlu. Ve stromu vpravo je tento součet

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

Důkaz

Důkaz kódů předpony

Příklad pro binární strom. Červené uzly představují strom předpony. Je zobrazena metoda výpočtu počtu potomků listových uzlů v celém stromu.

Nejprve si ukážeme, že Kraftova nerovnost platí kdykoli ${ displaystyle S}$ je kód předpony.

Předpokládejme to ${ displaystyle ell _ {1} leqslant ell _ {2} leqslant cdots leqslant ell _ {n}}$ . Nechat ${ displaystyle A}$ být plný ${ displaystyle r}$ -ary strom hloubky ${ displaystyle ell _ {n}}$ (tedy každý uzel ${ displaystyle A}$ na úrovni ${ displaystyle < ell _ {n}}$ má ${ displaystyle r}$ děti, zatímco uzly na úrovni ${ displaystyle ell _ {n}}$ jsou listy). Každé dlouhé slovo ${ displaystyle ell leqslant ell _ {n}}$ přes ${ displaystyle r}$ -ary abeceda odpovídá uzlu v tomto stromu v hloubce ${ displaystyle ell}$ . The ${ displaystyle i}$ th slovo v kód předpony odpovídá uzlu ${ displaystyle v_ {i}}$ ; nechat ${ displaystyle A_ {i}}$ být množina všech listových uzlů (tj. uzlů v hloubce ${ displaystyle ell _ {n}}$ ) v podstromu ${ displaystyle A}$ zakořeněné v ${ displaystyle v_ {i}}$ . Ten podstrom je výškový ${ displaystyle ell _ {n} - ell _ {i}}$ , my máme

{ displaystyle | A_ {i} | = r ^ { ell _ {n} - ell _ {i}}.}

Protože kód je kód předpony, tyto podstromy nemohou sdílet žádné listy, což znamená, že

{ displaystyle A_ {i} čepice A_ {j} = varnothing, quad i neq j.}

Tedy vzhledem k tomu, že celkový počet uzlů v hloubce ${ displaystyle ell _ {n}}$ je ${ displaystyle r ^ { ell _ {n}}}$ , my máme

{ displaystyle left | bigcup _ {i = 1} ^ {n} A_ {i} right | = sum _ {i = 1} ^ {n} | A_ {i} | = sum _ {i = 1} ^ {n} r ^ { ell _ {n} - ell _ {i}} leqslant r ^ { ell _ {n}}}

z čehož vyplývá výsledek.

Naopak vzhledem k jakékoli seřazené posloupnosti ${ displaystyle n}$ přirozená čísla,

{ displaystyle ell _ {1} leqslant ell _ {2} leqslant cdots leqslant ell _ {n}}

uspokojující Kraftovu nerovnost lze vytvořit kód předpony s délkou kódového slova rovnou každé ${ displaystyle ell _ {i}}$ výběrem slova délky ${ displaystyle ell _ {i}}$ libovolně, poté vyloučit všechna slova větší délky, která mají předponu. Znovu to budeme interpretovat jako listové uzly ${ displaystyle r}$ -ary strom hloubky ${ displaystyle ell _ {n}}$ . Nejprve vyberte libovolný uzel z celého stromu v hloubce ${ displaystyle ell _ {1}}$ ; odpovídá prvnímu slovu našeho nového kódu. Protože vytváříme kód předpony, všichni potomci tohoto uzlu (tj. Všechna slova, která mají toto první slovo jako předponu) se stanou nevhodnými pro zahrnutí do kódu. Uvažujeme o potomcích do hloubky ${ displaystyle ell _ {n}}$ (tj. uzly listů mezi potomky); existují ${ displaystyle r ^ { ell _ {n} - ell _ {1}}}$ takové potomky uzlů, které jsou odebrány z úvahy. Další iterace vybere (přežívající) uzel v hloubce ${ displaystyle ell _ {2}}$ a odstraní ${ displaystyle r ^ { ell _ {n} - ell _ {2}}}$ další listové uzly atd. Po ${ displaystyle n}$ iterací jsme odstranili celkem

{ displaystyle sum _ {i = 1} ^ {n} r ^ { ell _ {n} - ell _ {i}}}

uzly. Otázkou je, zda musíme odstranit více listových uzlů, než ve skutečnosti máme k dispozici - ${ displaystyle r ^ { ell _ {n}}}$ celkem - v procesu vytváření kódu. Protože Kraftova nerovnost platí, máme

{ displaystyle sum _ {i = 1} ^ {n} r ^ { ell _ {n} - ell _ {i}} leqslant r ^ { ell _ {n}}}

a tak lze vytvořit předponový kód. Vzhledem k tomu, že výběr uzlů v každém kroku je do značné míry libovolný, lze obecně vytvořit mnoho různých vhodných předponových kódů.

Důkaz obecného případu

Nyní dokážeme, že Kraftova nerovnost platí kdykoli ${ displaystyle S}$ je jednoznačně dekódovatelný kód. (Konverznost nemusí být prokázána, protože jsme ji již prokázali u kódů předpon, což je silnější tvrzení.)

Označit ${ displaystyle C = suma _ {i = 1} ^ {n} r ^ {- l_ {i}}}$ . Myšlenkou důkazu je získat horní hranici ${ displaystyle C ^ {m}}$ pro ${ displaystyle m in mathbb {N}}$ a ukázat, že může platit pouze pro všechny ${ displaystyle m}$ -li ${ displaystyle C leq 1}$ . Přepsat ${ displaystyle C ^ {m}}$ tak jako

{ displaystyle { begin {aligned} C ^ {m} & = left ( sum _ {i = 1} ^ {n} r ^ {- l_ {i}} right) ^ {m} & = sum _ {i_ {1} = 1} ^ {n} sum _ {i_ {2} = 1} ^ {n} cdots sum _ {i_ {m} = 1} ^ {n} r ^ {- left (l_ {i_ {1}} + l_ {i_ {2}} + cdots + l_ {i_ {m}} right)} end {aligned}}}

Zvažte vše m- síly ${ displaystyle S ^ {m}}$ , ve formě slov ${ displaystyle s_ {i_ {1}} s_ {i_ {2}} tečky s_ {i_ {m}}}$ , kde ${ displaystyle i_ {1}, i_ {2}, tečky, i_ {m}}$ jsou indexy mezi 1 a ${ displaystyle n}$ . Všimněte si, že, protože S byl považován za jednoznačně dekódovatelný, ${ displaystyle s_ {i_ {1}} s_ {i_ {2}} tečky s_ {i_ {m}} = s_ {j_ {1}} s_ {j_ {2}} tečky s_ {j_ {m}} }$ naznačuje ${ displaystyle i_ {1} = j_ {1}, i_ {2} = j_ {2}, tečky, i_ {m} = j_ {m}}$ . To znamená, že každý součet odpovídá přesně jednomu slovu ${ displaystyle S ^ {m}}$ . To nám umožňuje přepsat rovnici na

{ displaystyle C ^ {m} = součet _ { ell = 1} ^ {m cdot ell _ {max}} q _ { ell} , r ^ {- ell}}

kde ${ displaystyle q _ { ell}}$ je počet kódových slov v ${ displaystyle S ^ {m}}$ délky ${ displaystyle ell}$ a ${ displaystyle ell _ {max}}$ je délka nejdelšího kódového slova v ${ displaystyle S}$ . Pro ${ displaystyle r}$ - abeceda písmen existuje pouze ${ displaystyle r ^ { ell}}$ možná dlouhá slova ${ displaystyle ell}$ , tak ${ displaystyle q _ { ell} leq r ^ { ell}}$ . Pomocí toho jsme horní mez ${ displaystyle C ^ {m}}$ :

{ displaystyle { begin {aligned} C ^ {m} & = sum _ { ell = 1} ^ {m cdot ell _ {max}} q _ { ell} , r ^ {- ell } & leq sum _ { ell = 1} ^ {m cdot ell _ {max}} r ^ { ell} , r ^ {- ell} = m cdot ell _ { max} end {zarovnáno}}}

Užívání ${ displaystyle m}$ -tý kořen, máme

{ displaystyle C = součet _ {i = 1} ^ {n} r ^ {- l_ {i}} leq vlevo (m cdot ell _ {max} vpravo) ^ { frac {1} {m}}}

Tato vazba platí pro všechny ${ displaystyle m in mathbb {N}}$ . Pravá strana je 1 asymptoticky, takže ${ displaystyle sum _ {i = 1} ^ {n} r ^ {- l_ {i}} leq 1}$ musí držet (jinak by byla nerovnost dostatečně velká ${ displaystyle m}$ ).

Alternativní konstrukce pro konverzaci

Vzhledem k posloupnosti ${ displaystyle n}$ přirozená čísla,

{ displaystyle ell _ {1} leqslant ell _ {2} leqslant cdots leqslant ell _ {n}}

uspokojením Kraftovy nerovnosti můžeme zkonstruovat kód předpony následovně. Definujte i^th kódové slovo, C_i, být první ${ displaystyle ell _ {i}}$ číslice za bod radixu (např. desetinná čárka) v základně r zastoupení

{ displaystyle sum _ {j = 1} ^ {i-1} r ^ {- ell _ {j}}.}

Všimněte si, že podle Kraftovy nerovnosti není tento součet nikdy větší než 1. Proto kódová slova zachycují celou hodnotu součtu. Proto pro j > i, první ${ displaystyle ell _ {i}}$ číslice C_j tvoří větší počet než C_i, takže kód je bez předpony.

Poznámky

^ Cover, Thomas M .; Thomas, Joy A. (2006), „Komprese dat“, Základy teorie informace (2. vyd.), John Wiley & Sons, Inc, str. 108–109, doi:10.1002 / 047174882X.ch5, ISBN 978-0-471-24195-9

Reference

Kraft, Leon G. (1949), Zařízení pro kvantování, seskupování a kódování pulzů modulovaných amplitudou, Cambridge, MA: MS Thesis, Katedra elektrotechniky, Massachusetts Institute of Technology, hdl:1721.1/12390.

McMillan, Brockway (1956), „Dvě nerovnosti vyplývající z jedinečné dešifrovatelnosti“, IEEE Trans. Inf. Teorie, 2 (4): 115–116, doi:10.1109 / TIT.1956.1056818.

Viz také

[EIT-1] Cover, Thomas M .; Thomas, Joy A. (2006), „Komprese dat“, Základy teorie informace (2. vyd.), John Wiley & Sons, Inc, str. 108–109, doi:10.1002 / 047174882X.ch5, ISBN 978-0-471-24195-9

[1]