Граница Синглтона

Граница Синглтона (названная в честь Р. К. Синглтона) устанавливает предел мощности кода ${\displaystyle C}$ с символами из поля ${\displaystyle \mathbb {F} _{q}}$ длины ${\displaystyle n}$ и минимального расстояния Хэмминга ${\displaystyle d}$.

Для ${\displaystyle A_{q}(n,\;d)}$ - максимально возможной мощности ${\displaystyle q}$-ичного кода длины ${\displaystyle n}$ (${\displaystyle q}$-ичный код — это код над полем из ${\displaystyle q}$ элементов) с минимальным расстоянием Хэмминга между двумя словами кода ${\displaystyle d}$ (то есть ${\displaystyle \mathrm {D} _{H}(w,\;w')\geqslant d}$ для любых двух кодовых слов ${\displaystyle w}$ и ${\displaystyle w'}$) выполняется следующее неравенство:

${\displaystyle A_{q}(n,\;d)\leqslant q^{n-d+1}.}$

В первую очередь заметим, что верхняя граница максимальной мощности любого ${\displaystyle q}$-ичного кода длины ${\displaystyle n}$ равняется ${\displaystyle q^{n}}$, так как каждый компонент данного кодового слова может принимать одно из ${\displaystyle q}$ разных значений независимо от других компонентов.

Пусть ${\displaystyle C}$ является ${\displaystyle q}$-ичным кодом. Тогда все слова ${\displaystyle c\in C}$ в кодe отличны друг от друга. Если мы сотрём первые ${\displaystyle d-1}$ символов каждого слова, тогда все оставшиеся кодовые слова должны оставаться разными, так как расстояние Хэмминга между словами кода ${\displaystyle C}$ по меньшей мере ${\displaystyle d}$. Следовательно мощность кода после удаления ${\displaystyle d-1}$ символов осталась прежней.

Длина нового слова

${\displaystyle n-(d-1)=n-d+1,}$

и следовательно максимально возможной мощностью такого кода является

${\displaystyle q^{n-d+1}.}$

Отсюда следует верхняя граница мощности и для изначального кода:

${\displaystyle A_{q}(n,\;d)\leqslant q^{n-d+1}.}$

Для линейных кодов с ${\displaystyle k}$ информационными символами неравенство для границы Синглтона можно записать как

${\displaystyle q^{k}\leqslant q^{n-d+1}}$

или

${\displaystyle k\leqslant n-d+1.}$

Линейные коды, для которых выполняется равенство ${\displaystyle k=n-d+1}$, называются разделимыми кодами с максимальным расстоянием или кодами МДР. Известными представителями этого семейства кодов являются код Рида — Соломона и коды, образуемые из него.

• R. C. Singleton. Maximum distance q-nary codes. IEEE Transactions on Information Theory, 10:116-118 [1, 11], 1964.
• Y. Komamiya. Application of logical mathematics to information theory. Proceedings of the 3rd Japanese National Congress for Applied Mathematics, 437 [1], 1953.

• Неравенство Гильберта — Варшамова
• Граница Плоткина
• Граница Хэмминга
• Граница Джонсона