2.1.3. Коды Хемминга

Теперь у читателя может возникнуть вопрос: насколько длинным при заданном числе проверочных символов может быть код, имеющий гарантированное кодовое расстояние 3? Поскольку для получения кодового расстояния 3 все множества из двух столбцов должны быть линейно независимыми, достаточно, чтобы все столбцы были различными и ненулевыми. Таким образом, для трех проверочных символов имеется семь различных ненулевых троек, для четырех — пятнадцать различных ненулевых четверок и т. д. Это дает семейство кодов с параметрами вида где Такие коды называются кодами Хемминга; впервые они были описаны Хеммингом в 1950 г. [9].

Коды Хемминга обладают несколькими замечательными свойствами. Прежде всего они являются примерами немногих известных совершенных кодов. Заметим, что для совершенного кода в формуле (1.4) должно выполняться равенство, которое в случае кодов Хемминга имеет вид

Поскольку для этих кодов последнее равенство, очевидно, справедливо. Другое свойство кодов Хемминга состоит в том, что они принадлежат к одному из немногих классов кодов, для которых полностью известен спектр. Определим весовую функцию кода равенством

где число кодовых слов веса Тогда для кода Хемминга с имеем 1

Коды Хемминга с кодовым расстоянием 3 можно превратить в коды Хемминга с расстоянием 4, добавив дополнительный проверочный символ, равный сумме всех остальных символов. Этот дополнительный проверочный символ переводит все кодовые слова веса 3 в слова веса 4, слова веса 5 в слова веса 6 и т. д. Если, например, применить эту процедуру к (7,4) - коду Хемминга, то получится следующая дополненная проверочная матрица:

Левая верхняя часть этой матрицы (ограниченная штриховыми линиями) совпадает с первоначальной проверочной матрицей и состоит из различных троек. Эти новые коды с кодовым расстоянием 4, полученные добавлением одного проверочного символа к кодам Хемминга, иногда называют расширенными кодами Хемминга. Их параметры имеют вид

Читатель мог заметить, что дополненная матрица Н в последнем примере уже не имеет канонической формы, т. е. правая часть этой матрицы уже не является единичной матрицей, что не позволяет определить каждый проверочный символ только по информационным символам. Этот недостаток можно исправить, прибавив каждую из первых трех строк матрицы к последней. В результате получим матрицу вида

Можно показать, что последняя строка полученной матрицы по-прежнему задает проверку на четность. Для этого вычислим ее действие на кодовый вектор. Если четыре строки матрицы Н, то произведение последней строки на кодовый вектор с имеет вид

поскольку для всех

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

матрицы Н. Любая линейная комбинация строк может служить проверочным уравнением, и любое множество из полученных таким способом линейно независимых уравнений может быть использовано для образования матрицы Н. Позже будем использовать это свойство для построения простых алгоритмов декодирования групповых кодов.