====== Zadání ======

Kódování: Entropie, nejistota, informace. Kódování a dekódovací pravidla, kódování s šumem. Shannonova věta, kódy opravující chyby. Lineární, binární Hammingovy a cyklické kódy.

====== Vypracování ======

===== Definice =====

Entropie = nejistota.

Nechť <math>X</math> je náhodná veličina, <math>P(X = 0) = p</math> a <math>P(X = 1) = 1 - p</math>, přičemž <math>0 < p < 1</math>.

Nejistota je funkce pravděpodobnosti dané veličiny.

Nejistota náhodné proměnné <math>Z</math>, která nabývá hodnoty <math>a_i</math> s pravděpodobností <math>p_i, (1 \leq i \leq n)</math> je funkcí pouze pravděpodobností <math>p_1, ..., p_n</math>. Tato funkce se značí <math>H(p_1, ..., p_n)</math>.

Pro funkci nejistoty platí:
  * <math>H(p_1, ..., p_n)</math> je maximální, když <math>p_1 = p_2 = ... = p_n = \frac{1}{n}</math>
  * pro každou permutaci <math>\pi</math> na <math>\{1, ..., n\}</math> platí <math>H(p_1, ..., p_n) = H(p_{\pi(1)}, ..., p_{\pi(n)})</math>
  * <math>H(p_1, ..., p_n) \geq 0</math> a rovnost nastává právě tehdy, když <math>p_i = 1</math> pro nějaké <math>i</math>.
  * <math>H(p_1, ..., p_n, 0) = H(p_1, ..., p_n)</math>
  * <math>H(\frac{1}{n}, ..., \frac{1}{n}) \leq H(\frac{1}{n + 1}, ..., \frac{1}{n + 1})</math>
  * <math>H(p_1, ..., p_n)</math> je spojitá funkce svých parametrů. Malé změny na vstupu dají malé změny na výstupu.
  * Pro <math>m, n \in \mathbb{N}: H(\frac{1}{m \cdot n}, ..., \frac{1}{m \cdot n}) = H(\frac{1}{m}, ..., \frac{1}{m}) + H(\frac{1}{n}, ..., \frac{1}{n})</math>
  * Nechť <math>p = p_1 + ... + p_m</math> a <math>q = q_1 + ... + q_n</math>, <math>p_i</math>, <math>q_j</math> jsou neznámé. Jsou-li <math>p</math> a <math>q</math> kladná čísla, <math>p + q = 1</math>, pak platí: <math>H(p_1, ..., p_m, q_1, ..., q_n) = H(p, q) + p \cdot H(\frac{p_1}{p}, ..., \frac{p_m}{p}) + q \cdot H(\frac{q_1}{q}, ..., \frac{q_n}{q})</math>

Buď <math>H(p_1, ..., p_n)</math> funkce definovaná pro každé <math>n \in \mathbb{N}</math> a pro všechny hodnoty <math>p_1, ..., p_n</math> tak, že <math>p_i \geq 0</math> a <math>\sum\limits_{i = 1}^{n} p_i = 1</math>. Pokud <math>H</math> splňuje výše uvedené axiomy, pak platí:

<math>H(p_1, ..., p_n) = - \lambda \sum\limits_{k} p_k \cdot </math> log <math>p_k</math>\\
kde <math>\lambda</math> je libovolná kladná konstanta (například <math>1</math>) a sumuje se přes všechna <math>k</math> taková, že <math>p_k > 0</math>.

Informace je funkce <math>I(p)</math>. Funkce <math>I(p)</math>, definovaná pro všechny <math>0 < p \leq 1</math>, splňuje podmínky:
  * <math>\forall 0 < p \leq 1: I(p) > 0</math>
  * <math>\forall 0 < p, q \leq 1: I(p \cdot q) = I(p) + I(q)</math>, kde <math>p</math> a <math>q</math> jsou pravděpodobnosti navzájem nezávislých jevů
  * spojitost vzhledem k <math>p</math>
když je tvaru <math>I(p) = - \lambda</math> log <math>p</math>, kde <math>\lambda</math> je kladná konstanca (například <math>1</math>).
===== Kódování =====

