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

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

  • 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 %

mgr-szz/in-psk/3-psk.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0