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

В теории кодирования , проверочная матрица из линейного блочного кода 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 (n-k)\times n}$

Синдромы [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

• Хилл, Раймонд (1986). Первый курс теории кодирования . Oxford Applied Mathematics and Computing Science Series. Издательство Оксфордского университета . С.  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
• Дж. Х. ван Линт (1992). Введение в теорию кодирования . GTM . 86 (2-е изд.). Springer-Verlag. С.  34 . ISBN 3-540-54894-7.