Коды Хэмминга

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

История

Коды Хэмминга были разработаны американским математиком и инженером Ричардом Хэммингом в 1947 году. Хэмминг работал в Bell Labs над вычислительной машиной Bell Model V, которая использовала перфокарты для ввода данных. Из-за высокой частоты ошибок при считывании перфокарт машина часто останавливалась, чтобы оператор мог вручную исправить ошибку. Хэмминг поставил задачу разработать метод, позволяющий не только обнаруживать, но и автоматически исправлять ошибки. Результатом его работы стали коды, названные впоследствии его именем. В 1950 году Хэмминг опубликовал статью «Error Detecting and Error Correcting Codes», в которой формально описал принципы построения таких кодов. Это положило начало теории помехоустойчивого кодирования.

Принцип работы

Код Хэмминга строится на основе добавления к блоку из \(k\) информационных битов \(r\) проверочных битов, образуя кодовое слово длиной \(n = k + r\). Проверочные биты располагаются на позициях, являющихся степенями двойки (1, 2, 4, 8, ...). Каждый проверочный бит контролирует определённое подмножество битов кодового слова, включая самого себя. Выбор подмножеств определяется двоичной записью номера позиции бита: проверочный бит с номером \(2^i\) контролирует все биты, в двоичном представлении номера которых присутствует \(2^i\).

Алгоритм кодирования

1. Определить количество проверочных битов \(r\) из условия \(2^r \ge k + r + 1\).
2. Разместить информационные биты на позициях кодового слова, не являющихся степенями двойки.
3. На позиции, являющиеся степенями двойки, поместить проверочные биты.
4. Значение каждого проверочного бита \(p_i\) вычислить как сумму по модулю два (XOR) всех битов кодового слова, номера которых в двоичной записи содержат \(2^i\).

Алгоритм декодирования и исправления ошибок

1. На приёмной стороне вычисляются синдромы — суммы по модулю два для тех же групп битов, что и при кодировании, включая проверочные биты.
2. Если все синдромы равны нулю, ошибок нет.
3. Если синдромы не равны нулю, их двоичное представление даёт номер бита, в котором произошла ошибка. Например, если синдромы дают число 5 (двоичное 0101), то ошибка в пятом бите кодового слова.
4. Ошибочный бит инвертируется.

Классификация

Коды Хэмминга классифицируются по нескольким признакам.

По длине кодового слова

• Стандартные коды Хэмминга: длина кодового слова \(n = 2^r - 1\), где \(r\) — количество проверочных битов. Примеры: (7,4) — 7 бит кодового слова, 4 информационных; (15,11); (31,26).
• Укороченные коды Хэмминга: получаются из стандартного кода путём уменьшения количества информационных битов при сохранении длины кодового слова. Например, код (12,8) получается из кода (15,11) удалением трёх информационных битов.
• Расширенные коды Хэмминга: добавляют один дополнительный проверочный бит (чётность всего кодового слова), что позволяет обнаруживать две ошибки и исправлять одну. Длина кодового слова \(n = 2^r\), количество информационных битов \(k = 2^r - r - 1\). Пример: (8,4).

По типу используемых символов

• Двоичные коды Хэмминга: работают с битами (0 и 1). Наиболее распространённый тип.
• Не-двоичные коды Хэмминга: используют символы из поля Галуа \(GF(q)\), где \(q\) — степень простого числа. Например, коды Хэмминга над \(GF(3)\) или \(GF(4)\). Обладают большей корректирующей способностью за счёт большего алфавита.

Пример кода (7,4)

Код (7,4) является классическим примером кода Хэмминга. Он использует 7 бит кодового слова, из которых 4 — информационные, 3 — проверочные. Проверочные биты располагаются на позициях 1, 2 и 4.

Кодирование

Пусть информационные биты: \(d_1, d_2, d_3, d_4\) (на позициях 3, 5, 6, 7). Проверочные биты:

