Сколько слов помещается: границы Хэмминга и Гильберта-Варшамова

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

Как думаешь, число три означает существование трёх слов

Для длины 4 и расстояния 3 исправляется одна ошибка. Вокруг каждого слова расположены пять записей: центр и четыре одноразрядных соседа. Всего четырёхбитных записей 16, поэтому код содержит не больше ⌊16/5⌋=3 слов.

Значит ли это, что три слова существуют? Нет: размещение должно одновременно удовлетворять всем попарным расстояниям. Подсчёт мест только запретил четыре центра. Он мог не заметить ограничение формы. Сейчас получим доказательство, что три центра тоже невозможны, хотя проверку количества мест они проходят.

На что это похоже

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

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

Механизм: упаковка и покрытие используют разные радиусы

В шаре Хэмминга радиуса t находятся V(n,t)=Σᵢ₌₀ᵗ C(n,i) слов. На расстоянии ровно i нужно выбрать i изменяемых позиций; у каждой двоичной позиции единственный способ измениться. Поэтому здесь число сочетаний, а не перестановок. Центр учтён членом C(n, 0)=1.

Для кода с расстоянием d шары радиуса t=⌊(d−1)/2⌋ не пересекаются. Все они лежат среди 2^n записей. Значит M·V(n,t)≤2^n, и граница Хэмминга: A(n,d)≤⌊2^n/V(n,t)⌋. Если граница достигается и шары занимают всё пространство, код называют совершенным. Хэмминг(7, 4) даёт 16 шаров по 8 записей, ровно 128: каждое семибитное слово находится на расстоянии не больше 1 от одного центра.

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

Шары радиуса d−1 вокруг выбранных слов обязаны покрывать всё пространство. Иначе непокрытую запись можно добавить: она достаточно далека от всех центров. Шары теперь могут перекрываться, но их суммарного объёма должно хватать для покрытия. Получаем слабую границу Гильберта-Варшамова: A(n,d)≥⌈2^n/V(n,d−1)⌉. Радиус здесь d−1, а не радиус исправления t.

Правило

Упаковка даёт запрет сверху: A(n,d)≤⌊2^n/V(n,⌊(d−1)/2⌋)⌋. Жадное покрытие даёт существование снизу: A(n,d)≥⌈2^n/V(n,d−1)⌉. Между разными оценками остаётся промежуток: ни одна из них сама не доказывает точный оптимум.

Далее предполагаем 1≤d≤n. Коды могут быть нелинейными и иметь число слов, не равное степени двойки. Линейность - дополнительная структура: XOR любых двух кодовых слов снова принадлежит коду. Например, код Хэмминга линеен, поскольку все его проверки линейны относительно XOR. В следующем разборе эта структура усилит нижнюю границу.

Разбор: почему линейная конструкция требует строгий знак

Для линейного кода составим матрицу проверок из r строк и n столбцов над 0 и 1. Умножение проверок на слово означает XOR столбцов, у которых соответствующий бит слова равен 1. Код состоит из слов с нулевым результатом. Сложение строк здесь тоже XOR: 1 XOR 1=0, а не 2. Преобразования Гаусса сохраняют решения: переставляем строки и прибавляем одну строку к другой через XOR, пока не выделим ведущие переменные.

Например, проверки x₁ XOR x₃=0 и x₂ XOR x₃=0 над тремя битами оставляют x₃ свободным. При x₃=0 получаем 000, при x₃=1 - 111: два слова. Если добавить третью проверку x₁ XOR x₂=0, она ничего не ограничит: это XOR первых двух строк. Число независимых строк называют рангом; здесь он 2.

Каждая независимая строка выражает одну ведущую переменную через остальные. Из n битов свободными остаются n−rank битов, каждый выбирается двумя способами. Потому решений 2^(n−rank). Строк всего r, ранг не больше r, и число кодовых слов не меньше 2^(n−r). Зависимость строк может только увеличить этот размер.

