Lineární kód

Z Multimediaexpo.cz

(Rozdíly mezi verzemi)

Aktuální verze z 14. 8. 2022, 14:52

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.

Obsah

1 Formální definice
2 Vlastnosti
3 Obvyklé značení
4 Příklady
5 Externí odkazy

Formální definice

Lineární kód délky n a stupně k je lineární podprostor o rozměru k vektorového prostoru \(\mathbb{F}_q^n\), kde \(\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 \(\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 \(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í:

\(\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].

Příklady

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

Externí odkazy

Náklady na energie a provoz naší encyklopedie prudce vzrostly. Potřebujeme vaši podporu... Kolik ?? To je na Vás. Náš FIO účet — 2500575897 / 2010
Informace o článku. Článek je převzat z Wikipedie, otevřené encyklopedie, do které přispívají dobrovolníci z celého světa. Tento text je dostupný za podmínek Creative Commons 3.0 Unported – creativecommons.org. Originální článek na české Wikipedii

@@ Řádka 3: / Řádka 3: @@
 == Formální definice ==
-'''Lineární kód''' délky ''n'' a stupně ''k'' je [[lineární podprostor]] o rozměru ''k'' [[vektorový prostor|vektorového prostoru]] <math>\mathbb{F}_q^n</math>, kde <math>\mathbb{F}_q</math> je konečné těleso s ''q'' prvky. Je-li ''q''&nbsp;=&nbsp;2, respektive ''q''&nbsp;=&nbsp;3, daný kód se označuje jako '''binární kód''', respektive '''ternární kód'''.
+'''Lineární kód''' délky ''n'' a stupně ''k'' je [[lineární podprostor]] o rozměru ''k'' [[vektorový prostor|vektorového prostoru]] <big>\(\mathbb{F}_q^n\)</big>, kde <big>\(\mathbb{F}_q\)</big> je konečné těleso s ''q'' prvky. Je-li ''q''&nbsp;=&nbsp;2, respektive ''q''&nbsp;=&nbsp;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''';
@@ Řádka 9: / Řádka 9: @@
 == Vlastnosti ==
-Jakožto lineární podprostor vektorového prostoru <math>\mathbb{F}_q^n</math> může být kód ''C'' zcela reprezentován [[lineární obal|lineárním obalem]] minimální množiny kódových slov – neboli [[báze (algebra)|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<sub>k</sub> | A), kde I<sub>k</sub> je [[jednotková matice]] k&nbsp;×&nbsp;k a A je libovolná matice k&nbsp;×&nbsp;(n&nbsp;−&nbsp;k).
+Jakožto lineární podprostor vektorového prostoru <big>\(\mathbb{F}_q^n\)</big> může být kód ''C'' zcela reprezentován [[lineární obal|lineárním obalem]] minimální množiny kódových slov – neboli [[báze (algebra)|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<sub>k</sub> | A), kde I<sub>k</sub> je [[jednotková matice]] k&nbsp;×&nbsp;k a A je libovolná matice k&nbsp;×&nbsp;(n&nbsp;−&nbsp;k).
-Matice <math>H: \mathbb{F}_q^n\to \mathbb{F}_q^{n-k}</math>, jejímž [[jádro matice|jádrem]] je ''C'', se nazývá [[kontrolní matice]] kódu ''C''. Má-li kód ''C'' generující matici G = (I<sub>k</sub> | A), pak jeho kontrolní matice odpovídá H = (-A<sup>t</sup> | I<sub>n-k</sub>).
+Matice <big>\(H: \mathbb{F}_q^n\to \mathbb{F}_q^{n-k}\)</big>, jejímž [[jádro matice|jádrem]] je ''C'', se nazývá [[kontrolní matice]] kódu ''C''. Má-li kód ''C'' generující matici G = (I<sub>k</sub> | A), pak jeho kontrolní matice odpovídá H = (-A<sup>t</sup> | I<sub>n-k</sub>).
 Z definice podprostoru také vyplývá, že minimální [[Hammingova vzdálenost]] ''d'' mezi libovolným kódovým slovem ''c''<sub>0</sub> a jinými kódovými slovy ''c''&nbsp;≠&nbsp;''c''<sub>0</sub> je konstantní. Jelikož je rozdíl dvou kódových slov ''c''&nbsp;−&nbsp;''c''<sub>0</sub> z kódu ''C'' opět kódovým slovem (tedy prvkem podprostoru ''C'') a zároveň platí ''d''(''c'',&nbsp;c<sub>0</sub>)&nbsp;=&nbsp;''d''(''c''&nbsp;−&nbsp;''c''<sub>0</sub>,&nbsp;0), je možné vyvodit následující:
-:<math>\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.</math>
+:<big>\(\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.\)</big>
 == Obvyklé značení ==