Úvod do teorie informace

Úvod do teorie informace Matematické základy komprese a digitální komunikace Tomáš Kroupa http://staff.utia.cas.cz/kroupa/ 1 Ústav

teorie informace a automatizace AV ČR 2 Katedra

matematiky FEL ČVUT

Obsah 1. 2. 3. 4. 5. 6. 7.

Úvod Charakteristiky informace Asymptotická rovnočetnost typických zpráv Kódování a komprese Univerzální komprese Informační kanály Dodatek

Část I Úvod Teorie informace je matematická disciplína, která zkoumá I

možnosti komprese informace,

I

metody rychlého a kvalitního přenosu informace.

Teorie informace je založena na pravděpodobnostním modelu zpráv a komunikace. Tato myšlenka umožnila Shannonovi v r.1948 ukázat převratný fakt: I

zvyšování výkonu přenosového zařízení není jediná cesta k potlačení chyb při přenosu informace, neboť

I

existuje určitá přenosová rychlost, od níž lze přenášet s libovolně malou pravděpodobností chyby.

Počátky teorie informace Suppose we have a set of possible events whose probabilities of occurence are p1 , p2 , . . . , pn . These probabilities are known but that is all we know concerning which event will occur. Can we find a measure of how much “choice” is involved in the selection of the event or how uncertain we are of the outcome? C. E. Shannon. A mathematical theory of communication. Bell System Tech. J., 27:379–423, 623–656, 1948.

C.E. Shannon (1916–2001)

Model komunikace podle Shannona

Dualita komprese a spolehlivé komunikace I

při kompresi informačního zdroje odstraňujeme redundantní informaci

I

větší redundance informace naopak zaručuje menší chybovost při přenosu

Podle toho rozlišujeme 2 třídy kódování: .1.

zdrojové

.2.

kanálové

Co je informační zdroj? Informační zdroj je matematický model zařízení, které produkuje zprávy. Podle druhu produkovaných zpráv rozeznáváme 3 základní typy informačních zdrojů, které generují znaky konečné abecedy X: .1.

náhodná veličina X s výběrovým prostorem X

.2.

náhodný vektor (X1 , . . . , Xn ) s výběrovým prostorem Xn

.3.

náhodný proces (Xn )n∈N s výběrovým prostorem XN

Tyto modely umožňují popsat zařízení, která generují zprávy obsahující I

1 znak

I

n znaků

I

libovolný počet znaků

Dva významy slova “bit” .1.

symbol z množiny {0, 1}

.2.

jednotka informace při dvojkovém základu logaritmu

I

podle Shannona zavedl termín “bit” známý statistik John W.Tukey již v roce 1947

I

díky zvolené jednotce informace používáme logaritmus log := log2

Příklady informačních zdrojů Příklad Uvažujme sekvenci znaků tuto větu chceme zakódovat Informační zdroj je náhodná veličina X s výběrovým prostorem X = {t, u, o, v, ě, c, h, e, m, z, a, k, ó, d, _}. Pravděpodobnosti pX (x), x ∈ X odhadneme z realizované sekvence.

Příklad Výskyty znaků ve zprávě x1 . . . xn jsou nezávislé. Rozdělení zdroje (X1 , . . . , Xn ) je potom popsáno pravděpodobnostní funkcí q(x1 , . . . , xn ) =

n ∏ i=1

pX (xi ),

xi ∈ X.

Příklady informačních zdrojů (pokr.) Příklad X = {A, . . . , Z, _}. Markovův řetězec (Xn )n∈N se stavovým prostorem X popisuje generování “slov” z anglické abecedy, kde pravděpodobnost dvojic písmen odpovídá typickému anglickému textu. Shannon uvádí tento příklad realizace: ON IE ANTSOUTINYS ARE T INCTORE ST BE S DEAMY ACHIN D ILONASIVE TUCOOWE AT TEASONARE FUSO TIZIN ANDY TOBE SEACE CTISBE

Jedna úloha komprese Chceme poslat příjemci co nejkratší zprávu o vítězi závodu, kterého se zúčastní 8 závodníků majících následující pravděpodobnosti výhry: ( −1 −2 −3 −4 −6 −6 −6 −6 ) 2 ,2 ,2 ,2 ,2 ,2 ,2 ,2 I

je možno použít zprávu mající 3 bity pro každého závodníka

I

lepší je však využít uvedené pravděpodobnosti ke konstrukci kódu kratší střední délky

Jedna úloha komprese (pokr.) Řešení I

střední délka kódu s 3-bitovými délkami kódových slov je 3

I

uvažujme následující kód s délkami slov ℓi = − log pi 1

2

3

4

5

6

7

8

0

10

110

1110

111100

111110

111101

111111

I

střední délka tohoto kódu je 2

I

kód kratší střední délky nelze nalézt!

Jedna úloha komunikace Chceme přenést zprávu složenou z bitů informačním kanálem, v němž dochází ke každé bitové inverzi s pravděpodobností q < 12 . Vstup: informační zdroj (Xn )n∈N , kde Xn ∼ Bi(1, 21 ) jsou nezávislé. Lze předzpracovat zdroj tak, že pravděpodobnost chyba/bit pe < q? Možné řešení I

zopakujme každý bit při přenosu (2n + 1)-krát, dekódujme podle většiny

I

při n = 1 to dává pe = 3q2 (1 − q) + q3 < q

I

je-li n → ∞, potom pe → 0

I

ale R → 0, kde R je rychlost (bit/použití kanálu)!

Jedna úloha komunikace (pokr.) Shannon ukázal, že lze zachovat R > 0 při pe → 0. Přesněji: I

existuje R > 0 takové, že chybu pe lze učinit libovolně malou

I

největší R s touto vlastností je tzv. kapacita kanálu

V našem příkladě: I

kapacita kanálu je ( ) 1 − −q log q − (1 − q) log(1 − q)

I

lze ukázat, že pokud je rychlost R = 1, potom neexistuje předpracování zdroje, které by umožnilo pe < q

I

pro R = 1 je tedy optimální připojit zdroj přímo ke kanálu!

Pilíře teorie informace I

Shannonova věta (1948)

I

asymptotická rovnočetnost typických zpráv

I

existence dolní meze bezeztrátové komprese

I

existence optimální kompresní metody (Huffman, 1952)

I

metoda typů (Csiszár, Körner, 1981)

I

existence univerzálních kódů (Lempel, Ziv, 1977)

Teorie informace je “jen” teorie? I am very seldom interested in applications. I am more interested in the elegance of a problem. Is it a good problem, an interesting problem? C. E. Shannon

Aplikace teorie informace Algoritmy pro efektivní ukládání a komunikaci informace v digitálních (i analogových) systémech. Namátkou: I

Huffmanovo kódování, aritmetické kódování, LZW

I

zpracování formátů JPEG, MP3, TIFF

I

kódy pro detekci a opravu chyb

I

statistické aplikace: odhad pravděpodobnostních modelů

I

princip minimální deskripční délky (MDL)

Část II Charakteristiky informace Entropie

Divergence

Vzájemná informace

Rychlost entropie

Entropie

Divergence


Rychlost entropie

Hartleyho míra informace Definice (Hartley, 1928) Hartleyho míra informace I je funkce I(n) = log n,

n ∈ N.

I

platí-li |X| = 2n pro nějaké n > 1, potom I(2n ) = n udává počet bitů, kterými lze reprezentovat prvek z X

I

pokud neexistuje n > 1 takové, že |X| = 2n , potom potřebujeme k reprezentaci X právě ⌈I(|X|)⌉ bitů

Entropie

Divergence


Rychlost entropie

Axiomy Hartleyho míry Věta (Rényi) Hartleyho míra informace je jediná funkce I : N → R následujících vlastností: .1.

I(ab) = I(a) + I(b)

.2.

I je rostoucí

.3.

I(2) = 1

Intepretace I

k vyjádření prvku z 2m+n -prvkové množiny stačí zřetězit původní bitová slova délek m a n

I

míra informace s počtem reprezentovaných prvků roste

I

informaci měříme v bitech

Entropie

Divergence


Rychlost entropie

Entropie: motivace Nechť A1 , . . . , Ak ⊆ Ω je úplný soubor jevů, kde |Ω| = n a Aj má |A | pravděpodobnost pj = nj . I

pro popis každého z n výsledků potřebujeme informaci I(n)

I

pokud se dozvíme, že výsledek patří do Aj , stačí nám k jeho určení informace I(|Aj |)

I

příslušnost do j-té třídy nám tak poskytla informaci I(n) − I(|Aj |) = − log pj

Průměrnou informaci, kterou nám přináší znalost zařazení prvku do třídy, tedy dostaneme jako −

k ∑ j=1

pj log pj .

Entropie

Divergence


