Kraftova nerovnost

Kraftova nerovnost je věta užívaná v teorii kódování. Udává omezení na délky kódových slov, které musí splňovat daný kód, aby mohl být kódem prefixovým. Zobecnění Kraftovy nerovnosti pro libovolný jednoznačně dekódovatelný kód se pak nazývá McMillanova věta.

Kraftova nerovnost

Matematicky lze Kraftovu nerovnost formulovat takto: Uvažujme \scriptstyle D-znakový prefixový kód kódující \scriptstyle r různých zpráv pomocí kódových slov délek \scriptstyle l_1, l_2, \ldots, l_r . Pak musí být splněna nerovnost

: \sum_{i=1}^r D^{-l_i} \leq 1 .

Naopak, pokud přirozená čísla \scriptstyle l_1, l_2, \ldots, l_r splňují výše uvedenou nerovnost, tak existuje prefixový kód s \scriptstyle D znaky a délkami kódových slov \scriptstyle l_1, l_2, \ldots, l_r .

Pozn: Číslo \scriptstyle D tedy představuje počet znaků, pomocí nichž kódujeme zprávy přicházející ze zdroje, pro binární kód je \scriptstyle D = 2, což odpovídá znakům 0 a 1. Po zakódování takovýmto kódem tedy z dané zprávy dostaneme posloupnost nul a jedniček. +more Pro ternární kódy máme \scriptstyle D = 3 (tj. znaky 0, 1, 2) atd. Hodnota \scriptstyle r udává, kolik různých zpráv chceme být schopni pomocí našeho kódu zakódovat. Čísla \scriptstyle l_1, l_2, \ldots, l_r pak označují délky jednotlivých kódových slov, tzn. máme-li danou \scriptstyle i-tou zprávu, tak \scriptstyle l_i udává počet znaků v posloupnosti použité pro zakódování této zprávy, např. pro \scriptstyle i-tou zprávu, jejíž kódové slovo je 00101 je \scriptstyle l_i = 5 .

Příklad

Uvažujme binární prefixový kód pro kódování cifer 0,1,2,…,9 vhodný pro zprávy, kde se často vyskytují znaky 0, 1 a řídce znaky 8, 9. (Máme tedy \scriptstyle D = 2 a \scriptstyle r = 10. +more) Nápad: pro 0 a 1 zvolíme kódové slovo délky 2, pro číslice 2 až 7 zvolíme kódové slovo délky 3 pro 8 a 9 zvolíme kódové slovo délky 4. Potom by převodní tabulka vypadala takto:.

0 00

1 01

2 1xx

3 1xx

4 1xx

5 1xx

6 1xx

7 1xx

8 xxxx

9 xxxx

Kombinace 1xx musí začínat jedničkou, aby byl kód prefixový, ale neposkytuje dost kombinací pro šest čísel. Kraftova nerovnost to předem říká ve výpočtu:

: 2 \cdot 2^{-2} + 6 \cdot 2^{-3} + 2 \cdot 2^{-4} = \frac{22}{16} > 1.

Naproti tomu kód

0 00

1 01

2 100

3 1010

4 1011

5 1100

6 1101

7 1110

8 11110

9 11111

prefixový je neboť:

: 2 \cdot 2^{-2} + 1 \cdot 2^{-3} + 5 \cdot 2^{-4} + 2 \cdot 2^{-5} = \frac{16 + 4 + 10 + 2}{32} = 1.

Důkaz

Zde uvedený důkaz byl převzat ze skript I. Vajdy . +more Nejprve bez újmy na obecnosti předpokládejme, že \scriptstyle l_1 \leq l_2 \leq \ldots \leq l_r a uvažujme \scriptstyle D-ární stromový graf, tj. z každého vrcholu grafu vychází krom vstupního právě \scriptstyle D dalších vrcholů-potomků. Na počátku tedy máme kořenový vrchol, z něhož vychází \scriptstyle D větví, z nichž se pak každá dělí na dalších \scriptstyle D větví, tj. celkem na \scriptstyle D^2 větví. Z tohoto je vidět, že na \scriptstyle i-té úrovni stromu se nachází \scriptstyle D^i vrcholů, kde kořenu odpovídá nultá úroveň. Pokud má tedy strom celkem \scriptstyle r úrovní, tak na této poslední úrovni se nachází \scriptstyle D^r vrcholů.

Tento stromový graf popisuje všechny možné kombinace znaků našeho kódu délky \scriptstyle r. Tj. +more pokud bychom měli binární kód kódující tři zprávy, tak by mu odpovídal binární strom o třech úrovních. Pokud by v binárním stromě vrchol pro nulu ležel nalevo od předchůdce a jednička napravo od něj, tak zprávu 001 bychom mohli vyjádřit jako cestu stromem z kořene do levého vrcholu (první nula), z něj do dalšího levého vrcholu (druhá nula) a z něj nakonec do pravého vrcholu (jednička na konci).

