Порождающая и проверочная матрицы линейного кода

Порождающая и проверочная матрицы линейного кода

Поиск эффективных и простых в обработке корректирующих кодов осуществляется с использованием компьютерного моделирования и алгебраических методов. В теории кодирования n - разрядному двоичному слову ставится в соответствие многочлен степени n или вектор в  n - мерном пространстве с компонентами, принимающими значения 1 и 0 (например, слову 101101 – многочлен х⁵+х³+х²+1).  Преобразования кодовых слов рассматриваются как операции над многочленами или векторами.

 Любое кодовое слово V  линейного блокового кода (n, k) можно получить умножением вектора  U, представляющего информационное слово, на порождающую матрицу G размерности  k x n:  V =U G.

 Принятое слово можно проверить на отсутствие ошибок умножением его на транспонированную проверочную матрицу H^т . Если слово принято без ошибок, результат умножения нулевой:  V H^т=0. 

 Проверочная матрица (parity-check matrix) связана с порождающей матрицей соотношением G H^т=0.

Порождающая матрица выбирается неоднозначно. Для упрощения кодирования и декодирования удобно использовать порождающую матрицу, составленную из двух матриц: единичной матрицы размерности k x k  и дописываемой справа матрицы-дополнения, или контрольной подматрицы, размерности  k x (n-k). Такая матрица порождает систематический код: первые  k  символов слова совпадают с исходным информационным словом, а остальные символы являются проверочными.

Пример

Информация в лекции "32 Конфликты социально-психологического уровня" поможет Вам.

Помехоустойчивая кодовая комбинация V  = 1010101 получена умножением информационного слова U = 1010  на порождающую матрицу G.

Если в принятом слове (V) нет ошибки, при умножении этого слова на проверочную матрицу Н^Т код синдрома нулевой:  V Н^Т =0.

При ошибке в первом разряде слова  V₁  код синдрома V₁ Н^Т = 110.

Номер строки матрицы H^т с этим кодом синдрома совпадает с номером ошибочного разряда принятой кодовой комбинации (№1).

При ошибке во втором разряде слова V₂  результат проверки V₂ Н^Т = 101. Полученный синдром находится во второй строке матрицы H^т, следовательно ошибочен разряд №2 принятой кодовой комбинации.

Реализация матричных операций на интегральных микросхемах не представляет технических трудностей.