Nejjednodušším modelem je zdroj bez paměti a kódování bez šumu. Zdroj je generátor posloupnosti symbolů z dané konečné abecedy. Pro zdroj bez paměti platí, značí-li <math>X_i</math> <math>i</math>-tý vygenerovaný symbol, pak pro každý symbol <math>a_j</math> je pravděpodobnost <math>P(X_i = a_j) = p_j</math> nezávislá na všech v minulosti nebo v budoucnosti vygenerovaných symbolech. <math>X_1, X_2, ...</math> je posloupnost identicky distribuovaných nezávislých náhodných veličin.

Entropie zdroje bez paměti je <math>H = - \sum p_j</math> log <math>p_j</math>, kde sčítáme přes množinu <math>j</math> takových, že <math>p_j > 0</math>.

Kódování nebo kód je zobrazení <math>f</math> z <math>\{w_1, ..., w_n\}</math> do <math>\Sigma^*</math>. Zpráva je konečný řetěz zdrojových slov. Je li správa <math>m = w_{i_1}...w_{i_k}</math> a <math>f</math> kódování, pak rozšíření <math>f</math> k <math>W^*</math> je definováno: <math>f(m) = f(w_{i_1})...f(w_{i_k})</math>.

Kódování je možné označovat taky jakou soubor kódových slov <math>C</math>.
==== Prefixové a jednoznačně dekódovatelné kódy ====

Kódování se nazývá bezprostředně dekódovatelné nebo prefixové, jestliže neexistují různé <math>w_i</math> a <math>w_j</math> takové, že <math>f(w_i)</math> je prefix <math>f(w_j)</math>.

Pokud má jednoznačné kódování minimální průměrnou délku slov, nazývá se kompaktní.

Má-li zdroj bez paměti entropii <math>H</math>, pak každé jednoznačně dekódovatelné kódování pro tento zdroj v abecedě o <math>D</math> symbolech musí mít délku alespoň <math>H =</math> log <math>D</math>: Navíc existuje takové jednoznačně dekódovatelné kódování, které má průměrnou délku slov menší nebo rovnu <math>1 + H =</math> log <math>D</math>.

Kompaktní kód je možné vytvořit například Huffmanovým kódováním.

===== Kódování s šumem =====

Uvážíme diskrétní kanál bez paměti. Kanál má vstupní <math>\Sigma_1</math> a výstupní <math>\Sigma_2</math> abecedu.

Pro vypouštěcí kanál platí, že <math>\Sigma_2 = \Sigma_1 \cup \{ * \}</math>, kde <math>*</math> představuje chybu přenosu, ke které dojde s pravděpodobností <math>\varepsilon</math>. Vypouštěcí kanál nedokáže zaměnit jeden znak abecedy za jiný znak vstupní abecedy, pouze zaměnit znak za <math>*</math>.

Nejběžnější model kanálu je binární symetrický kanál, kde <math>\Sigma_1 = \Sigma_2 = \{0, 1\}</math> a kanál může změnit <math>0</math> na <math>1</math> nebo naopak s pravděpodobností <math>p</math>.

Pro zajištění vyšší spolehlivosti přenosu zpráv je používaná redundance, parita, nebo jiné techniky, které umožňují detekovat nebo opravit chybně přenesenou zprávu.

===== Kódování a dekódovací pravidla =====

Buď dán kanál bez paměti se vstupní abecedou <math>\Sigma_1 = \{a_1, ..., a_m\}</math> a výstupní abecedou <math>\Sigma_2 = \{b_1, ..., b_k\}</math>. Kód délky <math>n</math> je libovolný systém <math>C</math> různých posloupností délky <math>n</math> symbolů ze <math>\Sigma_1</math>. Prvky <math>C</math> se nazývají kódová slova.

Je-li dán kód délky <math>n</math> s kódovými slovy <math>c_1, c_2, ..., c_N</math>, dekódovací pravidlo je libovolný rozklad množiny možných obdržených posloupností do disjunktních množin <math>R_1, R_2, ..., R_N</math> se zřejmou interpretací toho, že je-li obdržená posloupnost <math>y</math> prvkem <math>R_j</math>, pak <math>y</math> je dekódováno jako kódové slovo <math>c_j</math>.

