Криптография и теория информации

Код Хэмминга

Помехоустойчивое кодирование Открыть в лаборатории →

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

Расстояние Хэмминга

Определение

Расстояние Хэмминга d(x, y) между двоичными словами одинаковой длины — число позиций, в которых они различаются. Минимальное расстояние кода d — наименьшее расстояние между двумя различными кодовыми словами.

Например, d(10110, 11100) = 2. Расстояние — настоящая метрика: оно неотрицательно, симметрично и удовлетворяет неравенству треугольника. Если в канале произошло t ошибок, принятое слово находится на расстоянии t от отправленного.

Теорема

Код с минимальным расстоянием d

  • обнаруживает любые d − 1 ошибок;
  • исправляет любые t = ⌊(d − 1)/2⌋ ошибок, если декодировать в ближайшее кодовое слово.

Доказательство. Меньше чем d ошибок не могут превратить одно кодовое слово в другое — значит, принятое слово не кодовое и ошибка заметна. Для исправления: пусть отправлено c, принято r, d(c, r) ≤ t. Если бы для другого кодового слова c' было d(c', r) ≤ t, то по неравенству треугольника d(c, c') ≤ 2t ≤ d − 1 — противоречие. Значит, ближайшее к r кодовое слово — именно c.

Простейшие примеры: бит чётности (d = 2) обнаруживает одну ошибку, но не исправляет; тройное повторение 0 → 000, 1 → 111 (d = 3) исправляет одну ошибку, но втрое увеличивает объём. Код Хэмминга тоже имеет d = 3, но тратит гораздо меньше лишних битов.

Устройство кода Хэмминга (7,4)

Позиции кодового слова нумеруются с единицы: 1, 2, …, 7. На позициях — степенях двойки (1, 2, 4) стоят биты чётности, на остальных (3, 5, 6, 7) — 4 бита данных. Бит чётности на позиции 2^j проверяет все позиции, в двоичной записи номера которых установлен j-й бит, и делает сумму этих позиций по модулю 2 равной нулю:

Бит чётностиПроверяет позицииДвоичная запись позиций
p_11, 3, 5, 7··1
p_22, 3, 6, 7·1·
p_44, 5, 6, 71··
Пример кодирования

Данные 1011 записываем в позиции 3, 5, 6, 7:

Позиция1234567
Назначениеp_1p_2d_1p_4d_2d_3d_4
Бит0110011

p_1 = d_1 ⊕ d_2 ⊕ d_4 = 1 ⊕ 0 ⊕ 1 = 0, p_2 = d_1 ⊕ d_3 ⊕ d_4 = 1 ⊕ 1 ⊕ 1 = 1, p_4 = d_2 ⊕ d_3 ⊕ d_4 = 0 ⊕ 1 ⊕ 1 = 0. Кодовое слово: 0110011.

Синдром: как найти ошибку

Приёмник заново вычисляет три проверки по принятому слову. Результаты проверок, записанные как двоичное число s = s_4 s_2 s_1, называются синдромом.

Свойство

Если ошибок нет, синдром равен 0. Если ошибка одна, синдром равен номеру ошибочной позиции.

Почему. Ошибка в позиции i нарушает ровно те проверки, которые «видят» позицию i, — то есть проверки, соответствующие единицам в двоичной записи i. Поэтому набор нарушенных проверок и есть двоичная запись i.

Пример исправления

Отправлено 0110011, в канале испортился бит 6, принято 0110001.

s_1 = биты 1, 3, 5, 7: 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0; s_2 = биты 2, 3, 6, 7: 1 ⊕ 1 ⊕ 0 ⊕ 1 = 1; s_4 = биты 4, 5, 6, 7: 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1.

Синдром s = 110₂ = 6: инвертируем бит 6 и получаем 0110011, данные из позиций 3, 5, 6, 7 — 1011.

Матричная запись

Код Хэмминга — линейный: сумма (XOR) двух кодовых слов — снова кодовое слово. Его задаёт проверочная матрица H размера 3 × 7, столбец i которой — двоичная запись числа i:

H = [[0 0 0 1 1 1 1], [0 1 1 0 0 1 1], [1 0 1 0 1 0 1]]

Слово c кодовое тогда и только тогда, когда H·cᵀ = 0. Если принято r = c ⊕ e, где e — вектор ошибки, то синдром H·rᵀ = H·cᵀ ⊕ H·eᵀ = H·eᵀ зависит только от ошибки. При одной ошибке в позиции i это i-й столбец H, то есть двоичная запись i. Все столбцы различны и ненулевые — поэтому d = 3.

Семейство кодов и граница Хэмминга

Для m проверочных битов получаем код длины n = 2^m − 1 с k = n − m битами данных: (3,1) — тройное повторение, (7,4), (15,11), (31,26), … Чем длиннее блок, тем меньше доля избыточности, но тем выше шанс, что в блок попадут две ошибки.

Граница Хэмминга (для t = 1)
2^k·(n + 1) ≤ 2^n

Вокруг каждого из 2^k кодовых слов «шар» радиуса 1 содержит само слово и n слов с одной ошибкой; шары не пересекаются и помещаются среди всех 2^n слов.

Для кода Хэмминга 2^(n−m)·2^m = 2^n — равенство: шары покрывают всё пространство без остатка. Такие коды называют совершенными. Любое принятое слово либо кодовое, либо на расстоянии 1 ровно от одного кодового.

Две ошибки в блоке

При двух ошибках синдром ненулевой, но указывает на третью, ни в чём не виноватую позицию, — декодер «исправляет» её и вносит третью ошибку. Поэтому на практике используют расширенный код Хэмминга (8,4): к слову добавляют общий бит чётности. Он исправляет одну ошибку и обнаруживает две (SECDED — single error correction, double error detection); именно так устроена ECC-память.

В лаборатории

Выберите вариант (7,4) или (15,11), включите «Смоделировать ошибку» и нажмите на блок с ошибкой — откроется разбор проверок, синдрома и исправления. Открыть код Хэмминга →

Вопросы для самопроверки

  1. Закодируйте данные 0110 кодом Хэмминга (7,4).
    Ответd_1 d_2 d_3 d_4 = 0 1 1 0: p_1 = 0 ⊕ 1 ⊕ 0 = 1, p_2 = 0 ⊕ 1 ⊕ 0 = 1, p_4 = 1 ⊕ 1 ⊕ 0 = 0; слово 1100110.
  2. Принято слово 1110110. Есть ли ошибка, и где?
    Ответs_1 = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1, s_2 = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1, s_4 = 0 ⊕ 1 ⊕ 1 ⊕ 0 = 0; синдром 011₂ = 3 — ошибка в позиции 3, правильное слово 1100110.
  3. Сколько проверочных битов нужно коду Хэмминга, чтобы защитить 26 бит данных?
    Ответ5: код (31,26), так как 2^5 − 1 = 31 = 26 + 5.
  4. Почему код Хэмминга называют совершенным?
    ОтветГраница Хэмминга выполняется с равенством: каждое слово длины n находится на расстоянии не больше 1 ровно от одного кодового слова.