Obsah

Zadání
Vypracování
Předměty
Použitá literatura
Vypracoval

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ť $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á konstanca (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$ 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 sprá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á 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í.

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

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í $\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} (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 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.

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.

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

Předměty

PřF:M8170 Teorie kódování (jaro 2009), doc. RNDr. Jan Paseka, CSc.

Použitá literatura

Vypracoval

DevelX - Martin Jurča

stav - 100 %