Předpokládáme, že <math>C</math> neobsahuje symbol <math>?</math>, rozhodovací (dekódovací) pravidlo je funkce <math>f: \Sigma_2^n \rightarrow C \cup \{?\}</math>. Je-li <math>y</math> slovo v <math>\Sigma_2^n</math>, pak dekódovací pravidlo dekóduje <math>y</math> na <math>f(y)</math>, jinak hlásí chybu pokud <math>f(y) = ?</math>.

===== Shannonova věta =====

Kapacita kanálu je jeho míra schopnosti přenášet informace. Kapacita binárního symetrického kanálu s pravděpodobností chyby přenosu <math>p</math> je určena vztahem <math>C(p) = 1 + p</math> log <math>p + q</math> log <math>q</math>, kde <math>q = 1 - p</math>.

Buď dán binární symetrický kanál kapacity <math>C</math> a libovolné <math>R</math>, <math>0 < R < C</math>. Pak pro každou posloupnost <math>(M_n: 1 \leq n < \infty)</math> přirozených čísel splňujících <math>1 \leq M_n \leq 2^{R n} (1 \leq n < \infty)</math>, a všechna kladná <math>\varepsilon > 0</math>, existuje posloupnost kódů <math>(C_n: 1\leq n < \infty)</math> a přirozené číslo <math>N_0(\varepsilon)</math> tak, že <math>C_n</math> má <math>M_n</math> kódových slov délky <math>n</math> a maximální pravděpodobnost chyby <math>e(C_n) \leq \varepsilon</math> pro všechna <math>n \geq N_0(\varepsilon)</math>.

Jakým způsobem funguje tato věta. Předpokládejme, že pravděpodobnost chyby takovéhoto kanálu je taková, že kapacita kanálu <math>C(p) = 0.8</math>. Pak, je-li naše zpráva řetězec nul a jedniček, víme, že pro dostatečně velké <math>n</math>, položíme-li <math>R = 0.75</math>, existuje množina <math>2^{0.75n}</math> kódových slov délky <math>n</math>, která mají pravděpodobnost chyby menší než libovolně předem předepsaná hranice. Tudíž, abychom zakódovali zprávu ze zdroje, postup je následující:
  - Rozdělte zprávu do bloků délky <math>m</math>, přičemž <math>m</math> je takové, že <math>3 \lceil \frac{n}{4} \rceil = m \geq N_0(\varepsilon)</math>.
  - Zakódujte každý z těchto <math>m</math>-bloků do kódu <math>C_n</math> tak, že použijete kódové slovo délky <math>\frac{4m}{3}</math> pro každý <math>m</math>-blok.
  - Přeneste nově zakódovanou posloupnost kanálem.

===== Kódy opravující chyby =====

Buď <math>u, v</math> přirozená čísla. Řekneme, že kód <math>C</math> určí <math>u</math> chyb, jestliže pokud každé kódové slovo změníme alespoň na jednom a ne více než <math>u</math> místech, nebude výsledný řetězec kódové slovo. Řekneme, že kód <math>C</math> určí právě <math>u</math> chyb, jestliže určí <math>u</math> chyb a neurčí <math>u + 1</math> chyb.

Řekneme, že kód <math>C</math> opraví <math>v</math> chyb, jestliže, pokud použijeme pravidlo minimální vzdálenosti, jsme schopni opravit alespoň <math>v</math> chyb a v případě, kdy se nebudeme moci rozhodnout, dostaneme na výstupu chybu v dekódování. Řekneme, že kód <math>C</math> opraví právě <math>v</math> chyb, jestliže opraví <math>v</math> chyb a neopraví <math>v + 1</math> chyb.

