Информатика / Кодирование информации
Граница Синглтона: размер исправляющего кода
Граница Синглтона ограничивает число кодовых слов через длину блока, размер алфавита и минимальное расстояние. После удаления d−1 позиций разные кодовые слова должны оставаться различными.
Формула
Для двоичной длины n=7 верхняя оценка Синглтона равна2^(8−d). Это ограничения, а не размеры доказанно существующих кодов.
Обозначения
- $q$
- число символов алфавита, шт.
- $n$
- длина каждого кодового слова, символов
- $d$
- минимальное расстояние Хэмминга кода, позиций
- $M$
- число различных кодовых слов, шт.
- $k$
- размерность линейного кода над полем из q элементов, символов
Условия применения
Все слова имеют одну длину n, алфавит содержит q≥2 символов, а расстояние между любыми двумя разными словами не меньше d, 1≤d≤n. Для линейного случая M=q^k и q является мощностью конечного поля. Для произвольного кода надпись k не означает автоматически целую размерность.
Ограничения
Это необходимая верхняя граница, а не гарантия существования кода с равенством. При фиксированном малом алфавите другие границы могут быть сильнее. Расстояние d нельзя подменять числом исправляемых ошибок t: для исправления t произвольных ошибок требуется d≥2t+1.
Подробное объяснение
Удалим из всех кодовых слов одни и те же d−1 координат. Если два результата совпали, исходные слова могли различаться только в удалённых позициях, то есть не более чем в d−1 местах. Это противоречит минимальному расстоянию d. Значит, удаление координат остаётся инъективным отображением множества кодовых слов.
Оставшееся слово имеет n−d+1 координат, каждая из которых принимает q значений. Всего таких коротких записей q^(n−d+1), поэтому исходных слов не больше. Доказательство не требует линейности, вероятностной модели ошибок или алгоритма декодирования: это чисто комбинаторный подсчёт.
Для линейного кода число слов равно q^k. Логарифмирование даёт k≤n−d+1, или n−k≥d−1. Величина n−k — число проверочных символов, а не число ошибок. Чтобы исправлять t ошибок, необходимое условие Синглтона превращается в n−k≥2t, но оно всё ещё не обещает достаточность.
Равенство называют достижением границы Синглтона; для линейных кодов используется термин MDS. При этом требуемый размер алфавита и длина остаются существенными. Простая оценка полезна как первый фильтр параметров, а сравнение с границей Хэмминга показывает дополнительную цену раздельных областей исправления ошибок.
Как пользоваться формулой
- Укажите длину n, мощность алфавита q и требуемое расстояние d; если даны ошибки t, сначала перейдите к d≥2t+1.
- Вычислите число остающихся координат n−d+1 после удаления d−1 позиций и проверьте его неотрицательность.
- Возведите q в найденную степень, получив верхнюю границу M; для линейного кода сравните k с n−d+1.
- Если параметры проходят проверку, отдельно ищите конструкцию и более сильные границы: необходимое условие не является доказательством существования.
Историческая справка
Граница Синглтона входит в классическую теорию исправляющих кодов как оценка потери информационной ёмкости при требовании большого расстояния. Её доказательство строится на удалении координат и принципе Дирихле, поэтому оно отделено от конкретных физических моделей канала и способа реализации декодера.
В лекции MIT по Essential Coding Theory от 19 февраля 2013 года граница рассматривается вместе с примерами кодов, достигающих равенства, и с границами Хэмминга и Плоткина. В заметках Судхира Горпаде Aspects of Coding Theory она изложена и для произвольных кодов, и как следствие более сильной оценки линейных кодов. Современная запись M≤q^(n−d+1) сохраняет различие между общим количеством слов и целой размерностью линейного пространства.
Историческая линия формулы
Используется традиционное название «граница Синглтона». Проверяется именно современная комбинаторная формулировка; история первопубликации здесь не реконструируется. Равенство и термин MDS относятся к отдельному вопросу о конструкциях, а не следуют из одного верхнего ограничения.
Пример
Нужен двоичный блок длины n=7 с минимальным расстоянием d=3. Найдём ограничение числа сообщений и размерности линейного варианта, не утверждая существование кода предельного размера. После удаления двух общих позиций остаются пять битов. Они должны различать все кодовые слова, поэтому M≤2⁵=32. Для линейного кода k≤5, то есть проверочных битов n−k не меньше двух. Если требуется k=6, параметры невозможны уже по этой границе. Если k=5, граница лишь не запрещает параметры: для двоичного случая другие оценки могут усилить результат. Расстояние 3 обеспечивает возможность исправлять одну ошибку, но не три; число ошибок связано с расстоянием отдельным условием 2t+1≤d.
Частая ошибка
Нельзя считать M=q^n после введения расстояния d>1: это игнорирует ограничения между словами. Логарифм числа слов становится размерностью только для линейного кода. Не следует называть прохождение верхней границы конструкцией кода. Число удаляемых координат равно d−1, а не d; удаление d координат уже может склеить различные слова.
Практика
Задачи с решением
Пять битов
Условие. Для двоичного кода n=5,d=3 найдите верхнюю границу M.
Решение. M≤2^(5−3+1)=2³=8. Для линейного случая k≤3.
Ответ. Не более 8 слов.
Троичный алфавит
Условие. q=3,n=4,d=2. Ограничьте M.
Решение. После удаления одной координаты остаётся 3 символа. M≤3³=27.
Ответ. Не более 27 слов.
Дополнительные источники
- https://people.csail.mit.edu/madhu/ST13/scribe/lect04.pdf
- https://www.math.iitb.ac.in/~srg/Lecnotes/NotesOnCodes-IIITD.pdf
Связанные формулы
Информатика
Граница Гилберта: существование разделённого кода
Жадное добавление слов строит код с расстоянием не меньше d. Когда добавить слово больше нельзя, шары радиуса d−1 покрывают всё пространство и дают нижнюю границу достижимого размера.
Информатика
Граница Плоткина для двоичного кода большого расстояния
Когда минимальное расстояние двоичного кода превышает половину длины, попарные расстояния ограничивают число кодовых слов. Простой вариант границы Плоткина получается двойным подсчётом отличающихся битов.
Информатика
Граница Грисмера: минимальная длина линейного кода
Граница Грисмера ограничивает длину линейного кода суммой округлённых расстояний. Она учитывает размерность и алфавит и часто сильнее простой оценки n≥k+d−1.
Информатика
Граница Хэмминга: сколько слов помещается в исправляющий код
Граница Хэмминга ограничивает число слов M двоичного блочного кода длины n, исправляющего любые t замен. Области возможных повреждений вокруг разных слов должны помещаться среди всех двоичных строк без пересечений.
Информатика
Расстояние Хэмминга между двоичными словами
Расстояние Хэмминга между двоичными словами: формула d(x,y)=\sum [x_i\ne y_i] помогает величины d, x_i, y_i заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.