Все формулы РФ

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

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

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

Опубликовано: Обновлено:

Кодирование информацииАнализ данныхСтраницы с задачами и решениямиЕсть историческая справка

Формула

$$M\sum_{j=0}^{t}\binom{n}{j}\le 2^n$$
Схема Одна ошибка в слове из 7 бит
Одна ошибка в слове из 7 битОдна ошибка в слове из 7 битЧисло слов MНа одно словоНужно строк168128178136Доступно 2⁷ = 128 двоичных строк

Для 17 слов непересекающихся областей уже не хватает места.

Обозначения

$M$
число разрешённых кодовых слов, безразмерная величина
$n$
длина каждого слова, бит
$t$
гарантированно исправляемое число замен, число позиций
$j$
число замен в одном слое области ошибок, число позиций

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

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

Ограничения

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

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

У слова длины n ровно C(n,j) двоичных строк на расстоянии j: достаточно выбрать позиции замен, поскольку каждый бит имеет единственное противоположное значение. Сумма от j=0 до t считает само слово и все варианты не более чем с t заменами.

Каждая из M кодовых строк требует отдельной такой области. Если области пересекаются, полученное сообщение может соответствовать двум исходным словам, и исправление уже не гарантировано. Поэтому число строк во всех областях складывается без двойного счёта.

Всего двоичных строк длины n существует 2ⁿ. Сравнение занятых областей с общим числом строк даёт неравенство. При t=1 объём области особенно прост: одно исходное слово плюс n одиночных замен, всего n+1 строк.

Если код линейный и передаёт k информационных битов, M=2ᵏ. Для одной исправляемой ошибки из границы следует 2^(n−k)≥n+1. Это нижняя оценка числа проверочных комбинаций, но назначить проверочные биты всё равно нужно корректной конструкцией.

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

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

  1. Запишите длину слова n, число разных сообщений M и требуемое число исправляемых замен t.
  2. Посчитайте сумму сочетаний от нуля до t, обязательно включая исходное слово через C(n,0)=1.
  3. Умножьте объём одной области на M и сравните с общим числом двоичных строк 2 в степени n.
  4. Если граница выполнена, продолжайте проверку конструкции: одно это неравенство существование не доказывает.

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

Геометрический подход к кодированию развивался вместе с теорией исправления ошибок в XX веке. Пространство двоичных строк позволило говорить об упаковке шаров, хотя здесь расстояние считает несовпадающие позиции, а объём — число строк, а не евклидовы кубические единицы. Граница Хэмминга стала базовой оценкой допустимых параметров блочного кода. В современных курсах теории кодирования CMU и MIT её выводят через непересекающиеся области ошибок и сопоставляют с конкретными конструкциями. Особый интерес представляют случаи равенства: они показывают отсутствие свободного места между областями. Классические двоичные коды Хэмминга дают такие примеры для одной исправляемой ошибки, но общая задача построения хороших кодов намного шире этой семьи.

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

Название «граница Хэмминга» закреплено за оценкой упаковки областей ошибок в пространстве слов. Это ограничение параметров любого кода указанного типа; конкретные коды Хэмминга являются конструкциями, которые в некоторых случаях достигают этой границы.

Пример

Проверим код длины семь бит с 16 разрешёнными словами и исправлением одной ошибки. Здесь n=7, M=16, t=1. Область каждого слова содержит C(7,0)+C(7,1)=1+7=8 строк. Все области потребуют 16·8=128 строк, а пространство имеет 2⁷=128 строк. Граница выполняется с равенством; такие параметры реализуются двоичным кодом Хэмминга (7,4). Если потребовать 17 слов при той же длине и гарантии, потребуется 17·8=136 строк, что больше 128: это уже невозможно. Число 4 в обозначении (7,4) соответствует log₂16 информационным битам, а не числу исправляемых ошибок.

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

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

Практика

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

Три бита

Условие. При n=3 и t=1 найдите верхнюю границу M.

Решение. Объём области 1+3=4, всего строк 2³=8. Поэтому M≤8/4=2. Код 000,111 достигает границы.

Ответ. Не более 2 слов

Пять бит и два исправления

Условие. При n=5 и t=2 найдите верхнюю границу M.

Решение. Объём 1+5+C(5,2)=1+5+10=16. Всего 32 строки, поэтому M≤32/16=2. Пятикратное повторение достигает границы.

Ответ. Не более 2 слов

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

  • https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes4.pdf
  • https://ocw.mit.edu/courses/6-895-essential-coding-theory-fall-2004/46e3bde893d781f4104d0c63249d9111_lect11.pdf
  • https://www.cs.cmu.edu/~15853-f19/scribes/lec2.pdf

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

Информатика

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

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

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

Информатика

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

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

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

Математика

Число сочетаний без повторений

$C_n^k=\binom nk=\frac{n!}{k!(n-k)!}$

Формула описывает прием «неупорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.