В теории кодирования матрица проверки на чётность линейного блочного кода — это матрица, описывающая линейные соотношения, которым должны удовлетворять компоненты кодового слова. Она используется для выяснения, является ли конкретный вектор кодовым словом, а также в алгоритмах декодирования.
Определение Формально, матрица проверки на чётность линейного кода является порождающей матрицей дуального кода ⊥. Это означает, что кодовое слово c принадлежит C тогда и только тогда, когда произведение матрицы на вектор (некоторые авторынапрямую из записывают это в эквивалентной форме: c H ⊤ = 0).
Строки матрицы проверки чётности представляют собой коэффициенты уравнений проверки чётности. То есть они показывают, что линейные комбинации определённых цифр (компонентов) каждого кодового слова равны нулю. Например, матрица проверки чётности
,
компактно представляет уравнения проверки четности,
,
которые должны выполняться для вектора , если он есть кодовое слово в C.
Из определения матрицы проверки чётности непосредственно следует, что минимальное расстояние кода — это минимальное число d такое, что каждые d - 1 столбцов матрицы проверки чётности H являются линейно независимыми, при этом существуют d столбцов H, которые линейно зависимы.
Построение матрицы проверки на чётность Матрица проверки на чётность для заданного кода может быть получена из его порождающей матрицы (и наоборот). Если порождающая матрица для [n, k]-кода имеет стандартную форму
,
тогда матрица проверки на чётность задаётся как
,
так как
.
Отрицание выполняется в конечном поле Fq. Обратите внимание, что если характеристика базового поля равна 2 (т.е. 1 + 1 = 0 в этом поле), как в двоичных кодах, то - P = P, поэтому отрицание не требуется.
Например, если двоичный код имеет порождающую матрицу
,
то его матрица проверки чётности равна
.
Можно проверить, что G — матрица , в то время как H — матрица .
Синдромы Для любого вектора x окружающего векторного пространства s = H x называется синдромом x. Вектор x является кодовым словом тогда и только тогда, когда s = 0. Вычисление синдромов лежит в основе алгоритма декодирования синдромов.
Смотрите также
Код Хэмминга
Примечания
Ссылки
Категория:Теория кодирования