Калькулятор расстояния Хэмминга

Что такое расстояние Хэмминга

Расстояние Хэмминга между двумя строками одинаковой длины — это количество позиций, в которых они различаются. Например, между 1011101 и 1001001 расстояние равно 2: различаются третий и пятый символы. Для двоичных чисел расстояние равно количеству единиц в их побитовом исключающем ИЛИ (XOR):

d(a, b) = w(a ⊕ b)

где w — вес Хэмминга, то есть число ненулевых символов. Вес строки — это её расстояние до строки из одних нулей.

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

Минимальное расстояние между любыми двумя словами кода называют кодовым расстоянием d. Оно определяет возможности кода:

• код обнаруживает до d − 1 ошибок — столько искажений не могут превратить одно кодовое слово в другое;
• код исправляет до ⌊(d − 1) / 2⌋ ошибок — искажённое слово остаётся ближе к исходному, чем к любому другому.

Простой контроль чётности даёт d = 2 — одна ошибка обнаруживается, но не исправляется. Код Хэмминга имеет d = 3 и исправляет одну ошибку, расширенный код Хэмминга — d = 4.

Пример

Набор 00000, 01011, 10101, 11110 — четыре кодовых слова по 5 бит. Попарные расстояния: 3, 3, 4, 4, 3, 3. Минимальное расстояние 3, значит, код обнаруживает две ошибки и исправляет одну.

Где используется

• Теория кодирования — оценка корректирующей способности кодов.
• Криптография — проверка лавинного эффекта: при изменении одного бита входа хорошая хеш-функция меняет в среднем половину битов результата.
• Поиск похожих объектов — сравнение перцептивных хешей изображений, отпечатков документов, бинарных признаков в машинном обучении.
• Биоинформатика — число замен между последовательностями ДНК одинаковой длины.