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

Часть теории кодирования

В теории кодирования матрица проверки на четность линейного блочного кода 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{aligned}c_{3}+c_{4}&=0\\c_{1}+c_{2}&=0\end{aligned}}}$,

которое должно быть выполнено для того , чтобы вектор был кодовым словом 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_{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 — матрица , а H — матрица. ${\displaystyle k\times n}$ ${\displaystyle (n-k)\times n}$

Синдромы

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

Смотрите также

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

Примечания

1. например, Роман 1992, стр. 200
2. Роман 1992, стр. 201
3. Плесс 1998, стр. 9
4. Плесс 1998, стр. 20

Ссылки

• Хилл, Рэймонд (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.