Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Teorie kódování - Kapitola 2 Věta o kódování bez šumu pro zdroje bez paměti Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 28. února 2023 □ - = O Zdroje bez paměti • Základní pojmy V^/ | | Av V Fl V této kapitole dokážeme první a snadnější ze dvou Shannonových hlavních vět pro nejjednodušší třídu zdrojů. Zdroje bez paměti Prefixové kódy Kraftova nerovnost Kódování bez šumu Kompaktní kódování Generování rozdělení •M Fl V této kapitole dokážeme první a snadnější ze dvou Shannonových hlavních vět pro nejjednodušší třídu zdrojů. Stručný oxfordský slovník definuje zdroj jako pramen, vrchol zřídla, ze kterého proudí výstupy. Zdroje bez paměti Prefixové kódy Kraftova nerovnost Kódování bez šumu Kompaktní kódování Generování rozdělení •M Fl V této kapitole dokážeme první a snadnější ze dvou Shannonových hlavních vět pro nejjednodušší třídu zdrojů. Stručný oxfordský slovník definuje zdroj jako pramen, vrchol zřídla, ze kterého proudí výstupy. Ve své plné obecnosti, je to přesně to, co uvažujeme v teorii informace, ačkoliv typicky považujeme zdroj za proud symbolů jisté konečné abecedy. Zdroje bez paměti Prefixové kódy Kraftova nerovnost Kódování bez šumu Kompaktní kódování Generování rozdělení •M Fl V této kapitole dokážeme první a snadnější ze dvou Shannonových hlavních vět pro nejjednodušší třídu zdrojů. Stručný oxfordský slovník definuje zdroj jako pramen, vrchol zřídla, ze kterého proudí výstupy. Ve své plné obecnosti, je to přesně to, co uvažujeme v teorii informace, ačkoliv typicky považujeme zdroj za proud symbolů jisté konečné abecedy. Zdroj má obvykle nějaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Fl V této kapitole dokážeme první a snadnější ze dvou Shannonových hlavních vět pro nejjednodušší třídu zdrojů. Stručný oxfordský slovník definuje zdroj jako pramen, vrchol zřídla, ze kterého proudí výstupy. Ve své plné obecnosti, je to přesně to, co uvažujeme v teorii informace, ačkoliv typicky považujeme zdroj za proud symbolů jisté konečné abecedy. Zdroj má obvykle nějaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Tento náhodný mechanismus může být poměrně dost komplikovaný, ale my se budeme pro okamžik soustředit na následující opravdu speciální a jednoduchý příklad. Zdroje bez paměti Prefixové kódy Kraftova nerovnost Kódování bez šumu Kompaktní kódování Generování rozdělení •M Značí-li X, Mý symbol vytvořený zdrojem, dohodneme se pak, že, pro každý symbol ay, pravděpodobnost P(X, = aj) = pj je nezávislá na i a tedy je nezávislá na všech minulých nebo v budoucnosti vyslaných symbolech. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Značí-li Xj Mý symbol vytvořený zdrojem, dohodneme se pak, že, pro každý symbol a,, pravděpodobnost P(X, = aj) = Pj je nezávislá na i a tedy je nezávislá na všech minulých nebo v budoucnosti vyslaných symbolech. Jinak řečeno, X1, X2,... je právě posloupnost identicky distribuovaných, nezávislých náhodných veličin. Takovýto zdroj nazveme zdrojem s nulovou pamětí nebo zdrojem bez paměti a jeho entropie H je definována jako kde sčítáme přes množinu j takových, že py > 0. Cvičení 1.1 O Je-li S zdroj bez paměti s abecedou Z, rozšíření řádu n S je zdroj bez paměti S(n) s abecedou Z(n) skládající se ze všech řetězců délky n symbolů ze Z tak, že pravděpodobnost každého řetězce a je určena pravděpodobností, že je to řetězec prvních n symbolů vyslaných S. Dokažte, že S(n) má entropii H(S) = nH(S). Q Prefixové a jednoznačně dekódovatelné kódy 9 Definice • Příklady Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Príklady Fl Hlavní problém řešený v této kapitole je následující. Předpokládejme, že máme zdroj bez paměti S, který vysílá symboly z abecedy W = {w^,..., wnj s pravděpodobnostmi {Pi j • • • iPn}- Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Príklady Fl Hlavní problém řešený v této kapitole je následující. Předpokládejme, že máme zdroj bez paměti S, který vysílá symboly z abecedy W = {w^,..., wnj s pravděpodobnostmi {Pi j • • • iPn}- Z pedagogických důvodů budeme prvky W nazývat zdrojová slova a ptát se na následující otázku. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Príklady Fl Hlavní problém řešený v této kapitole je následující. Předpokládejme, že máme zdroj bez paměti S, který vysílá symboly z abecedy W = {w^,..., wnj s pravděpodobnostmi {Pi j • • • iPn}- Z pedagogických důvodů budeme prvky W nazývat zdrojová slova a ptát se na následující otázku. Je-li Z abeceda D symbolů, jak můžeme zakódovat zdrojová slova Wj pomocí symbolů z Z, abychom dostali co možná nejekonomičtější zakódování? Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Príklady Příklad 2.1 Předpokládejme, že zdroj S vysílá ctyri zdrojová slova a, Ď, c, d s pravděpodobnostmi Pa = 0.9, pb = 0.05, po = pd = 0.025. Srovnáme-li pak zakódování a^0, c->110, c/ —> 101 a->00, jb->01, c->10, oř~>11, ye evidentně průměrná délka zakódovaného zdroje 1.2 v prvním kódu a 2 v druhém kódu. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Príklady Formálněji, kódovaní nebo kód\e zobrazení f z {w^,..., wn} do Z*, kde Z* označuje soubor konečných řetězců symbolů z Z. Formálněji, kódování nebo kód\e zobrazení f z {w^,..., wn} do Z*, kde Z* označuje soubor konečných řetězců symbolů z Z. Zpráva je každý konečný řetězec zdrojových slov a, je-li m = i/i/,- ... wik a je-li ř kódování, pak rozšíření f na l/l/* je definováno obvyklým způsobem pomocí zřetězení f(m) = f(wh)...f(wik). Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Definice De Základní pojmy - Jednoznačně dekódovatelné kódy Kódování f je jednoznačně dekódovatelné, jestliže každý konečný řetězec z Z* je obraz nejvýše jedné zprávy. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Definice De Základní pojmy - Jednoznačně dekódovatelné kódy Kódování ŕ je jednoznačně dekódovatelné, jestliže každý konečný řetězec z Z* je obraz nejvýše jedné zprávy. Řetězce f(wj) se nazývají kódová slova a přirozená čísla \f(Wj)\ jsou slovní délky kódování f. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Definice De Základní pojmy - Jednoznačně dekódovatelné kódy Kódování ŕ je jednoznačně dekódovatelné, jestliže každý konečný řetězec z Z* je obraz nejvýše jedné zprávy. Řetězce f(wj) se nazývají kódová slova a přirozená čísla \f(Wj)\ jsou slovní délky kódování f. Průměrná délka (f) kódování f je definovaná jako m (f) = j2Pim)\. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Príklady Kódování f se nazývá bezprostředně dekódovatelné nebo prefixové, jestliže neexistují různé Wj a wj tak, že f(wj) je prefix f{Wj). Kódování f se nazývá bezprostředně dekódovatelné nebo prefixové, jestliže neexistují různé Wj a wj tak, že f(wj) je prefix f{Wj). Zde používáme, jak lze očekávat, prefixy obvyklém smyslu, že pokud x, y g Z*, pak x je prefix y, jestliže existuje z g Z* tak, ze xz = y. SUj íťs, Ur2 U.íj 100 101 1l0 111 Kódování f se nazývá bezprostředně dekódovatelné nebo prefixové, jestliže neexistují různé Wj a wj tak, že f(wj) je prefix f{Wj). Zde používáme, jak lze očekávat, prefixy obvyklém smyslu, že pokud x, y g Z*, pak x je prefix y, jestliže existuje z g Z* tak, ze xz = y. SUj íťs, Ur2 U.íj 100 101 1l0 111 Prefixová kódování jsou jednoznačně dekódovatelná. Skutečně, mají silnější vlastnost, že prefixový kód může být dekódován 'on line' bez pohledu do budoucnosti. Zdroje bez paměti Prefixové kódy Kraftova nerovnost Kódování bez šumu Kompaktní kódování Generování rozdělení Příklad 2.2 Předpokládejme, že Y. = {0,1} a máme čtyři zdrojová slova w-\,..,w4. Zdroje bez paměti Prefixové kódy Kraftova nerovnost Kódování bez šumu Kompaktní kódování Generování rozdělení Příklad 2.2 Předpokládejme, že Z = {0,1} a máme čtyři zdrojová slova w-\,..,w4. Prefixové kódování je f(w,) = 0, /(w2) = 10, f(w3) = J\J\0, r(iv4) = 1110. □ 13 Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Příklad 2.2 Předpokládejme, že Z = {0,1} a máme čtyři zdrojová slova wi,..,iy4. Prefixové kódování je f(iv1) = 0, /(w2) = 10, /(w/3) = 110, f(iv4) = 1110. Například zprávu 01101001010010 lze dekódovat jako W-\ 1/1/31/1/2 W-\ 1/1/2 w2 W-\ w2. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Príklady Příklad 2.2 Předpokládejme, že Z = {0,1} a máme čtyři zdrojová slova Prefixové kódování je = 0, f(w2) = 10, f(w3) = 110, f{w4) = 1110. Například zprávu 01101001010010 lze dekódovat jako i/i/3 i/i/2 1/1/2 ^2 ^1 ^2- (Toto je příklad toho, co je známo jako čárkové kódování, protože evidentně používáme nulu, abychom signalizovali konec slova.) Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Ne každé jednoznačně dekódovatelné kódování je prefixové. Příklad 2.3 Předpokládejme, že W = {w^,w2},Z = {0^} a kódování g je definováno jako flf(wi) = 0, 9{W2) = 01. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Ne každé jednoznačně dekódovatelné kódování je prefixové. Příklad 2.3 Předpokládejme, že W = {w^,w2},Z = {0^} a kódování g je definováno jako flf(wi) = 0, g(w2) = 01. Toto kódování není evidentně prefixové, ale lze snadno ověřit, že je jednoznačně dekódovatelné, pokud budeme postupovat zpět z konce zprávy. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Ne každé jednoznačně dekódovatelné kódování je prefixové. Příklad 2.3 Předpokládejme, že W = {w^,w2},Z = {0^} a kódování g je definováno jako flf(wi) = 0, g(w2) = 01. Toto kódování není evidentně prefixové, ale lze snadno ověřit, že je jednoznačně dekódovatelné, pokud budeme postupovat zpět z konce zprávy. Je zřejmé, že jednoznačně dekódovatelná kódování jsou o mnoho obtížnější pojem, než prefixová kódování. Ne každé jednoznačně dekódovatelné kódování je prefixové. Předpokládejme, že W = {w^,w2},Z = {0^} a kódování g je definováno jako flf(wi) = 0, g(w2) = 01. Toto kódování není evidentně prefixové, ale lze snadno ověřit, že je jednoznačně dekódovatelné, pokud budeme postupovat zpět z konce zprávy. Je zřejmé, že jednoznačně dekódovatelné kódování jsou o mnoho obtížnější pojem, než prefixová kódování. Překvapivě ukážeme, že můžeme omezit pozornost na prefixová kódování v našem hledání jednoznačně dekódovatelných kódování, která mají minimální průměrnou délku. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Príklady De Jiný pohled na prefixové kódování Poznámka 2.4 Uvažujme D-ární strom, tj. každý uzel buď má D následníků nebo je listem. Nechť dále větve stromu reprezentují symboly příslušných kódových slov Např., D větví vycházejících z kořenového uzlu reprezentuje možné výskyty prvního symbolu kódového slova. Pak každé kódové slovo je reprezentováno listem našeho stromu. Cesta od kořene k listu se pak řídí symboly kódového slova. Evidentně, protože kódová slova jsou právě listy, není žádné kódové slovo předchůdcem jiného kódového slova, tj. naše kódování je prefixové. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Príklady De Jiný pohled na prefixové kódování Poznámka 2.4 Uvažujme D-ární strom, tj. každý uzel buď má D následníků nebo je listem. Nechť dále větve stromu reprezentují symboly příslušných kódových slov. Např., D větví vycházejících z kořenového uzlu reprezentuje možné výskyty prvního symbolu kódového slova. Pak každé kódové slovo je reprezentováno listem našeho stromu. Cesta od kořene k listu se pak řídí symboly kódového slova. Evidentně, protože kódová slova jsou právě listy, není žádné kódové slovo předchůdcem jiného kódového slova, tj. naše kódování je prefixové. Obráceně, mějme prefixové kódování na abecedě o D písmenech a uvažme maximální D-ární strom, který má hloubku rovnu nejdelšímu slovu našeho kódování. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Jiný pohled na prefixové kódování Poznámka 2.4 Podmínka, že se jedná o prefixové kódování implikuje, že žádné kódové slovo není předchůdcem jiného kódového slova v našem stromu. Zejména tedy každé kódové slovo eliminuje všechny své následníky jakožto možná kódová slova. Root Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Príklady De Jiný pohled na prefixové kódování Poznámka 2.4 Podmínka, že se jedná o prefixové kódování implikuje, že žádné kódové slovo není předchůdcem jiného kódového slova v našem stromu. Zejména tedy každé kódové slovo eliminuje všechny své následníky jakožto možná kódová slova. Lze tedy z maximálního stromu odebrat všechny následníky kódových slov a obdržíme pak D-ární strom, kde listy odpovídají kódovým slovům. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Príklady De Jiný pohled na prefixové kódování Poznámka 2.5 Ačkoliv jsme definovali kódování jako zobrazení, často ho identifikujeme se souborem C kódových slov Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Príklady De Jiný pohled na prefixové kódování Poznámka 2.5 Ačkoliv jsme definovali kódování jako zobrazení, často ho identifikujeme se souborem C kódových slov Cvičení 2.6 O Ukažte, že pro každé přirozené číslo m existuje prefixové kódování nad {0,1}, které má slova všech délek v množině {1,..., m}. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení McMillanova nerov- Dukaz nerovnosti nost Mc r r rlQl/ÁHrw/otQlnó \sŕ\r\\ Q Kraftova a McMillanova rozdělení pomocí vrhu nerovnosti iHpální minrp e McMillanova nerovnost o Důkaz nerovností Zdroje bez paměti Kraftova nerovnost Kompaktní kódování , „ , Prefixové kódy Kódování bez šumu Generování rozdělení McMillanova nerov- nost Mc Kraftova a McMillanova nerovnosti Fl V tomto odstavci dokážeme dvě základní nerovnosti, které ospravedlňují naši dřívější poznámku, že můžeme v podstatě zapomenout na pojem jednoznačné dekódovatelnosti a omezit pozornost na prefixová kódování. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt Fl V tomto odstavci dokážeme dvě základní nerovnosti, které ospravedlňují naši dřívější poznámku, že můžeme v podstatě zapomenout na pojem jednoznačné dekódovatelnosti a omezit pozornost na prefixová kódování. Nejdříve vyslovme nerovnosti. KRAFTOVA NEROVNOST Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt Fl V tomto odstavci dokážeme dvě základní nerovnosti, které ospravedlňují naši dřívější poznámku, že můžeme v podstatě zapomenout na pojem jednoznačné dekódovatelnosti a omezit pozornost na prefixová kódování. Nejdříve vyslovme nerovnosti. KRAFTOVA NEROVNOST Je-li Z abeceda mohutnosti Dal/l/ obsahuje N slov, pak nutná a dostatečná podmínka, že existuje prefixové kódování f: W -> Z* se slovními délkami ^,..., //v je, že platí n r D~i> < i (3.1) Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt McMILLANOVA NEROVNOST Je-li Z abeceda mohutnosti Dal/l/ obsahuje N slov, pak nutná a dostatečná podmínka, že existuje jednoznačně dekódovatelné kódování f: W -> Z* se slovními délkami /1?...,/a/ je, že platí(3.1). Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt McMILLANOVA NEROVNOST Je-li Z abeceda mohutnosti Dal/l/ obsahuje N slov, pak nutná a dostatečná podmínka, že existuje jednoznačně dekódovatelné kódování f: W -> Z* se slovními délkami /1?...,/a/ je, že platí(3.1). Kombinací těchto dvou nerovností dostaneme: Věta 3.1 Jednoznačně dekódovatelné kódování s předepsanou délkou slov existuje právě tehdy, když existuje prefixový kód se stejnou délkou slov DŮKAZ KRAFTOVY NEROVNOSTI Předpokládejme, že množina {/1,..., In} splňuje n £ O"* S 1. /=1 □ S1 DŮKAZ KRAFTOVY NEROVNOSTI Předpokládejme, že množina {/1,..., In} splňuje n E D"' í 1 • /=1 Přepišme nerovnost do tvaru / E "/D"y' ^1 > y'=i kde n,- je počet /, rovných j, I = max/, a vynásobme ji D1. DŮKAZ KRAFTOVY NEROVNOSTI Předpokládejme, že množina {/1,..., In} splňuje n E °-' s i. /=1 Prepíšme nerovnost do tvaru E "/D"y' ^1 > y'=i kde /iy je počet /, rovných y, / = max/, a vynásobme ji D' Přepišme tuto nerovnost opět do tvaru a?, < D1 - n} D/_1 - ... - n/_1 D. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Dukaz nerovnosti nost Mc Důkaz Věty 3.1 - Kraftova nerovnost Protože rij jsou všechna nezáporná, postupně dostaneme z (3.2) nerovnosti n/_-i < D/_1 - A7-| D'~2 - ... - n,_2D, ni-2 < D'~2 ~ "1 D'~3 - n/_3D, n3 < D3 - n-i D2 - ... - n2D, (3.3) n2< Ď2 - n-i D, A7-| < D. Zdroje bez paměti Prefixové kódy Kraftova nerovnost Kódování bez šumu Kompaktní kódování Generování rozdělení cMillanova nerov-st Důkaz nerovností Protože rij jsou všechna nezáporná, postupně dostaneme z (3.2) nerovnosti n/_i < D/_1 - m D>~2 - . n3 < D3 r\\ Ď2 - ... - n2D, n2< D2 - n-\ D, "1 < D. (3-3) Tyto nerovnosti jsou klíč ke konstrukci kódování s danou délkou slov. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt Nejdříve vyberme n-i slov délky 1, přičemž použijeme různá písmena z Z. Zbývá nám D - n-| nepoužitých symbolů a můžeme vytvořit (D - n^)D slov délky 2 přidáním písmena ke každému z těchto symbolů. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt Nejdříve vyberme n-i slov délky 1, přičemž použijeme různá písmena z Z. Zbývá nám D - n-| nepoužitých symbolů a můžeme vytvořit (D - n^)D slov délky 2 přidáním písmena ke každému z těchto symbolů. Vyberme našich n2 délky 2 libovolně z těchto slov a zbývá nám pak D2 - n-i D - n2 prefixů délky 2. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt Nejdříve vyberme n-i slov délky 1, přičemž použijeme různá písmena z Z. Zbývá nám D - n-| nepoužitých symbolů a můžeme vytvořit (D - n^)D slov délky 2 přidáním písmena ke každému z těchto symbolů. Vyberme našich n2 délky 2 libovolně z těchto slov a zbývá nám pak D2 - n-i D - n2 prefixů délky 2. Tyto lze užít pro vytvoření (D2 - n^D - n2)D slov délky 3, ze kterých můžeme vybrat n3 libovolně atd. Pokračujeme-li tímto způsobem, pokaždé je zachována vlastnost, že žádné slovo není prefixem jiného. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt Nejdříve vyberme n-i slov délky 1, přičemž použijeme různá písmena z Z. Zbývá nám D - n-| nepoužitých symbolů a můžeme vytvořit (D - n^)D slov délky 2 přidáním písmena ke každému z těchto symbolů. Vyberme našich n2 délky 2 libovolně z těchto slov a zbývá nám pak D2 - n-i D - n2 prefixů délky 2. Tyto lze užít pro vytvoření (D2 - n^D - n2)D slov délky 3, ze kterých můžeme vybrat n3 libovolně atd. Pokračujeme-li tímto způsobem, pokaždé je zachována vlastnost, že žádné slovo není prefixem jiného. V každém případě zjistíme, že nerovnosti (3.3) nám dovolí provést tento výběr. Tedy skončíme s prefixovým kódováním s předepsanými délkami kódování. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Dukaz nerovnosti nost Mc Důkaz Věty 3.1 - McMiIlanová nerovnost Dokázali jsme, že numerická podmínka (3.1) je dostatečná pro existenci prefixového kódování. Ačkoliv Kraft rovněž dokázal i nutnost podmínky (3.1), jedná se o bezprostřední důsledek McMillanovy nerovnosti, kterou v dalším dokážeme. Podaný důkaz je o mnoho jednodušší, než McMillanův původní důkaz a patří Karushovi (1961). Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Dukaz nerovnosti nost Mc Důkaz Věty 3.1 - McMiIlanová nerovnost Dokázali jsme, že numerická podmínka (3.1) je dostatečná pro existenci prefixového kódování. Ačkoliv Kraft rovněž dokázal i nutnost podmínky (3.1), jedná se o bezprostřední důsledek McMillanovy nerovnosti, kterou v dalším dokážeme. Podaný důkaz je o mnoho jednodušší, než McMillanův původní důkaz a patří Karushovi (1961). DŮKAZ McMILLANOVY NEROVNOSTI Předpokládejme, že máme jednoznačně dekódovatelné kódování C s délkami slov l^...,lN. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení McMillanova nerov- Důkaz nerovností nost Důkaz Věty 3.1 - McMillanova nero vnost Dokázali jsme, že numerická podmínka (3.1) je dostatečná pro existenci prefixového kódování. Ačkoliv Kraft rovněž dokázal i nutnost podmínky (3.1), jedná se o bezprostřední důsledek McMillanovy nerovnosti, kterou v dalším dokážeme. Podaný důkaz je o mnoho jednodušší, než McMillanův původní důkaz a patří Karushovi (1961). DŮKAZ McMILLANOVY NEROVNOSTI Předpokládejme, že máme jednoznačně dekódovatelné kódování C s délkami slov l^...,lN. Pokud / = max/,, pak, pro každé kladné celé číslo r, máme r rl (V1 + • • • + D"'") = biD~'\ (3-4) /=1 kde bj je nezáporné celé číslo. <*> <*> = Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Dukaz nerovnosti nost Mc Důkaz Věty 3.1 - McMiIlanová nerovnost Ale celá čísla b\ jsou právě počet možností, kolika způsoby lze řetězec délky / z symbolů abecedy Z utvořit konkatenací r kódových slov z délek vybraných z množiny {/1,..., /a/}. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Dukaz nerovnosti nost Mc Důkaz Věty 3.1 - McMiIlanová nerovnost Ale celá čísla b\ jsou právě počet možností, kolika způsoby lze řetězec délky / z symbolů abecedy Z utvořit konkatenací r kódových slov z délek vybraných z množiny {/1,..., /a/}. Jelikož je kódování C jednoznačně dekódovatelné, každý řetězec délky / tvořený z kódových slov musí odpovídat nejvýše jedné posloupnosti kódových slov. Musíme tedy mít Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Dukaz nerovnosti nost Mc Důkaz Věty 3.1 - McMiIlanová nerovnost Ale celá čísla b\ jsou právě počet možností, kolika způsoby lze řetězec délky / z symbolů abecedy Z utvořit konkatenací r kódových slov z délek vybraných z množiny {/1,..., /a/}. Jelikož je kódování C jednoznačně dekódovatelné, každý řetězec délky / tvořený z kódových slov musí odpovídat nejvýše jedné posloupnosti kódových slov. Musíme tedy mít bj < D' (1 < / < rl). Dosadíme-li do (3.4), obdržíme (d_/i + ••• + D'1^ < Ir. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Dukaz nerovnosti nost Mc Důkaz Věty 3.1 - McMiIlanová nerovnost Proto 7=1 a protože r bylo libovolné kladné celé číslo, dostáváme limitním přechodem r oc na pravé straně McMillanovu nerovnost. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Dukaz nerovnosti nost Mc Důkaz Věty 3.1 - McMiIlanová nerovnost Proto 7=1 a protože r bylo libovolné kladné celé číslo, dostáváme limitním přechodem r -> oc na pravé straně McMillanovu nerovnost. Cvičení 3.2 O Jaký je maximální počet slov binárního prefixového kódování, ve kterém je maximální délka slova 7? Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt Nalezneme binární kód s délkami kódových slov 1,2,3,3. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt Nalezneme binární kód s délkami kódových slov 1,2,3,3. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt Nalezneme binární kód s délkami kódových slov 1,2,3,3. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt Nalezneme binární kód s délkami kódových slov 1,2,3,3. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení cMillanova nerov- Důkaz nerovností DSt Nalezneme binární kód s délkami kódových slov 1,2,3,3. Q Věta o kódování bez šumu pro zdroje bez paměti • Základní odhad • Shannonovo kódování I,, r r i o n i ani diskrétních Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Věta o kódování bez šumu pro zdroje bez paměti Fl Uvažujme nyní následující situaci. Mějme zdroj S bez paměti, který vysílá slova ,..., wN s (kladnými) pravděpodobnostmi p-i,..., pN, každé vyslané slovo je vybráno nezávisle na všech jiných slovech. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Věta o kódování bez šumu pro zdroje bez paměti Fl Uvažujme nyní následující situaci. Mějme zdroj S bez paměti, který vysílá slova ,..., wN s (kladnými) pravděpodobnostmi p-i,..., pN, každé vyslané slovo je vybráno nezávisle na všech jiných slovech. Náš problém je: je-li dán takovýto zdroj společně s abecedou Z, najděte jednoznačně dekódovatelné kódování, jež má minimální průměrnou délku slov. Takovéto kódování nazýváme kompaktní. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Věta o kódování bez šumu pro zdroje bez paměti Fl Uvažujme nyní následující situaci. Mějme zdroj S bez paměti, který vysílá slova ,..., wN s (kladnými) pravděpodobnostmi p-i,..., pN, každé vyslané slovo je vybráno nezávisle na všech jiných slovech. Náš problém je: je-li dán takovýto zdroj společně s abecedou Z, najděte jednoznačně dekódovatelné kódování, jež má minimální průměrnou délku slov. Takovéto kódování nazýváme kompaktní. Heuristický přístup k tomuto problému by mohl být následující. Zdroj S má entropii H = -^P/logp/. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Věta o kódování bez šumu pro zdroje bez paměti Maximální entropie v abecedě o D písmenech je logD. Tedy počet symbolů abecedy potřebný v průměru na zakódování slova ze zdroje by měl být asi H/logD. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Věta o kódování bez šumu pro zdroje bez paměti Maximální entropie v abecedě o D písmenech je logD. Tedy počet symbolů abecedy potřebný v průměru na zakódování slova ze zdroje by měl být asi H/logD. Tuto hrubou ideu nyní upřesníme. Věta 4.1 Má-// zdroj bez paměti entropii H, pak každé jednoznačně dekódovatelné kódování C pro tento zdroj v abecedě o D symbolech musí mít délku alespoň H/logD. Navíc existuje takové jednoznačně dekódovatelné kódování, které má průměrnou délku slov menší než 1 + H/logD. Rovnost l(C) = H/logD platí právě tehdy, když p\ = D~ji, kde // je délka zakódování slova w,. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Důkaz Věty 4.1 - Kódování bez šumu Předpokládejme, že máme jednoznačně dekódovatelné kódování Cs délkami slov l^...,lN. Předpokládejme dále, že pravděpodobnosti emitovaných slov odpovídajících těmto délkám jsou p-i,... ,p/y. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Důkaz Věty 4.1 - Kódování bez šumu Předpokládejme, že máme jednoznačně dekódovatelné kódování Cs délkami slov l^...,lN. Předpokládejme dále, že pravděpodobnosti emitovaných slov odpovídajících těmto délkám jsou p-i,... ,p/v. Tedy H = -J2 A'logP/ a průměrná délka kódování C je dána /(C) = 5>//. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Důkaz Věty 4.1 - Kódování bez šumu Předpokládejme, že máme jednoznačně dekódovatelné kódování C s délkami slov l^...,lN. Předpokládejme dále, že pravděpodobnosti emitovaných slov odpovídajících těmto délkám jsou p-i,... ,p/v. Tedy H = -J2 P/logP/ a průměrná délka kódování C je dána /(C) = 5>//. Z Kraft-McMillanovy nerovnosti víme, že G=J2 njD-J < 1. y'=i Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení I kladní odhad Shannon Definujme g, (1 < / < N) jako tedy je (qi,..., q n) pravděpodobnostní rozdělení. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení i kladní odhad Shannon Definujme g, (1 < / < N) jako tedy je (qi,..., q n) pravděpodobnostní rozdělení. Aplikujme Klíčové Lemma a obdržíme pak H = ~Y1 A'logP/ <~Y1 P/logQ/. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Důkaz Věty 4.1 - Kódování bez šumu Definujme g,- (1 < / < N) jako tedy je (q-i,..., q^) pravděpodobnostní rozdělení. Aplikujme Klíčové Lemma a obdržíme pak H = ~Y1 Pil°SPi -~Y1 A-log<7/ Ale log<7/ = -//logD - logG. □ S1 Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Důkaz Věty 4.1 - Kódování bez šumu Definujme g,- (1 < / < N) jako tedy je (q-i,..., q^) pravděpodobnostní rozdělení. Aplikujme Klíčové Lemma a obdržíme pak H = - E A-logP/ < - E A-logqf/ Ale Tedy log<7/ = -//logD - logG. H < fa Pili) logD+ (Y, pi) logG. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Důkaz Věty 4.1 - Kódování bez šumu Ale G < 1 z Kraft-McMillanovy nerovnosti a tedy, jak je požadováno, H< /(C)logD. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Důkaz Věty 4.1 - Kódování bez šumu Ale G < 1 z Kraft-McMillanovy nerovnosti a tedy, jak je požadováno, H< /(C)logD. Dále platí 0 -logp/ a /, je minimální vzhledem k této vlastnosti, víme, že // < 1 - logp//logD. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Důkaz Věty 4.1 - Kódování bez šumu Odtud víme, že existuje jednoznačně dekódovatelné (ve skutečnosti prefixové) kódování s těmito slovními délkami. Ale, protože (4.1) je ekvivalentní s //logD > -logp/ a /, je minimální vzhledem k této vlastnosti, víme, že // < 1 - logp//logD. Máme tedy, že /(C) = ^p///<1+H/loga Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Shannon Cvičení 4.2 O Zakódujeme-li n stejně pravděpodobných slov nad binární abecedou, věta o kódování bez šumu tvrdí, že průměrná délka slova l(C) každého kompaktního jednoznačně dekódovatelného kódování splňuje log2n < /(C), pro které hodnoty n platí rovnost? Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Základní odhad Shannon Cvičení 4.2 O Zakódujeme-li n stejně pravděpodobných slov nad binární abecedou, věta o kódování bez šumu tvrdí, že průměrná délka slova l(C) každého kompaktního jednoznačně dekódovatelného kódování splňuje log2n < /(C), pro které hodnoty n platí rovnost? O Srovnejme hranice věty o kódování bez šumu s délkou kompaktního zakódování 2k - 1 stejně pravděpodobných slov nad {0,1}. Předpokládejme, že máme dán zdroj S bez paměti ze slov wi,..., wN s pravděpodobnostmi p1,..., pN a že si přejeme najít kompaktní kódování pro S nad abecedou {0,1,... ,D - 1}. • bez újmy na obecnosti předpokládáme p, > 0, Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Shannonovo kódování Shannon Předpokládejme, že máme dán zdroj S bez paměti ze slov wi,..., wN s pravděpodobnostmi p1,..., pN a že si přejeme najít kompaktní kódování C£ pro S nad abecedou {0,1,... ,D - 1}. • bez újmy na obecnosti předpokládáme p, > 0, položíme logDP -1 Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Shannonovo kódování Shannon Předpokládejme, že máme dán zdroj S bez paměti ze slov wi,..., wN s pravděpodobnostmi p1,..., pN a že si přejeme najít kompaktní kódování C£ pro S nad abecedou {0,1,...,D- 1}. • bez újmy na obecnosti předpokládáme p, > 0, položíme logDpJ -1 • tato čísla splňují Kraftovu nerovnost: n -1 n n Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Shannonovo kódování Shannon Předpokládejme, že máme dán zdroj S bez paměti ze slov wi,..., wN s pravděpodobnostmi p1,..., pN a že si přejeme najít kompaktní kódování C£ pro S nad abecedou {0,1,...,D- 1}. • bez újmy na obecnosti předpokládáme p, > 0, položíme logDP -1 • tato čísla splňují Kraftovu nerovnost: n /=1 -1 n n /=1 /=1 slova kódování C£ nalezneme pomocí konstrukce prefixového kódu se zadanými délkami //. Použití Shannonova kódování může být mnohem horší než kompaktní kódování. Použití Shannonova kódování může být mnohem horší než kompaktní kódování. Například uvažme dva symboly, z nichž jeden se vyskytuje s pravděpodobností 0,9999 a druhý s pravděpodobností 0,0001. Použití Shannonova kódování může být mnohem horší než kompaktní kódování. Například uvažme dva symboly, z nichž jeden se vyskytuje s pravděpodobností 0,9999 a druhý s pravděpodobností 0,0001. V případě Shannonova kódování použijeme délku kódového slova 1 bit, respektive 14 bitů. V případě kompaktního kódován to bude zjevně 1 bit pro oba symboly. Použití Shannonova kódování může být mnohem horší než kompaktní kódování. Například uvažme dva symboly, z nichž jeden se vyskytuje s pravděpodobností 0,9999 a druhý s pravděpodobností 0,0001. V případě Shannonova kódování použijeme délku kódového slova 1 bit, respektive 14 bitů. V případě kompaktního kódování to bude zjevně 1 bit pro oba symboly. Rozdíl průměrných délek pak bude 0,0013 ve prospěch kompaktního kódování. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení dní odhad Shannon Věta 4.4 (Divergence je cena za nevhodné kódování) Buď dán zdroj S bez paměti ze slov w^...,wN s (kladnými) pravděpodobnostmi p1,..., pN. Nechť dále q = (q1,..., Qa/) je (kladné) rozdělení pravděpodobností a je Shannonův kód zkonstruovaný na základě rozdělení q v abecedě o D symbolech. Potom platí: [H{X) + D(p||q)]/logD < UCg) < [H{X) + D(p||q)]/logD + 1. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení F* I ■ kladní odhad Shannon Nejprve dokažme horní mez. Platí: fc(Cg) = E,=1 Pi [logDQ/-1l < E,=1 Pi • (logoQ/-1 + 1) = Pi ■ logo (f • i) + ĽZ=1 P/ = E,=1 P/ • logD| + E,=1 Pi ■ logo^ + 1 E!Li Pi ■ logf + E/=1 Pi • log^J /logD + 1 = [H(X) + D(p||q)]/logD+1. □ S Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Shannon Nyní obdobně dokažme dolní mez. Platí: lp(Cqs) = Ľ/=iP/[logDQr1l > E/=i P/■ logoQ/-1 = Ej£i Pi ■ logD (f ■£) = E/=iP/-iogD| + E!v=iP/-iogD^ E,=1 Pi ■ logf + E/=1 Pi ■ log^j /logD = [H(X) + D(p||q)]/logD. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti v \s iti ly Q Konstruování kompaktních kódování • Konstrukce • Důkaz korektnosti • Nebinární případ r o /*x eti Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti Konstruování kompaktních kódování Fl Předpokládejme, že máme dán zdroj S bez paměti ze slov wi,..., wN s pravděpodobnostmi p1,..., pN a že si přejeme najít kompaktní kódování C pro S nad abecedou Z. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti Konstruování kompaktních kódování Fl Předpokládejme, že máme dán zdroj S bez paměti ze slov wi,..., wN s pravděpodobnostmi p1,..., pN a že si přejeme najít kompaktní kódování C pro S nad abecedou Z. Z věty o kódování bez šumu víme, že průměrná délka musí splňovat ohraničení H/logD < /(C) < 1 + H/logD, (5.1) ale snadno se vidí, že dolní hranice lze dosáhnout pouze, když Pí jsou jisté celočíselné mocniny D. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti Konstruování kompaktních kódování Fl Předpokládejme, že máme dán zdroj S bez paměti ze slov wi,..., wN s pravděpodobnostmi p1,..., pN a že si přejeme najít kompaktní kódování C pro S nad abecedou Z. Z věty o kódování bez šumu víme, že průměrná délka musí splňovat ohraničení H/logD < /(C) < 1 + H/logD, (5.1) ale snadno se vidí, že dolní hranice lze dosáhnout pouze, když Pí jsou jisté celočíselné mocniny D. Z Kraft-McMillanovy nerovnosti máme: Jestliže existuje kompaktní jednoznačně dekódovatelné kódování o průměrné délce I, pak existuje kompaktní prefixové kódování o průměrné délce I. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení konstrukce >ůkaz kore Nebinární případ Můžeme se tedy omezit na prefixová kódování. Nyní popíšeme metodu navrhnutou Huffmanem v roce 1952 pro konstruování kompaktníhu prefixového kódování pro výše uvedený zdroj S v případě, že Z je binární abeceda. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení konstrukce >ůkaz kore Nebinární případ Můžeme se tedy omezit na prefixová kódování. Nyní popíšeme metodu navrhnutou Huffmanem v roce 1952 pro konstruování kompaktníhu prefixového kódování pro výše uvedený zdroj S v případě, že Z je binární abeceda. Výsledný kód není určen jednoznačně (např. bitovou inverzí nebo permutací na abecedě Z získáme jiný optimální kód). Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení konstrukce >ůkaz kore Nebinární případ Můžeme se tedy omezit na prefixová kódování. Nyní popíšeme metodu navrhnutou Huffmanem v roce 1952 pro konstruování kompaktníhu prefixového kódování pro výše uvedený zdroj S v případě, že Z je binární abeceda. Výsledný kód není určen jednoznačně (např. bitovou inverzí nebo permutací na abecedě Z získáme jiný optimální kód). Jednoznačně není zadána ani délka kódových slov. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení konstrukce >ůkaz kore Nebinární případ Můžeme se tedy omezit na prefixová kódování. Nyní popíšeme metodu navrhnutou Huffmanem v roce 1952 pro konstruování kompaktníhu prefixového kódování pro výše uvedený zdroj S v případě, že Z je binární abeceda. Výsledný kód není určen jednoznačně (např. bitovou inverzí nebo permutací na abecedě Z získáme jiný optimální kód). Jednoznačně není zadána ani délka kódových slov. Huffmanovo kódování se používá na závěrečné zpracování formátů JPEG, MP3, DEFLATE, PKZIP resp. na předzpracování souboru pro aritmetické kódování. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti Konstruování kompaktních kódování Nejprve dokážeme některé vlastnosti kompaktního prefixového kódování C nad Z = {0,1}. Budeme užívat l(w) k označení délky slova wv C. Lemma 5.1 Kompaktní kódování pro zdroj s právě dvěma slovy a w2 je -> 0, w2 -> 1. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení konstrukce >ůkaz kore Nebinární případ Nejprve dokážeme některé vlastnosti kompaktního prefixového kódování C nad Z = {0,1}. Budeme užívat l(w) k označení délky slova wv C. Lemma 5.1 Kompaktní kódování pro zdroj s právě dvěma slovy a w2 je -> 0, w2 -> 1. Důkaz je zřejmý. Zdroje bez paměti Prefixové kódy Kraftova nerovnost Kódování bez šumu Kompaktní kódování Generování rozdělení Konstrukce Důkaz korektnosti Nebinární případ Konstruování kompaktních kódování h Lemma 5.2 Je-li C prefixové a kompaktní kódování a p, > py, pak l(Wj) < /(IV;). Zdroje bez paměti Prefixové kódy Kraftova nerovnost Kódování bez šumu Kompaktní kódování Generování rozdělení Konstrukce Důkaz korektnosti Nebinární případ Konstruování kompaktních kódování h Lemma 5.2 Je-li C prefixové a kompaktní kódování a p\ > Pj, pak l(Wj) < l(Wj). Důkaz. Pokud tomu tak není, vytvořme nový kód C z C záměnou zakódování w-, a wj. Pak průměrná délka je zmenšena a stále máme prefixové kódování. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení konstrukce >ůkaz kore Nebinární případ Dnstruování kompaktních kódování I Lemma 5.2 Je-li C prefixové a kompaktní kódování a p\ > Pj, pak l(Wj) < l(Wj). Důkaz. Pokud tomu tak není, vytvořme nový kód C z C záměnou zakódování w-, a wj. Pak průměrná délka je zmenšena a stále máme prefixové kódování. Lemma 5.3 Je-li C prefixové a kompaktní kódování, pak mezi všemi kódovými slovy v C maximální délky musí existovat alespoň dvě lišící se pouze v poslední číslici. Důkaz. Nechť tomu tak není; pak můžeme odebrat poslední číslici z těchto všech kódových slov maximální délky a stále máme prefixové kódování, což je spor s kompaktností C. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti HUFFMANUV KÓDOVACÍ ALGORITMUS Beze ztráty obecnosti můžeme předpokládat, že zdroj S má svůj systém zdrojových slov {w^,..., wN} uspořádaných tak, že pravděpodobnosti p, vyslání Wj splňují Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti HUFFMANUV KÓDOVACÍ ALGORITMUS Beze ztráty obecnosti můžeme předpokládat, že zdroj S má svůj systém zdrojových slov {w^,..., wN} uspořádaných tak, že pravděpodobnosti p, vyslání Wj splňují Pí > P2 > • • • > Pn- Huffmanova procedura konstruuje rekurzivně posloupnost zdrojů So, S-i,..., S/v-2 tak, že S0 = S a Sk je získáno z Sk^ ztotožněním dvou nejméně pravděpodobných symbolů z S/c_i s jediným symbolem a z Sk. Pravděpodobnost, že symbol a je vyslán z S/c je brána jako součet pravděpodobností jeho dvou vytvářejících symbolů v Sk^. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení onstrukce ° kaz kor ITMUS Nebinární případ Tedy S^ je získán z S0 ztotožněním wN a wN_^ do jednoho symbolu wN_^ vyskytujícího se s pravděpodobností pN + p/v_i. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti HUFFMANUV KÓDOVACÍ ALGORITMUS Tedy S^ je získán z S0 ztotožněním wN a wN_^ do jednoho symbolu wN_^ vyskytujícího se s pravděpodobností pN + p/v_i. V každém stavu máme zdroj s o jeden méně symboly. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení konstrukce >ůkaz kore ITMUS Nebinární případ Tedy S^ je získán z S0 ztotožněním wN a wN_^ do jednoho symbolu wN_^ vyskytujícího se s pravděpodobností pN + p/v_i. V každém stavu máme zdroj s o jeden méně symboly. Po N - 2 takovýchto redukcích dospějeme k zdroji Sn-2, k^rÝ má pouze dva symboly. Přechod mezi Sy_1 a Sy lze nejlépe vidět na následujícím obrázku. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti HUFFMANUV KÓDOVACÍ ALGORITMUS Zakódování Pravděpodobnost Slovo Slovo Pravděpodobnost Zakódování 91 92 v2 1/1 u2 92 9/c-i 9/c+i 9/c-i 9ř + 9ř+i Qk 9ŕ-i 9ř 9ř+i W-1 W+1 9ř-i Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti HUFFMANUV KÓDOVACÍ ALGORITMUS Je-li dáno zakódování g\ ,..., at zdroje Sy, Huffmanova procedura pro nalezení zakódování zdroje Sy_1 je následující velmi snadné pravidlo. Předpokládejme pravděpodobnosti > q2 > • • • > slov z Sy_i jsou takové, že slovo vytvořené z vt a vř+i je slovo i/^ z Sy. Pak by Huffmanovo zakódování Sy_i mělo být, jak je ukázáno v levém sloupci předchozí tabulky. Formálně, mělo by být zadáno pravidlem v,- -+(Tj (1 < / < k - 1), v,- (k < i < t - 1), Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti HUFFMANUV KÓDOVACÍ ALGORITMUS Zakódování cr2 Pravděpodobnost Slovo 92 v2 Slovo Pravděpodobnost Zakódování u2 Q2 cr2 07c-1 07c+1 07c+2 Q/c-1 Q/c Q/c+1 Q/c-1 Qř + Qř+1 07c-1 G k 0/C+1 07 (^,0) (^,1) Qř-1 Qř+i W-1 W+1 Qř-1 0r Sy- Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti HUFFMANUV KÓDOVACÍ ALGORITMUS Zpětným zpracováním nastartujeme naši zakódovací proceduru zakódováním dvou slov z Sn-2 s dvěma kódovými slovy 0 a 1; pak Sn-3 bude mít tři kódová slova atd. a budeme pokračovat ve výše uvedené proceduře, až dosáhneme Huffmanová kódu pro S = S0. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti HUFFMANUV KÓDOVACÍ ALGORITMUS Zpětným zpracováním nastartujeme naši zakódovací proceduru zakódováním dvou slov z Sn-2 s dvěma kódovými slovy 0 a 1; pak Sn-3 bude mít tři kódová slova atd. a budeme pokračovat ve výše uvedené proceduře, až dosáhneme Huffmanová kódu pro S = S0. Příklad 5.4 V následující tabulce je uvedeno Huffmanovo kódování francouzského a anglického jazyka. Frekvence udává, kolikrát se písmeno objevilo ve vzorku 1000 slov. Další tabulka ukazuje Huffmanovo kódování anglického jazyka (včetně mezery) založené na pravděpodobnostech z jiného korpusu. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinární prípad Důkaz korektnosti HUFFMANŮV KÓDOVACÍ ALGOR ITMUS Char FFsi Codepsi FEsi Codew, , E 850 00 591 100 A 395 1110 368 1111 S 388 1101 275 0110 I 366 1100 286 0111 T 356 1011 473 001 N 355 1010 320 1100 R 305 1001 308 1011 U 295 0111 111 00010 L 278 0101 153 10101 O 255 0100 360 1110 D 200 11110 171 11011 C 148 10000 124 01010 M 145 01101 114 00011 P 144 01100 89 00000 V 75 100010 41 1101001 Q 61 1111110 5 1101000101 G 51 1111101 90 00001 F 46 1111100 132 01011 B 42 1000111 65 101000 H 35 11111111 237 0100 J 29 11111110 6 1101000110 X 17 10001100 7 1101000111 Y 10 100011010 89 110101 Z 8 1000110111 3 1101000100 K 2 10001101101 19 11010000 W 1 10001101100 68 101001 Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti HUFFMANUV KÓDOVACÍ ALGORITMUS di Pi log9 — h C((li) a 0.0575 4.1 4 0000 b 0.0128 6.3 6 001000 c 0.0263 5.2 5 00101 d 0.0285 5.1 5 10000 e 0.0913 3.5 4 1100 f 0.0173 5.9 6 111000 g 0.0133 6.2 6 001001 h 0.0313 5.0 5 10001 i 0.0599 4.1 4 1001 j 0.0006 10.7 10 1101000000 k 0.0084 6.9 7 1010000 1 0.0335 4.9 5 11101 m 0.0235 5.4 6 110101 n 0.0596 4.1 4 0001 0 0.0689 3.9 4 1011 P 0.0192 5.7 6 111001 q 0.0008 10.3 9 110100001 r 0.0508 4.3 5 11011 s 0.0567 4.1 4 0011 t 0.0706 3.8 4 1111 u 0.0334 4.9 5 10101 v 0.0069 7.2 8 11010001 w 0.0119 6.4 7 1101001 x 0.0073 7.1 7 1010001 y 0.0164 5.9 6 101001 z 0.0007 10.4 10 1101000001 - 0.1928 2.4 2 01 Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti HUFFMANUV KÓDOVACÍ ALGORITMUS Budeme ilustrovat Huffmanovu metodu na skutečně malém příkladě. Příklad 5.5 Předpokládejme, že S je zdroj s pěti zdrojovými slovy a pravděpodobnostmi (viz níže). Pak vývoj H u ffmanová zakódování lze považovat za procházení šipek dopředu a pak zakódování zpátky. w P C W P C W P C W P C 0.5 1 Ví 0.5 1 1/1 0.5 1 0.5 0 1/1/2 0.2 01 v2 0.2 01 u2 0.3 00 0.5 1 1/1/3 0.15 001 v3 0.15 000 u3 0.2 01 1/1/4 0.1 0000 v4 0.15 001 1/1/5 0.05 0001 W: slovo, P: pravděpodobnost C: kódování Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení konstrukce >ůkaz kore ITMUS Nebinární případ Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení konstrukce >ůkaz kore Nebinární případ Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení konstrukce >ůkaz kore Nebinární případ Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení konstrukce >ůkaz kore Nebinární případ Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinární prípad Důkaz korektnosti HUFFMANŮV KÓDOVACÍ ALGOR ITMUS /-;-n Nalezneme Huffmanův binární kód pro príklad 5.5 - 4. krok Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení konstrukce >ůkaz kore Nebinární případ Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti HUFFMANUV KÓDOVACÍ ALGORITMUS Příklad 5.5 (Pokračování) Výsledné zakódování 1, w2 01, w3 001, w4 0000, w5 0001 má průměrnou délku 1.95 na zdrojové slovo. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti HUFFMANUV KÓDOVACÍ ALGORITMUS Příklad 5.5 (Pokračování) Výsledné zakódování 1, w2 01, w3 001, w4 0000, w5 0001 má průměrnou délku 1.95 na zdrojové slovo. Poznámka 5.6 Minimálně dvakrát v horním příkladu jsme schopni provést výběr, protože dvě slova mají stejné pravděpodobnosti. Pokud tento případ nastane, dostaneme různá zakódování. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti L Z Lemmatu 5.1 víme, že zakódování Sn-2 dvěma symboly 0 a 1 je optimální. Důkaz bude tedy úplný, jestliže budeme schopni dokázat, že kompaktnost je zachovávána při přechodu ze zdroje Si ke zdroji S,-_i. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Konstrukce Nebinarni prípad Dukaz korektnosti L Z Lemmatu 5.1 víme, že zakódování Sn-2 dvěma symboly 0 a 1 je optimální. Důkaz bude tedy úplný, jestliže budeme schopni dokázat, že kompaktnost je zachovávána při přechodu ze zdroje Sy ke zdroji Sy_i. Předpokládejme tedy, že Sy je kompaktně zakódován a že /-i,..., lt jsou délky slov a-i,..., at, ale že Huffmanovo zakódování C,-_i zdroje S,-_i není kompaktní. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení nstrukce ikaz kore Nebinární prípad Z Lemmatu 5.1 víme, že zakódování Sn-2 dvěma symboly 0 a 1 je optimální. Důkaz bude tedy úplný, jestliže budeme schopni dokázat, že kompaktnost je zachovávána při přechodu ze zdroje Sy ke zdroji Sy_i. Předpokládejme tedy, že Sy je kompaktně zakódován a že /-i,..., lt jsou délky slov a-i,..., at, ale že Huffmanovo zakódování Cy_i zdroje Sy_1 není kompaktní. Existuje tedy prefixové kompaktní kódování C zdroje Sy_1 tak, ze /(C) b, 10 i-» c, 11 ^ a nám rovněž poskytne rozdělení \,\,\z příkladu 6.1. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dlskretni rozděleni Binární stromy Problémy k reseni Generování diskrétních rozdělení vrhem ideální mince Například, zobrazení 00 h> a, 01 h> b, 10 h> c, 11 h> a nám rovněž poskytne rozdělení \,\,\z příkladu 6.1. Ale průměrný počet ideálních bitů potřebných pro vygenerování této náhodné proměnné je 1(2) + 1(2) + 1(2) + 1(2) = 2 bity. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dlskretni rozděleni Binární stromy Problémy k reseni Generování diskrétních rozdělení vrhem ideální mince Například, zobrazení 00 h> a, 01 h> ď, 10 h> c, 11 h> a nám rovněž poskytne rozdělení \,\,\z příkladu 6.1. Ale průměrný počet ideálních bitů potřebných pro vygenerování této náhodné proměnné je 1(2) + 1(2) + 1(2) + 1(2) = 2 bity. Není tedy tak efektivní jako přiřazení z příkladu 6.1, kde jsme potřebovali pouze 1,5 bitů. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dlskretni rozděleni Binární stromy Problémy k reseni Generování diskrétních rozdělení vrhem ideální mince Například, zobrazení 00 h> a, 01 h> ď, 10 h> c, 11 h> a nám rovněž poskytne rozdělení \,\,\z příkladu 6.1. Ale průměrný počet ideálních bitů potřebných pro vygenerování této náhodné proměnné je 1(2) + 1(2) + 1(2) + 1(2) = 2 bity. Není tedy tak efektivní jako přiřazení z příkladu 6.1, kde jsme potřebovali pouze 1,5 bitů. Můžeme tedy očekávat, že budeme potřebovat alespoň tolik nahodilosti v ideálních bitech, kolik vytvoříme ve výstupních symbolech. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Diskrétní rozdělení Dyadické rozdělení Binární stromy Problémy k řešení Generování diskrétních rozdělení v rhem ideální mince Například, zobrazení 00 h> a, 01 h> ď, 10 h> c, 11 h> a nám rovněž poskytne rozdělení \,\,\z příkladu 6.1. Ale průměrný počet ideálních bitů potřebných pro vygenerování této náhodné proměnné je 1(2) + 1(2) + 1(2) + 1(2) = 2 bity. Není tedy tak efektivní jako přiřazení z příkladu 6.1, kde jsme potřebovali pouze 1,5 bitů. Můžeme tedy očekávat, že budeme potřebovat alespoň tolik nahodilosti v ideálních bitech, kolik vytvoříme ve výstupních symbolech. Protože entropie je míra nahodilosti a každý ideální bit má entropii jednoho bitu, můžeme čekat, že počet použitých ideálních bitů bude alespoň tolik jako entropie výstupu. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dlskretni rozděleni Binární stromy Problémy k reseni Generování diskrétních rozdělení vrhem ideální mince Pro další úvahy označme y množinu listů úplného stromu. Dále uvažujme pravděpodobnostní rozdělení na listech tak, že pravděpodobnost listu hloubky k stromu bude 2~k. Buď dále Y náhodná proměnná s touto distribucí. Máme pak následující lemma. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dlskretni rozděleni Binární stromy Problémy k reseni Generování diskrétních rozdělení vrhem ideální mince Pro další úvahy označme y množinu listů úplného stromu. Dále uvažujme pravděpodobnostní rozdělení na listech tak, že pravděpodobnost listu hloubky k stromu bude 2~k. Buď dále Y náhodná proměnná s touto distribucí. Máme pak následující lemma. Lemma 6.2 Pro každý úplný strom uvažujeme pravděpodobnostní rozdělení na listech tak, že pravděpodobnost listu hloubky k stromu bude 2~k. Pak střední hodnota hloubky stromu je rovna entropii tohoto rozdělení. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dlskretni rozděleni Binární stromy Problémy k reseni Lemma 6.2 Pro každý úplný strom uvažujeme pravděpodobnostní rozdělení na listech tak, že pravděpodobnost listu hloubky k stromu bude 2~k. Pak střední hodnota hloubky stromu je rovna entropii tohoto rozdělení. MA Střední hodnota hloubky stromu je rovna et = Y1 My)2_/C(y) yey a entropie rozdělení náhodné proměnné Y je i yey 2*(y)~log2 2*(y) yey (6.2) (6.3) kde k{y) značí hloubku listu yey. Tedy h(Y) = etrs „ „ s „ Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dlskretni rozděleni Binární stromy Problémy k reseni Věta 6.3 Fl Pro každý algoritmus generující náhodnou proměnnou X je střední hodnota počtu ideálních bitů alespoň rovna entropii H(X), tj. ET > H(X). (6.4) Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dlskretni rozděleni Binární stromy Problémy k reseni Věta 6.3 Fl Pro každý algoritmus generující náhodnou proměnnou X je střední hodnota počtu ideálních bitů alespoň rovna entropii H(X), tj. ET > H(X). (6.4) MA Každý algoritmus generující náhodnou proměnnou X pomocí ideálních bitů můžeme reprezentovat pomocí úplného binárního stromu. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dlskretni rozděleni Binární stromy Problémy k reseni Věta 6.3 Fl Pro každý algoritmus generující náhodnou proměnnou X je střední hodnota počtu ideálních bitů alespoň rovna entropii H(X), tj. ET > H(X). (6.4) MA Každý algoritmus generující náhodnou proměnnou X pomocí ideálních bitů můžeme reprezentovat pomocí úplného binárního stromu. Označme všechny listy tohoto stromu různými symboly yey = {1,2,...}. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dlskretni rozděleni Binární stromy Problémy k reseni Věta 6.3 Fl Pro každý algoritmus generující náhodnou proměnnou X je střední hodnota počtu ideálních bitů alespoň rovna entropii H(X), tj. ET > H(X). (6.4) MA Každý algoritmus generující náhodnou proměnnou X pomocí ideálních bitů můžeme reprezentovat pomocí úplného binárního stromu. Označme všechny listy tohoto stromu různými symboly yey = {1,2,...}. Je-li strom nekonečný, pak je i abeceda y nekonečná. Zde je nutno být opatrný - zatím jsme pracovali pouze s náhodnými proměnnými s konečným oborem hodnot, ale snadno nahlédneme, že v tomto případě všechny úvahy zůstanou stejné!!! Zde je nutno být opatrný - zatím jsme pracovali pouze s náhodnými proměnnými s konečným oborem hodnot, ale snadno nahlédneme, že v tomto případě všechny úvahy zůstanou stejné!!! Uvažme nyní náhodnou proměnnou Y definovanou na listech tohoto stromu tak, že pro každý list y e y hloubky k (y) je pravděpodobnost P(Y = y) = 2~k^\ Zde je nutno být opatrný - zatím jsme pracovali pouze s náhodnými proměnnými s konečným oborem hodnot, ale snadno nahlédneme, že v tomto případě všechny úvahy zůstanou stejné!!! Uvažme nyní náhodnou proměnnou Y definovanou na listech tohoto stromu tak, že pro každý list y e y hloubky k (y) je pravděpodobnost P(Y = y) = 2~k^\ Dle Lemmatu 6.2 je střední hodnota hloubky stromu rovna entropii H (Y). Ale náhodná proměnná X je funkcí náhodné proměnné Y a tedy H (X) / ' (6-7) kde p{7) = 2~J nebo 0. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Zřejmě je tento proces ekvivalentní nalezení binárních rozvojů pravděpodobností p,. Buď tedy binární rozvoj pravděpodobnosti p, tvaru P/ = I>/ ' (6-7) kde p-y) = 2~J nebo 0. Pak atomy rozvoje jsou {pW|/ = 1,2,...,m,y>1}. Protože ^™p, = 1, bude i součet těchto atomů S/,y>i P/7) = 1 ■ Přitom připojíme atom s pravděpodobností 2~J jako list hloubky j ke stromu. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Zřejmě je tento proces ekvivalentní nalezení binárních rozvojů pravděpodobností p,. Buď tedy binární rozvoj pravděpodobnosti p, tvaru P/ = 5>/y)> (6-7) kde p-y) = 2~J nebo 0. Pak atomy rozvoje jsou {pW|/ = 1,2,...,m,y>1}. Protože ^™p, = 1, bude i součet těchto atomů S/,y>i P/7) = 1 ■ Přitom připojíme atom s pravděpodobností 2~J jako list hloubky j ke stromu. Hloubky atomů splňují Kraftovu nerovnost, můžeme tedy zkonstruovat binární strom, kde atomy mají požadovanou hloubku. Zdroje bez paměti Prefixové kódy Kraftova nerovnost Kódování bez šumu Kompaktní kódování Generování rozdělení iskrétní rozdělení Binární strom Dyadické rozdělení Problémy k řešení Příklad 6.5 Nechť náhodná proměnná X má pravděpodobnostní rozdělení X = a b s pravděpodobností §, s pravděpodobností g. (6.8) Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Příklad 6.5 Nechť náhodná proměnná X má pravděpodobnostní rozdělení X = a s pravděpodobností §, b s pravděpodobností g. (6.8) Nejprve určíme binární rozvoje těchto pravdepodobností: | = 0.10101010...2, ^ =0.01010101 ...2. (6.9) Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Příklad 6.5 Nechť náhodná proměnná X má pravděpodobnostní rozdělení X = a s pravděpodobností §, b s pravděpodobností g. (6.8) Nejprve určíme binární rozvoje těchto pravdepodobností: | = 0.10101010...2, ^ =0.01010101 ...2. Pak příslušné atomy pro rozvoj jsou: (6.9) 2 /1 1 1 3 ^ V 2'8'32' " " 1 /1 1 1 3 ^ V4' 16'64'" ' u i jy (6.10) Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Příklad 6.5 (Pokračování) Tyto atomy můžeme připojit ke stromu (viz sousední obrázek), který generuje pravděpodobnostní rozdělení 2 1 3' 3' Tato procedura nám poskytne binární strom, který generuje náhodnou proměnnou X. Tato procedura nám poskytne binární strom, který generuje náhodnou proměnnou X. V předchozím jsme tvrdili, že tato procedura je optimální v tom smyslu, že náš binární strom bude mít minimální střední hodnotu hloubky. Tato procedura nám poskytne binární strom, který generuje náhodnou proměnnou X. V předchozím jsme tvrdili, že tato procedura je optimální v tom smyslu, že náš binární strom bude mít minimální střední hodnotu hloubky. Nepodáme zde úplný formální důkaz, ale namísto toho ohraničíme střední hodnotu hloubky stromu vygenerovaného tímto postupem. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Dyadické rozdělení - Odhad hloubky stromu Věta 6.6 Pro optimální algoritmus generující náhodnou proměnnou X střední hodnota počtu ideálních bitů mezi H(X) a H(X) + 2, tj. H{X) 1 :pp-)>o /=1 Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Důkaz Věty 6.6 - Odhad hloubky stromu Můžeme najít takové přirozené číslo nh že 2_A7/ < p, < 2_A7/+1, neboli A7, — 1 < -logp, < 77/. (6.16) Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , _ ,. , , , Prefixové kódy Kódování bez šumu Generování rozdělení dyadické rozděleni Binární stromy Problémy k reseni Důkaz Věty 6.6 - Odhad hloubky stromu Můžeme najít takové přirozené číslo nh že 2_A7/ < p, < 2_A7/+1, neboli n/ - 1 < -log pí < rij. (6.16) Nutně tedy p|y) > 0 pouze pokud j > n. Můžeme tedy přepsat (6.15) do tvaru m T,= Y, J2~J a H(Y) = J2T,. (6.17) j>n,:p^>0 /=1 □ t3 Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Diskrétní rozdělení Dyadické rozdělení Binární stromy Problémy k řešení Důkaz Věty 6.6 - Odhad hloubky st romu Můžeme najít takové přirozené číslo nh že 2_A7/ < p, < 2_A7/+1, neboli A7, — 1 < -logp, < 77/. (6.16) Nutně tedy p)J) > 0 pouze pokud j > n. Můžeme tedy přepsat (6.15) do tvaru m T,= J2-J a H(Y) = Y/Ti. (6.17) j>nr.p^>0 /=1 Zároveň dle definice atomu můžeme zapsat p,- jakožto j>nr.pf]>0 Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Diskrétní rozdělení Dyadické rozdělení Binární stromy Problémy k řešení Důkaz Věty 6.6 - Odhad hloubky st romu Ukažme nejprve, že platí T, < -p,log p, + 2p,. Zřejmě (a) Ti + p/log p/ - 2pi < T- pi(m -^-2pj=Tj- (m + 1 )p,- Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Důkaz Věty 6.6 - Odhad hloubky stromu Ukažme nejprve, že platí T, < -p,log p, + 2p,. Zřejmě (a) Ti + p/log p/ - 2pi < T- pi(m - 1) - 2p,- = 7} - (m + 1 )p,- = £y>n,,pP>o;'2-y' - ("/ + 1)^>nř:p«>02"y' Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Důkaz Věty 6.6 - Odhad hloubky stromu Ukažme nejprve, že platí T, < -p,log p, + 2p,. Zřejmě (a) Ti + p/log p/ - 2pi < T- pi(m - 1) - 2p,- = 7} - (m + 1 )p,- = ^y>nř:pp>0^2"y' - ("/ + 1)^>nř:p«>02"y' = Ey>n,pO)>0^'-"/-1)2-y Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Důkaz Věty 6.6 - Odhad hloubky stromu Ukažme nejprve, že platí T, < -p,log p, + 2p,. Zřejmě (a) Ti + p/log p/ - 2pi < T- pi(m - 1) - 2p,- = 7} - (m + 1 )p,- = ^y>nř:pp>0^2"y' - ("/ + 1)^>nř:p«>02"y' = E^n/:/3Ífl>0(/-i/-i)2-^ = -2-^ + 0 + Ey>(n,+2):po)>00--n/-1)2-/ Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Důkaz Věty 6.6 - Odhad hloubky stromu Ukažme nejprve, že platí 7} < -p,log p,- + 2p,. Zřejmě (a) Ti + p/log p, - 2pi < T- pi(m - 1) - 2p,- = 7} - (m + 1 )p, = ^y>nř:pp>0^2"y' - ("/ + 1)^>nř:p«>02"y' = Ey>n,pO)>0^'-"/-1)2-y = -2-^ + 0 + E/>(n,+2):pO)>00--n/-1)2-/ (^-2-'+E,>1:pr,+i)>0/c2-^1) Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Důkaz Věty 6.6 - Odhad hloubky stromu Ukažme nejprve, že platí 7} < -p,log p,- + 2p,. Zřejmě (a) Ti + p/log Pí - 2pi < T- pi(m -J\)-2pj=Tj- (n, + 1 )p, = ^y>nř:pp>0^2"y' - ("/ + 1)^>nř:p«>02"y' = Ey>n,pO)>0^'-"/-1)2-y' = -2-^ + 0 + E/>(n,+2):pO)>00--n/-1)2-/ (=)-2-"' + V , -k2-(k+"i+V ^/c>1 : (c) >1:p,(/<+n'+1)>0 < -2"n' + E/01 /c2-(/c+n'+1) = -2"n' + -2-(n'+1)2 = 0, Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Důkaz Věty 6.6 - Odhad hloubky stromu Ukažme nejprve, že platí 7} < -p,log p,- + 2p,. Zřejmě (a) Ti + p/log p/ - 2pi < T- pi(m -^-Zp-^Tj- (n, + 1 )p, = Ey>n,pO)>0^'-"/-1)2-y = -2-^ + 0 + E/>(n,+2):pO)>00--n/-1)2-/ (c) >1:p,(/<+n'+1)>0 < -2"n' + E/01 /c2-(/c+n'+1) = -2"n' + -2-(n'+1)2 = 0, přičemž (a) plyne ze vztahu (6.16), (b) plyne ze změny proměnných v rámci sumy a (c) plyne z rozšíření oboru sumace. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování Prefixové kódy Kódování bez šumu Generování rozdělení Diskrétní rozdělení Dyadické rozdělení Binární stromy Problémy k řešení Důkaz Věty 6.6 - Odhad hloubky st romu Ukázali jsme tedy, že Ti<-pi\ogpi + 2pi. (6.19) Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Důkaz Věty 6.6 - Odhad hloubky stromu Ukázali jsme tedy, že Ti < -pi\ogpi + 2pj. (6.19) Protože ET = Y^IL-\ Ti, máme okamžitě, že m m m ET = E T' < - E A'log Pi + 2 E Pi = H(X) + 2. (6-20) /=1 /=1 /=1 Problémy 2 O Ve hře na šachovnici má jeden z hráčů (A) uhádnout, kam jeho protivník umístil královnu. Hráči A je povoleno šest otázek, které musí být pravdivě zodpovězeny odpovědí ano/ne. Dokažte, že existuje strategie, při které může hráč A vždy vyhrát tuto hru, ale že nelze zajistit výhru, pokud má povoleno pouze pět otázek. O Je-li hra z předchozího příkladu hraná na šachovnici o rozměrech n x n, kolik otázek potřebuje hráč A, aby bezpečně vyhrál. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni O Najděte průměrnou délku optimálního (kompaktního) jednoznačně dekódovatelného binárního kódu pro zdroj bez paměti, který vysílá šest slov s pravděpodobnostmi 0.25,0.10,0.15,0.05,0.20,0.25. Analyzováním Huffmanová algoritmu ukažme, že zdroj bez paměti vysílá N slov a jestliže ^,..., In jsou délky kódových slov optimálního kódování nad binární abecedou, pak h h-----h In < \{N2 + N -2). Problémy 2 O Máte k dispozici rovnovážnou váhu a devět zdánlivě identických mincí. Bylo Vám sděleno, že jedna mince je různá od zbývajících stejných mincí. Máte za úkol najít, o kterou minci se jedná a zda je těžší nebo lehčí. Navrhněte strategii o nejvýše 3 váženích pro řešení tohoto problému. Abychom obecně vyřešili tentýž problém pro n mincí v k váženích, je nutno, aby platilo, že k log 3 > log 2n. Dokažte. O V Huffmanově algoritmu pro binární abecedu aplikovaném na N zdrojových slov jsou délky slov pro konečné optimální zakódování A|,..., lN. Dokažte, že /H-----h In > N log2 N. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Problémy 2 O Mějme dva hráče, hráče A a hráče B. Tito hráči hrají hru s náhodnou kostkou, která má n stran a nabývá hodnot 1,..., n s pravděpodobnostmi p1, p2,..., pn. Hráč B vrhá kostkou za závěsem a hráč A má zjistit hodnotu po vržení kostky co možná nejrychleji. Hráč A se může ptát hráče B a ten mu musí pravdivě odpovídat buď ano nebo ne. Ukažte, že průměrný počet otázek pro úspěšnou strategii hráče A musí být alespoň entropie Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Problémy 2 O Ukažte, že optimální zakódování zdroje s N stejně pravděpodobnými zdrojovými slovy v abecedě o D písmenech, je A7?ax{(Dr+1 - N - b)/{D - 1), N} slov délky r, kde b je určeno vztahem A/ + ď=D + /c(D-1), 0 < fc< D - 1, ■ a r je největší přirozené číslo tak, že Dr p/+1. Nechť navíc i a1=0, a2 = Pi, a3 = p!+p2,..., aN = p^+p2 + --- + p/v-i. Nechť irij (1 < i < N) je definováno jako nejmenší takové přirozené číslo m,- splňující2~mi < pt, tj. m, = riogg-^ □ S s -f) <\cy Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Problémy 2 O Je-li pak a* binární rozvoj čísla ay- na rny desetinných míst, je kódování s j i y a j 1 < j < N jednoznačne dekódovatelné pro zdroj S. Ukažte, že se nejedná o optimální zakódování, ale že průměrná délka 1 kódování splňuje h(s) < 7< H(S) + 1. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Problémy 2 O Jsou-li A|,... Jn délky slov binárního Huffmanová kódování zdrojových slov majících pravděpodobnost p-i,..., pn, pak redundance kódování je definována jako n /c=1 Ukažte, že platí r < pmax + log[2(log e)/e] = pmax + 0.086, kdepmax = max/p,. Zdroje bez paměti Kraftova nerovnost Kompaktní kódování ^. , , , , ,. . , , Prefixové kódy Kódování bez šumu Generování rozdělení Dyadické rozděleni Binární stromy Problémy k reseni Problémy 2 Q Buď C prefixové kódování zdroje s N zdrojovými slovy v abecedě Z o D písmenech se slovními délkami h,...,lN takové, že platí i n /=1 Ukažte, že existuje libovolně dlouhá posloupnost v Z*, kterou nelze dekódovat.