Важнейшие линейные коды

Код Хэмминга – является одним из важнейших линейных кодов. Коды Хэмминга имеют параметры (2^m - 1; 2^m - 1 - m) и обычно задаются проверочной матрицей. Столбцами проверочной матрицы являются все ненулевые двоичные числа длины m. Например, для кода (7, 4) проверочная матрица имеет следующий вид:

0 0 0 1 1 1 1

H = 0 1 1 0 0 1 1

1 0 1 0 1 0 1

Столбцы с номерами 1, 2, 4, образующие единичную подматрицу, являются проверочными.

Определим корректирующую способность кодов Хэмминга. Предварительно напомним, что весом W(a) слова а называется число ненулевых элементов, и в линейном коде расстояние d(a, b) между двумя словами а и b равно весу некоторого третьего слова а + b, то есть d(a, b) = W(a + b).

Для определения минимального расстояния воспользуемся равенством a^. H^T = 0.

Предположим, что d(a, b) = 1 . Тогда в коде существует слово веса 1, что невозможно, так как для слов веса один, a^. H^T ≠ 0. Теперь предположим, что d(a, b) = 2. Тогда в коде существует слово веса 2, что также невозможно, поскольку никакие два столбца проверочной матрицы не дадут в сумме нулевой вектор. Следовательно, d(a, b) >= 3.

Простым подбором нетрудно найти слово веса три, для которого a^. H^T = 0 Окончательно получим d_min = 3, то есть коды Хэмминга исправляют любую одиночную ошибку. Поскольку все 2^m - 1 векторов, задающих одиночные ошибки, принадлежат различным смежным классам, то этими смежными классами и кодовым пространством исчерпываются все 2^m смежных классов. Их образующими является ненулевой вектор и векторы единичного веса. Следовательно, коды Хэмминга являются совершенными.

Код Хэмминга можно удлинить на один символ, добавив общую проверку на четность. Добавление проверочного символа увеличивает вес слов на единицу, то есть d = 4. Проверочная матрица Н" удлиненного кода имеет вид:

H = 0 H

: :

1 1 1 0 . . . 1

Декодирование производится так:

1.Если синдром равен нулю, то считается, что ошибок нет.

2.Если синдром отличен от нуля и на последнем месте стоит 1, то предполагается, что произошла одиночная ошибка, на местоположение которой указывает синдром матрицы Н.

3.Если синдром отличен от нуля и на последнем месте стоит 0, то обнаружена неисправимая ошибка.

На практике чаще используются модифицированные (укороченные) коды Хэмминга. Операция укорочения является обратной к только что описанной операции удлинения и заключается в выборе всех кодовых слов, первая координата которых равна нулю, X₁ = 0, и в удалении этой координаты в выбранных словах. Размерность данных кодов (2^m - 2; 2^m - m - 2).Укорочение кодов используется для упрощения схем кодеков.