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

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

Определение

Формально проверочная матрица линейного кода C является порождающей матрицей двойственного кода C H ^⊥ . Это означает, что кодовое слово c находится в C тогда и только тогда, когда произведение матрицы и вектора H c ^⊤ = 0 (некоторые авторы записал бы это в эквивалентной форме: c H ^⊤ = 0 .)

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

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

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

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

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

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

Создание матрицы проверки четности

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

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

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

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

потому что

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

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

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

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

тогда его проверочная матрица равна

$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 является $k\times n$ матрица, а H является $(n-k)\times n$ матрица.

Синдромы

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

См. также

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

Ссылки

• Хилл, Раймонд (1986). Первый курс теории кодирования . Оксфордская серия по прикладной математике и информатике. Издательство Оксфордского университета . стр. 69 . ISBN  0-19-853803-0 .
• Плесс, Вера (1998), Введение в теорию кодов, исправляющих ошибки (3-е изд.), Wiley Interscience, ISBN  0-471-19047-0
• Роман, Стивен (1992), Теория кодирования и информации , GTM , vol. 134, Шпрингер-Верлаг, ISBN  0-387-97812-7
• Дж. Х. ван Линт (1992). Введение в теорию кодирования . ГТМ . Том. 86 (2-е изд.). Спрингер-Верлаг. стр. 34 . ISBN  3-540-54894-7 .