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

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

Формально, матрица проверки на четность H линейного кода C является матрицей-генератором дуального кода , C ^⊥ . Это означает, что кодовое слово c находится в C тогда и только тогда, когда произведение матрицы на вектор H c ^⊤ = 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{align}c_{3}+c_{4}&=0\\c_{1}+c_{2}&=0\end{align}}}$,

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

Из определения матрицы проверки четности непосредственно следует, что минимальное расстояние кода — это минимальное число 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_{nk}\end{bmatrix}}}$,

потому что

${\displaystyle GH^{\top }=PP=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 — матрица , а H — матрица.${\displaystyle k\times n}$${\displaystyle (nk)\times n}$

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

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

• Хилл, Рэймонд (1986). Первый курс по теории кодирования. Oxford Applied Mathematics and Computing Science Series. Oxford University Press . С. 69. ISBN 0-19-853803-0.
• Плесс, Вера (1998), Введение в теорию кодов, исправляющих ошибки (3-е изд.), Wiley Interscience, ISBN 0-471-19047-0
• Роман, Стивен (1992), Теория кодирования и информации , GTM , т. 134, Springer-Verlag, ISBN 0-387-97812-7
• JH van Lint (1992). Введение в теорию кодирования. GTM . Т. 86 (2-е изд.). Springer-Verlag. С. 34. ISBN 3-540-54894-7.