• \(p_1\) (позиция 1) = \(d_1 \oplus d_2 \oplus d_4\) (контролирует позиции 1, 3, 5, 7)
• \(p_2\) (позиция 2) = \(d_1 \oplus d_3 \oplus d_4\) (контролирует позиции 2, 3, 6, 7)
• \(p_4\) (позиция 4) = \(d_2 \oplus d_3 \oplus d_4\) (контролирует позиции 4, 5, 6, 7)

Декодирование

Вычисляются синдромы:

• \(s_1 = p_1 \oplus d_1 \oplus d_2 \oplus d_4\)
• \(s_2 = p_2 \oplus d_1 \oplus d_3 \oplus d_4\)
• \(s_4 = p_4 \oplus d_2 \oplus d_3 \oplus d_4\)

Если \(s_1 = 0, s_2 = 0, s_4 = 0\), ошибок нет. Если, например, \(s_1 = 1, s_2 = 0, s_4 = 1\), то синдром равен 101 (двоичное), что соответствует 5-й позиции, где произошла ошибка.

Применение

Коды Хэмминга находят широкое применение в системах, где требуется надёжная передача или хранение данных с возможностью коррекции одиночных ошибок.

• Память компьютеров: коды Хэмминга используются в модулях оперативной памяти (RAM) с коррекцией ошибок (ECC — Error-Correcting Code). Например, серверные модули DDR4 ECC используют коды Хэмминга для исправления однобитовых ошибок и обнаружения двухбитовых.
• Цифровая связь: применяются в системах спутниковой связи, радиосвязи, модемах для защиты от помех.
• Хранение данных: используются в некоторых типах RAID-массивов, флэш-памяти и жёстких дисках для обнаружения и исправления ошибок.
• Космическая техника: в телеметрии и системах управления космических аппаратов для защиты от радиационных воздействий.
• Криптография: в некоторых схемах стеганографии и квантового распределения ключей.

Достоинства и недостатки

Достоинства

• Простота реализации: алгоритмы кодирования и декодирования легко реализуются как аппаратно (с помощью логических схем), так и программно.
• Высокая скорость: из-за малой вычислительной сложности коды Хэмминга могут обрабатывать данные с высокой скоростью.
• Эффективность: для кодов с длиной кодового слова до 31 бита избыточность не превышает 30%, что приемлемо для многих приложений.
• Совершенство: коды Хэмминга достигают границы Хэмминга, то есть не существует более эффективных кодов с теми же параметрами.

Недостатки

• Ограниченная корректирующая способность: исправляют только одну ошибку на кодовое слово. При двух и более ошибках код может либо неверно исправить, либо не обнаружить их.
• Чувствительность к пакетам ошибок: если ошибки происходят в соседних битах (пакет ошибок), код может не справиться.
• Избыточность: для коротких блоков данных (например, 4 бита) избыточность составляет 75%, что может быть неэффективно.

Интересные факты

• Ричард Хэмминг изначально разработал код для исправления ошибок в перфокартах, но его работа оказала огромное влияние на всю теорию информации.
• Код Хэмминга (7,4) является одним из самых простых и часто используется в учебных целях для демонстрации принципов помехоустойчивого кодирования.
• Существует обобщение кодов Хэмминга — коды Голея, которые могут исправлять до трёх ошибок.
• В 1970-х годах коды Хэмминга были использованы в системе передачи данных «Викинг» (NASA) для связи с Марсом.

Источники

• Хэмминг, Р. В. «Error Detecting and Error Correcting Codes». Bell System Technical Journal, 1950.
• Питерсон, У. У., Уэлдон, Э. Дж. «Коды, исправляющие ошибки». — М.: Мир, 1976.
• Мак-Вильямс, Ф. Дж., Слоэн, Н. Дж. А. «Теория кодов, исправляющих ошибки». — М.: Связь, 1979.
• Блейхут, Р. Э. «Теория и практика кодов, контролирующих ошибки». — М.: Мир, 1986.