Přeskočit na obsah

Kraftova nerovnost

Z Wikipedie, otevřené encyklopedie

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

[editovat | editovat zdroj]

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

.

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

Pozn: Číslo tedy představuje počet znaků, pomocí nichž kódujeme zprávy přicházející ze zdroje, pro binární kód je , 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 (tj. znaky 0, 1, 2) atd. Hodnota udává, kolik různých zpráv chceme být schopni pomocí našeho kódu zakódovat. Čísla pak označují délky jednotlivých kódových slov, tzn. máme-li danou -tou zprávu, tak udává počet znaků v posloupnosti použité pro zakódování této zprávy, např. pro -tou zprávu, jejíž kódové slovo je 00101 je .

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 a .) 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:

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ť:

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

Tento stromový graf popisuje všechny možné kombinace znaků našeho kódu délky . 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 -té úrovni, kde je pevně zvolené číslo mezi nulou a . Když budeme chápat tento vrchol jako kořen nového -árního stromu (tj. podstromu původně uvažovaného stromu o celkem úrovních), tak tento strom bude mít celkem úrovní a na své poslední úrovni bude mít vrcholů.

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

Mějme tedy -ární strom o úrovních a podívejme se na -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. -tou úroveň, stromu, tak tam ubylo vrcholů spojených s výše vybraným vrcholem. Na úrovni nám teď zbývá vrcholů, z nichž vedou větve. Vyjděme z některého z nich, dojděme na úroveň a aplikujme postup obdobný tomu výše. Takto pokračujme až na -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 -té úrovni vrchol, tj. mám kódové slovo délky , tak už neexistují kódová slova, která by měla toto slovo jako prefix. Neboli mám-li na úrovni 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 , tak nutně musí existovat vrchol stromu na úrovni .

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

.

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 a splňující Kraftovu nerovnost. Z výše popsaného postupu je zřejmé, že existuje stromový graf o úrovních takový, že na -té úrovni (pro každé ) 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 -tém kroku procházel, tak na pozici ve slově napíšu jeden ze znaků 0, 1 až D). Takto zkonstruovaný kód je zřejmě prefixový.

Zobecnění Kraftovy nerovnosti

[editovat | editovat zdroj]

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 . Neboli: Pro délky spočetně mnoha kódových slov přináležejících prefixovému -znakovému kódu platí

.

Naopak, splňují-li přirozená čísla tuto nerovnost, tak existuje prefixový -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í

[editovat | editovat zdroj]

Zde uvedený důkaz lze použít i pro tvrzení s 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 [1].

Dokažme nejdříve implikaci zleva, tj. máme slova délek a chceme odvodit Kraftovu nerovnost. Mějme -té kódové slovo, to má délku . Můžeme ho tedy vyjádřit jako posloupnost znaků . Každý znak nabývá hodnot a dané kódové slovo můžeme tedy chápat jako číslo v -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

.

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 -té slovo je délky splňující , tak jemu odpovídající číslo neleží v intervalu

.

Pro názornost na chvíli uvažujme konkrétní příklad, kdy je , tj. . 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 leželo -té slovo, tak by muselo mít prvních znaků shodných s -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 , 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 splňující danou nerovnost a chceme najít prefixový kód, jehož kódová slova budou mít délky . Označme si a vyberme z něj libovolné číslo . Prvních znaků tohoto čísla (v daném pořadí) interpretujeme jako kódové slovo našeho kódu. Sestrojíme nyní množinu , kde je interval definovaný výše v první polovině důkazu. Analogický postup neustále opakujeme, čímž dostaneme posloupnost intervalů , kde . Z Kraftovy nerovnosti plyne, že nebude nikdy prázdná a fakt, že intervaly jsou disjunktní, zajišťuje, že námi vytvářená slova odpovídají prefixovému kódu.

McMillanova věta

[editovat | editovat zdroj]

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 libovolného jednoznačně dekódovatelného -znakového kódu splňují nerovnost

.

Pozn: Číslo tedy představuje počet znaků, pomocí nichž kódujeme zprávy přicházející ze zdroje, pro binární kód je , 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 (tj. znaky 0, 1, 2) atd. Čísla pak označují délky jednotlivých kódových slov. To znamená, máme-li danou -tou zprávu, tak udává počet znaků v posloupnosti použité pro zakódování této zprávy, např. pro -tou zprávu, jejíž kódové slovo je 00101, je .

Důkaz McMillanovy věty

[editovat | editovat zdroj]

Následující důkaz je též převzat ze skript I. Vajdy [1]. 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ž jsou délky slov jednoznačně dekódovatelného kódu konečného zdroje , tak platí

Nechť je rozšíření kódu a je jistá zpráva. Pak délky slov (obraz zprávy při kódování ) splňují podmínku

.

Z toho plyne

,

kde a symbol udává počet zpráv zakódovaných do slov délky . Protože je kód jednoznačně dekódovatelný, nejvýše jedno se zobrazí do slova délky a proto . Tedy

Odsud dostáváme

Neboť můžeme 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 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

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

  1. a b c VAJDA, Igor. Teorie informace. Praha: Vydavatelství ČVUT, 2004. ISBN 80-01-02986-7.  — skripta FJFI ČVUT