Kontrolní matice

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Kontrolní matice lineárního kódu C je v teorii kódování generující maticí jeho duálního kódu. Označíme-li kontrolní matici jako H, pak platí, že kódové slovo reprezentované vektorem c náleží ke kódu C právě tehdy, když HTc=0.

Řádky kontrolní matice realizují v daném kódovém slově kontrolu parity. Každý řádek představuje jistou lineární kombinaci cifer kódového slova a ta se musí rovnat nule. Například kontrolní matice

H = 

\begin{bmatrix}
  0011\\
  1100
\end{bmatrix}

udává, že nule se musí rovnat součet první a druhé cifry, stejně jako součet třetí a čtvrté cifry.

Sestrojení kontrolní matice[editovat | editovat zdroj]

Kontrolní matici daného kódu lze odvodit z jeho generující matice (a naopak). Je-li generující matice kódu [n, k] ve standardním tvaru

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

příslušná kontrolní matice se vypočte následovně:

H = \begin{bmatrix} -P^T | I_{n-k} \end{bmatrix}.

Vzhledem k tomu, že je lineární kód definován nad konečným polem o velikosti q, musí být výše uvedený minusový operátor aplikován společně s operací modulo q. Z toho vyplývá, že například u binárních kódů (q = 2) není aritmetická negace vůbec zapotřebí, jelikož -1 = 1 (mod 2).

Má-li například jistý binární kód generující matici

G = 
\begin{bmatrix}
10|101 \\
01|110 \\
\end{bmatrix},

pak jeho kontrolní matice odpovídá

H = 
\begin{bmatrix}
11|100 \\
01|010 \\
10|001 \\
\end{bmatrix}.

Odkazy[editovat | editovat zdroj]

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