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

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

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

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

Формула

$$M\le q^{n-d+1},\qquad k\le n-d+1\quad\text{для линейного }[n,k,d]_q\text{-кода}$$
Схема Расстояние уменьшает верхнюю границу
64d=232d=316d=48d=5

Для двоичной длины 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. При этом требуемый размер алфавита и длина остаются существенными. Простая оценка полезна как первый фильтр параметров, а сравнение с границей Хэмминга показывает дополнительную цену раздельных областей исправления ошибок.

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

  1. Укажите длину n, мощность алфавита q и требуемое расстояние d; если даны ошибки t, сначала перейдите к d≥2t+1.
  2. Вычислите число остающихся координат n−d+1 после удаления d−1 позиций и проверьте его неотрицательность.
  3. Возведите q в найденную степень, получив верхнюю границу M; для линейного кода сравните k с n−d+1.
  4. Если параметры проходят проверку, отдельно ищите конструкцию и более сильные границы: необходимое условие не является доказательством существования.

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

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

В лекции 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

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

Информатика

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

$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$

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

Информатика

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

$n\ge g_q(k,d)=\sum_{i=0}^{k-1}\left\lceil\frac{d}{q^i}\right\rceil$

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

Информатика

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

$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 заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.