Информатика / Кодирование информации
Граница Гилберта: существование разделённого кода
Жадное добавление слов строит код с расстоянием не меньше d. Когда добавить слово больше нельзя, шары радиуса d−1 покрывают всё пространство и дают нижнюю границу достижимого размера.
Формула
Слои радиусов0,1,2 содержат1,7,21слово. Сумма29используется в нижней границе ceil(128/29)=5.
Обозначения
- $A_q(n,d)$
- максимальное число слов длины n с расстоянием не меньше d, шт.
- $q,n$
- размер алфавита и длина слова, шт.
- $d$
- требуемое минимальное расстояние, позиций
- $V_q(n,r)$
- число слов в шаре Хэмминга радиуса r, шт.
- $\lceil x\rceil$
- округление вещественного числа вверх до целого, —
Условия применения
Алфавит конечен, q≥2, слова имеют одинаковую длину n и расстояние Хэмминга. Требуется целое d в диапазоне 1≤d≤n. Код не обязан быть линейным. Объём шара одинаков для всех центров, поскольку изменение фиксированного набора координат не зависит от значений исходного слова.
Ограничения
Полученный код не гарантированно линейный, оптимальный или удобный для декодирования. Число в нижней границе нельзя читать как верхнее ограничение. Радиус d−1 относится к покрытию максимального по включению кода, а не к радиусу однозначного исправления floor((d−1)/2).
Подробное объяснение
Начнём с пустого кода и добавим любое слово. Затем разрешаем добавлять только слово, расстояние от которого до всех уже выбранных не меньше d. Процесс заканчивается, поскольку пространство из qⁿ слов конечно. Итог максимален по включению: к нему нельзя добавить ещё слово, но это не означает максимальный возможный размер среди всех кодов.
Если после остановки осталось слово на расстоянии не меньше d от всех выбранных, его можно было бы добавить. Значит, каждое слово пространства лежит в шаре радиуса d−1 вокруг хотя бы одного выбранного слова. Суммарный размер этих шаров не меньше qⁿ; пересечения шаров допускаются и только ослабляют оценку.
Для центра шара выбирают j изменяемых координат C(n,j) способами. Каждая новая буква имеет q−1 вариантов, так что слой размера j содержит C(n,j)(q−1)ʲ слов. Сумма слоёв до d−1 даёт V. Из M·V≥qⁿ следует M≥qⁿ/V, а целочисленность M позволяет округлить отношение вверх.
Этот аргумент отличается от упаковочной границы Хэмминга. Там малые шары исправления не пересекаются и дают верхнюю оценку. Здесь более крупные шары покрывают пространство и дают нижнюю оценку существования. Одинаковая формула объёма не делает направления неравенств или радиусы взаимозаменяемыми.
Как пользоваться формулой
- Задайте n,q,d и проверьте, что требуется существование произвольного кода, а не линейная конструкция с заданным декодером.
- Вычислите объём шара радиуса d−1 суммой C(n,j)(q−1)^j, включая центральное слово при j=0.
- Разделите q^n на объём и округлите вверх; полученное целое является гарантированным снизу достижимым размером.
- Сравните с верхними границами и при необходимости выполните жадную конструкцию, сохраняя расстояние не меньше d при каждом добавлении.
Историческая справка
Граница Гилберта относится к классическим оценкам существования кодов, получаемым жадным выбором разделённых слов. В учебной литературе её часто обсуждают рядом с границей Гилберта — Варшамова; линейная версия использует дополнительные алгебраические соображения, поэтому важно указывать, какую конечную оценку применяют.
В современном учебнике Essential Coding Theory оценки через упаковку и покрытие рассматриваются как разные способы связать расстояние с числом сообщений. Жадный аргумент ценен тем, что даёт конкретную конечную процедуру без предположения о случайном физическом канале. При переходе к асимптотике биномиальные суммы связывают с энтропией, но для малых блоков точная сумма и целочисленное округление сохраняют информацию, которую предельная формула теряет.
Историческая линия формулы
Здесь используется конечная граница Гилберта для произвольных кодов через покрытие шарами радиуса d−1. Линейная оценка, известная под именем Гилберта — Варшамова, не отождествляется с этой формулировкой. Даты исторического приоритета без отдельного первоисточника не приводятся.
Пример
Для двоичных слов длины 7 требуется расстояние не меньше 3. Найдём гарантированный размер кода по покрывающему аргументу. Эта задача не требует, чтобы множество слов образовывало линейное пространство. Радиус покрытия d−1=2, поэтому V₂(7,2)=C(7,0)+C(7,1)+C(7,2)=1+7+21=29. Всего 2⁷=128 слов. Отношение 128/29≈4,4138, и округление вверх даёт A₂(7,3)≥5. Это означает, что существует код минимум из пяти слов; не утверждается, что 5—наилучший размер. Радиус исправления для расстояния 3 равен 1, а здесь использован 2, потому что доказательство связано с невозможностью добавить новый центр, а не с непересечением областей исправления.
Частая ошибка
Округлять нижнюю границу вниз необязательно и теряет полезную единицу, если отношение нецелое. Нельзя подставлять радиус исправления вместо d−1 в покрывающем доказательстве. Максимальный по включению код не обязан иметь максимальное число слов. Граница существования произвольного кода сама по себе не доказывает существование линейного кода той же размерности.
Практика
Задачи с решением
Четыре бита
Условие. Найдите нижнюю границу для n=4,q=2,d=2.
Решение. V₂(4,1)=1+4=5. Потолок 16/5 равен 4.
Ответ. Существует код минимум из 4 слов.
Три бита
Условие. Для n=3,q=2,d=2 примените ту же границу.
Решение. V₂(3,1)=4, всего 8 слов, поэтому A₂(3,2)≥8/4=2.
Ответ. Не менее 2 слов гарантированно.
Дополнительные источники
- https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/ada-coding-book.pdf
- https://courses.csail.mit.edu/6.440/spring08/scribe/lec8.pdf
- https://arxiv.org/abs/math/0404325
Связанные формулы
Информатика
Граница Синглтона: размер исправляющего кода
Граница Синглтона ограничивает число кодовых слов через длину блока, размер алфавита и минимальное расстояние. После удаления d−1 позиций разные кодовые слова должны оставаться различными.
Информатика
Граница Плоткина для двоичного кода большого расстояния
Когда минимальное расстояние двоичного кода превышает половину длины, попарные расстояния ограничивают число кодовых слов. Простой вариант границы Плоткина получается двойным подсчётом отличающихся битов.
Информатика
Граница Грисмера: минимальная длина линейного кода
Граница Грисмера ограничивает длину линейного кода суммой округлённых расстояний. Она учитывает размерность и алфавит и часто сильнее простой оценки n≥k+d−1.
Информатика
Граница Хэмминга: сколько слов помещается в исправляющий код
Граница Хэмминга ограничивает число слов M двоичного блочного кода длины n, исправляющего любые t замен. Области возможных повреждений вокруг разных слов должны помещаться среди всех двоичных строк без пересечений.
Информатика
Расстояние Хэмминга между двоичными словами
Расстояние Хэмминга между двоичными словами: формула d(x,y)=\sum [x_i\ne y_i] помогает величины d, x_i, y_i заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.