Uvažujme nyní konkrétní vrchol na \scriptstyle i_0-té úrovni, kde \scriptstyle i_0 je pevně zvolené číslo mezi nulou a \scriptstyle r. Když budeme chápat tento vrchol jako kořen nového \scriptstyle D-árního stromu (tj. +more podstromu původně uvažovaného stromu o celkem \scriptstyle r úrovních), tak tento strom bude mít celkem \scriptstyle r - i_0 úrovní a na své poslední úrovni bude mít \scriptstyle D^{r - i_0} vrcholů.

Nejprve dokážeme implikaci zleva, tj. máme prefixový kód a chceme ukázat, že musí platit Kraftova nerovnost.

Mějme tedy \scriptstyle D-ární strom o \scriptstyle r úrovních a podívejme se na \scriptstyle l_1-tou úroveň. Zde vezměme jeden vrchol a odřízněme větve z něj vycházející. +more Podíváme-li se nyní na poslední, tj. \scriptstyle r-tou úroveň, stromu, tak tam ubylo \scriptstyle D^{r - l_1} vrcholů spojených s výše vybraným vrcholem. Na úrovni \scriptstyle l_1 nám teď zbývá \scriptstyle D^{l_1} - 1 vrcholů, z nichž vedou větve. Vyjděme z některého z nich, dojděme na úroveň \scriptstyle l_2 a aplikujme postup obdobný tomu výše. Takto pokračujme až na \scriptstyle r-tou úroveň. Zde by se mohlo namítnout, že odřezáváním nemáme zajištěno, že nějaký vrchol na této úrovni vůbec zůstane. Jenomže my jsme uvažovali prefixový kód, tzn. pokud mám na \scriptstyle l_i-té úrovni vrchol, tj. mám kódové slovo délky \scriptstyle l_i, tak už neexistují kódová slova, která by měla toto slovo jako prefix. Neboli mám-li na úrovni \scriptstyle l_i vrchol odpovídající danému kódovému slovu a odříznu všechny z něj vycházející vrcholy, tak žádný z těchto odříznutých vrcholů neodpovídá kódovému slovu. Protože nyní předpokládáme, že existuje kódové slovo délky \scriptstyle l_r, tak nutně musí existovat vrchol stromu na úrovni \scriptstyle l_r.

Zapišme nyní, co odřezávání znamená pro počet vrcholů na poslední, tj. \scriptstyle r-té, úrovni stromového grafu. +more Pro každé \scriptstyle i \in \{ 1, \ldots, r \} jsme odřezáním přišli o \scriptstyle D^{r - l_i} vrcholů ležících na \scriptstyle r-té úrovni. Protože odřezaných vrcholů na této úrovni nemůže být víc než celkový počet vrcholů na této úrovni, který je roven \scriptstyle D^r, dostáváme nerovnost.

: \sum_{i=1}^r D^{r - l_i} \leq D^r .

Když tuto nerovnost vydělíme její pravou stranou obdržíme Kraftovu nerovnost.

Dokážeme nyní opačnou implikaci, tj. máme přirozená čísla \scriptstyle l_1 \leq l_2 \leq \ldots \leq l_r a \scriptstyle D splňující Kraftovu nerovnost. +more Z výše popsaného postupu je zřejmé, že existuje stromový graf o \scriptstyle D úrovních takový, že na \scriptstyle l_i-té úrovni (pro každé \scriptstyle i \in \{ 1, \ldots, r\}) se bude nacházet vrchol, z něhož už žádné vrcholy vycházet nebudou. Těmto vrcholům můžeme přiřadit kódové slovo (vezmu cestu od kořene k tomuto vrcholu a podle toho, kterou větví jsem v \scriptstyle i-tém kroku procházel, tak na \scriptstyle i pozici ve slově napíšu jeden ze znaků 0, 1 až D). Takto zkonstruovaný kód je zřejmě prefixový.

Zobecnění Kraftovy nerovnosti

Kraftovu nerovnost lze vyslovit nejen pro konečný počet zpráv, ale i pro spočetnou množinu zpráv. Tvrzení výše lze proto formulovat i pro \scriptstyle r = \infty. +more Neboli: Pro délky \scriptstyle l_1, l_2, \ldots spočetně mnoha kódových slov přináležejících prefixovému \scriptstyle D-znakovému kódu platí.

: \sum_{i=1}^\infty D^{-l_i} \leq 1 .

