Teorie Entropie a Kodovani

Teorie kódování

Základní pojmy

Označme $\chi := X(\Omega)$ množinu všech hodnot diskrétní náhodné veličiny $X$.

Definice: Kód diskrétní náhodné veličiny
Buď $D = \{0, 1, \dots, D - 1\}$ konečná abeceda. Kód diskrétní náhodné veličiny $X$ je libovolné zobrazení $C : \chi \to D^*$, kde $$D^* = \bigcup_{n \in \mathbb{N}} D^n$$ je množina konečných řetězců symbolů abecedy $D$.

Definice: Kódové slovo a střední délka kódu
Hodnotu $C(x)$ kódu $C$ diskrétní náhodné veličiny $X$ v bodě $x \in \chi$ nazýváme kódovým slovem příslušným k hodnotě $x$ a jeho délku značíme $l(x)$.
Střední délka kódu $C$ je $$L(C) = E[l(X)] = \sum_{x \in \chi} l(x) P(X = x).$$

Definice: Typy kódů
Kód $C$ diskrétní náhodné veličiny $X$ je:

• nesingulární, pokud je $C : \chi \to D^*$ prosté zobrazení, tj. pro každé $x, x' \in \chi$ platí $(x \neq x') \Rightarrow (C(x) \neq C(x'))$,
• jednoznačně dekódovatelný, pokud je jeho rozšíření $C^*$ nesingulární, kde $C^* : \chi^* \to D^*$ je definováno pomocí $$C^*(x_1 \dots x_n) = C(x_1) \dots C(x_n), \text{ pro každé } n \in \mathbb{N} \text{ a } x_1, \dots, x_n \in \chi,$$
• instantní (prefixový), pokud žádné kódové slovo není počátkem jiného kódového slova.

Platí:

• Jednoznačně dekódovatelný kód je nesingulární.
• Instantní kód je jednoznačně dekódovatelný.

Huffmanův kód

Sestavení stromu pro Huffmanův kód:

1. Vytvoř list pro každý symbol a dej všechny do fronty.
2. Dokud je ve frontě více než jeden uzel:
3. Vyjmi dva uzly s nejnižší pravděpodobností z fronty.
4. Vytvoř nový uzel s těmito dvěma uzly jako potomky a s pravděpodobností rovnou součtu jejich pravděpodobností.
5. Zařaď tento uzel do fronty.
6. Zbývající uzel je kořen a strom je kompletní.

Sestavení kódu:

1. Přiřaď hranám hodnoty 1 a 0, např. 1 vždy vedoucí k potomkovi s vyšší pravděpodobností.
2. Kódové slovo je sekvence hodnot čtených od kořene.

Vlastnosti Huffmanova kódu:

• Huffmanův kód je optimální, tj. je-li $C^*$ Huffmanův kód a $C'$ libovolný jednoznačně dekódovatelný kód, pak $$L(C^*) \leq L(C').$$ Navíc platí $$H_D(X) \leq L(C^*) < H_D(X) + 1.$$

Teorie entropie

Základní entropie

Definice: Shannonova entropie
(Shannonova) entropie diskrétní náhodné veličiny $X$ s pravděpodobnostní funkcí $p(x) = P(X = x)$ definujeme jako $$H(X) = - E \log p(X) = - \sum_{x \in \chi} p(x) \log p(x),$$ kde klademe $0 \log 0 = 0$.

Platí: - $H(X) \geq 0$ - Obecně definujeme $H_b(X)$ s použitím logaritmu o základu $b$. Není-li řečeno jinak, uvažujeme základ logaritmu $b = 2$. $$H_b(X) = (\log_b c)H_c(X)$$

Věta o střední délce kódu a entropii:
Nechť $C$ je jednoznačně dekódovatelný kód diskrétní náhodné veličiny $X$ nad $D$-ární abecedou. Potom platí nerovnost $$L(C) \geq H_D(X).$$ Rovnost nastává právě tehdy, když pro každé $x \in \chi$ $$P(X = x) = D^{-l(x)}.$$

Sdružená a podmíněná entropie

Definice: Sdružená entropie
Sdružená entropie $H(X, Y)$ diskrétních náhodných veličin $X$ a $Y$, jejichž rozdělení je určeno sdruženou pravděpodobnostní funkcí $p(x, y) = P(X = x, Y = y)$, je definována vztahem $$H(X, Y) = -E \log p(X, Y) = - \sum_{x \in X} \sum_{y \in Y} p(x, y) \log p(x, y).$$

Definice: Podmíněná entropie
Nechť $X$ a $Y$ jsou diskrétní náhodné veličiny se sdruženou pravděpodobnostní funkcí $p(x, y)$. Podmíněná entropie $H(Y | X)$ je definována vztahem $$H(Y | X) = -E \log p(Y | X) = -\sum_{x \in X} \sum_{y in Y} p(x, y) \log \frac{p(y|x)}{p(x)} = \sum_{x \in X} p(x)H(Y | X = x),$$ kde $$p(y|x) = \frac{P(X = x, Y = y)}{P(X = x)}$$ je podmíněná pravděpodobnostní funkce.

Věta (Chain rule):
$$H(X, Y) = H(X) + H(Y | X).$$

Důsledek:
Pro nezávislé $X$ a $Y$ platí $$H(X, Y) = H(X) + H(Y).$$

Relativní entropie a vzájemná informace

Definice: Relativní entropie
Relativní entropie nebo Kullback-Leiblerova vzdálenost $D(p || q)$ mezi pravděpodobnostní funkcí $p$ a pravděpodobnostní funkcí $q$ nějaké diskrétní náhodné veličiny je definována vztahem $$D(p||q) = E_p \left(\log \frac{p(X)}{q(X)}\right) = \sum_{x \in X} p(x) \log \frac{p(x)}{q(x)}.$$

Definice: Vzájemná informace
Vzájemná informace $I(X; Y)$ je definována vztahem $$I(X; Y) = D(p(x, y) || p(x)p(y)) = E_{p(x,y)} \left(\log \frac{p(X, Y)}{p(X)p(Y)}\right) = \sum_{x \in X} \sum_{y \in Y} p(x, y) \log \frac{p(x, y)}{p(x)p(y)}.$$

Vlastnosti vzájemné informace:

• $I(X; Y) = I(Y; X)$
• $I(X; Y) = H(X) - H(X|Y)$
• $I(X; Y) = H(Y) - H(Y|X)$
• $I(X; Y) = H(X) + H(Y) - H(X, Y)$
• $I(X; Y) \geq 0$ a $I(X; Y) = 0$ právě tehdy, když jsou $X$ a $Y$ nezávislé.