Информатика · объяснение и практика
Как расстояние между кодовыми словами связано с исправлением ошибок
Считаем различающиеся позиции, отделяем обнаружение ошибки от исправления и выводим ограничения по минимальному расстоянию кодовых слов.

В теме Кодирование чисел, текста, изображения и звука · Учебная карта
Главная мысль
Расстояние Хэмминга между строками одинаковой длины — число различающихся позиций. Для двоичного кода минимальное расстояние между допустимыми словами определяет гарантии при заменах битов: до d−1 ошибок можно обнаруживать, а до floor((d−1)/2) — однозначно исправлять ближайшим словом.
Сравнивайте позиции, а не величины чисел
У слов 10110 и 10001 различаются третья, четвёртая и пятая позиции, поэтому расстояние равно 3. Разность числовых значений здесь не нужна. При изменении одного бита расстояние до исходной строки увеличивается на один, независимо от того, какой вес этот бит имел бы в двоичном числе.
Определение предполагает одинаковую длину и замену символов на заданных позициях. Вставка или удаление сдвигают следующие позиции и требуют другой модели расстояния. При работе с текстом дополнительно выбирают единицу сравнения: байты, кодовые точки или графемы могут дать разные длины и разные результаты.
Пример
Для 00000 и 11111 расстояние равно 5. Пусть это единственные допустимые слова кода.
Тогда любая замена от одного до четырёх битов не превращает одно допустимое слово в другое: полученная строка будет недопустимой, и ошибка обнаружится.
Обнаружить не значит восстановить
Код из 00000 и 11111 после одной или двух замен позволяет выбрать ближайшее исходное слово однозначно. Например, 00101 находится на расстоянии 2 от 00000 и 3 от 11111. При обещании не более двух ошибок выбираем 00000. Но если реально произошли три ошибки, то же наблюдаемое слово могло прийти от 11111.
Поэтому гарантия исправления всегда опирается на модель канала и верхнюю границу числа замен. Утверждать «мы точно восстановили исходник» вне этого условия нельзя. Для полного перебора небольшого кода вычисляют расстояния всех пар разных допустимых слов и берут минимум, а не расстояние одной случайно выбранной пары.
Почему для исправления нужно расстояние больше удвоенной ошибки
Если принятое слово находится не дальше t замен от двух разных кодовых слов, эти два исходника отличаются не больше чем в 2t позициях: каждое можно связать с другим через принятое слово. Значит, при минимальном расстоянии d>2t такая неоднозначность невозможна. Именно это объясняет предел гарантированного исправления.
Для обнаружения достаточно, чтобы меньше d замен не могли превратить одно допустимое слово в другое. При ровно d замен такое превращение уже возможно, и проверка допустимости его не заметит. Кодирование с избыточностью не обещает распознавать любое повреждение. В задаче заранее уточняют, требуется только сигнал ошибки или ещё и восстановление, потому что эти требования дают разные ограничения.
От чтения к действию
А теперь — вы
Частые вопросы
Почему нельзя обещать исправить d−1 ошибок?
Это предел гарантированного обнаружения, а не исправления. Повреждённое слово уже может оказаться ближе к другому исходнику, хотя само ещё не является допустимым.
Что если ближайших слов два?
Без дополнительной информации однозначного исправления нет. Правильный декодер должен сообщить неоднозначность или отказ согласно принятому правилу, а не придумывать уверенный ответ.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Чем проверка случайной ошибки отличается от криптографической защиты
Отличаем обнаружение случайного повреждения от проверки подлинности, сохраняем доверенный эталон и проверяем, почему подмена файла вместе с его суммой может остаться незамеченной.
Открыть темуПочему префиксный код читается без разделителей
Расшифровываем поток по дереву кодов, проверяем отсутствие одного слова в начале другого и различаем мгновенное и просто однозначное декодирование.
Открыть тему