Naopak, splňují-li přirozená čísla tuto nerovnost, tak existuje prefixový \scriptstyle D-znakový kód s těmito délkami slov.

Pozn: Další zobecnění (pro jednoznačně dekódovatelné kódy) pak představuje McMillanova věta (viz níže).

Důkaz zobecněného tvrzení

Zde uvedený důkaz lze použít i pro tvrzení s \scriptstyle r konečným, můžeme ho tedy chápat jako alternativu k výše uvedenému důkazu. I tento důkaz byl převzat ze skript .

Dokažme nejdříve implikaci zleva, tj. máme slova délek \scriptstyle l_1, l_2, \ldots a chceme odvodit Kraftovu nerovnost. +more Mějme \scriptstyle i-té kódové slovo, to má délku \scriptstyle l_i. Můžeme ho tedy vyjádřit jako posloupnost znaků \scriptstyle z_1 z_2 \ldots z_{l_i}. Každý znak \scriptstyle z_j nabývá hodnot \scriptstyle 0 až \scriptstyle D-1 a dané kódové slovo můžeme tedy chápat jako číslo v \scriptstyle D-znakové číselné soustavě. Konkrétně, lze ho chápat jako desetinný rozvoj čísla nacházejícího se mezi 0 a 1 následujícím způsobem.

:0,z_1 z_2 \ldots z_{l_i} = \sum_{j=1}^{l_i} z_j D^{-j}.

Neboť nyní předpokládáme, že náš kód je prefixový, je zobrazení, které kódovému slovu přiřazuje číslo z intervalu [0,1] výše uvedeným způsobem, prosté. Není těžké si rozmyslet, že prefixovost kódu zaručuje následující vlastnost: jestliže \scriptstyle k-té slovo je délky \scriptstyle l_k splňující \scriptstyle l_k \geq l_i, tak jemu odpovídající číslo neleží v intervalu

:I(l_i) = (0,z_1 z_2 \ldots z_{l_i}; 0,z_1 z_2 \ldots z_{l_i} + D^{-l_i}).

Pro názornost na chvíli uvažujme konkrétní příklad, kdy je \scriptstyle I(l_i) = (0,536; 0,537), tj. \scriptstyle l_i = 3. +more Patří do něj třeba čísla 0,5361 nebo 0,5369, neleží v něm ale čísla 0,536 a 0,537 (jedná se o otevřený interval). Z tohoto příkladu je patrné, že kdyby v intervalu \scriptstyle I(l_i) leželo \scriptstyle k-té slovo, tak by muselo mít prvních \scriptstyle l_i znaků shodných s \scriptstyle i-tým slovem, což je spor s prefixovostí kódu, kterou jsme předpokládali.

Máme tedy každému kódovému slovu jednoznačně přiřazen interval délky \scriptstyle D^{-l_i}, který je disjunktní s kterýmkoli jiným intervalem odpovídajím odlišnému slovu. Navíc všechny tyto intervaly leží v intervalu [0,1] a to musí platit i pro jejich sjednocení. +more Protože jsou všechny intervaly navzájem disjunktní je míra jejich sjednocení rovna součtu jejich délek. Míra sjednocení je navíc seshora omezena délkou intervalu [0,1], tzn. jedničkou. Zapíšeme-li tento argument pomocí matematických symbolů, dostáváme okamžitě zobecněnou Kraftovu nerovnost.

Dokažme nyní druhou implikaci. Máme tedy přirozená čísla \scriptstyle l_1, l_2, \ldots splňující danou nerovnost a chceme najít prefixový kód, jehož kódová slova budou mít délky \scriptstyle l_1, l_2, \ldots . +more Označme si \scriptstyle I_1 = [0,1] a vyberme z něj libovolné číslo \scriptstyle 0,z_1 z_2 \ldots . Prvních \scriptstyle l_1 znaků tohoto čísla (v daném pořadí) interpretujeme jako kódové slovo našeho kódu. Sestrojíme nyní množinu \scriptstyle I_2 = I_1 - I(l_1), kde \scriptstyle I(l_1) je interval definovaný výše v první polovině důkazu. Analogický postup neustále opakujeme, čímž dostaneme posloupnost intervalů \scriptstyle I_1, I_2, \ldots, kde \scriptstyle I_n = I_{n-1} - I(l_{n-1}). Z Kraftovy nerovnosti plyne, že \scriptstyle I_n nebude nikdy prázdná a fakt, že intervaly \scriptstyle I_1, I_2, \ldots jsou disjunktní, zajišťuje, že námi vytvářená slova odpovídají prefixovému kódu.

McMillanova věta