Чтобы расстояние было хотя бы d, никакие от одного до d−1 столбцов не должны давать нулевой XOR. Добавляя новый столбец, исключим XOR всех наборов не больше d−2 прежних столбцов, включая пустой набор. Иначе новый столбец вместе с этим набором создаст зависимость. Различных запрещённых векторов не больше Σᵢ₌₀^(d−2) C(n−1,i). Всего векторов 2^r; при строгом превышении остаётся свободный.

Поэтому выбираем минимальное r с 2^r>Σᵢ₌₀^(d−2) C(n−1,i). Это даёт линейную границу Гильберта-Варшамова A(n,d)≥2^(n−r). Здесь рассматриваем d≥2. При равенстве все векторы могли оказаться запрещены: заменить > на ≥ нельзя. Например, для n=8,d=3 справа 8, поэтому нужны четыре строки, а не три.

from math import comb


def obem(n, t):
    return sum(comb(n, i) for i in range(t + 1))


def granicy(n, d):
    # Слабая GV: покрываем пространство шарами радиуса d-1.
    v = obem(n, d - 1)
    lower = (2 ** n + v - 1) // v
    upper = 2 ** n // obem(n, (d - 1) // 2)
    # Линейная GV требует СТРОГО больше запрещённых столбцов.
    forbidden = sum(comb(n - 1, i) for i in range(d - 1))
    r = 0
    while 2 ** r <= forbidden:
        r += 1
    linear = 2 ** (n - r)
    return lower, linear, upper


print("n d   GV   линейная GV   Хэмминг")
for n, d in [(4, 3), (6, 3), (7, 3), (8, 3)]:
    a, b, c = granicy(n, d)
    print(n, d, a, b, c)

codes = [x for x in range(16)]
triple = any(all((a ^ b).bit_count() >= 3
                 for a, b in [(x, y), (x, z), (y, z)])
             for x in codes for y in codes if y > x
             for z in codes if z > y)
print("три слова длины 4 с расстоянием 3 существуют:", triple)

n d   GV   линейная GV   Хэмминг
4 3 2 2 3
6 3 3 8 9
7 3 5 16 16
8 3 7 16 28
три слова длины 4 с расстоянием 3 существуют: False

Для n=7,d=3 линейная нижняя и верхняя границы равны 16. Конструкция предыдущего урока достигает этого числа. Для n=8,d=3 оценки 16 и 28 различны: таблица не определяет оптимум. Улучшить оценки и построить хорошие коды - отдельная задача, которую такие вычисления лишь ограничивают с двух сторон.

Разбор: точный запрет и изменение длины

Предположим, существуют три четырёхбитных слова с попарными расстояниями не меньше 3. Сложим расстояния всех трёх пар: получится не меньше 9. Но в каждой позиции либо все три бита одинаковы и вклад 0, либо один отличается от двух и вклад 2. Четыре позиции дают не больше 8. Противоречие. Два слова 0000 и 1111 существуют, значит A(4, 3)=2. Это сильнее верхней границы 3 из начала урока.

Ещё один приём - менять длину. Удаление одного столбца уменьшает расстояние максимум на 1 и при d≥2 не склеивает различные кодовые слова. Если d чётно, в обратную сторону можно добавить общую чётность к коду с нечётным расстоянием d−1: оно вырастет до d. Поэтому для чётного d верно A(n,d)=A(n−1,d−1). Например, A(8, 4)=A(7, 3)=16; расширенный Хэмминг здесь тоже оптимален по числу слов.

Если же зафиксировать одну позицию, не меньше половины слов имеют в ней одинаковый бит. Оставим эти слова и удалим общий столбец: расстояния не изменятся. Отсюда A(n,d)≤2·A(n−1,d) для невырожденных параметров. Такое укорочение отличается от простого удаления столбца: сначала выбирается часть словаря, чтобы сохранить расстояние.

Что ломается без этого

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

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

Зачем это в работе

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

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

Теперь сам

Для n=6,d=3 линейная конструкция дала 8 слов, а упаковка разрешила не больше 9. Доказано ли существование девяти? Затем объясни, почему для n=7,d=3 можно назвать точный максимум, а не только две границы.