Информатика / Кодирование информации
Граница Грисмера: минимальная длина линейного кода
Граница Грисмера ограничивает длину линейного кода суммой округлённых расстояний. Она учитывает размерность и алфавит и часто сильнее простой оценки n≥k+d−1.
Формула
Для 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. Все величины безразмерны как количества символов; дробные промежуточные числа округляются вверх до целого числа координат.
Как пользоваться формулой
- Убедитесь, что речь о линейном коде над конечным полем, и зафиксируйте целые q,k,d до вычисления границы длины.
- Для индексов i=0,…,k−1 рассчитайте d/q^i; возьмите потолок каждого отношения отдельно, сохранив единицы в хвосте.
- Сложите ровно kцелых слагаемых; сравните заданную длину n с суммой и отклоните параметры при nменьше результата.
- Если неравенство выполнено, отдельно найдите конструкцию или доказательство существования; также сравните с простой оценкой 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
Связанные формулы
Информатика
Граница Синглтона: размер исправляющего кода
Граница Синглтона ограничивает число кодовых слов через длину блока, размер алфавита и минимальное расстояние. После удаления d−1 позиций разные кодовые слова должны оставаться различными.
Информатика
Граница Гилберта: существование разделённого кода
Жадное добавление слов строит код с расстоянием не меньше d. Когда добавить слово больше нельзя, шары радиуса d−1 покрывают всё пространство и дают нижнюю границу достижимого размера.
Информатика
Граница Плоткина для двоичного кода большого расстояния
Когда минимальное расстояние двоичного кода превышает половину длины, попарные расстояния ограничивают число кодовых слов. Простой вариант границы Плоткина получается двойным подсчётом отличающихся битов.
Информатика
Граница Хэмминга: сколько слов помещается в исправляющий код
Граница Хэмминга ограничивает число слов M двоичного блочного кода длины n, исправляющего любые t замен. Области возможных повреждений вокруг разных слов должны помещаться среди всех двоичных строк без пересечений.
Информатика
Расстояние Хэмминга между двоичными словами
Расстояние Хэмминга между двоичными словами: формула d(x,y)=\sum [x_i\ne y_i] помогает величины d, x_i, y_i заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.