Lineární kód

Lineární kód je v teorii kódování typem blokového kódu používaným metodami pro detekci a opravu chyb. Lineární kódy umožňují realizaci efektivnějších algoritmů pro kódování a dekódování než jiné kódy.

Formální definice

Lineární kód délky n a stupně k je lineární podprostor dimenze k vektorového prostoru ${\displaystyle \mathbb {F} _{q}^{n}}$, kde ${\displaystyle \mathbb {F} _{q}}$ je konečné těleso s q prvky. Je-li q = 2, respektive q = 3, daný kód se označuje jako binární kód, respektive ternární kód.

JINAK: Lineární kód je kód, kde lineární kombinace dvou nebo i více kódových slov je opět kódové slovo;

Vlastnosti

Jakožto lineární podprostor vektorového prostoru ${\displaystyle \mathbb {F} _{q}^{n}}$ může být kód C zcela reprezentován lineárním obalem minimální množiny kódových slov – neboli báze daného vektorového prostoru. Kódová slova této báze bývají obvykle uspořádána do řádků matice G, označované jako generující matice kódu C. Matice G je ve standardním tvaru, platí-li G = (I_k | A), kde I_k je jednotková matice k × k a A je libovolná matice k × (n − k).

Matice ${\displaystyle H:\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n-k}}$, jejímž jádrem je C, se nazývá kontrolní matice kódu C. Má-li kód C generující matici G = (I_k | A), pak jeho kontrolní matice odpovídá H = (-A^t | I_n-k).

Z definice podprostoru také vyplývá, že minimální Hammingova vzdálenost d mezi libovolným kódovým slovem c₀ a jinými kódovými slovy c ≠ c₀ je konstantní. Jelikož je rozdíl dvou kódových slov c − c₀ z kódu C opět kódovým slovem (tedy prvkem podprostoru C) a zároveň platí d(c, c₀) = d(c − c₀, 0), je možné vyvodit následující:

${\displaystyle \min _{c\in C,\ c\neq c_{0}}d(c,c_{0})=\min _{c\in C,c\neq c_{0}}d(c-c_{0},0)=\min _{c\in C,c\neq 0}d(c,0)=d.}$

Obvyklé značení

Pro různé druhy kódů se obecně používá písmeno C. Lineární kód délky n, dimenze k (tzn. s k kódovými slovy v bázi, nebo také s k řádky generující matice) a s Hammingovou vzdáleností d se označuje jako kód [n, k, d] (nebo přesněji [n, k, d]_q).

Příklady

Příklady některých lineárních kódů:

Reference

V tomto článku byl použit překlad textu z článku Linear code na anglické Wikipedii.