Код Хэмминга

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

История

Разработка кодов Хэмминга была вызвана практическими проблемами, возникавшими при работе ранних электромеханических вычислительных машин. В 1940-х годах в Bell Labs Ричард Хэмминг столкнулся с тем, что ошибки при считывании данных с перфокарт приводили к аварийным остановкам вычислений. Существовавшие методы контроля чётности позволяли только обнаружить факт ошибки, но не указывали её местоположение. Хэмминг поставил задачу создать код, который не только выявлял бы ошибку, но и позволял бы её автоматически исправить.

В 1950 году Хэмминг опубликовал статью «Error detecting and error correcting codes», в которой описал метод построения кодов с минимальным расстоянием 3 (коды Хэмминга), способных исправлять любую одиночную ошибку. Позднее были разработаны расширенные версии (с дополнительным битом общей чётности), позволяющие также обнаруживать двойные ошибки. Коды Хэмминга стали первыми практически применимыми помехоустойчивыми кодами и заложили основы теории кодирования.

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

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

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

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

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

1. Получатель вычисляет синдром ошибки — набор из \(r\) битов, каждый из которых равен сумме по модулю 2 всех битов кодового слова, входящих в соответствующую группу (включая проверочный бит).
2. Если синдром равен нулю, ошибок нет.
3. Если синдром не равен нулю, его двоичное значение указывает номер позиции бита, в котором произошла ошибка.
4. Бит на указанной позиции инвертируется.

Пример

Для кодирования 4 информационных битов (\(k=4\)) требуется 3 проверочных бита (\(r=3\)), так как \(2^3 = 8 \ge 4 + 3 + 1 = 8\). Длина кодового слова \(n = 7\). Проверочные биты располагаются на позициях 1, 2, 4. Информационные — на позициях 3, 5, 6, 7.

Пусть информационные биты: \(d_1=1, d_2=0, d_3=1, d_4=0\). Кодовое слово: \(p_1, p_2, d_1, p_3, d_2, d_3, d_4\).

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

Итоговое кодовое слово: 1 0 1 1 0 1 0.

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

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

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

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

По наличию дополнительной проверки

• Обычный код Хэмминга: исправляет одиночные ошибки, но не обнаруживает двойные (при двукратной ошибке синдром может указать на неверную позицию).
• Расширенный код Хэмминга: добавляется один дополнительный бит общей чётности для всего кодового слова. Это позволяет обнаруживать двойные ошибки, но не исправлять их. Пример: расширенный код (8,4) на основе (7,4).

Характеристики

• Минимальное кодовое расстояние: для обычного кода Хэмминга равно 3, для расширенного — 4.
• Корректирующая способность: исправляет одну ошибку в кодовом слове.
• Обнаруживающая способность: расширенный код обнаруживает до двух ошибок.
• Кодовая скорость: \(R = k/n\). Для совершенных кодов \(R = 1 - \frac{r}{2^r - 1}\). С ростом \(r\) скорость стремится к 1, но уменьшается относительная избыточность.
• Линейность: код является линейным, то есть сумма по модулю 2 любых двух кодовых слов также является кодовым словом.

Применение

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

• Память компьютеров: используются в модулях оперативной памяти (DRAM) с коррекцией ошибок (ECC). Например, код (72,64) — расширенный код Хэмминга, применяемый в серверных модулях памяти для исправления одиночных и обнаружения двойных ошибок.
• Телекоммуникации: применяются в системах передачи данных, где канал связи характеризуется низким уровнем помех (например, в некоторых стандартах цифрового телевидения и радиосвязи).
• Хранение данных: используются в некоторых RAID-системах (например, RAID 2) и в системах хранения на магнитных носителях.
• Космическая связь: применялись в ранних космических аппаратах (например, в программе «Вояджер») для защиты телеметрии от помех.
• Криптография: коды Хэмминга используются в стеганографии для встраивания скрытых сообщений в изображения (метод LSB с коррекцией ошибок).

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

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

Критика

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

Источники

• Hamming R. W. Error detecting and error correcting codes // Bell System Technical Journal. — 1950. — Vol. 29, No. 2. — P. 147–160.
• Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976.
• Блейхут Р. Теория и практика кодов, контролирующих ошибки. — М.: Мир, 1986.
• Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. — М.: Связь, 1979.