Информатика / Кодирование информации

Минимальное расстояние кода: сколько ошибок можно исправить

Минимальное расстояние между разрешёнными кодовыми словами определяет гарантированное число исправляемых замен битов. Чтобы исправить любые t ошибок, нужно расстояние не меньше 2t+1.

Опубликовано: 18 октября 2026 г.Обновлено: 18 октября 2026 г.

Формула

t=\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor

Схема Одиночные ошибки кода повторения

Два непересекающихся набора содержат по четыре строки.

Обозначения

$dₘᵢₙ$: минимальное расстояние Хэмминга между разными кодовыми словами, число позиций
$t$: гарантированное число исправляемых замен, число позиций

Условия применения

Рассматривается блочный код с как минимум двумя словами одинаковой длины и ошибки замены символов. Расстояние берут по всем различным парам разрешённых слов. Декодирование выбирает ближайшее слово; гарантия относится к любому расположению не более t ошибок.

Ограничения

Формула не оценивает вероятность ошибки канала и не описывает вставки или удаления битов. При большем числе замен иногда тоже возможно правильное решение, но общей гарантии уже нет. Обнаружение повреждения и восстановление исходного слова требуют разных расстояний.

Подробное объяснение

Вокруг каждого разрешённого слова можно представить множество всех строк, получаемых не более чем t заменами. Декодер должен однозначно связать каждую такую строку с исходным словом. Если два множества пересекаются, одна принятая строка имеет два возможных происхождения.

Неравенство треугольника показывает, что при расстоянии между исходными словами больше 2t пересечение невозможно. Для целого расстояния условие записывается dₘᵢₙ≥2t+1. Решая его относительно целого t, получаем целую часть половины dₘᵢₙ−1.

При расстоянии два одиночную ошибку можно обнаружить, но не всегда исправить: строка между двумя словами может находиться на расстоянии один от каждого. Расстояние три уже гарантирует однозначное исправление одной замены. Дополнительная единица в условии устраняет ничью.

Гарантированное обнаружение до dₘᵢₙ−1 замен объясняется иначе: меньшее число изменений не может превратить разрешённое слово в другое разрешённое. Это не значит, что декодер одновременно исправляет столько же ошибок. Проверка принадлежности к коду и выбор исходного слова — разные задачи.

Расстояние кода определяется худшей парой. Даже если большинство пар далеко друг от друга, одна близкая пара ограничивает гарантию для всего кода. Поэтому при ручной проверке маленького набора надо перечислить все пары, а не только сравнить слова с нулевой строкой, если линейность не установлена.

Как пользоваться формулой

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

Историческая справка

Понятие расстояния между кодовыми словами стало одним из основных инструментов теории исправления ошибок в середине XX века. Оно связывает инженерную задачу передачи с геометрией конечного множества строк: ошибки соответствуют перемещению по позициям, а избыточность раздвигает разрешённые слова. Современные университетские курсы MIT излагают условие 2t+1 через разделение областей возможных повреждений. Название расстояния Хэмминга связано с развитием помехоустойчивых кодов, но приведённая гарантия является общим следствием метрики и не ограничивается одним конкретным кодом Хэмминга. Код повторения показывает идею без сложных матриц; более эффективные конструкции сохраняют тот же принцип однозначности при меньшем относительном расходе лишних битов.

Историческая линия формулы

Расстояние Хэмминга — стандартный язык теории блочных кодов. Условие исправления через минимальное расстояние относится к любому коду в этой модели; его не следует смешивать с отдельной конструкцией кодов Хэмминга или с алгоритмом вычисления проверочных разрядов.

Пример

Код передаёт один бит тройным повторением: разрешены только 000 и 111. Между словами различаются все три позиции, поэтому dₘᵢₙ=3. Получаем t=⌊(3−1)/2⌋=1: любая одиночная замена исправляется. Например, принято 010. Оно отличается от 000 в одной позиции, а от 111 в двух, поэтому ближайшее слово — 000. Проверка границы: строка 110, полученная двумя заменами из 000, ближе к 111; декодер большинства ошибётся. Таким образом, гарантия «одна ошибка» не означает исправление любой повреждённой строки. Расстояния измеряются количеством различающихся позиций, а не числовой разностью двоичных чисел.

Частая ошибка

Не вычитайте двоичные числа арифметически вместо подсчёта различий по позициям. Не заменяйте минимальное расстояние средним. Не округляйте t вверх. Не приравнивайте dₘᵢₙ−1 обнаруживаемых ошибок к числу исправляемых. Не распространяйте результат на потерю или вставку бита без отдельной модели синхронизации.

Практика

Задачи с решением

Расстояние пять

Условие. Минимальное расстояние блочного кода равно 5. Сколько произвольных замен он гарантированно исправляет?

Решение. t=⌊(5−1)/2⌋=⌊2⌋=2. Условие 2t+1=5 выполняется.

Ответ. 2 замены

Чётное расстояние

Условие. Минимальное расстояние равно 4. Найдите гарантии исправления и обнаружения.

Решение. Исправление: ⌊(4−1)/2⌋=1. Обнаружение без требования исправить: до 4−1=3 замен.

Ответ. 1 исправляемая или до 3 обнаруживаемых замен

Дополнительные источники

https://ocw.mit.edu/courses/6-004-computation-structures-spring-2017/pages/c1/c1s1/
https://web.mit.edu/6.02/www/f2011/handouts/6.pdf

Связанные формулы

Информатика

Расстояние Хэмминга между двоичными словами

$d(x,y)=\sum [x_i\ne y_i]$

Расстояние Хэмминга между двоичными словами: формула d(x,y)=\sum [x_i\ne y_i] помогает величины d, x_i, y_i заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.

Информатика

Граница Хэмминга: сколько слов помещается в исправляющий код

$M\sum_{j=0}^{t}\binom{n}{j}\le 2^n$

Граница Хэмминга ограничивает число слов M двоичного блочного кода длины n, исправляющего любые t замен. Области возможных повреждений вокруг разных слов должны помещаться среди всех двоичных строк без пересечений.

Информатика

Количество наборов битовой строки

$N = 2^n$

Количество наборов битовой строки длины n равно 2^n, потому что каждая позиция независимо принимает одно из двух значений: 0 или 1.