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

Граница Грисмера: минимальная длина линейного кода

Граница Грисмера ограничивает длину линейного кода суммой округлённых расстояний. Она учитывает размерность и алфавит и часто сильнее простой оценки n≥k+d−1.

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

Формула

$$n\ge g_q(k,d)=\sum_{i=0}^{k-1}\left\lceil\frac{d}{q^i}\right\rceil$$
Схема Каждое округление сохраняется
3i=02i=11i=21i=3

Для q=2,k=4,d=3слагаемые равны3,2,1,1. Последние дроби положительны, поэтому их потолки не нули.

Обозначения

$q$
мощность конечного поля, —
$k$
размерность линейного кода, символов
$d$
минимальное расстояние кода, позиций
$n$
длина кодового слова, символов
$g_q(k,d)$
нижняя граница требуемой длины, символов

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

Код линейный над конечным полем из q элементов, k≥1 и d≥1 целые. q является степенью простого числа. Потолок применяется к каждому слагаемому d/q^i отдельно. Для нелинейного множества слов произвольно вводить целое k и применять ту же сумму нельзя.

Ограничения

Граница необходима, но не всегда достижима; выполнение n≥g_q не является конструкцией. Для проверки существования могут понадобиться дополнительные ограничения и таблицы кодов. Сумму нельзя заменить округлением всего геометрического ряда: несколько отдельных округлений могут дать существенно больше.

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

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

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

Каждый из k−1 членов после первого при d≥1 не меньше единицы. Поэтому g_q(k,d)≥d+k−1 и из границы Грисмера следует линейная граница Синглтона. Улучшение появляется, когда некоторые ранние потолки больше единицы. Чем меньше q при прочих равных, тем дольше сохраняются такие дополнительные вклады.

Когда q^i>d, положительное отношение меньше единицы, но его потолок по-прежнему равен 1. Поэтому хвост суммы не обнуляется. Это частая причина занижения оценки для больших k. Все величины безразмерны как количества символов; дробные промежуточные числа округляются вверх до целого числа координат.

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

  1. Убедитесь, что речь о линейном коде над конечным полем, и зафиксируйте целые q,k,d до вычисления границы длины.
  2. Для индексов i=0,…,k−1 рассчитайте d/q^i; возьмите потолок каждого отношения отдельно, сохранив единицы в хвосте.
  3. Сложите ровно kцелых слагаемых; сравните заданную длину n с суммой и отклоните параметры при nменьше результата.
  4. Если неравенство выполнено, отдельно найдите конструкцию или доказательство существования; также сравните с простой оценкой d+k−1.

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

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

В учебных заметках Судхира Горпаде Aspects of Coding Theory для курса 2017 года граница дана вместе с построением остаточного кода и выводом границы Синглтона как следствия. Современные исследования аддитивных кодов отдельно обсуждают, какие обобщения сохраняют подобные ограничения, а какие требуют новых условий. Для учебного расчёта поэтому существенны слова «линейный над полем»: они обозначают гипотезу теоремы, а не техническую деталь хранения сообщений.

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

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

Пример

Требуется двоичный линейный код размерности k=3 с минимальным расстоянием d=4. В нём 2³=8 слов. Нижняя граница длины g₂(3,4)=ceil4+ceil2+ceil1=4+2+1=7. Значит, длина 6 невозможна. Покажем достижимость длины 7 в этом примере. Возьмём порождающую матрицу 3×7, столбцы которой — все ненулевые двоичные тройки. Для любого ненулевого сообщения uлинейная форма u·vпринимает 1 ровно на четырёх из восьми троек; исключённая нулевая тройка даёт 0. Поэтому каждое ненулевое кодовое слово имеет вес 4, и минимальное расстояние равно 4. Получен код[7,3,4]₂. Проверка учитывает линейность: разность двух различных слов — ненулевое слово того же кода.

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

Не следует округлять вниз или округлять только итоговую вещественную сумму. Нельзя заменять потолок малой положительной дроби нулём. Число членов равно k, индексы начинаются с 0. Существование произвольного кода с Mсловами не разрешает применять линейную границу с k=log_qMбез доказательства линейности.

Практика

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

Размерность четыре

Условие. q=2,k=4,d=3. Найдите нижнюю границу n.

Решение. Потолки 3,2,1,1 дают 7. Простой предел Синглтона даёт только 3+4−1=6.

Ответ. n≥7.

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

Условие. q=2,k=3,d=5. Найдите минимально допустимую длину по границе.

Решение. ceil5+ceil2,5+ceil1,25=5+3+2=10. Это не доказывает достижимость длины 10.

Ответ. n≥10.

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

  • https://www.math.iitb.ac.in/~srg/Lecnotes/NotesOnCodes-IIITD.pdf
  • https://web.mat.upc.edu/simeon.michael.ball/additiveboundfixed.pdf

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

Информатика

Граница Синглтона: размер исправляющего кода

$M\le q^{n-d+1},\qquad k\le n-d+1\quad\text{для линейного }[n,k,d]_q\text{-кода}$

Граница Синглтона ограничивает число кодовых слов через длину блока, размер алфавита и минимальное расстояние. После удаления d−1 позиций разные кодовые слова должны оставаться различными.

Информатика

Граница Гилберта: существование разделённого кода

$A_q(n,d)\ge\left\lceil\frac{q^n}{V_q(n,d-1)}\right\rceil,\qquad V_q(n,r)=\sum_{j=0}^{r}\binom nj(q-1)^j$

Жадное добавление слов строит код с расстоянием не меньше d. Когда добавить слово больше нельзя, шары радиуса d−1 покрывают всё пространство и дают нижнюю границу достижимого размера.

Информатика

Граница Плоткина для двоичного кода большого расстояния

$d>\frac n2\quad\Longrightarrow\quad M\le\left\lfloor\frac{2d}{2d-n}\right\rfloor$

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

Информатика

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

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

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

Информатика

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

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

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