Порождающая и проверочная матрицы линейного кода
Порождающая и проверочная матрицы линейного кода
Поиск эффективных и простых в обработке корректирующих кодов осуществляется с использованием компьютерного моделирования и алгебраических методов. В теории кодирования n - разрядному двоичному слову ставится в соответствие многочлен степени n или вектор в n - мерном пространстве с компонентами, принимающими значения 1 и 0 (например, слову 101101 – многочлен х5+х3+х2+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.
При ошибке в первом разряде слова V1 код синдрома V1 НТ = 110.
Номер строки матрицы Hт с этим кодом синдрома совпадает с номером ошибочного разряда принятой кодовой комбинации (№1).
При ошибке во втором разряде слова V2 результат проверки V2 НТ = 101. Полученный синдром находится во второй строке матрицы Hт, следовательно ошибочен разряд №2 принятой кодовой комбинации.
Реализация матричных операций на интегральных микросхемах не представляет технических трудностей.