Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

1.2.2. Проверочная матрица линейного кода

Поскольку линейный код V является подпространством, то для него существует ортогональное дополнение (или нулевое подпространство). Ортогональное дополнение V' (n,k) - кода V состоит из всех векторов длины n, ортогональных к каждому вектору vÎV. Векторы и называются ортогональными, если их скалярное произведение равно 0. Для двоичных векторов скалярное произведение равно сумме произведений соответствующих компонент. Например, скалярное произведение (00101, 10110) векторов 00101 и 10110 есть вектор 00100 = 0×1 + + 0×0 + 1×1 + 0×1 + 1×0. Ортогональное дополнение также является подпространством и, таким образом, может рассматриваться как линейный код. Множество V' - называется кодом, дуальным или двойственным к V.

Ортогональное дополнение V' (n,k) - кода V имеет размерность (n - k); соответственно любой его базис состоит из (n-k) векторов. Порождающая матрица Н ортогонального дополнения называется проверочной матрицей кода V.

Т. к проверочная матрица состоит из базисных векторов ортогонального дополнения, то двоичный вектор с является кодовым словом, если и только если сНT = 0. Таким образом, проверка на наличие ошибок при передаче кодового слова сводится к умножению двух матриц вместо перебора всех кодовых слов. Умножение матриц, размерность которых составляет несколько тысяч, при современной вычислительной технике выполняется очень быстро.

Проверочную матрицу можно построить путем нахождения фундаментальной системы решений для соответствующей системы уравнений. Матрица

из предыдущего раздела порождает следующую систему уравнений:

Основная матрица системы совпадает с матрицей G. Неизвестные x1, x2 и x3, для которых существует минор, не равный 0, можно объявить главными неизвестными. Тогда неизвестные x4 и x5 являются свободными. Мы выбираем для них линейно независимые значения 01 и 10 и получаем системы уравнений:


      и               

Из первой системы получаем x1= 1, x2 = 0, x3 = 1, т. е. решением исходной системы является вектор 10101. Из второй системы получаем x1= 1, x2 = 1, x3 = 0, т. е. вторым решением в фундаментальной системе решений является вектор 11010. Таким образом, получаем проверочную матрицу:

.

Заметим, что подобно порождающей матрице, для одного и того же кода существуют различные проверочные матрицы.


Связь кодового расстояния линейного кода и проверочной матрицы устанавливается следующей теоремой:

Теорема 1.3. Каждое не нулевое кодовое слово имеет вес не менее w, тогда и только тогда, когда любая совокупность из w столбцов матрицы Н является линейно независимой.

Доказательство. Для любого кодового слова с выполняется равенство сНT = 0. Пусть кодовое слово с имеет вес u. Исключим из рассмотрения нулевые компоненты вектора. Полученное равенство будет соотношением линейной зависимости u столбцов из Н. Следовательно, Н содержит множество из u линейно зависимых столбцов. Таким образом, в коде существует слово веса u, если и только если в матрице Н существует совокупность из u линейно зависимых столбцов. Таким образом, все не нулевые слова кода имеют вес не меньше w, если и только если любая совокупность из w-1 столбцов матрицы Н является линейно независимой.

Как следствие теорем 1.1 и 1.3 имеет место следующее утверждение:

Следствие. Расстояние линейного кода не менее w, если и только если любая совокупность из w-1 столбцов матрицы Н является линейно независимой.

Согласно сформулированным выше утверждениями, для того чтобы найти (п,k)-код, исправляющий t ошибок, достаточно построить матрицу Н размерности (п - k) × n, в которой любые 2t столбцов линейно независимы.