Дуальные коды
Проверочная матрица
Линейный систематический блочный код может быть определен также с использованием так называемой проверочной матрицы H, обладающей следующим свойством:
- если некоторая последовательность U является кодовым словом, то
U* HT = 0. (1317)
Другими словами, проверочная матрица H ортогональна любой кодовой последовательности данного кода.
Проверочная матрица имеет размерность (n-k)*n и следующую структуру :
| P00 | P10 | … | Pk-1, 0 | … | ||||||
| P01 | P11 | … | Pk-1, 1 | … | ||||||
| H = | P22 | P12 | … | Pk-1, 2 | … | , (318) | ||||
| … | … | … | … | … | … | … | … | … | ||
| P0, n-k-1 | P1, n-k-1 | … | Pk-1, n-k-1 | … | ||||||
| PT | I1(n-k)´(n-k) |
где PT - транспонированная подматрица P из порождающей матрицы G ;
I1(n-k)´(n-k) - единичная матрица соответствующего размера.
Видно, что единичная и проверочная подматрицы в G и H поменялись местами, кроме того, изменился их размер.
Для рассматриваемого нами в качестве примера (7,4)-кода Хемминга проверочная матрица H имеет вид
| H(7,4)= | . (319) | |||||||
Проверочная матрица позволяет легко определить, является ли принятая последовательность кодовым словом данного кода.
Пусть, к примеру, принята последовательность символов c = (1011001), тогда
| T | ||||||||
| c* HT = (1011001) | = (1 1 0) ¹ 0 . | |||||||
Отсюда можно сделать вывод, что последовательность c = (1011001) не является кодовым словом данного кода.
Рассмотрим другой пример. Допустим, принята последовательность d = (0010111), тогда
| T | ||||||||
| d × HT = (0010111) | = (0 0 0) ¹ 0 , | |||||||
то есть двоичная последовательность d принадлежит коду с проверочной матрицей H.
Рассматривая матрицы G и H, можно сделать следующие интересные выводы. Каждая из них содержит множество линейно независимых векторов, то есть каждая из матриц может рассматриваться как базис некоторого линейного пространства. Кроме того, каждое из этих пространств является подпространством векторного пространства, состоящего из всех наборов двоичных символов длиной n.
Скалярное произведение каждой строки матрицы G на каждую строку матрицы H равно нулю, то есть
H× GT = 0 и G× HT = 0 . (3.20)
Следовательно, можно "поменять ролями" эти две матрицы и использовать Н как порождающую матрицу, а G как проверочную матрицу некоторого другого кода.
Коды, связанные таким образом, называются дуальными друг другу, т.е., задав каким-либо образом линейный блочный код, мы автоматически задаем и второй, дуальный ему код. Правда, если исходный код был получен так, чтобы иметь минимальную избыточность при заданной исправляющей способности, то гарантировать хорошее качество дуального ему кода мы не можем. Такие коды обычно имеют исправляющую способность, одинаковую с исходными, но большую, чем у них, избыточность.
Например, если рассмотренный в качестве примера (7,4)-код Хемминга имеет избыточность 7/4 и при этом позволяет исправлять одну ошибку в кодовом слове из 7 символов (об этом будем подробно говорить в следующих разделах настоящего пособия), то дуальный ему код (7,3) также исправляет одну ошибку на 7 символов, но уже имеет избыточность 7/3, то есть на 3 информационных символа содержит 4 проверочных.