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 $D$-znakový prefixový kód kódující $r$ různých zpráv pomocí kódových slov délek $l_1,l_2,\dots ,l_r$. Pak musí být splněna nerovnost

$\sum _{i=1}^r{D}^{-l_i}\le 1$.

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

Pozn: Číslo $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 $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. Pro ternární kódy máme $D=3$ (tj. znaky 0, 1, 2) atd. Hodnota $r$ udává, kolik různých zpráv chceme být schopni pomocí našeho kódu zakódovat. Čísla $l_1,l_2,\dots ,l_r$ pak označují délky jednotlivých kódových slov, tzn. máme-li danou $i$-tou zprávu, tak $l_i$ udává počet znaků v posloupnosti použité pro zakódování této zprávy, např. pro $i$-tou zprávu, jejíž kódové slovo je 00101 je $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 $D=2$ a $r=10$.) 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 . Nejprve bez újmy na obecnosti předpokládejme, že $l_1\le l_2\le \dots \le l_r$ a uvažujme $D$-ární stromový graf, tj. z každého vrcholu grafu vychází krom vstupního právě $D$ dalších vrcholů-potomků. Na počátku tedy máme kořenový vrchol, z něhož vychází $D$ větví, z nichž se pak každá dělí na dalších $D$ větví, tj. celkem na $D^2$ větví. Z tohoto je vidět, že na $i$-té úrovni stromu se nachází $D^i$ vrcholů, kde kořenu odpovídá nultá úroveň. Pokud má tedy strom celkem $r$ úrovní, tak na této poslední úrovni se nachází $D^r$ vrcholů.

Tento stromový graf popisuje všechny možné kombinace znaků našeho kódu délky $r$. Tj. 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 $i_0$-té úrovni, kde $i_0$ je pevně zvolené číslo mezi nulou a $r$. Když budeme chápat tento vrchol jako kořen nového $D$-árního stromu (tj. podstromu původně uvažovaného stromu o celkem $r$ úrovních), tak tento strom bude mít celkem $r-i_0$ úrovní a na své poslední úrovni bude mít $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 $D$-ární strom o $r$ úrovních a podívejme se na $l_1$-tou úroveň. Zde vezměme jeden vrchol a odřízněme větve z něj vycházející. Podíváme-li se nyní na poslední, tj. $r$-tou úroveň, stromu, tak tam ubylo $D^{r-l_1}$ vrcholů spojených s výše vybraným vrcholem. Na úrovni $l_1$ nám teď zbývá $D^{l_1}-1$ vrcholů, z nichž vedou větve. Vyjděme z některého z nich, dojděme na úroveň $l_2$ a aplikujme postup obdobný tomu výše. Takto pokračujme až na $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 $l_i$-té úrovni vrchol, tj. mám kódové slovo délky $l_i$, tak už neexistují kódová slova, která by měla toto slovo jako prefix. Neboli mám-li na úrovni $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 $l_r$, tak nutně musí existovat vrchol stromu na úrovni $l_r$.

Zapišme nyní, co odřezávání znamená pro počet vrcholů na poslední, tj. $r$-té, úrovni stromového grafu. Pro každé $i\in \{1,\dots ,r\}$ jsme odřezáním přišli o $D^{r-l_i}$ vrcholů ležících na $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 $D^r$, dostáváme nerovnost

