Generující matice

Generující matice je v teorii kódování bází lineárního kódu, generující všechna možná kódová slova. Označíme-li matici G a lineární kód C, pak

w = cG

kde w je určité kódové slovo z C, c je řádkový vektor a mezi w a c existuje bijekce. Generující matice kódu ($n$, $M = q^k$, $d$)_$q$ má velikost k × n. V uvedeném zápise je $n$ délka kódového slova, $k$ je počet informačních znaků, $d$ je Hammingova vzdálenost kódu a $q$ je počet možných symbolů abecedy (tedy např. q = 2 pro binární kód). O takovém kódu lze rovněž říci, že má počet redundantních znaků $r = n - k$.

Standardní tvar generující matice je

$G = \begin{bmatrix} I_k | P \end{bmatrix}$

kde $I_k$ je jednotková matice k × k a P je libovolná matice k × r.

Pomocí generující matice lze pro daný kód sestrojit kontrolní matici (a naopak).

Ekvivalentní kódy

Kódy C₁ a C₂ jsou ekvivalentní (značeno C₁ ~ C₂), pakliže může jeden kód vzniknout z toho druhého pomocí následujících transformací:

1. permutací složek
2. násobením složek konstantou

Ekvivalentní kódy mají stejnou Hammingovu vzdálenost.

Generující matice ekvivalentního kódu může být získána z dané generující matice pomocí následujících transformací:

1. permutací řádků
2. násobením řádků konstantou
3. sčítáním řádků
4. permutací sloupců
5. násobením sloupců konstantou

Odkazy

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