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í:

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

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:

$\forall 0 < p \leq 1: I(p) > 0$
$\forall 0 < p, q \leq 1: I(p \cdot q) = I(p) + I(q)$ , kde $p$ a $q$ jsou pravděpodobnosti navzájem nezávislých jevů
spojitost vzhledem k $p$

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_n$ má $M_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í:

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)$ .
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.
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:

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.
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_q$ má $q^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:

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 $[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:

$C$ je lineární
pokud vektor $w = (w_1, ..., w_n) \in C$ , pak i vektor $w' = (w_n, w_1, ..., w_{n - 1}) \in C$ .

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ů:

00, 11 – žádný výstup,
01 – výstup 0 s pravděpodobností $p \cdot (1-p)$ ,
10 – výstup 1 s pravděpodobností $(1-p) \cdot p$ .

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$ :

$1111^2 = 01234321$
náhodný výstup $2343$
$2343^2 = 05489649$
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

Odpovídá učivu z předmětu M8170 Teorie kódování
Předmět má dobrá skripta - http://is.muni.cz/el/1431/jaro2011/M8170/um/ (soubor PREDLAwideboc.pdf)
IV111 (Bouda) - Všechny slidy

Vypracoval

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

Obsah