Матрица проверки на чётность

В теории кодирования матрица проверки на чётность линейного блочного кода ${\displaystyle C}$ — это матрица, описывающая линейные соотношения, которым должны удовлетворять компоненты кодового слова. Она используется для выяснения, является ли конкретный вектор кодовым словом, а также в алгоритмах декодирования.

Формально, матрица проверки на чётность ${\displaystyle H}$ линейного кода ${\displaystyle C}$ является порождающей матрицей дуального кода ${\displaystyle C}$^⊥. Это означает, что кодовое слово c принадлежит C тогда и только тогда, когда произведение матрицы на вектор Hc^⊤ = 0 (некоторые авторы^[1] записывают это в эквивалентной форме: c H ^⊤ = 0).

Строки матрицы проверки чётности представляют собой коэффициенты уравнений проверки чётности.^[2] То есть они показывают, что линейные комбинации определённых цифр (компонентов) каждого кодового слова равны нулю. Например, матрица проверки чётности

${\displaystyle H=\left[{\begin{array}{cccc}0&0&1&1\\1&1&0&0\end{array}}\right]}$,

компактно представляет уравнения проверки четности,

${\displaystyle {\begin{aligned}c_{3}+c_{4}&=0\\c_{1}+c_{2}&=0\end{aligned}}}$,

которые должны выполняться для вектора ${\displaystyle (c_{1},c_{2},c_{3},c_{4})}$, если он есть кодовое слово в C.

Из определения матрицы проверки чётности непосредственно следует, что минимальное расстояние кода — это минимальное число d такое, что каждые d - 1 столбцов матрицы проверки чётности H являются линейно независимыми, при этом существуют d столбцов H, которые линейно зависимы.

Матрица проверки на чётность для заданного кода может быть получена из его порождающей матрицы (и наоборот).^[3] Если порождающая матрица для [n, k]-кода имеет стандартную форму

${\displaystyle G={\begin{bmatrix}I_{k}|P\end{bmatrix}}}$,

тогда матрица проверки на чётность задаётся как

${\displaystyle H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}}$,

так как

${\displaystyle GH^{\top }=P-P=0}$.

Отрицание выполняется в конечном поле F_q. Обратите внимание, что если характеристика базового поля равна 2 (т.е. 1 + 1 = 0 в этом поле), как в двоичных кодах, то - P = P, поэтому отрицание не требуется.

Например, если двоичный код имеет порождающую матрицу

${\displaystyle G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]}$,

то его матрица проверки чётности равна

${\displaystyle H=\left[{\begin{array}{cc|ccc}-1&-1&1&0&0\\0&-1&0&1&0\\-1&0&0&0&1\\\end{array}}\right]}$.

Можно проверить, что G — матрица ${\displaystyle k\times n}$ , в то время как H — матрица ${\displaystyle (n-k)\times n}$.

Для любого вектора x окружающего векторного пространства s = H x называется синдромом x. Вектор x является кодовым словом тогда и только тогда, когда s = 0. Вычисление синдромов лежит в основе алгоритма декодирования синдромов. ^[4]

• Код Хэмминга

• Hill, Raymond. A first course in coding theory. — Oxford University Press, 1986. — P. 69. — ISBN 0-19-853803-0.
• Pless, Vera (1998), Introduction to the Theory of Error-Correcting Codes (3rd ed.), Wiley Interscience, ISBN 0-471-19047-0
• Roman, Steven (1992), Coding and Information Theory, GTM, vol. 134, Springer-Verlag, ISBN 0-387-97812-7
• J.H. van Lint. Introduction to Coding Theory. — 2nd. — Springer-Verlag, 1992. — Vol. 86. — P. 34. — ISBN 3-540-54894-7.