В теории кодирования , проверочная матрица из линейного блочного кода C представляет собой матрицу , которая описывает линейные соотношения , что компоненты кодового слова должны удовлетворять. Его можно использовать, чтобы решить, является ли конкретный вектор кодовым словом, а также он используется в алгоритмах декодирования.
Определение [ править ]
Формально матрица контроля по четности, H линейного кода C представляет собой порождающую матрицу из двойного кода , C ⊥ . Это означает, что кодовое слово c находится в C тогда и только тогда, когда произведение матрицы на вектор H c ⊤ = 0 (некоторые авторы [1] записали бы это в эквивалентной форме, c H ⊤ = 0. )
Строки матрицы проверки на четность являются коэффициентами уравнений проверки на четность. [2] То есть они показывают, как линейные комбинации определенных цифр (компонентов) каждого кодового слова равны нулю. Например, матрица проверки на четность
- ,
компактно представляет уравнения проверки на четность,
- ,
которые должны быть выполнены для вектора быть кодовым словом C .
Из определения матрицы проверки на четность непосредственно следует, что минимальное расстояние кода - это минимальное число d такое, что каждые d - 1 столбец матрицы проверки на четность H являются линейно независимыми, в то время как существует d столбцов H , которые линейно зависимый.
Создание матрицы проверки четности [ править ]
Матрица проверки на четность для данного кода может быть получена из его порождающей матрицы (и наоборот). [3] Если порождающая матрица для [ n , k ] -кода имеет стандартную форму
- ,
тогда матрица проверки на четность имеет вид
- ,
так как
- .
Отрицание проводится в конечном поле F q . Обратите внимание, что если характеристика нижележащего поля равна 2 (т. Е. 1 + 1 = 0 в этом поле), как в двоичных кодах , то - P = P , поэтому отрицание не требуется.
Например, если в двоичном коде есть образующая матрица
- ,
то его матрица проверки на четность
- .
Можно проверить, что G - матрица, а H - матрица.
Синдромы [ править ]
Для любой (строки) вектор х окружающего векторного пространства, ев = Н х ⊤ называется синдромом от й . Вектор x является кодовым словом тогда и только тогда, когда s = 0 . Расчет синдромов является основой алгоритма декодирования синдромов . [4]
См. Также [ править ]
Заметки [ править ]
- ^ например, Роман 1992 , стр. 200
- ↑ Роман 1992 , стр. 201
- ^ Плесс 1998 , стр. 9
- ^ Плесс 1998 , стр. 20
Ссылки [ править ]
- Хилл, Раймонд (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.