Kontrolní matice

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ž H^Tc=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

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 komutativním tělesem 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}}.$

Reference

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