Hammingova vzdálenost <math>d(x, y)</math> mezi vektory <math>x</math> a <math>y</math> je počet míst, ve kterých se <math>x</math> a <math>y</math> liší. Váha slova <math>x = x_1 x_2 ... x_n</math> je pak počet nenulových znaků slova <math>x</math>, t.j. <math>wt(x) = d(x, 0)</math>, kde <math>0</math> je slovo z <math>n</math> nul.

Buď <math>x \in Z_r^n, \rho > 0</math>. Sférou <math>S_\rho^{n, r}(x)</math> v <math>Z_r^n</math> se středem <math>x</math> a poloměrem <math>\rho</math> rozumíme množinu <math>S_{\rho}^{n, r}(x) = \{y \in Z_r^n | d(x, y) \leq \rho\}</math>.

Objemem sféry <math>S_\rho^{n, r}(x)</math> nazveme číslo <math>V_\rho^{n, r}(x) = card(S_\rho^{n, r}(x))</math>, t.j. počet řetězců délky <math>n</math>, které mají Hammingovu vzdálenost od <math>x</math> nejvýše <math>\rho</math>.

Platí, že <math>V_\rho^{n, r}(x) = \sum\limits_{k = 0}^{\rho} {n \choose k} (r - 1)^k</math>.

Pro kód <math>C</math> platí, že minimální vzdálenost kódu <math>C</math> je <math>d(C) = min\{d(c_i, c_j)\}</math>. Má-li kód minimální vzdálenost <math>d</math>, lze opravit pomocí dekódování podle pravidla minimální vzdálenosti až <math>\frac{1}{2} (d - 1)</math> chyb. Kód <math>C</math> určí <math>d - 1</math> chyb.

Pokud má kód <math>C</math> právě <math>M</math> kódových slov délky <math>n</math> a minimální vzdálenost <math>d</math>, mluvíme o <math>(n, M, d)</math>-kódu.
===== Lineární kódy =====

Považujme <math>\Sigma</math> za těleso <math>F_q</math> o <math>q</math> prvcích. Buď dále <math>V_n(q)</math> vektorový prostor dimenze <math>n</math> nad tělesem <math>F_q</math>. Typický prvek tohoto vektorového prostoru budeme psát jako <math>x = (x_1, ..., x_n)</math>, případně <math>x = x_1 ... x_n</math>, kde <math>x_i \in F_q</math>.

Lineární kód <math>C</math> nad <math>\Sigma</math> je definován jakožto podprostor prostoru <math>V_n(q)</math>. Má-li tento podprostor dimenzi <math>k</math>, mluvíme o <math>[n, k]</math>-kódu, pokud je minimální vzdálenost <math>d</math>, tak mluvíme o <math>[n, k, d]</math>-kódu. Protože každý k-dimenzionální podprostor nad <math>F_q</math> má <math>q^k</math> prvků, každý <math>[n, k, d]</math>-kód nad <math>F_q</math> je <math>(n, q^k, d)</math>-kód.

Generující matice pro lineární <math>[n, k]</math> kód je libovolná matice rozměrů <math>k \times n</math>, jejíž řádky tvoří <math>k</math> lineárně nezávislých kódových slov z <math>C</math>.

Každou generující matici je možné následujícími úpravami:
  * záměna řádků
  * násobení řádku nenulovým skalárem
  * přičtení k řádku skalární násobek jiného řádku
  * záměna sloupců
  * násobení sloupce nenulovým skalárem
upravit do tvaru <math>[E_k, A]</math>, kde <math>E_k</math> je jednotková matice typu <math>k \times k</math>.

Minimální vzdálenost <math>d</math> lineárního kódu <math>C</math> je minimální váha <math>w</math> všech nenulových vektorů z <math>C</math>.

Nechť <math>C</math> je lineární <math>[n, k]</math>-kód nad <math>F_q = \Sigma</math> a má generující matici:

<math>G = \begin{bmatrix} r_1 \\ r_2 \\ \vdots \\ r_k \end{bmatrix} = [E_k, A]</math>.

Kódová slova <math>C</math> jsou vektory délky <math>n</math> tvaru <math>\sum\limits_{i = 1}^{k} a_i r_i</math>, <math>a_i \in F_q</math>.