$\sum _{i=1}^r{D}^{r-l_i}\le 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 $l_1\le l_2\le \dots \le l_r$ a $D$ splňující Kraftovu nerovnost. Z výše popsaného postupu je zřejmé, že existuje stromový graf o $D$ úrovních takový, že na $l_i$-té úrovni (pro každé $i\in \{1,\dots ,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 $i$-tém kroku procházel, tak na $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 $r=\mathrm{\infty }$. Neboli: Pro délky $l_1,l_2,\dots$ spočetně mnoha kódových slov přináležejících prefixovému $D$-znakovému kódu platí

$\sum _{i=1}^{\mathrm{\infty }}{D}^{-l_i}\le 1$.

Naopak, splňují-li přirozená čísla tuto nerovnost, tak existuje prefixový $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 $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 $l_1,l_2,\dots$ a chceme odvodit Kraftovu nerovnost. Mějme $i$-té kódové slovo, to má délku $l_i$. Můžeme ho tedy vyjádřit jako posloupnost znaků $z_1{z}_2\dots z_{l_i}$. Každý znak $z_j$ nabývá hodnot $0$ až $D-1$ a dané kódové slovo můžeme tedy chápat jako číslo v $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\dots 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 $k$-té slovo je délky $l_k$ splňující $l_k\ge l_i$, tak jemu odpovídající číslo neleží v intervalu

$I(l_i)=(0,z_1{z}_2\dots z_{l_i};0,z_1{z}_2\dots z_{l_i}+D^{-l_i})$.

Pro názornost na chvíli uvažujme konkrétní příklad, kdy je $I(l_i)=(0,536;0,537)$, tj. $l_i=3$. 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 $I(l_i)$ leželo $k$-té slovo, tak by muselo mít prvních $l_i$ znaků shodných s $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 $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í. 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 $l_1,l_2,\dots$ splňující danou nerovnost a chceme najít prefixový kód, jehož kódová slova budou mít délky $l_1,l_2,\dots$. Označme si $I_1=[0,1]$ a vyberme z něj libovolné číslo $0,z_1{z}_2\dots$. Prvních $l_1$ znaků tohoto čísla (v daném pořadí) interpretujeme jako kódové slovo našeho kódu. Sestrojíme nyní množinu $I_2=I_1-I(l_1)$, kde $I(l_1)$ je interval definovaný výše v první polovině důkazu. Analogický postup neustále opakujeme, čímž dostaneme posloupnost intervalů $I_1,I_2,\dots$, kde $I_n=I_{n-1}-I(l_{n-1})$. Z Kraftovy nerovnosti plyne, že $I_n$ nebude nikdy prázdná a fakt, že intervaly $I_1,I_2,\dots$ 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ů). Větu lze vyslovit v následujícím znění:

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

$\sum _{i=1}^{\mathrm{\infty }}{D}^{-l_i}\le 1$.

Pozn: Číslo $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 $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. Pro ternární kódy máme $D=3$ (tj. znaky 0, 1, 2) atd. Čísla $l_1,l_2,\dots$ pak označují délky jednotlivých kódových slov. To znamená, máme-li danou $i$-tou zprávu, tak $l_i$ udává počet znaků v posloupnosti použité pro zakódování této zprávy, např. pro $i$-tou zprávu, jejíž kódové slovo je 00101, je $l_i=5$.

Důkaz McMillanovy věty

Následující důkaz je též převzat ze skript I. Vajdy . 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ž $l(x)$ jsou délky slov jednoznačně dekódovatelného kódu $C:𝒳\to {𝒟}^{\ast }$ konečného zdroje $(𝒳,p)$, tak platí

$\sum _{x\in 𝒳}{D}^{-l(x)}\le 1.$

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

$l(x)=\sum _{i=1}^{n}l(x_i)$.

Z toho plyne

${\left(\sum _{x\in 𝒳}{D}^{-l(x)}\right)}^n=\sum _{𝐱\in {𝒳}^n}{D}^{-l(𝐱)}=\sum _{k=1}^{n\cdot l_{\mathrm{m}\mathrm{a}\mathrm{x}}}m(k)D^{-k}$,

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

${\left(\sum _{x\in 𝒳}{D}^{-l(x)}\right)}^n\le \sum _{k=1}^{n\cdot l_{\mathrm{m}\mathrm{a}\mathrm{x}}}{D}^k{D}^{-k}=n\cdot l_{\mathrm{m}\mathrm{a}\mathrm{x}}.$

Odsud dostáváme

$\sum _{x\in 𝒳}{D}^{-l(x)}\le (n{l}_{\mathrm{m}\mathrm{a}\mathrm{x}}{)}^{\frac{1}{n}}\to 1\text{pro}n\to \mathrm{\infty }.$

Neboť můžeme $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 $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}\le 1\text{pro}m=1,2,\dots$

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