McMillanova věta je tvrzení z oblasti teorie informace, které dává do vztahu délky kódových slov jednoznačně dekódovatelných kódů. Jedná se o zobecnění Kraftovy nerovnosti, která je primárně dokázána pro prefixové kódy (ty tvoří podmnožinu množiny jednoznačně dekódovatelných kódů). +more Větu lze vyslovit v následujícím znění:.

Délky slov \scriptstyle l_i libovolného jednoznačně dekódovatelného \scriptstyle D-znakového kódu splňují nerovnost

:\sum_{i=1}^\infty D^{-l_i} \leq 1.

Pozn: Číslo \scriptstyle D tedy představuje počet znaků, pomocí nichž kódujeme zprávy přicházející ze zdroje, pro binární kód je \scriptstyle D = 2, což odpovídá znakům 0 a 1. Po zakódování takovýmto kódem tedy z dané zprávy dostaneme posloupnost nul a jedniček. +more Pro ternární kódy máme \scriptstyle D = 3 (tj. znaky 0, 1, 2) atd. Čísla \scriptstyle l_1, l_2, \ldots pak označují délky jednotlivých kódových slov. To znamená, máme-li danou \scriptstyle i-tou zprávu, tak \scriptstyle l_i udává počet znaků v posloupnosti použité pro zakódování této zprávy, např. pro \scriptstyle i-tou zprávu, jejíž kódové slovo je 00101, je \scriptstyle l_i = 5 .

Důkaz McMillanovy věty

Následující důkaz je též převzat ze skript I. Vajdy . +more Důkaz provedeme ve dvou krocích, nejprve dokážeme nerovnost pro jednoznačně dekódovatelné kódy s konečným počtem kódových slov. Poté zobecníme toto prozatímní tvrzení i na kódy s nespočetně mnoha slovy.

Ukažme nejprve, že když \scriptstyle l(x) jsou délky slov jednoznačně dekódovatelného kódu \scriptstyle C: \mathcal{X} \to \mathcal{D}^\ast konečného zdroje \scriptstyle (\mathcal{X},p), tak platí

:\sum_{x \in \mathcal{X}} D^{-l(x)} \leq 1.

Nechť \scriptstyle C^n: \mathcal{X}^n \to \mathcal{D}^n je rozšíření kódu \scriptstyle C a \scriptstyle \mathbf{x} = (x_1, \ldots, x_n) \in \mathcal{X}^n je jistá zpráva. Pak délky \scriptstyle l(x) slov \scriptstyle C^n(\mathbf{x}) (obraz zprávy \scriptstyle \mathbf{x} při kódování \scriptstyle C^n) splňují podmínku

:l(x) = \sum_{i=1}^n l(x_i).

Z toho plyne

: \left( \sum_{x \in \mathcal{X}} D^{-l(x)} \right)^n = \sum_{\mathbf{x} \in \mathcal{X}^n} D^{-l(\mathbf{x})} = \sum_{k=1}^{n \cdot l_{\mathrm{max}}} m(k) D^{-k},

kde \scriptstyle l_{\mathrm{max}} = \max_{x \in \mathcal{X}} (l(x)) a symbol \scriptstyle m(k) udává počet zpráv \scriptstyle \mathbf{x} \in \mathcal{X}^n zakódovaných do slov délky \scriptstyle k. Protože je kód jednoznačně dekódovatelný, nejvýše jedno \scriptstyle \mathbf{x} \in \mathcal{X}^n se zobrazí do slova délky \scriptstyle k a proto \scriptstyle m(k) \leq D^k. +more Tedy.

: \left( \sum_{x \in \mathcal{X}} D^{-l(x)} \right)^n \leq \sum_{k=1}^{n \cdot l_{\mathrm{max}}} D^k D^{-k} = n \cdot l_{\mathrm{max}}.

Odsud dostáváme

:\sum_{x \in \mathcal{X}} D^{-l(x)} \leq (n l_{\mathrm{max}})^{\frac{1}{n}} \to 1 \quad \text{pro} \quad n \to \infty.

Neboť můžeme \scriptstyle n volit libovolně, dokázali jsme tak tvrzení pro konečné zdroje.

Důkaz dokončíme tak, že si uvědomíme, že podmnožina kterýchkoli \scriptstyle m slov jednoznačně dekódovatelného kódu představuje jednoznačně dekódovatelný kód. Na něj můžeme použít tvrzení dokázané v první části tohoto důkazu, čímž dostaneme

:\sum_{i=1}^m D^{-l_i} \leq 1 \quad \text{pro} \quad m = 1, 2, \ldots

Stačí už tedy jen vzít limitu pro \scriptstyle m \to \infty a zobecněné tvrzení pro spočetně mnoho kódových slov je dokázáno.

Reference

Kategorie:Kódování