9. Код Хемминга

Пусть количество сообщений, которые требуется передавать абоненту, равно 16. Для их безызбыточного кодирования можно использовать двоичные слова длины 4, но тогда код не будет корректировать ошибки. При использовании слов длины 5, как мы уже знаем, можно обнаружить, но не исправить любую одиночную ошибку. Впрочем, из дополнения 3 предыдущего параграфа вытекает, что если добавить 5 проверочных символов, то код сможет не только исправлять одиночные, но и обнаруживать двойные ошибки. Возникает вопрос: нельзя ли для этой цели обойтись меньшим количеством проверочных символов?

Вычислим сначала, каково минимальное число проверочных символов, необходимое для исправления любых одиночных ошибок. Нетрудно убедиться, что двух добавочных символов для этого недостаточно (предлагаем читателю проверить это самостоятельно).

Попробуем обойтись тремя проверочными символами, т. е. будем использовать для кодирования сообщений двоичные слова α₁α₂α₃α₄α₅α₆α₇ длины 7. Наша задача - определить, произошла ли ошибка, и если произошла, то в каком месте. Но это то же самое, что указать одно из восьми чисел от 0 до 7 (0 соответствует отсутствию ошибки).

Пусть требуется передать сообщение, кодируемое словом α₁α₂α₃α₄. Добавим к этому слову три символа α₅, α₆, α₇, определяемые равенствами (здесь и до конца параграфа все равенства берутся по модулю 2):

Если теперь нужно выяснить, допущена ли при передаче слова α₁α₂α₃α₄α₅α₆α₇ одиночная ошибка в одном из символов α₄, α₅, α₆, α₇, то для этого достаточно вычислить сумму:

Ее значение, равное 1, соответствует ответу "да", значение 0 - ответу "нет" (почему?).

В случае "да" проверим, нет ли ошибки в символах α₆, α₇, в случае "нет" - не содержится ли ошибка в символах α₂, α₃. В каждом из этих случаев ответ дает значение суммы:

Если, например, значения обеих сумм (2) и (3) равны 1, то ошибка содержится либо в α₆, либо в α₇. Всего имеется четыре комбинации значений сумм s₁, s₂; они приведены в следующей таблице:

Таблица 18

Наконец в каждом из четырех случаев нужно выбрать одну из двух возможностей. Это позволит сделать значение суммы

Итак, мы имеем три проверочных соотношения:

которые позволяют либо установить, что ошибки нет, либо однозначно указать ее место.

Отметим особо, что если произошла одиночная ошибка, то ее положение указывается числом с двоичной записью s₁s₂s₃. Пусть, например, s₁ = 1, s₂ = 0, s₃ = 1. Согласно таблице 18 ошибка допущена в четвертом или пятом разрядах; поскольку s₃ = 1, она - в пятом разряде, но s₁s₂s₃ = 101 как раз и есть двоичная запись числа 5.

Изученный здесь код - это код Хемминга длины 7 с четырьмя информационными символами.

В общем случае кодовые слова двоичного кода Хемминга, позволяющего исправить одиночную ошибку, имеют длину 2^m - 1 (m - натуральное). Для определения положения ошибки тогда уже нужно m проверок, т. е. m проверочных символов. Оставшиеся 2^m - 1 - m символов являются информационными. Проверки строятся по аналогии с рассмотренным случаем. Значения m проверок, как и выше, образуют номер положения ошибки.

Вернемся, однако, к вопросу, поставленному в начале этого параграфа. Добавим к кодовым словам кода Хемминга длины 7 еще один проверочный символ α₀, а к проверочным соотношениям (5) еще одно (общую проверку на четность):

Новый код по-прежнему будет содержать 16 кодовых слов, потому что, как и раньше, символы α₁, α₂, α₃, α₄ могут быть взяты какими угодно; по ним из соотношений (1) определяются символы α₅, α₆, α₇, а из равенства (6) и символ α₀. В случае одиночной ошибки добавленное соотношение (6) нарушается, а значения α₁, α₂, α₃ образуют номер положения ошибки. Если же произошла двойная ошибка, то соотношение (6) будет выполнено, а хотя бы одно из равенств (5) нарушится (почему?). Это и позволяет обнаружить любую двойную ошибку. Итак, для исправления одиночных и обнаружения двойных ошибок к четырем информационным символам достаточно добавить четыре проверочных символа. Можно показать, что обойтись меньшим числом проверочных символов невозможно.

Построенное множество кодовых слов α₀α₁α₂α₃α₄α₅α₆α₇, удовлетворяющих соотношениям (5) и (6), - пример расширенного кода Хемминга (длины 8 с четырьмя информационными символами).