Pokud je zpráva braná jako posloupnost <math>s = (s_1, ..., s_k)</math>, zakódujeme <math>s</math> pomocí kódového slova <math>c = (c_1, ..., c_n)</math>, kde <math>c_i</math> jsou určena předpisem <math>[c_1, ..., c_n] = [s_1, ..., s_n][E_k, A]</math>.

Matice kontroly parity kódu <math>C</math> je matice <math>H = [-A^T, E_{n - k}]</math>. Platí, že <math>z \in C</math> právě tehdy, když <math>H[z_1, ..., z_n]^T = 0</math>. <math>C</math> má minimální vzdálenost <math>d</math> tehdy a jen tehdy, když každých <math>d - 1</math> sloupců matice <math>H</math> je nezávislých, ale některých <math>d</math> sloupců je lineárně závislých.

==== Dekódování ====

Nechť <math>y</math> je obdržený vektor, pak <math>e</math> je možný chybový vektor vektoru <math>y</math>, pokud existuje <math>c \in C</math> takové, že <math>y - c = e</math>. Pro dekódování podle pravidla minimální vzdálenosti stačí najít chybový vektor s minimální vahou.
===== Binární Hammingovy kódy =====

Nechť <math>r \in \mathbb{N}</math> a <math>n = 2^r - 1</math>. Nechť je kontrolní matice <math>H</math> typu <math>r \times (2^r - 1)</math>, jejíž sloupce tvoří navzájem nenulové vektory z <math>V_r</math>. <math>H</math> je kontrolní matice binárního <math>[n, k]</math>-kódu, kde <math>n = 2^r - 1, k = n - r</math>. Mluvíme pak o Hammingově <math>[n, k]</math>-kódu. Každý Hammingův kód je perfektní kód opravující jednu chybu.
===== Cyklické kódy =====

Kód <math>C</math> se nazývá cyklický, pokud:
  * <math>C</math> je lineární
  * pokud vektor <math>w = (w_1, ..., w_n) \in C</math>, pak i vektor <math>w' = (w_n, w_1, ..., w_{n - 1}) \in C</math>.

Vektor <math>w</math> je možné identifikovat polynomem <math>w(x) = w_1 + w_2 x + w_3 x^2 + ... + w_n x^{n - 1}</math>. Je-li <math>w(x)</math> polynomiální reprezentace <math>w \in C</math>, je i <math>w(x)f(x)</math> kódové slovo pro každý polynom <math>f</math> stupně nejvýše <math>n - 1</math>.

Je-li <math>g(x)</math> nenulový polynom minimálního stupně v <math>C</math>, pak <math>g(x)</math> generuje kód <math>C</math> v tom smyslu, že každé kódové slovo <math>w(x) \in C</math> je tvaru <math>w(x) = f(x)g(x)</math> pro vhodný polynom <math>f(x)</math>.

Je-li <math>C</math> cyklický kód délky <math>n</math> s generujícím polynomem <math>g(x) = g_1 + g_2 x + ... + g_k x^{k-1}</math>, pak jeho generující matice typu <math>(n - k + 1) \times n</math> má tvar:

<math>G = \begin{bmatrix} g_1 & g_2 & g_3 & \dots & g_k & 0 & 0 & \dots & 0 \\ 0 & g_1 & g_2 & \dots & g_{k - 1} & g_k & 0 & \dots & 0 \\ 0 & 0 & g_1 & \dots & g_{k - 2} & g_{k - 1} & g_k & \dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & \dots & \dots & \dots & g_{k - 2} & g_{k - 1} & g_k \end{bmatrix}</math>

Je-li <math>g</math> generující polynom cyklického kódu <math>C</math> délky <math>n</math>, pak <math>g</math> dělí polynom <math>(x^n - 1)</math>.

====== Předměty ======

[[https://is.muni.cz/auth/predmety/predmet.pl?id=458527|PřF:M8170]] Teorie kódování (jaro 2009), doc. RNDr. Jan Paseka, CSc.

====== Použitá literatura ======

-

====== Vypracoval ======

DevelX - Martin Jurča

stav - 100 %