Rychlost entropie

Entropie Definice Nechť X je náhodná veličina s konečným výběrovým prostorem X a pravděpodobnostní funkcí pX . Entropie náhodné veličiny X je ∑ H(X) = − pX (x) log pX (x), x∈X

kde užíváme konvenci 0 log 0 = 0. 5

0.5

4

0.4

3

0.3

2

0.2

1

0.1

0.2

0.4

0.6

0.8

1.0

Funkce t 7→ − log t, t ∈ (0, 1⟩

0.2

0.4

0.6

0.8

1.0

Funkce t 7→ −t log t, t ∈ (0, 1⟩

Entropie

Divergence


Entropie jako střední hodnota Definujme pro každé x ∈ X, { − log pX (x), g(x) = 0,

0 < pX (x) 6 1, pX (x) = 0.

Potom střední hodnota funkce g(X) náhodné veličiny X je ∑ E(g(X)) = g(x)pX (x) = H(X). x∈X

Interpretace (pomocí Hartleyho míry informace I) Předpokládejme pX (x) = 2−nx , x ∈ X, kde nx ∈ N. Potom g(x) = nx a platí tak ∑ H(X) = pX (x)I(2nx ). x∈X

Rychlost entropie

Entropie

Divergence


Rychlost entropie

Entropie jako funkce Nechť |X| = n + 1. Entropii H lze chápat jako reálnou funkci H : ∆n → R, kde ∆n je pravděpodobnostní n-simplex. 1.0

0.8

1.5

0.6

1.0

1.0 0.4

0.5 0.0 0.0

0.2

0.5

0.5 0.2

0.4

0.6

Entropie na ∆1

0.8

1.0

1.0

Entropie na ∆2

0.0

Entropie

Divergence


Rychlost entropie

Axiomy entropie Věta Entropie H(p1 , . . . , pn ) je jediná funkce ∆n−1 → ⟨0, ∞) následujících vlastností: .1.

H nezávisí na pořadí argumentů p1 , . . . , pn

.2.

Funkce (p, 1 − p) ∈ ∆1 7→ H(p, 1 − p) je spojitá

.3.

H( 12 , 12 ) = 1

.4.

H(p1 , . . . , pn ) = ( ) 1 2 H(p1 + p2 , p3 , . . . , pn ) + (p1 + p2 )H p p+p , p p+p 1

2

1

2

První tři axiomy mají velmi přirozenou interpretaci. A co čtvrtý?

Entropie

Divergence


Rychlost entropie

Interpretace 4.axiomu Příklad Úkolem je uhodnout zvolené číslo z množiny {1, . . . , 5}. Lze použít např. tyto dvě strategie: I I

náhodně vybereme číslo z množiny {1, . . . , 5}, náhodný pokus je tak popsán rovnoměrným rozdělením pi = 15 , i = 1, . . . , 5 { } volíme prvek množiny {1, 2}, 3, 4, 5 podle rozdělení (nejprve ) 2 1 1 1 5 , 5 , 5 , 5 , potom případně náhodně volíme číslo z {1, 2}

Dostaneme: ( ) I H 1 , 1 , 1 , 1 , 1 = log 5 ) (5 5 5 5)5 ( I H 2, 1, 1, 1 + 2H 1, 1 = 5 5 5 5 5 2 2

2 5

log 5 −

2 5

+ 35 log 5 +

2 5

= log 5

Entropie

Divergence


Rychlost entropie

Entropie o základu d Věta Nechť d > 0 a Hd (X) = −

∑ x∈X

pX (x) logd pX (x). Pak

Hd (X) = logd 2 · H(X).

Důkaz. Pro každé t > 0 platí rovnost t = 2log t . Jejím logaritmováním získáme vztah logd t = logd 2 · log t, ze kterého tvrzení plyne.

Entropie

Divergence


Rychlost entropie

Minimální entropie Věta Platí H(X) > 0. Rovnost H(X) = 0 nastane právě tehdy, když je rozdělení X Diracovo.

Důkaz. I

nerovnost plyne přímo z definice entropie

I

pokud má X Diracovo rozdělení, potom H(X) = log 1 = 0

I

obráceně, z existence x ∈ X s vlastností 1 > pX (x) > 0 plyne −pX (x) log pX (x) > 0, a tudíž H(X) > 0

Poznámka. Maximum entropie snadno nalezneme až po zavedení tzv. informační divergence.

Entropie

Divergence


Rychlost entropie

Sdružená a podmíněná entropie Definice Nechť (X, Y) je náhodný vektor s konečným výběrovým prostorem X × Y. Sdružená entropie (X, Y) je ∑ H(X, Y) = − pXY (x, y) log pXY (x, y). (x,y)∈X×Y

Pro dané x ∈ X, pX (x) > 0 je podmíněná entropie dána jako ∑ H(Y | X = x) = − pY|X (y | x) log pY|X (y | x) y∈Y

a střední podmíněná entropie je H(Y | X) =

∑ x∈X

pX (x)H(Y | X = x),

kde H(Y | X = x) definujeme libovolně, pokud pX (x) = 0.

Entropie

Divergence


Rychlost entropie

Řetězcové pravidlo Věta Platí H(X, Y) = H(X) + H(Y | X).

Důkaz. Jelikož pXY (x, y) = pX (x)pY|X (y|x),dostaneme H(X, Y) = −

∑

pXY (x, y) log pX (x)pY|X (y | x)

(x,y)∈X×Y

=−

∑

pXY (x, y) log pX (x) + pXY (x, y) log pY|X (y | x)

(x,y)∈X×Y

=−

∑ x∈X

pX (x) log pX (x) +

∑ x∈X

H(Y | X = x)pX (x).

Entropie

Divergence


Sdružená entropie nezávislých veličin Věta Jsou-li X, Y nezávislé, pak H(Y|X) = H(Y)

a

H(X, Y) = H(X) + H(Y).

Důkaz. Důsledek řetězcového pravidla, vztahu pY|X (y|x) = pY (y) pro nezávislé veličiny X, Y a H(Y|X = x) = H(Y).

Rychlost entropie

Entropie

Divergence


Rychlost entropie

Není entropie jako entropie! -What are you thinking? -Entropy. -Entropy? Yeah, entropy. Boris explained it. It’s why you can’t get the toothpaste back in the tube. -You mean, once something happens, it’s difficult to put it back the way it was? Woody Allen, Whatever Works (2009) Termín entropie zavedl do fyziky Rudolf Clausius v r. 1865: entropie termodynamického systému je určena prostřednictvím 2. zákona termodynamiky.

Entropie

Divergence


Rychlost entropie

Není entropie jako entropie! (pokr.) My greatest concern was what to call it. I thought of calling it ‘information’, but the word was overly used, so I decided to call it ‘uncertainty’. When I discussed it with John von Neumann, he had a better idea. Von Neumann told me, ‘You should call it entropy, for two reasons. In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, nobody knows what entropy really is, so in a debate you will always have the advantage. C. Shannon M. Tribus, E.C. McIrvine. Energy and information. Scientific American 224, 1971.

Entropie

Divergence

Entropie

Divergence


Rychlost entropie


Rychlost entropie

Entropie

Divergence


Rychlost entropie

Informační divergence Definice Informační divergence pravděpodobnostních funkcí p a q na X je D(p∥q) =

∑

p(x) log

x∈X

p(x) , q(x)

při využití konvence 0 log 0t = 0, t ∈ ⟨0, 1⟩ a r log 0r = ∞, r ∈ (0, 1⟩. Jiná terminologie I

relativní entropie

I

Kullback-Leiblerova divergence

Entropie

Divergence


Rychlost entropie

Informační nerovnost Věta Vždy platí D(p∥q) > 0. Rovnost D(p∥q) = 0 nastane právě tehdy, když p = q.

Důkaz. Nechť A = {x ∈ X | p(x) > 0}. Použijeme Jensenovu nerovnost: −D(p∥q) =

∑ x∈A

p(x) log

∑ ∑ q(x) (2) q(x) (1) p(x) 6 log 6 log q(x) = 0. p(x) p(x) x∈A

x∈X

Pokud D(p∥q) = 0, pak rovnost v (1) dává díky ryzí konkávnosti q(x) = c > 0. Tudíž funkce log t a Jensenově nerovnosti p(x) ∑ ∑ x∈A ∑q(x) = c x∈A ∑ p(x) = c. Rovnost v (2) znamená c = x∈A q(x) = x∈X q(x) = 1.

Entropie

Divergence


Rychlost entropie

Maximální entropie Věta Platí H(X) 6 log |X|. Rovnost H(X) = log |X| nastane právě tehdy, když má X rovnoměrné rozdělení.

Důkaz. Nechť q(x) = |X|−1 , x ∈ X. Potom D(p∥q) =

∑ x∈X

p(x) log

p(x) = log |X| − H(X). q(x)

Tvrzení tudíž plyne z informační nerovnosti.

Entropie

Divergence

Entropie

Divergence


Rychlost entropie


Rychlost entropie

Entropie

Divergence


Rychlost entropie

Vzájemná informace Definice Nechť (X, Y) je náhodný vektor s konečným výběrovým prostorem X × Y. Vzájemná informace I(X; Y) je definována jako I(X; Y) = D(pXY ∥pX pY ) =

∑

pXY (x, y) log

(x,y)∈X×Y

pXY (x, y) . pX (x)pY (y)

Interpretace I(X; Y) měří odlišnost sdruženého rozdělení náhodného vektoru (X, Y) od součinového rozdělení jeho marginálů, kterým by se vektor (X, Y) řídil, pokud by X a Y byly nezávislé.

Entropie

Divergence


Rychlost entropie

Vzájemná informace měří pokles entropie Věta Platí I(X; Y) = H(X) − H(X | Y) = H(Y) − H(Y | X).

Důkaz. Protože pXY = pX|Y pY , dostaneme I(X; Y) =

∑

pXY (x, y) log

(x,y)∈X×Y

=

∑

pX|Y (x | y) pX (x)

−pXY (x, y) log pX (x) + pXY (x, y) log pX|Y (x | y)

(x,y)∈X×Y

=−

∑ x∈X

pX (x) log pX (x) −

∑ y∈Y

H(X | Y = y)pY (y).

Entropie

Divergence


Rychlost entropie

Vzájemná informace: hod mincí Příklad Náhodný pokus: 1 hod 1 symetrickou mincí. Definujeme: { { 1, padl líc, 1, padl rub, X= Y= 0, padl rub, 0, padl líc. Potom H(X) = log 2 = 1 a H(X | Y) = 0, neboť X = 1 − Y. Proto I(X; Y) = H(X) = 1. Jiná intepretace. Zdroj X je přenesen informačním kanálem, který provede bitovou inverzi. Původní informace o zdroji X je tak zcela zachována veličinou Y.

Entropie

Divergence


Rychlost entropie

Vzájemná informace: informační kanál Příklad Zdroj X s výběr.prostorem {1, . . . , 6} a rovnoměrným rozdělením má být přenesen informačním kanálem. Každá podmíněná pravděpodobnostní funkce pX|Y je nenulová a rovnoměrná na 4-prvkové množině.Tedy . I(X; Y) = H(X) − H(X | Y) = log 6 − log 4 = log 3 − 1 = 0.58, . přičemž H(X) = 2.58.

Entropie

Divergence


Rychlost entropie

Vlastnosti vzájemné informace Věta I

0 6 I(X; Y) = I(Y; X) 6 H(X)

I

I(X; Y) = 0 ⇔ X a Y jsou nezávislé

I

I(X; Y) = H(X) ⇔ pro každé y ∈ Y s pY (y) > 0 je podmíněná pravděpodobnostní funkce pX|Y (. | y) Diracova

Entropie

Divergence


Rychlost entropie

Vlastnosti vzájemné informace (pokr.) Důkaz. I

Nezápornost a symetrie I(X, Y) plyne přímo z definice, druhá nerovnost je důsledkem vztahu I(X; Y) = H(X) − H(X | Y)

I

Charakterizace rovnosti I(X; Y) = 0 je důsledkem definice I a vlastností inf. divergence.

I

I(X; Y) = H(X) ⇔ H(X | Y) = 0 ⇔ H(X | Y = y) = 0 pro každé y ∈ Y, pY (y) > 0 ⇔ pX|Y (. | y) je Diracova.

Entropie

Divergence


Rychlost entropie

Důležité (ne)rovnosti Věta Platí: I

I(X; Y) 6 min { H(X), H(Y) }

I

H(X | Y) 6 H(X)

I

H(X | Y) = 0 ⇔ existuje f : Y → X splňující pX|Y (f(y) | y) = 1 pro každé y ∈ Y, pY (y) > 0

I

H(X | Y) = H(X) ⇔ X, Y nezávislé

I

I(X; X) = H(X)

I

I(X; Y) = H(X) + H(Y) − H(X, Y)

I

H(X, Y) 6 H(X) + H(Y), přičemž rovnost nastává ⇔ X, Y nezávislé

Entropie

Divergence

Entropie

Divergence


Rychlost entropie


Rychlost entropie

Entropie

Divergence


Rychlost entropie

Motivace I

zdroj (X1 , . . . , Xn ) má sdruženou entropii H(X1 , . . . , Xn )

I

jsou-li Xi nezávislé, potom H(X1 , . . . , Xn ) =

n ∑

H(Xi )

i=1 I

jsou-li Xi nezávislé a stejně rozdělené, potom H(X1 , . . . , Xn ) = nH(X1 )

Jak popíšeme informaci obsaženou ve zdroji (Xn )n∈N ?

Entropie

Divergence


Rychlost entropie

Příklad Markovův řetězec (Xn )n∈N stavový prostor X = {1, 2} α, β ∈ ⟨0, 1⟩, α + β > 0 .α .1 − α

1..

.2 .β

( ) 1−α α Matice přechodu je P = . β 1−β

.1 − β

Entropie

Divergence


Rychlost entropie

Rychlost entropie I

pro n → ∞ není entropie zdroje (X1 , . . . , Xn ) shora omezena, neboť H(X1 , . . . , Xn ) 6 log |X|n

I

hledejme entropii na jeden znak zprávy!

Definice Rychlost entropie náhodného procesu (Xn )n∈N je H ((Xn )n∈N ) = lim

n→∞

pokud tato limita existuje.

1 H(X1 . . . , Xn ), n

Entropie

Divergence


Rychlost entropie

Rychlost entropie: příklady Příklad Je-li zdroj zpráv X1 , X2 , . . . takový, že Xi jsou nezávislé a stejně rozdělené, potom H ((Xn )n∈N ) = lim

n→∞

1 nH(X1 ) = H(X1 ). n

Ovšem lze nalézt i bezpaměťový zdroj (tj. nezávislý proces (Xn )n∈N ), pro nějž limita 1∑ lim H(Xi ) n→∞ n n

i=1

neexistuje!

Entropie

Divergence


Rychlost entropie

Mezní podmíněná entropie Definice e ((Xn )n∈N ) náhodného procesu Mezní podmíněná entropie H (Xn )n∈N je limita posloupnosti H(X1 ), H(X2 |X1 ), H(X3 |X2 , X1 ), . . . pokud tato limita existuje. Dostáváme tak 2 pojmy: I H ((Xn )n∈N ) je entropie na znak vyslané zprávy e ((Xn )n∈N ) je entropie rozdělení podmíněného minulými I H pozorováními Oba pojmy splývají pro stacionární informační zdroje.

Entropie

Divergence


Rychlost entropie

Stacionární informační zdroj Definice Zdroj (Xn )n∈N je stacionární, pokud platí [ ] [ ] P X1 = x1 , . . . , Xn = xn = P X1+ℓ = x1 , . . . , Xn+ℓ = xn pro každé n ∈ N, každý časový posun ℓ a každé x1 , . . . , xn ∈ X.

Příklad Bezpaměťový zdroj X1 , X2 , . . . , kde Xi jsou stejně rozdělené.

Zajímavější příklad Homogenní Markovův řetězec s maticí přechodu P a počátečním rozdělením p(0), které je stacionární: p(0) = p(0)P.

Entropie

Divergence


Rychlost entropie

Stacionarita a mezní podmíněná entropie Věta Je-li zdroj (Xn )n∈N stacionární, potom je posloupnost e H(X2 |X1 ), H(X3 |X2 , X1 ), . . . nerostoucí a její limita H((X n )n∈N ) existuje.

Důkaz. Pro n > 2 platí H(Xn+1 |Xn , . . . , X1 ) 6 H(Xn+1 |Xn , . . . , X2 ), kde H(Xn+1 |Xn , . . . , X2 ) = H(Xn |Xn−1 , . . . , X1 ). díky stacionaritě. Dostaneme tak nerostoucí posloupnost e nezáporných reálných čísel, jejíž limita H((X n )n∈N ) existuje.

Entropie

Divergence


Rychlost entropie

Stacionarita a rychlost entropie Věta Je-li zdroj (Xn )n∈N stacionární, potom rychlost entropie H((Xn )n∈N ) existuje a platí e H((Xn )n∈N ) = H((X n )n∈N ).

Důkaz. Podle řetězcového pravidla pro sdruženou entropii platí ∑n H(Xi |Xi−1 , . . . , X1 ) + H(X1 ) H(X1 . . . , Xn ) = i=2 . n n e Vpravo je průměr posloupnosti, která konverguje k H((X n ) ∈ N). e Tudíž musí konvergovat k H((Xn ) ∈ N) i posloupnost průměrů.

Entropie

Divergence


Rychlost entropie

Markovský zdroj Definice Markovský zdroj informace je stacionární Markovův řetězec.

Příklad (pokr.) .α .1 − α

1..

.2

.1 − β

.β β α Řetězec uvažujeme s počátečním rozdělením p(0) = ( α+β , α+β ), to splňuje p(0) = p(0)P.

Entropie

Divergence


Rychlost entropie markovského zdroje Věta Pokud je zdroj informace (Xn )n∈N markovský, potom je jeho rychlost entropie H((Xn )n∈N ) = H(X2 |X1 ).

Důkaz. e H((Xn )n∈N ) = H((X n )n∈N ) = lim H(Xn+1 |Xn , . . . , X1 ) n→∞

= lim H(Xn+1 |Xn ) = H(X2 |X1 ). n→∞

Rychlost entropie

Entropie

Divergence


Rychlost entropie

Příklad markovského zdroje Příklad (pokr.) .α .1 − α

1..

.2

.1 − β

.β β α Počáteční rozdělení p(0) = ( α+β , α+β ). Rychlost entropie je

H((Xn )n∈N ) = H(X2 |X1 ) =

β α+β H(α, 1

− α) +

α α+β H(β, 1

− β).

Entropie

Divergence


Rychlost entropie

Příklad markovského zdroje: α = β = Příklad: H((Xn )n∈N ) = 1 .12 .12

1..

.2

.12

.12 Počáteční rozdělení p(0) = ( 12 , 21 ) Jde o bezpaměťový zdroj informace: ve zprávě x1 x2 . . . , xi ∈ {1, 2} má každý řetězec xm xm+1 . . . xm+ℓ stejnou pravděpodobnost 2−ℓ−1 .

1 2

Entropie

Divergence


Rychlost entropie

Příklad markovského zdroje: α = 0 Příklad: H((Xn )n∈N ) = 0 .0 .1

1..

.2 .β

Počáteční rozdělení p(0) = (1, 0) Jde o deterministický zdroj informace: zpráva 111 . . . vznikne s pravděpodobností 1.

.1 − β

Entropie

Divergence


Rychlost entropie

Příklad markovského zdroje: β = 0 Příklad: H((Xn )n∈N ) = 0 .α .1 − α

1..

.2 .0

Počáteční rozdělení p(0) = (0, 1) Jde o deterministický zdroj informace: zpráva 222 . . . vznikne s pravděpodobností 1.

.1

Entropie

Divergence


Rychlost entropie

Příklad markovského zdroje: α = β = 1 Příklad: H((Xn )n∈N ) = 0 .1 .0

1..

.2

.0

.1 Počáteční rozdělení p(0) = ( 12 , 21 ) Jde o nedeterministický zdroj informace, ale každá zpráva je jednoznačně určena prvním znakem: zprávy 1212 . . . mají pravděpodobnost 12 .

a

2121 . . .

Část III Asymptotická rovnočetnost typických zpráv

Prolog k bezeztrátové kompresi

Typické zprávy


Typické zprávy

Motivace Příklad Bezpaměťový zdroj generuje 100 bitů s pravděpodobnostmi p(0) = 0.995, p(1) = 0.005. Máme zakódovat každou zprávu x1 . . . x100 , která obsahuje nejvýše tři bity 1. I

počet typických zpráv (nejvýše tři bity 1) je ( ) ( ) ( ) ( ) 100 100 100 100 + + + = 166 751 0 1 2 3

I

tudíž stačí kódová slova délky ⌈log 166 751⌉ = 18

I

tak zakódujeme zprávy z množiny, jejíž pravděpodobnost je ) 3 ( ∑ 100 0.005i 0.995100−i = 0.99833 i i=0


Typické zprávy

Motivace (pokr.) Příklad (pokr.) I

tím ovšem dosáhneme jen ztrátové komprese

I

atypické zprávy (více než tři 1) můžeme zakódovat pomocí 100 log 2 = 100 bitů

I

přidáním počátečního příznakového bitu odlišíme kódová slova pro typické a atypické zprávy

I

střední délka kódového slova je tak 0.99833 · 19 + 0.00167 · 101 = 19.13694


Typické zprávy

Motivace (pokr.) Jak poznáme typické zprávy? I

pravděpodobnost typické zprávy (0, . . , 0}) je | .{z 100×

p100 = 0.995100 = 0.60577

I

povšimněme si, že existuje ε > 0 takové, že ( ) −100 H(0.005,0.995)−ε p100 ≈ 2

I

pravděpodobnost typické zprávy x1 . . . x100 je tedy přibližně 2−100H(0.005,0.995)


Typické zprávy

Obecná úloha Uvažujme tyto informační zdroje: I

X s pravděpodobnostní funkcí p na množině X

I

(X1 , . . . , Xn ), n ∈ N, popsaný pomocí sdružené pravděpodobnostní funkce pn (xn ) =

n ∏

p(xi ),

xn = (x1 , . . . , xn ) ∈ Xn

i=1

na množině Xn Interpretace I

zdroj (X1 , . . . , Xn ) je bezpaměťový

I

pravděpodobnost výskytu znaku x ∈ X je vždy p(x)


Typické zprávy

Obecná úloha (pokr.) Pro dlouhé zprávy řešme tuto úlohu bezeztrátové komprese: I

hledáme binární blokový kód pro (X1 , . . . , Xn ): kódujeme celé bloky zpráv x1 . . . xn , nikoli jednotlivé znaky xi !

I

tento kód musí umožňovat jednoznačnou rekonstrukci původních zpráv z Xn

I

cílem je minimalizovat střední délku tohoto kódu

AEP (Asymptotic Equipartition Property) I

využití slabého zákona velkých čísel v teorii informace

I

efektivní komprese zpráv z typické množiny


Typické zprávy

Typičnost Definice Nechť ε > 0. Množina ε-typických zpráv zdroje (X1 , . . . , Xn ) je { } (n) Aε = xn ∈ Xn 2−n(H(X)+ε) 6 pn (xn ) 6 2−n(H(X)−ε) .

Ekvivalentně: zpráva xn ∈ Xn je ε-typická ⇔ 1 H(X) − ε 6 − log pn (xn ) 6 H(X) + ε. n Typické zprávy umožňují “dobrý” odhad entropie H(X).


Typické zprávy

AEP Věta Nechť ε > 0. .1.

Pro každé n ∈ N platí (n)

|Aε | 6 2n(H(X)+ε) .

.2.

Existuje nε takové, že (n)

P(Aε ) > 1 − ε,

.3.

(n)

pro n > nε .

|Aε | > (1 − ε)2n(H(X)−ε) , pro n > nε .


Typické zprávy

Důkaz AEP Důkaz. První tvrzení: 1=

∑

pn (xn ) >

xn ∈Xn

>

∑

∑

pn (xn )

(n)

xn ∈Aε

(n)

2−n(H(X)+ε) = 2−n(H(X)+ε) |Aε |.

(n)

xn ∈Aε

Druhé tvrzení: položme Yi = − log pXi (xi ). Pak E(Yi ) = H(X) a [ ] [ ] (n) P(Aε ) = P |Y¯n − H(X)| 6 ε = P |Y¯n − E(Yi )| 6 ε . Nerovnost tak plyne přímo ze slabého ZVČ.


Typické zprávy

Důkaz AEP (pokr.) Důkaz. Třetí tvrzení: pro n > nε platí ∑ (n) 1 − ε < P(Aε ) = pn (xn ) (n)

6

∑ (n)

xn ∈Aε

xn ∈Aε

(n)

2−n(H(X)−ε) = 2−n(H(X)−ε) |Aε |.


Typické zprávy

Využití AEP (n)

.1.

Horní odhad velikosti Aε

.2.

Množina typických zpráv má pravděpodobnost 1 pro n → ∞

.3.

Dolní odhad velikosti Aε

(n)

(závislý na n > nε )

Kódování pomocí AEP I

přednostní pozornost budeme věnovat typickým zprávám

I

takový přístup ale bude stačit k výhodné kompresi všech zpráv!


Typické zprávy

Kódování pomocí AEP (n)

.1.

každou zprávu z Aε lze zakódovat pomocí nejvýše n(H(X) + ε) + 1 bitů, přidáním počátečního příznakového bitu 0 je horní mez n(H(X) + ε) + 2 bitů

.2.

každou zprávu z Xn \ Aε n log |X| + 2 bitů

(n)

zakódujeme pomocí nejvýše

Vlastnosti I

kód umožňuje dékodování ihned po obdržení kódového slova

I

dosáhneme efektivní komprese: každé kódové slovo je v průměru vyjádřeno pomocí nH(X) bitů


Typické zprávy

Efektivita kódování pomocí AEP Věta Nechť ℓ(Xn ) značí délku kódového slova pro zprávu Xn . Pro každé ˆε > 0 platí ( ) 1 n E ℓ(X ) − H(X) < ˆε, pro n → ∞. n

I

uvedená věta platí pro nezávislé a stejně rozdělené veličiny X1 , X2 , . . . , ale existuje zobecnění pro jisté stacionární zdroje

I

střední délku kódového slova na jeden znak lze tak libovolně přiblížit k entropii původního zdroje


Typické zprávy

Efektivita kódování pomocí AEP (pokr.) Důkaz. Díky 2.tvrzení AEP platí pro n > n0 a ε > 0: ∑ ( ) E n1 ℓ(Xn ) = n1 pn (xn )ℓ(xn ) =

∑

(

xn ∈Xn

pn (xn ) H(X) + ε +

(n)

2 n

)

+

∑

( ) pn (xn ) log |X| + n2 (n)

xn ∈Aε

xn ∈Xn \Aε

) ( ) )( ( (n) (n) = H(X) + ε + n2 P(Aε ) + log |X| + n2 1 − P(Aε ) ( ) 6 H(X) + ε + n2 + ε log |X| + n2 | {z } ˆ ε


Typické zprávy

Ilustrace AEP Příklad Bezpaměťový zdroj generuje n = 25 bitů s pravděpodobnostmi p(0) = 0.4, p(1) = 0.6. Pro ε = 0.1 určíme (n)

.1.

Aε

.2.

P(Aε )

.3.

|Aε |

(n)

(n)

Stačí vyhodnotit počet jednotkových bitů ve zprávě délky 25.


Typické zprávy

Ilustrace AEP (pokr.) 0.15

0.10

0.05

5

10

15

20

Pravděpodobnostní funkce Bi(25,0.6)

25


Typické zprávy

Ilustrace AEP (pokr.) Příklad (pokr.) { (n) .. Aε 1

.2.

=

(x1 , . . . , x25 ) ∈

{0, 1}25

} 25 ∑ 11 6 xi 6 19 i=1

19 ( ) ∑ (n) 25 i 25−i P(Aε ) = = 0.93625 > 1 − ε = 0.9 i 0.6 0.4 i=11

.3.

(n)

|Aε | =

19 ( ) ∑ 25 i=11

i

(n)

= 26 366 510

Odhad velikosti Aε pomocí AEP je ( ) ( ) (n) n H(0.6,0.4)−ε n H(0.6,0.4)+ε 6 3×10 ≈ (1−ε)2 6 |Aε | 6 2 ≈ 1.15×108

Část IV Kódování a komprese Kódy Kraftova nerovnost Konstrukce kódů Huffmanův kód Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Kódování Definice Nechť X je náhodná veličina s výběrovým prostorem X. Nechť D je ∞ ∪ konečná abeceda a D∗ = Dn . Kód pro X je zobrazení n=1

C : X → D∗ . Poznámka. Pro D = {0, . . . , d − 1}, d > 2 hovoříme o d-znakovém kódu. Fyzikální principy přenosu a uchování dat vedou k využití zejména binárních kódů (d = 2).

Definice Střední délka kódu C je L(C) =

∑ x∈X

značí délku řetězce C(x).

pX (x)ℓ(C(x)), kde ℓ(C(x))

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Příklady kódů Příklad 1 Nechť pX (i) = 13 , i = 1, 2, 3. Mějme tento binární kód:

Zřejmě L(C) =

5 3

C(1) = 0, C(2) = 10, C(3) = 11. . = 1.¯6, přičemž H(X) = log 3 = 1.58.

Příklad 2 Nechť pX (i) = 2−i , i = 1, 2, 3 a pX (4) = 18 , i = 4. Mějme tento binární kód: C(1) = 0, C(2) = 10, C(3) = 110, C(4) = 111. Zřejmě L(C) = H(X) = 1.75.

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Třídy kódů Definice Kód C je I

nesingulární, pokud je C : X → D∗ prosté zobrazení.

I

jednoznačně dekódovatelný, pokud je jeho rozšíření C∗ nesingulární, kde C∗ : X∗ → D∗ je definováno pomocí C∗ (x1 . . . xn ) = C(x1 ) . . . C(xn ),

I

x 1 . . . x n ∈ X∗ .

instantní, pokud žádné kódové slovo C(x) není počátečním úsekem kódového slova C(x ′ ) pro x, x ′ ∈ X, x ̸= x ′ .

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Třídy kódů (pokr.) Věta (Vztahy mezi kódy) .1.

Každý instantní kód je jednoznačně dekódovatelný.

.2.

Každý jednoznačně dekódovatelný kód je nesingulární.

Důkaz. Druhé tvrzení plyne příme z definice rozšíření C∗ . Nechť C není jednoznačně dekódovatelný. Potom C∗ je singulární, tedy C∗ (x1 . . . xm ) = C∗ (y1 . . . yn ) pro nějaké dvě zprávy x1 . . . xm , y1 . . . yn ∈ X∗ , kde x1 . . . xm ̸= y1 . . . yn . Kratší ze slov C(x1 ), C(y1 ) musí být tudíž prefixem delšího z nich.

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Třídy kódů (pokr.) x 1 2 3 4 I I

singulární 0 0 0 0

nesingulární 0 010 01 10

jedn. dekódovatelný 10 00 11 110

instantní 0 10 110 111

pro nesingulární kód může být kódové slovo 010 dekódováno jako 2, 14 nebo 31 kód ve 4. sloupci je jednoznačně dekódovatelný: .. 1 .2.

pokud jsou první dva bity 00 nebo 10, lze je dekódovat pokud jsou první dva bity 11, potom 2-1 je-li další bit 1, pak je první znak zprávy 3 2-2 je-li délka řetězce nulových bitů za 11 lichá, pak je první znak zprávy 4 2-3 je-li délka řetězce nulových bitů za 11 sudá, pak je první znak zprávy 3

.3.

na další znaky kódového slova použijeme stejný postup

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Instantní kódy I

neinstantní jednoznačně dekódovatelný kód obecně umožňuje dekódovaní až po přečtení celého rozšířeného kódového slova C(x1 . . . xn )

I

instantní kód umožňuje dekódování ihned po obdržení kódového slova, které je v kódové knize

Příklad X = {1, 2, 3, 4}, C(1) = 0, C(2) = 10, C(3) = 110, C(4) = 111 Potom rozšířené kódové slovo 01011111010 kóduje zprávu 12432, tedy C∗ (12432) = 01011111010.

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Jak konstruovat kódy? Úloha. Pro náhodnou veličinu X hledáme kód C, jehož střední délka L(C) je minimální I

ukážeme, že při hledání minima se lze omezit na množinu instantních kódů

I

při konstrukci instantního kódu nelze přiřazovat krátká kódová slova všem znakům zdrojové abecedy X, neboť to by vedlo k porušení instantnosti

I

existuje dolní mez pro střední délku libovolného kódu, kterou nelze překročit

I

existuje užitečná charakterizace libovolného instantního kódu pomocí délek jeho kódových slov (Kraftova nerovnost)

Kódy

Kraftova nerovnost

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Konstrukce kódů

Huffmanův kód

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Kraftova nerovnost Věta (Kraft, 1949) Délky slov ℓ1 , . . . , ℓm libovolného instantního d-znakového kódu splňují nerovnost m ∑ d −ℓi 6 1. i=1

Obráceně, splňují-li ℓ1 , . . . , ℓm ∈ N tuto nerovnost, potom existuje instantní d-znakový kód s délkami slov ℓ1 , . . . , ℓm .

Příklad Kraftova nerovnost je splněna pro koeficienty ℓ1 , . . . , ℓm každé dyadické pravděpodobnostní funkce p, tedy p splňující p(xi ) = 2 −ℓi , i = 1, . . . , m. Např. pro m = 3 jsou takové koeficienty pouze 1, 2, 2.

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

1.důkaz Kraftovy nerovnosti Větu dokážeme dvěma různými způsoby pro binární kódy (d = 2).

Důkaz. K instantnímu kódu. zkonstruujeme kódovací strom:

.0

.00

.1

.01

.000 .001 .010 .011

.10

.11

.100 .101 .110 .111

V kódovacím stromě jsou kódová slova vyznačena žlutě. Jelikož je kód instantní, žádné kódové slovo není následníkem jiného kódového slova.

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

1.důkaz Kraftovy nerovnosti (pokr.) Pokračování důkazu. Nechť ℓ je délka nejdelšího kódového slova. Potom: I

každé kódové slovo v úrovni ℓi má právě 2ℓ−ℓi následníků v úrovni ℓ

I

tyto množiny následníků jsou vzájemně disjunktní pro všechna kódová slova díky instantnosti kódu

I

počet uzlů v úrovni ℓ je 2ℓ , tedy dostáváme m ∑ i=1

2ℓ−ℓi 6 2ℓ ,

což dává

m ∑ i=1

2 −ℓi 6 1

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

1.důkaz Kraftovy nerovnosti (pokr.) Pokračování důkazu. Obráceně, nechť platí Kraftova nerovnost a ℓ1 6 · · · 6 ℓm . Mějme binární strom hloubky ℓm : I

v úrovni ℓ1 vyznačme libovolný uzel a vyjměme jeho následníky

I

v úrovni ℓ2 existuje alespoň jeden uzel, neboť počet uzlů je zde nyní 2ℓ2 − 2ℓ2 −ℓ1

I

v úrovni ℓ2 vyznačme libovolný uzel a vyjměme jeho následníky

I

v posledním kroku musí na poslední úrovni ℓm zbýt alespoň jeden uzel, jelikož díky Kraftově nerovnosti platí 2ℓm − 2ℓm −ℓ1 − · · · − 2ℓm −ℓm−1 > 1

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Ilustrace Kraftovy nerovnosti Příklad Nalezneme binární kód s délkami kódových slov 1,2,3,3. .

.0

.00

.1

.01

.000 .001 .010 .011

.10

.11

.100 .101 .110 .111

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód


.0

.00

.1

.01

.000 .001 .010 .011

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód


.0

.00

.1

.01

.000 .001 .010 .011

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód


.0

.00

.1

.01

.010 .011

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód


.0

.00

.1

.01

.010 .011

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód


.0

.00

.1

.01

.010 .011

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

2.důkaz Kraftovy nerovnosti Důkaz. Každému kódovému slovu y1 . . . yℓi ∈ {0, 1}∗ lze v dvojkové číselné soustavě přiřadit číslo 0.y1 . . . yℓi =

ℓi ∑

yj 2−j

j=1

z intervalu [0, 1], přičemž toto zobrazení je prosté. Každé kódové slovo tak můžeme ztotožnit s intervalem ⟨ ) 0.y1 . . . yℓi , 0.y1 . . . yℓi + 2−ℓi čísel z ⟨0, 1⟩, jejichž dvojkový rozvoj začíná jako 0.y1 . . . yℓi .

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

2.důkaz Kraftovy nerovnosti (pokr.) Pokračování důkazu. Všechny takové intervaly jsou po dvou disjunktní, jelikož kód je m ∑ instantní, a tudíž 2 −ℓi 6 1. i=1

Obráceně, nechť je pro ℓ1 , . . . , ℓm splněna Kraftova nerovnost. Volme libovolné 0.y1 . . . yℓ1 ∈ ⟨0, 1⟩ a označme I1 = ⟨0, 1⟩, ) ⟨ I(ℓ1 ) = 0.y1 . . . yℓ1 , 0.y1 . . . yℓ1 + 2−ℓ1 ,

I2 = I1 \ I(ℓ1 ).

Uvedenou konstrukci použijeme pro ℓ2 na I2 atd. Kraftova nerovnost spolu s disjunktností všech intervalů Ij zaručuje neprázdnost množin Ij = Ij−1 \ I(ℓj−1 ) a instantnost kódu se slovy y1 . . . yℓ1 , . . . , y1 . . . yℓm .

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Kraftova nerovnost pro jednoznačně dekódovatelné kódy Věta (McMillan, 1956) Délky slov ℓ1 , . . . , ℓm libovolného jednoznačně dekódovatelného d-znakového kódu splňují nerovnost m ∑

d −ℓi 6 1.

i=1

Obráceně, splňují-li ℓ1 , . . . , ℓm ∈ N tuto nerovnost, potom existuje jednoznačně dekódovatelný d-znakový kód s délkami slov ℓ1 , . . . , ℓm .

Kódy

Kraftova nerovnost

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Konstrukce kódů

Huffmanův kód

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Hledáme optimální kód I

Kraftova nerovnost umožňuje konstrukci kódu pomocí zadaných délek kódových slov ℓ1 , . . . , ℓm

I

hledání kódu minimální střední délky tak lze formulovat jako optimalizační úlohu

I

pro pravděpodobnostní funkci pX na m-prvkové množině X a d ∈ N tak hledáme minimum funkce ¯ 1 , . . . , ℓm ) = L(ℓ

m ∑

pX (xi )ℓi

i=1

na množině {

} m ∑ −ℓi (ℓ1 , . . . , ℓm ) ∈ N 61 d m

i=1

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Hledáme optimální kód (pokr.) I

zanedbejme celočíselné omezení kladené na (ℓ1 , . . . , ℓm ) a předpokládejme v Kraftově nerovnosti rovnost: m ∑

d −ℓi = 1

i=1 I

¯ metodou potom snadno nalezneme vázaný extrém funkce L Lagrangeových multiplikátorů: ℓi′ = − logd p(xi ),

I

i = 1, . . . , m

′ ) je hodnota minima rovna Shannonově v bodě (ℓ1′ , . . . , ℓm entropii: ′ ¯ 1′ , . . . , ℓm )= L(ℓ

m ∑ i=1

pX (xi )ℓi′ = Hd (X)

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Hledáme optimální kód (pokr.) I

′ ) ∈ Rm ! nalezli jsme pouze vektor (ℓ1′ , . . . , ℓm

I

′ ) ∈ Nm ovšem pro každou d-adickou pX platí (ℓ1′ , . . . , ℓm

I

můžeme se pokusit najít instantní kód, jehož délky slov by se ′ ), tato úloha je však obtížně “příliš nelišily” od (ℓ1′ , . . . , ℓm řešitelná

Některé konstrukce kódů: .1.

Shannonova

.2.

Huffmanova

.3.

Shannon-Fano-Eliasova Žádný způsob kódování nepřekoná mez danou entropií!

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Dolní mez komprese Věta I

Střední délka L(C) libovolného instantního d-znakového kódu C pro náhodnou veličinu X splňuje nerovnost L(C) > Hd (X).

I

Rovnost L(C) = Hd (X) platí právě tehdy, když pX (x) = d−ℓ(C(x)) .

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Důkaz Důkaz.

L − Hd (X) = −

∑

pX (x) logd d−ℓ(C(x)) +

x∈X

Položme c =

∑

L − Hd (X) =

∑ x∈X

pX (x) logd

pX (x) logd pX (x)

x∈X

d−ℓ(C(x)) , r(x) =

x∈X

∑

d−ℓ(C(x)) . c

Potom

pX (x) − logd c = Dd (pX ∥r) + logd c−1 . r(x)

Ovšem Dd (pX ∥r) > 0 a c 6 1 díky Kraftově nerovnosti. Druhá část tvrzení platí, neboť D(pX ∥r) = 0 ⇔ pX = r.

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Shannonovo kódování Vstup: inf. zdroj (X, p), kde X = {x1 , . . . , xn }, p = (p1 , . . . , pn ) Výstup: kód CS : X → {0, 1, . . . , d − 1}∗ I

bez újmy na obecnosti předpokládáme pi > 0

I

položme

⌈ ⌉ ℓi = logd p−1 , i

tato čísla splňují Kraftovu nerovnost: n ∑ i=1 I

d

−⌈logd p−1 i ⌉

6

n ∑ i=1

d

− logd p−1 i

=

n ∑

pi = 1

i=1

slova kódu CS nalezneme pomocí konstrukce instantního kódu se zadanými délkami ℓi

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Meze Shannonova kódování Věta Platí Hd (X) 6 L(CS ) < Hd (X) + 1.

Důkaz. Snadno plyne z dolní meze komprese a nerovnosti ⌈ ⌉ 6 ℓi = logd p−1 < logd p−1 + 1. logd p−1 i i i

Poznámka. Střední délka optimálního kódu C∗ tedy splňuje Hd (X) 6 L(C∗ ) < Hd (X) + 1.

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Nevhodné kódování Věta (Divergence je cena za nevhodné kódování) Je-li X náhodná veličina s pravděpodobnostní funkcí p a CSq je Shannonův kód zkonstruovaný na základě rozdělení q, potom platí: H(X) + D(p∥q) 6 Lp (CSq ) < H(X) + D(p∥q) + 1.

Důkaz. Odvodíme horní mez, dolní mez se odvodí analogicky: ∑ ⌉ ∑ ( ) ⌈ p(x) log q−1 (x) + 1 Lp (CSq ) = p(x) log q−1 (x) < =

∑ x∈X

x∈X

p(x) log

(

p(x) 1 q(x) p(x)

)

x∈X

+ p(x) = D(p∥q) + H(X) + 1.

Kódy

Kraftova nerovnost

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Konstrukce kódů

Huffmanův kód

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Úvod I

Huffman nalezl v r.1951 optimální kód CH , tedy instantní kód minimalizující střední délku na množině všech jednoznačně dekódovatelných kódů

I

výsledný kód není určen jednoznačně (např. bitovou inverzí získáme jiný optimální kód)

I

jednoznačně není zadána ani délka kódových slov aplikace

I

I I

závěrečné zpracování formátů JPEG, MP3, DEFLATE, PKZIP předzpracování souboru pro aritmetické kódování

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Algoritmus Vstup: inf. zdroj (X, p), kde X = {x1 , . . . , xn }, p = (p1 , . . . , pn ) Výstup: kód CH : X → {0, 1}∗ .1.

.2.

Z prvků množiny X vytvoř množiny S1 = {x1 }, . . . , Sn = {xn }, S = {S1 , . . . , Sn } a uvažuj informační zdroj (S, p) Dokud S není jednoprvková: 2-1 najdi množiny Si , Sj , i ̸= j s nejnižšími pravděpodobnostmi pi , pj 2-2 prvkům z Si připiš bit 0, prvkům z Sj připiš bit 1 (bity připisujeme na začátek kódového slova) 2-3 polož S := S \ {Si , Sj } 2-4 polož S := S ∪ {Si ∪ Sj } a p(Si ∪ Sj ) := p(Si ) + p(Sj )

.3.

Každému xi ∈ X přiřaď slovo CH (xi ), které vzniklo postupným připisováním bitů

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Příklad x 1 2 3 4 5

p(x) 0.25 0.25 0.20 0.15 0.15

x (4, 5) 1 2 3

p(x) 0.30 0.25 0.25 0.20

x (2, 3) (4,5) 1

p(x) 0.45 0.30 0.25

x (1, 4, 5) (2,3)

p(x) 0.55 0.45

. .0 .00 .000 .001

.1 .01

.10

.11

kód 01 10 11 000 001

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Huffmanův vs. Shannonův kód Vždy platí: L(CS ) − L(CH ) < 1. Srovnání délek kód. slov:

Příklad Informační zdroj: X = {x1 , x2 }, p(x1 ) = 0.9999, p(x2 ) = 0.0001. I

Shannonův kód obsahuje slova délky 1 a 14

I

Huffmanův kód obsahuje slova délky 1 a 1

Příklad Informační zdroj: X = {x1 , x2 , x3 , x4 }, p(x1 ) = p(x2 ) = 3−1 , p(x3 ) = 4−1 , p(x4 ) = 12−1 . I

Huffmanův kód má slova délek (2, 2, 2, 2) nebo (1, 2, 3, 3)

I

Shannonův kód dává pro x3 slovo délky 2

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Vlastnosti optimálního kódu Věta Nechť C je instantní binární kód pro X se zdrojovou abecedou X = {1, . . . , n} takovou, že pX (1) > · · · > pX (n). Je-li C optimální, potom: I

je-li pX (x) > pX (y), pak ℓ(C(x)) 6 ℓ(C(y))

I

kódová slova C(n − 1) a C(n) mají stejnou délku a liší se pouze v posledním bitu

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Optimalita Huffmanova kódování Věta Nechť CH je Huffmanův kód a C je libovolný jednoznačně dekódovatelný kód pro náhodnou veličinu X. Potom L(CH ) 6 L(C).

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Vlastnosti Huffmanova kódování Výhody I

minimální střední délka

I

snadná implementace

I

není patentová ochrana

Nevýhody I

vstupem je informační zdroj, což vyžaduje načtení celého souboru dat kvůli výpočtu četností jednotlivých symbolů

I

pro zdroje s entropií 1 bit může být neefektivní

Eliasův kód

Kódy

Kraftova nerovnost

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Konstrukce kódů

Huffmanův kód

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

(Shannon-Fano-)Eliasův kód I

využívá dvojkový rozvoj pX (x) ∈ (0, 1) k zakódování znaku x∈X

I

algoritmus je významnou částí aritmetického kódování

I

předpoklad: vstup je zdroj X s výběrovým prostorem X = {1, . . . , m},

pX (x) > 0

Definice Modifikovaná distribuční funkce je funkce G : X → [0, 1] definovaná jako ∑ G(x) = pX (y) + 12 pX (x), x ∈ X. y<x

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Dvojkový rozvoj pravděpodobností I

zřejmě platí: x1 ̸= x2 ⇒ G(x1 ) ̸= G(x2 )

I

lze využít dvojkový rozvoj G(x) jako binární kód pro x ∈ X?

Příklad X = {1, 2, 3},

pX (1) = 2−1 , pX (2) = pX (3) = 2−2  −2  x=1 2 = 0.012 , −1 −3 G(x) = 2 + 2 = 0.1012 , x=2   −1 −2 −3 2 + 2 + 2 = 0.1112 , x = 3

Dostaneme kód: 01, 101, 111 ale Huffmanův kód: 0, 10, 11! Uvedený postup je možno zobecnit.

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Aproximace I

uvažujme délku kódových slov ℓ(x) := ⌈− log pX (x)⌉ + 1

I

je-li G(x) =

∞ ∑ n=1

an 2−n pro an ∈ {0, 1}, definujeme

⌊G(x)⌋ℓ(x) :=

ℓ(x) ∑

an 2−n

n=1

Věta Pro každé x ∈ X platí G(x) − ⌊G(x)⌋ℓ(x) < 2−ℓ(x) 6 G(x) − FX (x − 1).

Eliasův kód

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Eliasův kód

Algoritmus I

určíme funkce ℓ(x) a ⌊G(x)⌋ℓ(x)

I

zdrojový symbol x ∈ X zakódujeme pomocí ℓ(x) bitů z rozvoje ⌊G(x)⌋ℓ(x)

I

předchozí věta zaručuje, že tento kód je nesingulární

I

…a dokonce instantní!

Věta Eliasův kód C je instantní a pro jeho střední délku platí L(C) > H(X) + 2.

Kódy

Kraftova nerovnost

Konstrukce kódů

Huffmanův kód

Vlastnosti Eliasova kódování Algoritmus lze aplikovat též na celé bloky zdrojových symbolů délky n: I

to ovšem vyžaduje velmi přesnou aritmetiku bitové reprezentace reálných čísel

I

navíc složitost roste exponenciálně s délkou bloku n

I

řešení nabízí aritmetické kódování

Eliasův kód

Část V Univerzální komprese

O čem to bude? Not only does God play dice, sometimes he throws them where we can’t see them. Stephen Hawking I

specifická komprese: všechny doposud uvedené kompresní algoritmy vyžadují znalost pravděpodobnostní funkce pX určující rozdělení zdroje X

I

univerzální komprese nevyžaduje znalost rozdělení zdroje, kódování probíhá “on the fly”

LZ algoritmy I

autoři Lempel a Ziv publikovali 2 základní varianty algoritmu LZ77 a LZ78

I

algoritmus má mnoho různých variací, jako je např. Lempel-Ziv-Welsch LZW

I

jde o třídu adaptivních kompresních algoritmů se slovníkem

I

LZ77 a LZ78 asymptoticky dosahují rychlosti entropie pro tzv. stacionární ergodické zdroje

LZ78 (stromová verze LZ) I

řetězec x1 . . . xn ∈ Xn délky n je sekvenčně testován na výskyt nejkratších řetězců, které se nevyskytly v předchozím kroku

I

každý takový řetězec je označen a uložen do slovníku

I

díky minimalitě ukládaného řetězce jsou jeho prefixy již ve slovníku

I

zvláště řetězec xi . . . xk musel být uložen do slovníku před řetězcem xi . . . xk xk+1

Kód tvoří posloupnost dvojic (Uk , xk ), kde I

Uk je ukazatel na odpovídající prefix xi . . . xℓ ,

I

xk je poslední znak řetězce xi . . . xℓ xk .

Ilustrace LZ78 Příklad X = {A, B}, řetězec ABBABBABBBAABABAA Dostaneme následující řetězce: A, B, BA, BB, AB, BBA, ABA, BAA Posloupnost dvojic: (0, A), (0, B), (2, A), (2, B), (1, B), (4, A), (5, A), (3, A)

Ilustrace LZ78 (pokr.) Příklad X = {0, 1}, řetězec 1011010100010 Dostaneme následující řetězce: 1, 0, 11, 01, 010, 00, 10 Postupně rozšiřujeme délku bitových slov pro vyjádření ukazatelů. Posloupnost dvojic: (, 1), (0, 0), (01, 1), (10, 1), (100, 0), (010, 0), (001, 0) Výsledný kód může tvořit pouze řetězec 100011101100001000010

Lempel-Ziv-Welschův algoritmus (LZW) I

ukládání posledního bitu v LZ78 není efektivní

I

lze ukládat pouze ukazatele do budovaného slovníku

I

LZW je základem většiny aplikací (např. compress v Unixu, ZIP, RAR, komprese v některých modemech, GIF, PDF)

Efektivita LZ78 Nechť c(n) je počet řetězců ve slovníku pro x1 . . . xn ∈ {0, 1}n . I

kód se skládá z c(n) dvojic (ukazatel,poslední bit)

I

potřebujeme tedy celkem nejvýše c(n)(log c(n) + 1) bitů

I

lze ukázat, že pro tzv. stacionární ergodický zdroj (Xn )n∈N je možno docílit asymptoticky optimální komprese, neboť platí c(n)(log c(n) + 1) → H((Xn )n∈N ) n s pravděpodobností 1

Část VI Informační kanály

Kapacita kanálu

Shannonova věta o kapacitě

Motivace Příklad (Vajda,2004) Holub má přepravit 1 bit informace (výhra/prohra bitvy) na místo určení. Jaká je kapacita použitého informačního kanálu v případě, že .1.

bude holub sežrán sokolem s pravděpodobností 0.2

.2.

holub se vyhne sokolům, ale s pravděpodobností 0.2 je odchycen špiónem, který mu zprávu změní na opačnou

Kapacita kanálu


Informační kanál Definice Informační kanál je trojice K = ⟨X, P, Y⟩, kde I

X je m-prvková vstupní abeceda

I

Y je n-prvková výstupní abeceda

I

P je matice m × n podmíněných pravděpodobností:   pY|X (y1 |x1 ) pY|X (y2 |x1 ) . . . pY|X (yn |x1 )  pY|X (y1 |x2 ) pY|X (y2 |x2 ) . . . pY|X (yn |x2 )   P=   .................... pY|X (y1 |xm ) pY|X (y2 |xm ) . . . pY|X (yn |xm )

Kapacita kanálu


Informační kapacita Definice Informační kapacita kanálu K = ⟨X, P, Y⟩ je C(K) = kde I(X; Y) =

∑ ∑ x∈X y∈Y

sup I(X; Y),

pX ∈∆m−1

pX (x)pY|X (y|x) log

pX (x)pY|X (y|x) pX (x)pY (y) .

I

jelikož I(X; Y) je spojitou funkcí pX (x) na kompaktní množině ∆m−1 , supréma se nabývá pro nějaké pX ∈ ∆m−1

I

výpočetně výhodnější jsou vztahy I(X; Y) = H(X) − H(X|Y) = H(Y) − H(Y|X)

Kapacita kanálu


Vlastnosti kapacity Věta Nechť K = ⟨X, P, Y⟩ je informační kanál. Potom: I

C(K) > 0

I

C(K) 6 log m

I

C(K) 6 log n

I

I(X; Y) je spojitá konkávní funkce na množině ∆m−1

Kapacita kanálu


Výpočet kapacity I

hledáme maximum rozdílu H(Y) − H(Y|X) v proměnné pX ∈ ∆m−1

I

lze využít optimalizačních metod

I

výpočet je ovšem snadný pro kanály, v nichž se pravděpodobnostní funkce pY|X (·|xi ), pY|X (·|xj ) liší pouze permutací odpovídajících pravděpodobností

I

v nich totiž H(Y|X) nezávisí na pX , neboť pro každé x ∈ X platí H(Y|X) = H(Y|x)

Kapacita kanálu


Binární bezšumový kanál X = Y = {0, 1} 0..

.1 Kapacita C(K) = 1

.1

.1

.0

.1

Kapacita kanálu


Binární symetrický kanál X = Y = {0, 1} 0..

.1 − p

.0

. p .p .1

.1 − p

Kapacita C(K) = 1 − H(p, 1 − p)

.1

Kapacita kanálu


Šumový kanál s disjunktními přechody X = {0, 1}, Y = {00, 01, 10, 11} .12 .0

.12

.00

.01

. .1

.12 .12

Kapacita C(K) = 1

.10

.11

Kapacita kanálu


Zmatená klávesnice X = Y = {a, b, . . . , z} .a

.b.

.12 .12 .12 .12 .12

.. . .z Kapacita C(K) = log 13

.a

.b

.c .. .

.12

.z

Kapacita kanálu


Binární kanál se zámlkou X = {0, 1}, Y = {0, 1, z} .0

.1 − p

.0

.p .

.z .p

.1 Kapacita C(K) = 1 − p

.1 − p

.1

Kapacita kanálu


Zámlka lepší než záměna Věta Kapacita binárního kanálu s pravděpodobností zámlky 2p (0 < p < 12 ) je větší než kapacita binárního symetrického kanálu s pravděpodobností záměny p.

Kapacita kanálu

Kapacita kanálu



Kapacita kanálu


Bezpaměťové rozšíření kanálu Definice Nechť

( )y∈Y K = ⟨X, pY|X (y|x) x∈X , Y⟩

je informační kanál. Bezpaměťové rozšíření kanálu K je kanál ⟨ ( )y∈Yn ⟩ Kn = Xn , pnY|X (y|x) x∈Xn , Yn , kde pnY|X (y|x) =

n ∏ i=1

pYi |Xi (yi |xi ).

Kapacita kanálu


Kanálové kódování I

kodér funguje na vstupu kanálu jako zobrazení κ : W → Xn

I I

zdroje W s abecedou W = {1, . . . , M} kanál přijímá pouze slova tvaru κ(i) = x(i) dekodér funguje na výstupu kanálu jako zobrazení δ : Yn → W

Definice (M, n)-kód kodéru κ na vstupu kanálu K je množina {x(1), . . . , x(M)} ⊆ Xn M vstupních slov délky n.

Kapacita kanálu


Pravděpodobnosti chyb Definice Pro libovolný (M, n)-kód na vstupu kanálu K definujeme: I

podmíněná pravděpodobnost chyby slova i ∈ W je ∑ ( ) λi = pnY|X y|x(i) y∈Yn δ(y)̸=i

I

maximální pravděpodobnost chyby je λ(n) = max λi i∈W

I

průměrná pravděpodobnost chyby je p(n) =

1 M

M ∑ i=1

λi

Kapacita kanálu


Rychlost kódu a dosažitelnost Definice Rychlost (M, n)-kódu na vstupu kanálu K je R=

log M n

bit/kanálový znak.

Definice Rychlost R > 0 je v kanálu K dosažitelná, existuje-li posloupnost (2nR , n)-kódů takových, že lim λ(n) = 0.

n→∞

Kapacita kanálu


Operační kapacita kanálu Definice Operační kapacita kanálu Cop (K) je suprémum rychlostí R, které jsou v kanálu dosažitelné.

Kapacita kanálu


Shannonova věta Věta (Shannon, 1948) Pro libovolný informační kanál K platí Cop (K) = C(K).

I

důkaz je konstruktivní!

I

ovšem je nutno prohledat všechny možné kodéry, těch je nR

Xn2 I

pro praktické použití se tedy nehodí

Část VII Dodatek

Značení a konvence I

log znamená log2

I

pokud A je konečná množina, pak |A| značí počet prvků v A

I

pro libovolné x ∈ R značí symbol ⌈x⌉ nejmenší celé číslo y takové, že x 6 y

Pravděpodobnostní simplex Definice Nechť X je (n + 1)-prvková množina. Pravděpodobnostní n-simplex je množina ∆n všech pravděpodobnostních funkcí na X: } { n+1 ∑ n+1 pi = 1 . ∆n = p ∈ R pi > 0, i=1

0.0

1.0

0.5

1.0 1.0

0.8

0.6 0.5

0.4

0.2 0.0 0.0 0.5 0.2

0.4

∆1

0.6

0.8

1.0

1.0

∆2

Jensenova nerovnost Věta Nechť f : (a, b) → R je konkávní funkce. Je-li t1 ,∑ . . . , tn ∈ (a, b), potom pro všechna α1 , . . . , αn ∈ ⟨0, 1⟩ splňující ni=1 αi = 1 platí ( n ) n ∑ ∑ f αi ti > αi f(ti ). i=1

i=1

Pokud je f ryze konkávní, potom rovnost v Jensenově nerovnosti implikuje t1 = · · · = tn . Pravděpodobnostní interpretace Je-li X náhodná veličina s konečným výběrovým prostorem X ⊆ R a f je konkávní funkce na nějakém intervalu obsahujícím X, potom f(E X) > E(f(X)).

Literatura Thomas M. Cover and Joy A. Thomas. Elements of information theory. Wiley-Interscience [John Wiley & Sons], NJ, 2006. I. Vajda. Teorie informace. Vydavatelství ČVUT, 2004.

Úvod do teorie informace

Recommend Documents