Obsah

1. Teorie kódování

Základy teorie kódování, Shannonova věta. Entropie. Generování skutečně náhodných a pseudonáhodných sekvencí.

Vypracování

Definice

Entropie = nejistota.

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

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

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

Pro funkci nejistoty platí:

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

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

Informace je funkce I(p). Funkce I(p), definovaná pro všechny 0 < p \leq 1, splňuje podmínky:

když je tvaru I(p) = - \lambda \log p, kde \lambda je kladná konstanta (například 1).

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 X_i i-tý vygenerovaný symbol, pak pro každý symbol a_j je pravděpodobnost P(X_i = a_j) = p_j nezávislá na všech v minulosti nebo v budoucnosti vygenerovaných symbolech. X_1, X_2, ... je posloupnost identicky distribuovaných nezávislých náhodných veličin.

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

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

Kódování je možné označovat taky jakou soubor kódových slov C.

Prefixové a jednoznačně dekódovatelné kódy

Kódování se nazývá jednoznačně dekódovatelné, jestliže každý konečný řetězec z \Sigma^* je obraz nejvýše jedné zprávy.

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

Pokud má jednoznačné kódování minimální průměrnou délku slov, nazývá se kompaktní. Kompaktní kód je možné vytvořit například Huffmanovým kódováním.

Věta o kódování bez šumu

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

Kódování se šumem

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

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

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

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 \Sigma_1 = \{a_1, ..., a_m\} a výstupní abecedou \Sigma_2 = \{b_1, ..., b_k\}. Kód délky n je libovolný systém C různých posloupností délky n symbolů ze \Sigma_1. Prvky C se nazývají kódová slova.

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

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

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 p je určena vztahem C(p) = 1 + p \log p + q \log q, kde q = 1 - p.

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

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 C(p) = 0.8. Pak, je-li naše zpráva řetězec nul a jedniček, víme, že pro dostatečně velké n, položíme-li R = 0.75, existuje množina 2^{0.75n} kódových slov délky n, 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í:

  1. Rozdělte zprávu do bloků délky m, přičemž m je takové, že 3 \lceil \frac{n}{4} \rceil = m \geq \frac{3}{4} N_0(\varepsilon).
  2. Zakódujte každý z těchto m-bloků do kódu C_n tak, že použijete kódové slovo délky \frac{4m}{3} pro každý m-blok.
  3. Přeneste nově zakódovanou posloupnost kanálem.

Zjednodušená verzia (Honza R.): Kapacita kanálu je C = 0.8, hľadáme teda kód s kapacitou R = 0.75 < C. Správu rozdelíme do blokov dĺžky m a každý blok kódujeme slovom dĺžky n. Aby sme dosiahly kapacitu prenosu R, musí platiť m = R.n, t.j. m =  \frac{3}{4} n. Veta zaručuje, že pre dostatočne veľké n (a teda aj m) existuje kód s ľubovoľne malou chybou prenosu.

Kódy opravující chyby

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

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

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

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

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

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

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

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

(n, M, d)-kód je maximální, pokud:

  1. Není obsažen v žádném větším kódu se stejnou minimální vzdáleností, tj. není obsažen v žádném (n, M+1, d)-kódu.
  2. pro všechna slova x existuje kódové slovo c s vlastností d(x,c) < d.

Lineární kódy

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

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

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

Každou generující matici je možné následujícími úpravami:

upravit do tvaru [E_k, A], kde E_k je jednotková matice typu k \times k.

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

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

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

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

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

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

Dekódování

Nechť y je obdržený vektor, pak e je možný chybový vektor vektoru y, pokud existuje c \in C takové, že y - c = e. 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ť r \in \mathbb{N} a n = 2^r - 1. Nechť je kontrolní matice H typu r \times (2^r - 1), jejíž sloupce tvoří navzájem nezávislé nenulové vektory z V_r. H je kontrolní matice binárního [n, k]-kódu, kde n = 2^r - 1, k = n - r. Mluvíme pak o Hammingově [n, k]-kódu. Každý Hammingův kód je perfektní kód opravující jednu chybu.

Cyklické kódy

Kód C se nazývá cyklický, pokud:

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

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

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

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}

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

Generování skutečně náhodných a pseudonáhodných sekvencí

Extraktor náhodnosti

Typicky zdroj náhodnosti generuje náhodná data s nějakým rozdělením. Extraktor náhodnosti má za úkol převést toto rozdělení na uniformní rozdělení nebo se mu co nejvíce přiblížit.

Pro známé pravděpodobnosti je možné jednotlivé výstupy shlukovat tak, že extraktor vrátí stejnou hodnotu pro různé vstupy. Pravděpodobnost skupiny je součet pravděpodobností jednotlivých výstupů.

Pro neznámé pravděpodobnosti je možné využít například Von Neumannův extraktor. Zdroj generuje sekvenci náhodných bitů nezávisle podle neznámého pravděpodobnostního rozdělení, 0 s pravděpodobností p a 1 s pravděpodobností 1-p. Sekvenci je možné rozdělit na dvojice bitů:

Generování náhodných sekvencí

Při generování skutečně náhodných sekvencí se využívají různé měřitelné fyzikální jevy, např. rozpad radioaktivních prvků nebo měření atmosferického šumu.

Generování pseudonáhodných sekvencí

V deterministickém prostředí počítačů není možné generovat skutečně náhodná data bez použití specializovaného HW. Softwarově je možné generovat pouze pseudonáhodná data. Generátor pseudonáhodných čísel je algoritmus, který rozvojem náhodné vstupní hodnoty (semínko, seed) generuje výstupní sekvenci. V ideálním případě jsou tato data nerozlišitelná od náhodných. Kvalita generátoru záleží na kvalitě semínka a kvalitě algoritmu.

Von Neumannova middle-square metoda

Vstup generátoru je libovolné číslo, to je umocněno. První a podlední čísla jsou odstraněna a zbytek je použit jako výstup a zároveň semínko pro další iteraci.

Příklad pro vstup 1111:

  1. 1111^2 = 01234321
  2. náhodný výstup 2343
  3. 2343^2 = 05489649
  4. náhodný výstup je 4896

Von Neumann použil 10místná čísla. Tento generátor není dobrý, protože má velmi malou periodu a některé hodnoty (například „0000“) se opakují ještě častěji.

Materiály

Vypracoval

DevelX - Martin Jurča (převzato z 3. otázky oboru PSK)
Drobné úpravy Ondra Mokoš
Opravy Honza Rusnačko